1 // CW 2

     2 //======

     3 

     4 

     5 

     6 // Rexp

     7 abstract class Rexp

     8 case object ZERO extends Rexp

     9 case object ONE extends Rexp

    10 case class CHAR(c: Char) extends Rexp

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

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

    13 case class STAR(r: Rexp) extends Rexp 

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

    15 

    16 case class RANGE(s: Set[Char]) extends Rexp

    17 case class PLUS(r: Rexp) extends Rexp

    18 case class OPTIONAL(r: Rexp) extends Rexp

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

    20 

    21 // Values

    22 abstract class Val

    23 case object Empty extends Val

    24 case class Chr(c: Char) extends Val

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

    26 case class Left(v: Val) extends Val

    27 case class Right(v: Val) extends Val

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

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

    30 

    31 

    32 // Convenience for typing

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

    34   case Nil => ONE

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

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

    37 }

    38 

    39 implicit def string2rexp(s : String) : Rexp = 

    40   charlist2rexp(s.toList)

    41 

    42 extension (r: Rexp) {

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

    44   def % = STAR(r)

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

    46 }

    47 

    48 

    49 extension (s: String) {

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

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

    52   def % = STAR(s)

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

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

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

    56 }

    57 

    58 // nullable

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

    60   case ZERO => false

    61   case ONE => true

    62   case CHAR(_) => false

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

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

    65   case STAR(_) => true

    66 

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

    68   case RANGE(_) => false

    69   case PLUS(r1) => nullable(r1)

    70   case OPTIONAL(_) => true

    71   case NTIMES(r1, i) => if (i == 0) true else nullable(r1)

    72 }

    73 

    74 // der

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

    76   case ZERO => ZERO

    77   case ONE => ZERO

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

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

    80   case SEQ(r1, r2) => 

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

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

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

    84 

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

    86   case RANGE(s) => if (s.contains(c)) ONE else ZERO 

    87   case PLUS(r1) => SEQ(der(c, r1), STAR(r1))

    88   case OPTIONAL(r1) => der(c, r1)

    89   case NTIMES(r, i) => 

    90     if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))

    91 }

    92 

    93 // Flatten

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

    95   case Empty => ""

    96   case Chr(c) => c.toString

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

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

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

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

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

   102 }

   103 

   104 // Env

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

   106   case Empty => Nil

   107   case Chr(c) => Nil

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

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

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

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

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

   113 }

   114 

   115 // Mkeps

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

   117   case ONE => Empty

   118   case ALT(r1, r2) => 

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

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

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

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

   123 

   124   case PLUS(r) => Stars(List(mkeps(r)))   // the first copy must match the empty string

   125   case OPTIONAL(r) => if (nullable(r)) Stars(List(mkeps(r))) else Stars(Nil)

   126   case NTIMES(r, i) => Stars(List.fill(i)(mkeps(r)))

   127 }

   128 

   129 // Inj

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

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

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

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

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

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

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

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

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

   139 

   140   case (RANGE(_), Empty) => Chr(c)

   141   case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)

   142   case (OPTIONAL(r), v1) => Stars(List(inj(r, c, v1)))

   143   case (NTIMES(r, n), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)

   144 }

   145 

   146 // Rectification functions

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

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

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

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

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

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

   153 }

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

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

   156 }

   157 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 

   158   (v:Val) => Sequ(f1(Empty), f2(v))

   159 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 

   160   (v:Val) => Sequ(f1(v), f2(Empty))

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

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

   163 }

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

   165 

   166 // Simp

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

   168   case ALT(r1, r2) => {

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

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

   171     (r1s, r2s) match {

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

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

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

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

   176     }

   177   }

   178   case SEQ(r1, r2) => {

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

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

   181     (r1s, r2s) match {

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

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

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

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

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

   187     }

   188   }

   189   case r => (r, F_ID)

   190 }

   191 

   192 // Lex

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

   194   case Nil => if (nullable(r)) mkeps(r) else 

   195     { throw new Exception("lexing error") } 

   196   case c::cs => {

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

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

   199   }

   200 }

   201 

   202 def ders_simp(cs: List[Char], r: Rexp) : Rexp = cs match {

   203   case Nil => r

   204   case c::cs => ders_simp(cs, simp(der(c, r))._1)

   205 } 

   206 

   207 def lexing_simp(r: Rexp, s: String) = env(lex_simp(r, s.toList))

   208 

   209 // Language specific code

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

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

   212 val LET: Rexp = RANGE(('A' to 'Z').toSet ++ ('a' to 'z').toSet)

   213 val SYM : Rexp = RANGE(Set('.', '_', '>', '<', '=', ';', ',', ':'))

   214 val PARENS : Rexp = "(" | "{" | ")" | "}"

   215 val SEMI : Rexp = ";"

   216 val WHITESPACE : Rexp = PLUS(" ") | "\n" | "\t" | "\r"

   217 val DIGIT : Rexp = RANGE(('0' to '9').toSet)

   218 val DIGIT1 : Rexp = RANGE(('1' to '9').toSet)

   219 val STRING : Rexp = "\"" ~ (LET | DIGIT | SYM | PARENS | " " | "\\n").% ~ "\""

   220 val ID : Rexp = LET ~ (LET | "_" | DIGIT).%

   221 val NUM : Rexp = "0" | (DIGIT1 ~ DIGIT.%)

   222 val EOL : Rexp = "\n" | "\r\n"

   223 val COMMENT : Rexp = "//" ~ (LET | DIGIT | SYM | " ").% ~ EOL 

   224 

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

   226                   ("o" $ OP) | 

   227                   ("str" $ STRING) |

   228                   ("p" $ PARENS) |

   229                   ("s" $ SEMI) | 

   230                   ("w" $ WHITESPACE) | 

   231                   ("i" $ ID) | 

   232                   ("n" $ NUM) |

   233 		  ("c" $ COMMENT)).%

   234 

   235 def esc(raw: String): String = {

   236   import scala.reflect.runtime.universe._

   237   Literal(Constant(raw)).toString

   238 }

   239 

   240 def escape(tks: List[(String, String)]) =

   241   tks.map{ case (s1, s2) => (s1, esc(s2))}

   242 

   243 // Token

   244 abstract class Token extends Serializable 

   245 case class T_KEYWORD(s: String) extends Token

   246 case class T_OP(s: String) extends Token

   247 case class T_STRING(s: String) extends Token

   248 case class T_PAREN(s: String) extends Token

   249 case object T_SEMI extends Token

   250 case class T_ID(s: String) extends Token

   251 case class T_NUM(n: Int) extends Token

   252 

   253 val token : PartialFunction[(String, String), Token] = {

   254   case ("k", s) => T_KEYWORD(s)

   255   case ("o", s) => T_OP(s)

   256   case ("str", s) => T_STRING(s)

   257   case ("p", s) => T_PAREN(s)

   258   case ("s", _) => T_SEMI

   259   case ("i", s) => T_ID(s)

   260   case ("n", s) => T_NUM(s.toInt)

   261 }

   262 

   263 // Tokenise

   264 def tokenise(s: String) : List[Token] = 

   265   lexing_simp(WHILE_REGS, s).collect(token)

   266 

   267 

   268 // Q2 Tests

   269 

   270 lex_simp(NTIMES("a", 3), "aaa".toList)

   271 lex_simp(NTIMES(("a" | ONE), 3), "aa".toList)

   272 

   273 // Q3 Programs

   274 

   275 val prog1 = """write "Fib";

   276 read n;

   277 minus1 := 0;

   278 minus2 := 1;

   279 while n > 0 do {

   280 temp := minus2;

   281 minus2 := minus1 + minus2;

   282 minus1 := temp;

   283 n := n - 1

   284 };

   285 write "Result";

   286 write minus2"""

   287 

   288 val prog2 = """start := 1000;

   289 x := start;

   290 y := start;

   291 z := start;

   292 while 0 < x do {

   293 while 0 < y do {

   294 while 0 < z do { z := z - 1 };

   295 z := start;

   296 y := y - 1

   297 };

   298 y := start;

   299 x := x - 1

   300 }"""

   301 

   302 val prog3 = """write "Input n please";

   303 read n;

   304 write "The factors of n are";

   305 f := 2;

   306 while n != 1 do {

   307 while (n / f) * f == n do {

   308 write f;

   309 n := n / f

   310 };

   311 f := f + 1

   312 }"""

   313 

   314 println(tokenise(prog1))

   315 println(tokenise(prog2))

   316 println(tokenise(prog3))

   317 

   318 

   319 // More tests

   320 

   321 println(lex_simp("x" $ OPTIONAL("a"), "a".toList))

   322 println(lex_simp("x" $ OPTIONAL("a"), "".toList))

   323 println(lex_simp("x" $ NTIMES(OPTIONAL("a"),4), "aa".toList))

   324 println(lex_simp("x" $ OPTIONAL("aa"), "aa".toList))

   325 println(lex_simp("x" $ OPTIONAL("aa"), "".toList))

   326 

   327 

   328 

   329 

   330 //===================

   331 println("Fib")

   332 println(tokenise(os.read(os.pwd / "fib.while")))

   333 

   334 println("Factors")

   335 println(tokenise(os.read(os.pwd / "factors.while")))

   336 

   337 println("Loops")

   338 println(tokenise(os.read(os.pwd / "loops.while")))

   339 

   340 println("Collatz")

   341 println(tokenise(os.read(os.pwd / "collatz.while")))

   342 

   343 println("Collatz 2")

   344 println(tokenise(os.read(os.pwd / "collatz2.while")))

   345 

   346 println("Primes")

   347 println(tokenise(os.read(os.pwd / "primes.while")))

   348 

   349 

   350 // some testcases for simplification

   351 

   352 def size(r: Rexp): Int = r match {

   353   case ZERO => 1

   354   case ONE => 1

   355   case CHAR(_) => 1

   356   case ALT(r1, r2) => 1 + size(r1) + size (r2)

   357   case SEQ(r1, r2) => 1 + size(r1) + size (r2)

   358   case STAR(r1) => 1 + size(r1)

   359   case PLUS(r1) => 1 + size(r1)

   360   case NTIMES(r1, n) => 1 + size(r1)

   361   case RECD(_, r1) => 1 + size(r1)

   362   case RANGE(_) => 1

   363 }

   364 

   365 val reg = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

   366 size(reg) // 5

   367 size(der('a', reg)) // 12

   368 size(simp(der('a', reg))._1) // 8

   369 size(simp(der('a', der('a', reg)))._1) // 8

   370 

   371 

   372 

   373 // python tests

   374 println(size(WHILE_REGS))

   375 println(size(ders_simp("r".toList, WHILE_REGS)))

   376 println(size(ID))

   377 println(size(ders_simp("read".toList, ID)))

   378 

   379 

   380 

   381 // for automated testing

   382 

   383 @main

   384 def main(file: String) = {

   385   // empty - nothing to run

   386 }

   387 

   388 @main

   389 def test(file: String) = {

   390   val contents = os.read(os.pwd / file)

   391   tokenise(contents)

   392 }

   393 

   394