1 

     2 // regular expressions including NOT

     3 abstract class Rexp

     4 

     5 case object NULL extends Rexp

     6 case object EMPTY extends Rexp

     7 case object ALLC extends Rexp            // recognises any character

     8 case class CHAR(c: Char) extends Rexp

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

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

    11 case class STAR(r: Rexp) extends Rexp

    12 case class NOT(r: Rexp) extends Rexp     // negation of a regular expression

    13 

    14 

    15 // nullable function: tests whether the regular 

    16 // expression can recognise the empty string

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

    18   case NULL => false

    19   case EMPTY => true

    20   case ALLC => false

    21   case CHAR(_) => false

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

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

    24   case STAR(_) => true

    25   case NOT(r) => !(nullable(r))

    26 }

    27 

    28 // tests whether a regular expression 

    29 // cannot recognise more

    30 def no_more (r: Rexp) : Boolean = r match {

    31   case NULL => true

    32   case EMPTY => false

    33   case ALLC => false

    34   case CHAR(_) => false

    35   case ALT(r1, r2) => no_more(r1) && no_more(r2)

    36   case SEQ(r1, r2) => if (nullable(r1)) (no_more(r1) && no_more(r2)) else no_more(r1)

    37   case STAR(_) => false

    38   case NOT(r) => !(no_more(r))

    39 }

    40 

    41 

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

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

    44   case NULL => NULL

    45   case EMPTY => NULL  

    46   case ALLC => EMPTY

    47   case CHAR(d) => if (c == d) EMPTY else NULL

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

    49   case SEQ(r1, r2) => 

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

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

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

    53   case NOT(r) => NOT(der (c, r))

    54 }

    55 

    56 // regular expression for specifying 

    57 // ranges of characters

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

    59   case Nil => NULL

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

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

    62 }

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

    64 

    65 

    66 // one or more

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

    68 

    69 // many alternatives

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

    71   case Nil => NULL

    72   case r::Nil => r

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

    74 }

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

    76 

    77 // repetitions

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

    79   case Nil => NULL

    80   case r::Nil => r

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

    82 }

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

    84 

    85 // some convenience for typing in regular expressions

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

    87   case Nil => EMPTY

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

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

    90 }

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

    92 

    93 

    94 type Rule[T] = (Rexp, List[Char] => T)

    95 

    96 case class Tokenizer[T](rules: List[Rule[T]], excl: List[T] = Nil) {

    97 

    98   def munch(r: Rexp, action: List[Char] => T, s: List[Char], t: List[Char]) : Option[(List[Char], T)] = 

    99     s match {

   100       case Nil if (nullable(r)) => Some(Nil, action(t))

   101       case Nil => None

   102       case c::s if (no_more(der (c, r)) && nullable(r)) => Some(c::s, action(t))

   103       case c::s if (no_more(der (c, r))) => None

   104       case c::s => munch(der (c, r), action, s, t ::: List(c))

   105     }

   106 

   107   def one_token(s: List[Char]) : Either[(List[Char], T), String] = {

   108     val somes = rules.map { (r) => munch(r._1, r._2, s, Nil) }.flatten

   109     if (somes == Nil) Right(s.mkString) 

   110     else Left(somes sortBy (_._1.length) head)

   111   }

   112 

   113   def tokenize(cs: List[Char]) : List[T] = cs match {

   114     case Nil => Nil

   115     case _ => one_token(cs) match {

   116       case Left((rest, token)) => token :: tokenize(rest)

   117       case Right(s) => { println("Cannot tokenize: \"" + s + "\""); Nil } 

   118     }

   119   }

   120 

   121   def fromString(s: String) : List[T] = 

   122     tokenize(s.toList).filterNot(excl.contains(_))

   123 

   124   def fromFile(name: String) : List[T] = 

   125     fromString(io.Source.fromFile(name).mkString)

   126 

   127 }

   128 

   129 

   130 // parser combinators with input type I and return type T

   131 

   132 abstract class Parser[I <% Seq[_], T] {

   133   def parse(ts: I): Set[(T, I)]

   134 

   135   def parse_all(ts: I) : Set[T] =

   136     for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head

   137 

   138   def parse_single(ts: I) : T = parse_all(ts).toList match {

   139     case t::Nil => t

   140     case _ => { println ("Parse Error") ; sys.exit(-1) }

   141   }

   142     

   143   def || (right : => Parser[I, T]) : Parser[I, T] = new AltParser(this, right)

   144   def ==>[S] (f: => T => S) : Parser [I, S] = new FunParser(this, f)

   145   def ~[S] (right : => Parser[I, S]) : Parser[I, (T, S)] = new SeqParser(this, right)

   146   def ~>[S] (right : => Parser[I, S]) : Parser[I, S] = this ~ right ==> (_._2)

   147   def <~[S] (right : => Parser[I, S]) : Parser[I, T] = this ~ right ==> (_._1)

   148 }

   149 

   150 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] {

   151   def parse(sb: I) = 

   152     for ((head1, tail1) <- p.parse(sb); 

   153          (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)

   154 }

   155 

   156 class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {

   157   def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   

   158 }

   159 

   160 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {

   161   def parse(sb: I) = 

   162     for ((head, tail) <- p.parse(sb)) yield (f(head), tail)

   163 }

   164 

   165 

   166 // A parser and evaluator for teh while language

   167 // 

   168 //:load matcher.scala

   169 //:load parser3.scala

   170 

   171 // some regular expressions

   172 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")

   173 val DIGIT = RANGE("0123456789")

   174 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) 

   175 val NUM = PLUS(DIGIT)

   176 val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") 

   177 val SEMI: Rexp = ";"

   178 val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!=", "<", ">")

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

   180 val RPAREN: Rexp = ")"

   181 val LPAREN: Rexp = "("

   182 val BEGIN: Rexp = "{"

   183 val END: Rexp = "}"

   184 val COMMENT = SEQS("/*", NOT(SEQS(STAR(ALLC), "*/", STAR(ALLC))), "*/")

   185 

   186 // tokens for classifying the strings that have been recognised

   187 abstract class Token

   188 case object T_WHITESPACE extends Token

   189 case object T_COMMENT extends Token

   190 case object T_SEMI extends Token

   191 case object T_LPAREN extends Token

   192 case object T_RPAREN extends Token

   193 case object T_BEGIN extends Token

   194 case object T_END extends Token

   195 case class T_ID(s: String) extends Token

   196 case class T_OP(s: String) extends Token

   197 case class T_NUM(s: String) extends Token

   198 case class T_KWD(s: String) extends Token

   199 

   200 val lexing_rules: List[Rule[Token]] = 

   201   List((KEYWORD, (s) => T_KWD(s.mkString)),

   202        (ID, (s) => T_ID(s.mkString)),

   203        (OP, (s) => T_OP(s.mkString)),

   204        (NUM, (s) => T_NUM(s.mkString)),

   205        (SEMI, (s) => T_SEMI),

   206        (LPAREN, (s) => T_LPAREN),

   207        (RPAREN, (s) => T_RPAREN),

   208        (BEGIN, (s) => T_BEGIN),

   209        (END, (s) => T_END),

   210        (WHITESPACE, (s) => T_WHITESPACE),

   211        (COMMENT, (s) => T_COMMENT))

   212 

   213 // the tokenizer

   214 val Tok = Tokenizer(lexing_rules, List(T_WHITESPACE, T_COMMENT))

   215 

   216 // the abstract syntax trees

   217 abstract class Stmt

   218 abstract class AExp

   219 abstract class BExp 

   220 type Block = List[Stmt]

   221 case object Skip extends Stmt

   222 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt

   223 case class While(b: BExp, bl: Block) extends Stmt

   224 case class Assign(s: String, a: AExp) extends Stmt

   225 case class Write(s: String) extends Stmt

   226 

   227 case class Var(s: String) extends AExp

   228 case class Num(i: Int) extends AExp

   229 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp

   230 

   231 case object True extends BExp

   232 case object False extends BExp

   233 case class Relop(o: String, a1: AExp, a2: AExp) extends BExp

   234 

   235 // atomic parsers

   236 case class TokParser(tok: Token) extends Parser[List[Token], Token] {

   237   def parse(ts: List[Token]) = ts match {

   238     case t::ts if (t == tok) => Set((t, ts)) 

   239     case _ => Set ()

   240   }

   241 }

   242 implicit def token2tparser(t: Token) = TokParser(t)

   243 

   244 case object NumParser extends Parser[List[Token], Int] {

   245   def parse(ts: List[Token]) = ts match {

   246     case T_NUM(s)::ts => Set((s.toInt, ts)) 

   247     case _ => Set ()

   248   }

   249 }

   250 

   251 case object IdParser extends Parser[List[Token], String] {

   252   def parse(ts: List[Token]) = ts match {

   253     case T_ID(s)::ts => Set((s, ts)) 

   254     case _ => Set ()

   255   }

   256 }

   257 

   258 

   259 // arithmetic expressions

   260 lazy val AExp: Parser[List[Token], AExp] = 

   261   (T ~ T_OP("+") ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||

   262   (T ~ T_OP("-") ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || T  

   263 lazy val T: Parser[List[Token], AExp] = 

   264   (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || F

   265 lazy val F: Parser[List[Token], AExp] = 

   266   (T_LPAREN ~> AExp <~ T_RPAREN) || 

   267   IdParser ==> Var || 

   268   NumParser ==> Num

   269 

   270 // boolean expressions

   271 lazy val BExp: Parser[List[Token], BExp] = 

   272   (T_KWD("true") ==> ((_) => True: BExp)) || 

   273   (T_KWD("false") ==> ((_) => False: BExp)) ||

   274   (T_LPAREN ~> BExp <~ T_RPAREN) ||

   275   (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Relop("=", x, z): BExp } || 

   276   (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Relop("!=", x, z): BExp } || 

   277   (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Relop("<", x, z): BExp } || 

   278   (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Relop("<", z, x): BExp } 

   279 

   280 lazy val Stmt: Parser[List[Token], Stmt] =

   281   (T_KWD("skip") ==> ((_) => Skip: Stmt)) ||

   282   (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||

   283   (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==>

   284     { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||

   285   (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } || 

   286   (T_KWD("write") ~ IdParser) ==> { case (x, y) => Write(y) } 

   287 

   288 lazy val Stmts: Parser[List[Token], Block] =

   289   (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } ||

   290   (Stmt ==> ((s) => List(s) : Block))

   291 

   292 lazy val Block: Parser[List[Token], Block] =

   293   (T_BEGIN ~> Stmts <~ T_END) || 

   294   (Stmt ==> ((s) => List(s)))

   295 

   296 // compiler

   297 val beginning = """

   298 .class public XXX.XXX

   299 .super java/lang/Object

   300 

   301 .method public <init>()V

   302    aload_0

   303    invokenonvirtual java/lang/Object/<init>()V

   304    return

   305 .end method

   306 

   307 .method public static write(I)V 

   308     .limit locals 5 

   309     .limit stack 5 

   310     iload 0 

   311     getstatic java/lang/System/out Ljava/io/PrintStream; 

   312     swap 

   313     invokevirtual java/io/PrintStream/println(I)V 

   314     return 

   315 .end method

   316 

   317 

   318 .method public static main([Ljava/lang/String;)V

   319    .limit locals 200

   320    .limit stack 200

   321 

   322 """

   323 

   324 val ending = """

   325 

   326    return

   327 

   328 .end method

   329 """

   330 

   331 // for generating new labels

   332 var counter = -1

   333 

   334 def Fresh(x: String) = {

   335   counter += 1

   336   x ++ "_" ++ counter.toString()

   337 }

   338 

   339 type Env = Map[String, String]

   340 type Instrs = List[String]

   341 

   342 def compile_aexp(a: AExp, env : Env) : Instrs = a match {

   343   case Num(i) => List("ldc " + i.toString + "\n")

   344   case Var(s) => List("iload " + env(s) + "\n")

   345   case Aop("+", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("iadd\n")

   346   case Aop("-", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n")

   347   case Aop("*", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n")

   348 }

   349 

   350 def compile_bexp(b: BExp, env : Env, jmp: String) : Instrs = b match {

   351   case True => Nil

   352   case False => List("goto " + jmp + "\n")

   353   case Relop("=", a1, a2) => 

   354     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpne " + jmp + "\n")

   355   case Relop("!=", a1, a2) => 

   356     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpeq " + jmp + "\n")

   357   case Relop("<", a1, a2) => 

   358     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpge " + jmp + "\n")

   359 }

   360 

   361 

   362 def compile_stmt(s: Stmt, env: Env) : (Instrs, Env) = s match {

   363   case Skip => (Nil, env)

   364   case Assign(x, a) => {

   365     val index = if (env.isDefinedAt(x)) env(x) else env.keys.size.toString

   366     (compile_aexp(a, env) ++ 

   367      List("istore " + index + "\n"), env + (x -> index))

   368   } 

   369   case If(b, bl1, bl2) => {

   370     val if_else = Fresh("If_else")

   371     val if_end = Fresh("If_end")

   372     val (instrs1, env1) = compile_bl(bl1, env)

   373     val (instrs2, env2) = compile_bl(bl2, env1)

   374     (compile_bexp(b, env, if_else) ++

   375      instrs1 ++

   376      List("goto " + if_end + "\n") ++

   377      List("\n" + if_else + ":\n\n") ++

   378      instrs2 ++

   379      List("\n" + if_end + ":\n\n"), env2)

   380   }

   381   case While(b, bl) => {

   382     val loop_begin = Fresh("Loop_begin")

   383     val loop_end = Fresh("Loop_end")

   384     val (instrs1, env1) = compile_bl(bl, env)

   385     (List("\n" + loop_begin + ":\n\n") ++

   386      compile_bexp(b, env, loop_end) ++

   387      instrs1 ++

   388      List("goto " + loop_begin + "\n") ++

   389      List("\n" + loop_end + ":\n\n"), env1)

   390   }

   391   case Write(x) => 

   392     (List("iload " + env(x) + "\n" + "invokestatic XXX/XXX/write(I)V\n"), env)

   393 }

   394 

   395 def compile_bl(bl: Block, env: Env) : (Instrs, Env) = bl match {

   396   case Nil => (Nil, env)

   397   case s::bl => {

   398     val (instrs1, env1) = compile_stmt(s, env)

   399     val (instrs2, env2) = compile_bl(bl, env1)

   400     (instrs1 ++ instrs2, env2)

   401   }

   402 }

   403 

   404 def compile(input: String) : String = {

   405   val class_name = input.split('.')(0)

   406   val tks = Tok.fromFile(input)

   407   val ast = Stmts.parse_single(tks)

   408   val instructions = compile_bl(ast, Map.empty)._1

   409   (beginning ++ instructions.mkString ++ ending).replaceAllLiterally("XXX", class_name)

   410 }

   411 

   412 

   413 def compile_to(input: String, output: String) = {

   414   val fw = new java.io.FileWriter(output) 

   415   fw.write(compile(input)) 

   416   fw.close()

   417 }

   418 

   419 //

   420 val tks = Tok.fromString("x := x + 1")

   421 val ast = Stmt.parse_single(tks)

   422 println(compile_stmt(ast, Map("x" -> "n"))._1.mkString)

   423 

   424 

   425 

   426 //examples

   427 

   428 compile_to("loops.while", "loops.j")

   429 //compile_to("fib.while", "fib.j")

   430 

   431 

   432 // testing cases for time measurements

   433 /*

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

   435   val start = System.nanoTime()

   436   for (j <- 1 to i) code

   437   val end = System.nanoTime()

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

   439 }

   440 

   441 // for testing

   442 import scala.sys.process._

   443 

   444 val test_prog = """

   445 start := XXX;

   446 x := start;

   447 y := start;

   448 z := start;

   449 while 0 < x do {

   450  while 0 < y do {

   451   while 0 < z do {

   452     z := z - 1

   453   };

   454   z := start;

   455   y := y - 1

   456  };     

   457  y := start;

   458  x := x - 1

   459 };

   460 write x;

   461 write y;

   462 write z

   463 """

   464 

   465 

   466 def compile_test(n: Int) : Unit = {

   467   val class_name = "LOOP"

   468   val tks = Tok.fromString(test_prog.replaceAllLiterally("XXX", n.toString))

   469   val ast = Stmts.parse_single(tks)

   470   val instructions = compile_bl(ast, Map.empty)._1

   471   val assembly = (beginning ++ instructions.mkString ++ ending).replaceAllLiterally("XXX", class_name)

   472   val fw = new java.io.FileWriter(class_name + ".j") 

   473   fw.write(assembly) 

   474   fw.close()

   475   val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!!

   476   println(n + " " + time_needed(2, ("java " + class_name + "/" + class_name).!!))

   477 }

   478 

   479 List(1, 5000, 10000, 50000, 100000, 250000, 500000, 750000, 1000000).map(compile_test(_))

   480 

   481 

   482 

   483 // javabyte code assmbler

   484 //

   485 // java -jar jvm/jasmin-2.4/jasmin.jar loops.j

   486 

   487 */

   488 

   489 

   490 

   491 

   492