1 // A parser and interpreter for the While language

     2 // 

     3 

     4 import scala.language.implicitConversions

     5 import scala.language.reflectiveCalls

     6 

     7 

     8 // more convenience for the semantic actions later on

     9 case class ~[+A, +B](_1: A, _2: B)

    10 

    11 type IsSeq[A] = A => Seq[_]

    12 

    13 abstract class Parser[I : IsSeq, T] {

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

    15 

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

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

    18 }

    19 

    20 class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, ~[T, S]] {

    21   def parse(sb: I) = 

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

    23          (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2)

    24 }

    25 

    26 class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {

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

    28 }

    29 

    30 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {

    31   def parse(sb: I) = 

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

    33 }

    34 

    35 case class StrParser(s: String) extends Parser[String, String] {

    36   def parse(sb: String) = {

    37     val (prefix, suffix) = sb.splitAt(s.length)

    38     if (prefix == s) Set((prefix, suffix)) else Set()

    39   }

    40 }

    41 

    42 case object NumParser extends Parser[String, Int] {

    43   val reg = "[0-9]+".r

    44   def parse(sb: String) = reg.findPrefixOf(sb) match {

    45     case None => Set()

    46     case Some(s) => {

    47       val (head, tail) = sb.splitAt(s.length)

    48       Set((head.toInt, tail)) 

    49     }

    50   }

    51 }

    52 

    53 

    54 implicit def parser_interpolation(sc: StringContext) = new {

    55     def p(args: Any*) = StrParser(sc.s(args:_*))

    56 }

    57 

    58 // this string interpolation allows us to write 

    59 // things like the following for a StrParser

    60 //

    61 // p"<_some_string_>" 

    62 //

    63 // instead of StrParser(<_some_string_>)

    64 

    65 

    66 implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new {

    67   def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q)

    68   def ~[S](q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)

    69   def map[S](f: => T => S) = new MapParser[I, T, S](p, f) 

    70 }

    71 

    72 // these implicits allow us to use infic notation for

    73 // sequences and alternatives; we also can write map

    74 // for a parser

    75 

    76 

    77 // the abstract syntax trees for the WHILE language

    78 abstract class Stmt

    79 abstract class AExp

    80 abstract class BExp 

    81 

    82 type Block = List[Stmt]

    83 

    84 case object Skip extends Stmt

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

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

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

    88 case class Write(s: String) extends Stmt

    89 

    90 

    91 case class Var(s: String) extends AExp

    92 case class Num(i: Int) extends AExp

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

    94 

    95 case object True extends BExp

    96 case object False extends BExp

    97 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp

    98 case class And(b1: BExp, b2: BExp) extends BExp

    99 case class Or(b1: BExp, b2: BExp) extends BExp

   100 

   101 case object IdParser extends Parser[String, String] {

   102   val reg = "[a-z][a-z,0-9]*".r

   103   def parse(sb: String) = reg.findPrefixOf(sb) match {

   104     case None => Set()

   105     case Some(s) => Set(sb.splitAt(s.length))

   106   }

   107 }

   108 

   109 // arithmetic expressions

   110 lazy val AExp: Parser[String, AExp] = 

   111   (Te ~ p"+" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } ||

   112   (Te ~ p"-" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te

   113 lazy val Te: Parser[String, AExp] = 

   114   (Fa ~ p"*" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } || 

   115   (Fa ~ p"/" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa  

   116 lazy val Fa: Parser[String, AExp] = 

   117    (p"(" ~ AExp ~ p")").map{ case _ ~ y ~ _ => y } || 

   118    IdParser.map(Var) || 

   119    NumParser.map(Num)

   120 

   121 // boolean expressions with some simple nesting

   122 lazy val BExp: Parser[String, BExp] = 

   123    (AExp ~ p"==" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("==", x, z) } || 

   124    (AExp ~ p"!=" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("!=", x, z) } || 

   125    (AExp ~ p"<" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("<", x, z) } || 

   126    (AExp ~ p">" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop(">", x, z) } ||

   127    (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => And(y, v) } ||

   128    (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v) } ||

   129    (p"true".map[BExp]{ _ => True }) || 

   130    (p"false".map[BExp]{ _ => False }) ||

   131    (p"(" ~ BExp ~ p")").map[BExp]{ case _ ~ x ~ _ => x }

   132 

   133 // statement / statements

   134 lazy val Stmt: Parser[String, Stmt] =

   135   ((p"skip".map[Stmt]{_ => Skip }) ||

   136    (IdParser ~ p":=" ~ AExp).map[Stmt]{ case x ~ _ ~ z => Assign(x, z) } ||

   137    (p"write(" ~ IdParser ~ p")").map[Stmt]{ case _ ~ y ~ _ => Write(y) } ||

   138    (p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block)

   139      .map[Stmt]{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w) } ||

   140    (p"while" ~ BExp ~ p"do" ~ Block).map[Stmt]{ case _ ~ y ~ _ ~ w => While(y, w) }) 

   141  

   142 lazy val Stmts: Parser[String, Block] =

   143   (Stmt ~ p";" ~ Stmts).map[Block]{ case x ~ _ ~ z => x :: z } ||

   144   (Stmt.map[Block]{ s => List(s) })

   145 

   146 // blocks (enclosed in curly braces)

   147 lazy val Block: Parser[String, Block] =

   148   ((p"{" ~ Stmts ~ p"}").map{ case _ ~ y ~ _ => y } || 

   149    (Stmt.map(s => List(s))))

   150 

   151 

   152 Stmts.parse_all("x2:=5+3;")

   153 Block.parse_all("{x:=5;y:=8}")

   154 Block.parse_all("if(false)then{x:=5}else{x:=10}")

   155 

   156 val fib = """n := 10;

   157              minus1 := 0;

   158              minus2 := 1;

   159              temp := 0;

   160              while (n > 0) do {

   161                  temp := minus2;

   162                  minus2 := minus1 + minus2;

   163                  minus1 := temp;

   164                  n := n - 1

   165              };

   166              result := minus2""".replaceAll("\\s+", "")

   167 

   168 Stmts.parse_all(fib)

   169 

   170 

   171 // an interpreter for the WHILE language

   172 type Env = Map[String, Int]

   173 

   174 def eval_aexp(a: AExp, env: Env) : Int = a match {

   175   case Num(i) => i

   176   case Var(s) => env(s)

   177   case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)

   178   case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)

   179   case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)

   180   case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env)

   181 }

   182 

   183 def eval_bexp(b: BExp, env: Env) : Boolean = b match {

   184   case True => true

   185   case False => false

   186   case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)

   187   case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))

   188   case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)

   189   case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)

   190   case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env)

   191   case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env)

   192 }

   193 

   194 def eval_stmt(s: Stmt, env: Env) : Env = s match {

   195   case Skip => env

   196   case Assign(x, a) => env + (x -> eval_aexp(a, env))

   197   case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) 

   198   case While(b, bl) => 

   199     if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))

   200     else env

   201   case Write(x) => { println(env(x)) ; env }  

   202 }

   203 

   204 def eval_bl(bl: Block, env: Env) : Env = bl match {

   205   case Nil => env

   206   case s::bl => eval_bl(bl, eval_stmt(s, env))

   207 }

   208 

   209 def eval(bl: Block) : Env = eval_bl(bl, Map())

   210 

   211 // parse + evaluate fib program; then lookup what is

   212 // stored under the variable result 

   213 println(eval(Stmts.parse_all(fib).head)("result"))

   214 

   215 

   216 // more examles

   217 

   218 // calculate and print all factors bigger 

   219 // than 1 and smaller than n

   220 println("Factors")

   221 

   222 val factors =  

   223    """n := 12;

   224       f := 2;

   225       while (f < n / 2 + 1) do {

   226         if ((n / f) * f == n) then  { write(f) } else { skip };

   227         f := f + 1

   228       }""".replaceAll("\\s+", "")

   229 

   230 eval(Stmts.parse_all(factors).head)

   231 

   232 // calculate all prime numbers up to a number 

   233 println("Primes")

   234 

   235 val primes =  

   236    """end := 100;

   237       n := 2;

   238       while (n < end) do {

   239         f := 2;

   240         tmp := 0;

   241         while ((f < n / 2 + 1) && (tmp == 0)) do {

   242           if ((n / f) * f == n) then  { tmp := 1 } else { skip };

   243           f := f + 1

   244         };

   245         if (tmp == 0) then { write(n) } else { skip };

   246         n  := n + 1

   247       }""".replaceAll("\\s+", "")

   248 

   249 eval(Stmts.parse_all(primes).head)