1 import scala.annotation.tailrec

     2 import scala.language.implicitConversions

     3 import scala.language.reflectiveCalls 

     4 

     5 

     6 abstract class Rexp 

     7 case object ZERO extends Rexp 

     8 case object ONE extends Rexp

     9 case class CHAR(c: Char) extends Rexp 

    10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp 

    11 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 

    12 case class STAR(r: Rexp) extends Rexp 

    13 

    14 // some convenience for typing in regular expressions

    15 def charlist2rexp(s : List[Char]): Rexp = s match {

    16   case Nil => ONE

    17   case c::Nil => CHAR(c)

    18   case c::s => SEQ(CHAR(c), charlist2rexp(s))

    19 }

    20 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)

    21 

    22 implicit def RexpOps(r: Rexp) = new {

    23   def | (s: Rexp) = ALT(r, s)

    24   def % = STAR(r)

    25   def ~ (s: Rexp) = SEQ(r, s)

    26 }

    27 

    28 implicit def stringOps(s: String) = new {

    29   def | (r: Rexp) = ALT(s, r)

    30   def | (r: String) = ALT(s, r)

    31   def % = STAR(s)

    32   def ~ (r: Rexp) = SEQ(s, r)

    33   def ~ (r: String) = SEQ(s, r)

    34 }

    35 

    36 // enumerates regular expressions until a certain depth

    37 // using the characters in the string

    38 def generate(n: Int, s: String) : Set[Rexp] = n match {

    39   case 0 => Set(ZERO, ONE) ++ s.toSet.map(CHAR)

    40   case n => {

    41     val rs = generate(n - 1, s)

    42     rs ++

    43     (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) ++

    44     (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) ++

    45     (for (r <- rs) yield STAR(r))

    46   }

    47 }

    48 

    49 

    50 

    51 abstract class Val

    52 case object Empty extends Val

    53 case class Chr(c: Char) extends Val

    54 case class Sequ(v1: Val, v2: Val) extends Val

    55 case class Left(v: Val) extends Val

    56 case class Right(v: Val) extends Val

    57 case class Stars(vs: List[Val]) extends Val

    58 

    59 

    60 

    61 // extracts a string from value

    62 def flatten(v: Val) : String = v match {

    63   case Empty => ""

    64   case Chr(c) => c.toString

    65   case Left(v) => flatten(v)

    66   case Right(v) => flatten(v)

    67   case Sequ(v1, v2) => flatten(v1) + flatten(v2)

    68   case Stars(vs) => vs.map(flatten).mkString

    69 }

    70 

    71 def flat_len(v: Val) : Int = flatten(v).length

    72 

    73 // extracts a set of candidate values from a "non-starred" regular expression

    74 def values(r: Rexp) : Set[Val] = r match {

    75   case ZERO => Set()

    76   case ONE => Set(Empty)

    77   case CHAR(c) => Set(Chr(c))

    78   case ALT(r1, r2) => values(r1).map(Left(_)) ++ values(r2).map(Right(_)) 

    79   case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2)

    80   case STAR(r) => values(r).map(v => Stars(List(v))) ++ Set(Stars(Nil))  

    81     // to do much more would cause the set to be infinite

    82 }

    83 

    84 

    85 def values_str(r: Rexp, s: String) : Set[Val] =

    86   values(r).filter(flatten(_) == s)   

    87 

    88 val List(val1, val2) = values_str(("ab" | "a") ~ ("c" | "bc"), "abc").toList

    89 

    90 // Position

    91 type Pos = List[Int]

    92 

    93 

    94 def positions(v: Val) : Set[Pos] = v match {

    95   case Empty => Set(Nil)

    96   case Chr(c) => Set(Nil)

    97   case Left(v) => Set(Nil) ++ positions(v).map(0::_) 

    98   case Right(v) => Set(Nil) ++ positions(v).map(1::_)

    99   case Sequ(v1, v2) => Set(Nil) ++ positions(v1).map(0::_) ++ positions(v2).map(1::_)

   100   case Stars(vs) => Set(Nil) ++ vs.zipWithIndex.flatMap{ case (v, n) => positions(v).map(n::_) }

   101 } 

   102 

   103 val v1 = Sequ(Chr('a'), Chr('b'))

   104 val ps1 = positions(v1)

   105 val ps1L = positions(Left(v1))

   106 val ps1R = positions(Right(v1))

   107 

   108 val v3 = Stars(List(Left(Chr('x')), Right(Left(Chr('y')))))

   109 val v4 = Stars(List(Right(Right(Sequ(Chr('x'), Chr('y'))))))

   110 

   111 val ps3 = positions(v3)

   112 val ps4 = positions(v4)

   113 

   114 def at(v: Val, ps: List[Int]) : Val = (v, ps) match {

   115   case (v, Nil) => v

   116   case (Left(v), 0::ps) => at(v, ps)

   117   case (Right(v), 1::ps) => at(v, ps)

   118   case (Sequ(v1, v2), 0::ps) => at(v1, ps)

   119   case (Sequ(v1, v2), 1::ps) => at(v2, ps)

   120   case (Stars(vs), n::ps) => at(vs(n), ps)

   121 } 

   122 

   123 ps1.map(at(v1, _))

   124 ps1L.map(at(Left(v1), _))

   125 ps1R.map(at(Right(v1), _))

   126 

   127 

   128 def pflat_len(v: Val, p: Pos) : Int =

   129   if (positions(v) contains p) flat_len(at(v, p)) else -1

   130   

   131 

   132 // for lexicographic list-orderings

   133 import scala.math.Ordering.Implicits._

   134 

   135 def smaller_than(pss: Set[Pos], ps: Pos) : Set[Pos] = 

   136   pss.filter(_ < ps)

   137 

   138 

   139 // order from the alternative posix paper

   140 def ordr(v1: Val, p: List[Int], v2: Val) : Boolean = { 

   141   pflat_len(v1, p) > pflat_len(v2, p) && 

   142   smaller_than(positions(v1) | positions(v2), p).forall(q => pflat_len(v1, q) == pflat_len(v2, q))

   143 }

   144 

   145 //tests

   146 val List(val1, val2) = values_str(("ab" | "a") ~ ("c" | "bc"), "abc").toList

   147 

   148 positions(val1).map(p => (p, ordr(val1, p, val2))).filter{ case (_, b) => b == true }

   149 positions(val1)

   150 at(val1, List(0))

   151 

   152 smaller_than(positions(val1), List(1, 0))

   153 

   154 val List(val1, val2) = values_str("a" ~ (("ab" | "a") ~ ("c" | "bc")), "aabc").toList

   155 positions(val2).map(p => (p, ordr(val2, p, val1))).filter{ case (_, b) => b == true }