1 import scala.language.implicitConversions

     1 import scala.language.implicitConversions    

     3 import scala.util._

     3 import scala.annotation.tailrec   

     4 import scala.annotation.tailrec

     4 

     5 

     5 abstract class Rexp 

     6 sealed abstract class Rexp

     7 

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

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

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

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

    13 case class STAR(r: Rexp) extends Rexp

    11 case class STAR(r: Rexp) extends Rexp 

    14 

    12 case class RECD(x: String, r: Rexp) extends Rexp

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

    13 

    14 abstract class Val

    15 case object Void extends Val

    16 case class Chr(c: Char) extends Val

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

    18 case class Left(v: Val) extends Val

    19 case class Right(v: Val) extends Val

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

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

    22    

    23 // some convenience for typing in regular expressions

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

    35 }

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

    36 

    44 }

    37 def Range(s : List[Char]) : Rexp = s match {

    45 

    38   case Nil => NULL

    46 // nullable function: tests whether the regular 

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

    47 // expression can recognise the empty string

    40   case c::s => ALT(CHAR(c), Range(s))

    41 }

    42 def RANGE(s: String) = Range(s.toList)

    43 

    44 def PLUS(r: Rexp) = SEQ(r, STAR(r))

    45 

    46 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")

    47 val DIGIT = RANGE("0123456789")

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

    49 val NUM = PLUS(DIGIT)

    50 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" 

    51 val SEMI: Rexp = ";"

    52 val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">"

    53 val WHITESPACE = PLUS(RANGE(" \n"))

    54 val RPAREN: Rexp = ")"

    55 val LPAREN: Rexp = "("

    56 val BEGIN: Rexp = "{"

    57 val END: Rexp = "}"

    58 

    59 //regular expressions ranked by position in the list

    60 val regs: List[Rexp] = 

    61   List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE)

    62 

    70 }

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

    71 

    56 }

    72 def zeroable (r: Rexp) : Boolean = r match {

    57 

    73   case NULL => true

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

    74   case EMPTY => false

    75   case CHAR(_) => false

    76   case ALT(r1, r2) => zeroable(r1) && zeroable(r2)

    77   case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)

    78   case STAR(_) => false

    79 }

    80 

    83   case EMPTY => NULL  

    61   case EMPTY => NULL

    90 }

    68   case RECD(_, r1) => der(c, r1)

    91 

    69 }

    92 

    70 

    93 // calculates derivatives until all of them are zeroable

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

    94 @tailrec

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

    95 def munch(s: List[Char], 

    73   case Nil => r

    96           pos: Int, 

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

    97           rs: List[Rexp], 

    75 }

    98           last: Option[Int]): Option[Int] = rs match {

    76 

    99   case Nil => last

    77 // extracts a string from value

   100   case rs if (s.length <= pos) => last

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

   101   case rs => {

    79   case Void => ""

   102     val ders = rs.map(der(s(pos), _))

    80   case Chr(c) => c.toString

   103     val rs_nzero = ders.filterNot(zeroable(_))

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

   104     val rs_nulls = ders.filter(nullable(_))

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

   105     val new_last = if (rs_nulls != Nil) Some(pos) else last

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

   106     munch(s, 1 + pos, rs_nzero, new_last)

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

   107   }

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

   108 }

    86 }

   109 

    87 

   110 // iterates the munching function and prints 

    88 // extracts an environment from a value

   111 // out the component strings

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

   112 @tailrec

    90   case Void => Nil

   113 def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, 0, rs, None) match {

    91   case Chr(c) => Nil

   114   case None if (s == "") => println("EOF")

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

   115   case None => println(s"Lexing error: $s")

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

   116   case Some(n) => {

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

   117     val (head, tail) = s.splitAt(n + 1)

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

   118     print(s"|${head.replaceAll("\n","RET")}|")

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

   119     tokenize(tail, rs)

    97 }

   120   }

    98 

   121 }

    99 // injection part

   122 

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

   123 

   101   case EMPTY => Void

   124 val test_prog = """

   102   case ALT(r1, r2) => 

   125 start := XXX;

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

   126 x := start;

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

   127 y := start;

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

   128 z := start;

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

   129 while 0 < x do {

   107 }

   130  while 0 < y do {

   108 

   131   while 0 < z do {

   109 

   132     z := z - 1

   110 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {

   133   };

   111   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)

   134   z := start;

   112   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)

   135   y := y - 1

   113   case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)

   136  };     

   114   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))

   137  y := start;

   115   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))

   138  x := x - 1

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

   117   case (CHAR(d), Void) => Chr(c) 

   118   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))

   119 }

   120 

   121 // main lexing function (produces a value)

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

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

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

   125 }

   126 

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

   128 

   129 // some "rectification" functions for simplification

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

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

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

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

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

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

   136 }

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

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

   139 }

   140 def F_SEQ_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v))

   141 def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void))

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

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

   144 }

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

   146 

   147 // simplification of regular expressions returning also an

   148 // rectification function; no simplification under STAR 

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

   150   case ALT(r1, r2) => {

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

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

   153     (r1s, r2s) match {

   154       case (NULL, _) => (r2s, F_RIGHT(f2s))

   155       case (_, NULL) => (r1s, F_LEFT(f1s))

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

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

   158     }

   159   }

   160   case SEQ(r1, r2) => {

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

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

   163     (r1s, r2s) match {

   164       case (NULL, _) => (NULL, F_ERROR)

   165       case (_, NULL) => (NULL, F_ERROR)

   166       case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s))

   167       case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s))

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

   169     }

   170   }

   171   case RECD(x, r1) => {

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

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

   174   }

   175   case r => (r, F_ID)

   176 }

   177 

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

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

   180   case c::cs => {

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

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

   183   }

   184 }

   185 

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

   187 

   188 lexing_simp(("a" + "ab") | ("b" + ""), "ab")

   189 

   190 // Lexing Rules for a Small While Language

   191 

   192 def PLUS(r: Rexp) = r ~ r.%

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

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

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

   196 val NUM = PLUS(DIGIT)

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

   198 val SEMI: Rexp = ";"

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

   200 val WHITESPACE = PLUS(" " | "\n" | "\t")

   201 val RPAREN: Rexp = ")"

   202 val LPAREN: Rexp = "("

   203 val BEGIN: Rexp = "{"

   204 val END: Rexp = "}"

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

   206 

   207 

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

   209                   ("i" $ ID) | 

   210                   ("o" $ OP) | 

   211                   ("n" $ NUM) | 

   212                   ("s" $ SEMI) | 

   213                   ("str" $ STRING) |

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

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

   216                   ("w" $ WHITESPACE)).%

   217 

   218 //   Testing

   219 //============

   220 

   221 def time[T](code: => T) = {

   222   val start = System.nanoTime()

   223   val result = code

   224   val end = System.nanoTime()

   225   println((end - start)/1.0e9)

   226   result

   227 }

   228 

   229 val r1 = ("a" | "ab") ~ ("bcd" | "c")

   230 println(lexing(r1, "abcd"))

   231 

   232 val r2 = ("" | "a") ~ ("ab" | "b")

   233 println(lexing(r2, "ab"))

   234 

   235 

   236 // Two Simple While Tests

   237 //========================

   238 println("prog0 test")

   239 

   240 val prog0 = """read n"""

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

   242 

   243 println("prog1 test")

   244 

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

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

   247 

   248 

   249 // Big Test

   250 //==========

   251 

   252 val prog2 = """

   253 write "fib";

   254 read n;

   255 minus1 := 0;

   256 minus2 := 1;

   257 while n > 0 do {

   258   temp := minus2;

   259   minus2 := minus1 + minus2;

   260   minus1 := temp;

   261   n := n - 1

   140 write x;

   263 write "result";

   141 write y;

   264 write minus2

   142 write z

   145 tokenize(test_prog, regs)

   267 println("Tokens")

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

   269 

   270 for (i <- 1 to 80) {

   271   print(i.toString + ":  ")

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

   273 }

   274 

   275