1 import scala.language.implicitConversions    

     2 import scala.language.reflectiveCalls

     3 import scala.annotation.tailrec   

     4 import scala.io.Source

     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 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

    16 case class OPT(r: Rexp) extends Rexp

    17 case class NTIMES(r: Rexp, n: Int) extends Rexp

    18 

    19 abstract class Val

    20 case object Empty extends Val

    21 case class Chr(c: Char) extends Val

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

    23 case class Left(v: Val) extends Val

    24 case class Right(v: Val) extends Val

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

    26 case class Rec(x: String, v: Val) extends Val

    27    

    28 // some convenience for typing in regular expressions

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

    30   case Nil => ONE

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

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

    33 }

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

    35 

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

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

    38   def % = STAR(r)

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

    40 }

    41 

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

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

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

    45   def % = STAR(s)

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

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

    48   def $ (r: Rexp) = RECD(s, r)

    49 }

    50 

    51 def Alts(rs: List[Rexp]) : Rexp = rs match {

    52   case Nil => ZERO

    53   case r::Nil => r

    54   case r::rs => ALT(r, Alts(rs))

    55 }

    56 def ALTS(rs: Rexp*) = Alts(rs.toList)

    57 

    58 def Seqs(rs: List[Rexp]) : Rexp = rs match {

    59   case Nil => ONE

    60   case r::Nil => r

    61   case r::rs => SEQ(r, Seqs(rs))

    62 }

    63 def SEQS(rs: Rexp*) = Seqs(rs.toList)

    64 

    65 

    66 // nullable function: tests whether the regular 

    67 // expression can recognise the empty string

    68 def nullable (r: Rexp) : Boolean = r match {

    69   case ZERO => false

    70   case ONE => true

    71   case CHAR(_) => false

    72   case ALT(r1, r2) => nullable(r1) || nullable(r2)

    73   case SEQ(r1, r2) => nullable(r1) && nullable(r2)

    74   case STAR(_) => true

    75   case RECD(_, r1) => nullable(r1)

    76   case CRANGE(_) => false

    77   case PLUS(r) => nullable(r)

    78   case OPT(_) => true

    79   case NTIMES(r, n) => if (n == 0) true else nullable(r)

    80 }

    81 

    82 // derivative of a regular expression w.r.t. a character

    83 def der (c: Char, r: Rexp) : Rexp = r match {

    84   case ZERO => ZERO

    85   case ONE => ZERO

    86   case CHAR(d) => if (c == d) ONE else ZERO

    87   case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))

    88   case SEQ(r1, r2) => 

    89     if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))

    90     else SEQ(der(c, r1), r2)

    91   case STAR(r) => SEQ(der(c, r), STAR(r))

    92   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))

    95   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)))

    97 }

    98 

    99 // derivative w.r.t. a string (iterates der)

   100 @tailrec

   101 def ders (s: List[Char], r: Rexp) : Rexp = s match {

   102   case Nil => r

   103   case c::s => ders(s, der(c, r))

   104 }

   105 

   106 // extracts a string from value

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

   108   case Empty => ""

   109   case Chr(c) => c.toString

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

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

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

   113   case Stars(vs) => vs.map(flatten(_)).mkString

   114   case Rec(_, v) => flatten(v)

   115 }

   116 

   117 

   118 // extracts an environment from a value

   119 def env(v: Val) : List[(String, String)] = v match {

   120   case Empty => Nil

   121   case Chr(c) => Nil

   122   case Left(v) => env(v)

   123   case Right(v) => env(v)

   124   case Sequ(v1, v2) => env(v1) ::: env(v2)

   125   case Stars(vs) => vs.flatMap(env)

   126   case Rec(x, v) => (x, flatten(v))::env(v)

   127 }

   128 

   129 // injection part

   130 def mkeps(r: Rexp) : Val = r match {

   131   case ONE => Empty

   132   case ALT(r1, r2) => 

   133     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))

   134   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))

   135   case STAR(r) => Stars(Nil)

   136   case RECD(x, r) => Rec(x, mkeps(r))

   137   case PLUS(r) => Stars(List(mkeps(r)))

   138   case OPT(_) => Right(Empty)

   139   case NTIMES(r, n) => if (n == 0) Stars(Nil) else Stars(Nil.padTo(n, mkeps(r)))

   140 }

   141 

   142 

   143 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)

   145   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)

   147   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))

   149   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))

   150   case (CHAR(d), Empty) => Chr(c) 

   151   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)

   154   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)

   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 }

   159 

   160 // main unsimplified lexing function (produces a value)

   161 def lex(r: Rexp, s: List[Char]) : Val = s match {

   162   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")

   163   case c::cs => inj(r, c, lex(der(c, r), cs))

   164 }

   165 

   166 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)

   167 

   168 

   169 // some "rectification" functions for simplification

   170 def F_ID(v: Val): Val = v

   171 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))

   172 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))

   173 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {

   174   case Right(v) => Right(f2(v))

   175   case Left(v) => Left(f1(v))

   176 }

   177 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {

   178   case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))

   179 }

   180 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Empty), f2(v))

   181 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Empty))

   182 def F_RECD(f: Val => Val) = (v:Val) => v match {

   183   case Rec(x, v) => Rec(x, f(v))

   184 }

   185 def F_ERROR(v: Val): Val = throw new Exception("error")

   186 

   187 // simplification of regular expressions returning also an

   188 // rectification function; no simplification under STAR 

   189 def simp(r: Rexp): (Rexp, Val => Val) = r match {

   190   case ALT(r1, r2) => {

   191     val (r1s, f1s) = simp(r1)

   192     val (r2s, f2s) = simp(r2)

   193     (r1s, r2s) match {

   194       case (ZERO, _) => (r2s, F_RIGHT(f2s))

   195       case (_, ZERO) => (r1s, F_LEFT(f1s))

   196       case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))

   197                 else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 

   198     }

   199   }

   200   case SEQ(r1, r2) => {

   201     val (r1s, f1s) = simp(r1)

   202     val (r2s, f2s) = simp(r2)

   203     (r1s, r2s) match {

   204       case (ZERO, _) => (ZERO, F_ERROR)

   205       case (_, ZERO) => (ZERO, F_ERROR)

   206       case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))

   207       case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))

   208       case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))

   209     }

   210   }

   211   case RECD(x, r1) => {

   212     val (r1s, f1s) = simp(r1)

   213     (RECD(x, r1s), F_RECD(f1s))

   214   }

   215   case r => (r, F_ID)

   216 }

   217 

   218 def lex_simp(r: Rexp, s: List[Char]) : Val = s match {

   219   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")

   220   case c::cs => {

   221     val (r_simp, f_simp) = simp(der(c, r))

   222     inj(r, c, f_simp(lex_simp(r_simp, cs)))

   223   }

   224 }

   225 

   226 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList)

   227 

   228 

   229 // Some Tests

   230 //============

   231 

   232 def time_needed[T](i: Int, code: => T) = {

   233   val start = System.nanoTime()

   234   for (j <- 1 to i) code

   235   val end = System.nanoTime()

   236   (end - start)/(i * 1.0e9)

   237 }

   238 

   239 

   240 val r0 = ("a" | "ab") ~ ("b" | "")

   241 println(lexing(r0, "ab"))

   242 println(lexing_simp(r0, "ab"))

   243 

   244 val r1 = ("a" | "ab") ~ ("bcd" | "cd")

   245 println(lexing_simp(r1, "abcd"))

   246 

   247 println(lexing_simp((("" | "a") ~ ("ab" | "b")), "ab"))

   248 println(lexing_simp((("" | "a") ~ ("b" | "ab")), "ab"))

   249 println(lexing_simp((("" | "a") ~ ("c" | "ab")), "ab"))

   250 

   251 

   252 

   253 // Two Simple Tests for the While Language

   254 //========================================

   255 

   256 // Lexing Rules 

   257 

   258 def PLUSs(r: Rexp) = r ~ r.%

   259 val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"

   260 val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

   261 val ID = SYM ~ (SYM | DIGIT).% 

   262 val NUM = PLUSs(DIGIT)

   263 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false"

   264 val SEMI: Rexp = ";"

   265 val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/"

   266 val WHITESPACE = PLUSs(" " | "\n" | "\t")

   267 val RPAREN: Rexp = ")"

   268 val LPAREN: Rexp = "("

   269 val BEGIN: Rexp = "{"

   270 val END: Rexp = "}"

   271 val STRING: Rexp = "\"" ~ SYM.% ~ "\""

   272 

   273 

   274 val WHILE_REGS = (("k" $ KEYWORD) | 

   275                   ("i" $ ID) | 

   276                   ("o" $ OP) | 

   277                   ("n" $ NUM) | 

   278                   ("s" $ SEMI) | 

   279                   ("str" $ STRING) |

   280                   ("p" $ (LPAREN | RPAREN)) | 

   281                   ("b" $ (BEGIN | END)) | 

   282                   ("w" $ WHITESPACE)).%

   283 

   284 /*

   285 val WHILE_REGS = (KEYWORD | 

   286                   ID | 

   287                   OP | 

   288                   NUM | 

   289                   SEMI | 

   290                   LPAREN | RPAREN | 

   291                   BEGIN | END | 

   292                   WHITESPACE).%

   293 */

   294 

   295 

   296 println("prog0 test")

   297 

   298 val prog0 = """read n"""

   299 println(env(lexing_simp(WHILE_REGS, prog0)))

   300 

   301 println("prog1 test")

   302 

   303 val prog1 = """read  n; write (n)"""

   304 println(env(lexing_simp(WHILE_REGS, prog1)))

   305 

   306 

   307 // Bigger Test

   308 //=============

   309 val prog2 = """

   310 i := 2;

   311 max := 100;

   312 while i < max do {

   313   isprime := 1;

   314   j := 2;

   315   while (j * j) <= i + 1  do {

   316     if i % j == 0 then isprime := 0  else skip;

   317     j := j + 1

   318   };

   319   if isprime == 1 then write i else skip;

   320   i := i + 1

   321 }"""

   322 

   323 println("prog2 test - tokens")

   324 println(env(lexing_simp(WHILE_REGS, prog2)))

   325 

   326 

   327 val prog3 = """

   328 write "fib";

   329 read n;

   330 minus1 := 0;

   331 minus2 := 1;

   332 while n > 0 do {

   333   temp := minus2;

   334   minus2 := minus1 + minus2;

   335   minus1 := temp;

   336   n := n - 1

   337 };

   338 write "result";

   339 write minus2

   340 """

   341 

   342 println("prog3 test - tokens")

   343 println(env(lexing_simp(WHILE_REGS, prog3)))

   344 

   345 /*

   346 for (i <- 1 to 80) {

   347   print(i.toString + ":  ")

   348   time(lexing_simp(WHILE_REGS, prog2 * i))

   349 }

   350 */

   351 

   352 // Sulzmann's tests

   353 //==================

   354 

   355 val sulzmann = ("a" | "b" | "ab").%

   356 

   357 println(lexing_simp(sulzmann, "a" * 10))

   358 

   359 for (i <- 1 to 4501 by 500) {

   360   println(i + ": " + "%.5f".format(time_needed(1, lexing_simp(sulzmann, "a" * i))))

   361 }

   362 

   363 for (i <- 1 to 2001 by 500) {

   364   println(i + ": " + "%.5f".format(time_needed(1, lexing_simp(sulzmann, "ab" * i))))

   365 }

   366 

   367 

   368 // first benchmark regex 

   369 //=======================

   370 

   371 val reWord = CRANGE("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")

   372 

   373 val reWordStar = STAR(reWord)

   374 val reWordPlus = reWord ~ reWordStar

   375 val optionSet1 = "-" | "+" | "."

   376 val optionSet2 = "-" | "."

   377 val atTheRate = "@"

   378 val period = "."

   379 val optionSet3 = "," | ";"

   380 val whitespace = " "

   381 

   382 val re01 = reWordPlus

   383 val re02 = STAR(optionSet1 ~ reWordPlus)

   384 val re03 = atTheRate

   385 val re04 = reWordPlus

   386 val re05 = STAR(optionSet2 ~ reWordPlus)

   387 val re06 = period

   388 val re07 = reWordPlus

   389 val re08 = re05

   390 

   391 val re09 = optionSet3

   392 val re10 = STAR(whitespace)

   393 val re11 = reWordPlus

   394 val re12 = re02

   395 val re13 = atTheRate

   396 val re14 = reWordPlus

   397 val re15 = re05

   398 val re16 = period

   399 val re17 = reWordPlus

   400 val re18 = re05

   401 

   402 

   403 val re01_08 = SEQS(re01, re02, re03, re04, re05, re06, re07, re08)

   404 val re09_10 = re09 ~ re10

   405 val re11_18 = re01_08

   406 

   407 val re = re01_08 ~ STAR(re09_10 ~ re11_18)

   408 

   409 

   410 def process(s: String, i: Int) : Unit = {

   411   println(i + " " + "%.5f".format(time_needed(1, lexing(re, s))))

   412 }

   413 

   414 val filename = "../tests/emails.txt"

   415 val filelines = Source.fromFile(filename).getLines.take(76).zipWithIndex

   416 

   417 

   418 filelines.foreach({ case (s: String, i: Int) => process(s, i) })

   419 

   420