Mercurial Mercurial > hg > lexing / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
progs/scala/re-ext.scala
changeset 229 81c85f2746f5
parent 167 1b2b9000be88
child 231 02fd56e2019e
equal deleted inserted replaced
228:8b432cef3805 229:81c85f2746f5 
     4 import scala.io.Source
 
     4 import scala.io.Source
 
     5 
     5 
     6 abstract class Rexp 
     6 abstract class Rexp 
     7 case object ZERO extends Rexp
 
     7 case object ZERO extends Rexp
 
     8 case object ONE extends Rexp
 
     8 case object ONE extends Rexp
 
     9 case class CHAR(c: Char) extends Rexp
 
     9 case class CHARS(f: Char => Boolean) extends Rexp
 
    10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
    10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
    11 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
    11 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
    12 case class STAR(r: Rexp) extends Rexp 
    12 case class STAR(r: Rexp) extends Rexp 
    13 case class RECD(x: String, r: Rexp) extends Rexp
 
    13 case class RECD(x: String, r: Rexp) extends Rexp
 
    14 case class CRANGE(cs: String) extends Rexp
 
       
    15 case class PLUS(r: Rexp) extends Rexp
 
    14 case class PLUS(r: Rexp) extends Rexp
 
    16 case class OPT(r: Rexp) extends Rexp
 
    15 case class OPT(r: Rexp) extends Rexp
 
    17 case class NTIMES(r: Rexp, n: Int) extends Rexp
 
    16 case class NTIMES(r: Rexp, n: Int) extends Rexp
 
    18 
    17 
    19 abstract class Val
 
    18 abstract class Val
 
    26 case class Rec(x: String, v: Val) extends Val
 
    25 case class Rec(x: String, v: Val) extends Val
 
    27    
    26    
    28 // some convenience for typing in regular expressions
 
    27 // some convenience for typing in regular expressions
 
    29 def charlist2rexp(s : List[Char]): Rexp = s match {
 
    28 def charlist2rexp(s : List[Char]): Rexp = s match {
 
    30   case Nil => ONE
 
    29   case Nil => ONE
 
    31   case c::Nil => CHAR(c)
 
    30   case c::Nil => CHARS(_ == c)
 
    32   case c::s => SEQ(CHAR(c), charlist2rexp(s))
 
    31   case c::s => SEQ(CHARS(_ == c), charlist2rexp(s))
 
    33 }
 
    32 }
 
    34 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
 
    33 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
 
    35 
    34 
    36 implicit def RexpOps(r: Rexp) = new {
 
    35 implicit def RexpOps(r: Rexp) = new {
 
    37   def | (s: Rexp) = ALT(r, s)
 
    36   def | (s: Rexp) = ALT(r, s)
 
    66 // nullable function: tests whether the regular 
    65 // nullable function: tests whether the regular 
    67 // expression can recognise the empty string
 
    66 // expression can recognise the empty string
 
    68 def nullable (r: Rexp) : Boolean = r match {
 
    67 def nullable (r: Rexp) : Boolean = r match {
 
    69   case ZERO => false
 
    68   case ZERO => false
 
    70   case ONE => true
 
    69   case ONE => true
 
    71   case CHAR(_) => false
 
    70   case CHARS(_) => false
 
    72   case ALT(r1, r2) => nullable(r1) || nullable(r2)
 
    71   case ALT(r1, r2) => nullable(r1) || nullable(r2)
 
    73   case SEQ(r1, r2) => nullable(r1) && nullable(r2)
 
    72   case SEQ(r1, r2) => nullable(r1) && nullable(r2)
 
    74   case STAR(_) => true
 
    73   case STAR(_) => true
 
    75   case RECD(_, r1) => nullable(r1)
 
    74   case RECD(_, r1) => nullable(r1)
 
    76   case CRANGE(_) => false
 
       
    77   case PLUS(r) => nullable(r)
 
    75   case PLUS(r) => nullable(r)
 
    78   case OPT(_) => true
 
    76   case OPT(_) => true
 
    79   case NTIMES(r, n) => if (n == 0) true else nullable(r)
 
    77   case NTIMES(r, n) => if (n == 0) true else nullable(r)
 
    80 }
 
    78 }
 
    81 
    79 
    82 // derivative of a regular expression w.r.t. a character
 
    80 // derivative of a regular expression w.r.t. a character
 
    83 def der (c: Char, r: Rexp) : Rexp = r match {
 
    81 def der (c: Char, r: Rexp) : Rexp = r match {
 
    84   case ZERO => ZERO
 
    82   case ZERO => ZERO
 
    85   case ONE => ZERO
 
    83   case ONE => ZERO
 
    86   case CHAR(d) => if (c == d) ONE else ZERO
 
    84   case CHARS(f) => if (f(c)) ONE else ZERO
 
    87   case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
 
    85   case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
 
    88   case SEQ(r1, r2) => 
    86   case SEQ(r1, r2) => 
    89     if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
 
    87     if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
 
    90     else SEQ(der(c, r1), r2)
 
    88     else SEQ(der(c, r1), r2)
 
    91   case STAR(r) => SEQ(der(c, r), STAR(r))
 
    89   case STAR(r) => SEQ(der(c, r), STAR(r))
 
    92   case RECD(_, r1) => der(c, r1)
 
    90   case RECD(_, r1) => der(c, r1)
 
    93   case CRANGE(cs) => if (cs.contains(c)) ONE else ZERO
 
       
    94   case PLUS(r) => SEQ(der(c, r), STAR(r))
 
    91   case PLUS(r) => SEQ(der(c, r), STAR(r))
 
    95   case OPT(r) => ALT(der(c, r), ZERO)
 
    92   case OPT(r) => ALT(der(c, r), ZERO)
 
    96   case NTIMES(r, n) => if (n == 0) ZERO else der(c, SEQ(r, NTIMES(r, n - 1)))
 
    93   case NTIMES(r, n) => if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))
 
    97 }
 
    94 }
 
    98 
    95 
    99 // derivative w.r.t. a string (iterates der)
 
    96 // derivative w.r.t. a string (iterates der)
 
   100 @tailrec
 
    97 @tailrec
 
   101 def ders (s: List[Char], r: Rexp) : Rexp = s match {
 
    98 def ders (s: List[Char], r: Rexp) : Rexp = s match {
 
   134   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
 
   131   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
 
   135   case STAR(r) => Stars(Nil)
 
   132   case STAR(r) => Stars(Nil)
 
   136   case RECD(x, r) => Rec(x, mkeps(r))
 
   133   case RECD(x, r) => Rec(x, mkeps(r))
 
   137   case PLUS(r) => Stars(List(mkeps(r)))
 
   134   case PLUS(r) => Stars(List(mkeps(r)))
 
   138   case OPT(_) => Right(Empty)
 
   135   case OPT(_) => Right(Empty)
 
   139   case NTIMES(r, n) => if (n == 0) Stars(Nil) else Stars(Nil.padTo(n, mkeps(r)))
 
   136   case NTIMES(r, n) => Stars(List.fill(n)(mkeps(r)))
 
   140 }
 
   137 }
 
   141 
   138 
   142 
   139 
   143 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
 
   140 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
 
   144   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   141   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   145   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
 
   142   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
 
   146   case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
 
   143   case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
 
   147   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
 
   144   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
 
   148   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
 
   145   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
 
   149   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
 
   146   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
 
   150   case (CHAR(d), Empty) => Chr(c) 
   147   case (CHARS(_), Empty) => Chr(c) 
   151   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
 
   148   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
 
   152   case (CRANGE(_), Empty) => Chr(c) 
       
   153   case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   149   case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   154   case (OPT(r), Left(v1)) => Left(inj(r, c, v1))
 
   150   case (OPT(r), Left(v1)) => Left(inj(r, c, v1))
 
   155   case (NTIMES(r, n), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   151   case (NTIMES(r, n), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   156   case (NTIMES(r, n), Left(Sequ(v1, Stars(vs)))) => Stars(inj(r, c, v1)::vs)
 
       
   157   case (NTIMES(r, n), Right(Stars(v::vs))) => Stars(mkeps(r)::inj(r, c, v)::vs)
 
       
   158 }
 
   152 }
 
   159 
   153 
   160 // main unsimplified lexing function (produces a value)
 
   154 // main unsimplified lexing function (produces a value)
 
   161 def lex(r: Rexp, s: List[Char]) : Val = s match {
 
   155 def lex(r: Rexp, s: List[Char]) : Val = s match {
 
   162   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
 
   156   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
 
   366 
   360 
   367 
   361 
   368 // first benchmark regex 
   362 // first benchmark regex 
   369 //=======================
 
   363 //=======================
 
   370 
   364 
   371 val reWord = CRANGE("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")
 
   365 val reWord = CHARS("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" contains _)
 
   372 
   366 
   373 val reWordStar = STAR(reWord)
 
   367 val reWordStar = STAR(reWord)
 
   374 val reWordPlus = reWord ~ reWordStar
 
   368 val reWordPlus = reWord ~ reWordStar
 
   375 val optionSet1 = "-" | "+" | "."
 
   369 val optionSet1 = "-" | "+" | "."
 
   376 val optionSet2 = "-" | "."
 
   370 val optionSet2 = "-" | "."
lexing