1 // Parser Combinators:

     2 // Simple Version for WHILE-language

     3 //====================================

     4 //

     5 // with some added convenience for

     6 // map-parsers and grammar rules

     7 //

     8 // call with

     9 //

    10 //    amm comb2.sc

    11 

    12 

    13 // more convenience for the map parsers later on;

    14 // it allows writing nested patterns as

    15 // case x ~ y ~ z => ...

    16 

    17 

    18 

    19 case class ~[+A, +B](x: A, y: B)

    20 

    21 // constraint for the input

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

    23 

    24 

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

    26   def parse(in: I): Set[(T, I)]

    27 

    28   def parse_all(in: I) : Set[T] =

    29     for ((hd, tl) <- parse(in); 

    30         if tl.isEmpty) yield hd

    31 }

    32 

    33 // parser combinators

    34 

    35 // sequence parser

    36 class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], 

    37                                  q: => Parser[I, S]) extends Parser[I, ~[T, S]] {

    38   def parse(in: I) = 

    39     for ((hd1, tl1) <- p.parse(in); 

    40          (hd2, tl2) <- q.parse(tl1)) yield (new ~(hd1, hd2), tl2)

    41 }

    42 

    43 // alternative parser

    44 class AltParser[I : IsSeq, T](p: => Parser[I, T], 

    45                               q: => Parser[I, T]) extends Parser[I, T] {

    46   def parse(in: I) = p.parse(in) ++ q.parse(in)   

    47 }

    48 

    49 // map parser

    50 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], 

    51                                  f: T => S) extends Parser[I, S] {

    52   def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl)

    53 }

    54 

    55 

    56 

    57 // atomic parser for (particular) strings

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

    59   def parse(sb: String) = {

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

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

    62   }

    63 }

    64 

    65 // atomic parser for identifiers (variable names)

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

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

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

    69     case None => Set()

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

    71   }

    72 }

    73 

    74 

    75 // atomic parser for numbers (transformed into ints)

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

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

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

    79     case None => Set()

    80     case Some(s) => {

    81       val (hd, tl) = sb.splitAt(s.length)

    82       Set((hd.toInt, tl)) 

    83     }

    84   }

    85 }

    86 

    87 // the following string interpolation allows us to write 

    88 // StrParser(_some_string_) more conveniently as 

    89 //

    90 // p"<_some_string_>" 

    91 

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

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

    94 }    

    95 

    96 // more convenient syntax for parser combinators

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

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

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

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

   101 }

   102 

   103 

   104 

   105 // the abstract syntax trees for the WHILE language

   106 abstract class Stmt

   107 abstract class AExp

   108 abstract class BExp 

   109 

   110 type Block = List[Stmt]

   111 

   112 case object Skip extends Stmt

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

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

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

   116 case class Write(s: String) extends Stmt

   117 

   118 case class Var(s: String) extends AExp

   119 case class Num(i: Int) extends AExp

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

   121 

   122 case object True extends BExp

   123 case object False extends BExp

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

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

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

   127 

   128 

   129 // arithmetic expressions

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

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

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

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

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

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

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

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

   138    IdParser.map(Var) || 

   139    NumParser.map(Num)

   140 

   141 // boolean expressions with some simple nesting

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

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

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

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

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

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

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

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

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

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

   152 

   153 // a single statement 

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

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

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

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

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

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

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

   161  

   162  

   163 // statements

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

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

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

   167 

   168 // blocks (enclosed in curly braces)

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

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

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

   172 

   173 

   174 // Examples

   175 Stmt.parse_all("x2:=5+3")

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

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

   178 

   179 

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

   181              minus1 := 0;

   182              minus2 := 1;

   183              temp := 0;

   184              while (n > 0) do {

   185                  temp := minus2;

   186                  minus2 := minus1 + minus2;

   187                  minus1 := temp;

   188                  n := n - 1

   189              };

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

   191 

   192 Stmts.parse_all(fib)

   193 

   194 

   195 // an interpreter for the WHILE language

   196 type Env = Map[String, Int]

   197 

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

   199   case Num(i) => i

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

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

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

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

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

   205 }

   206 

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

   208   case True => true

   209   case False => false

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

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

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

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

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

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

   216 }

   217 

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

   219   case Skip => env

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

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

   222   case While(b, bl) => 

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

   224     else env

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

   226 }

   227 

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

   229   case Nil => env

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

   231 }

   232 

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

   234 

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

   236 // stored under the variable "result" 

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

   238 

   239 

   240 // more examles

   241 

   242 // calculate and print all factors bigger 

   243 // than 1 and smaller than n

   244 println("Factors")

   245 

   246 val factors =  

   247    """n := 12;

   248       f := 2;

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

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

   251         f := f + 1

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

   253 

   254 println(eval(Stmts.parse_all(factors).head))

   255 

   256 

   257 // calculate all prime numbers up to a number 

   258 println("Primes")

   259 

   260 val primes =  

   261    """end := 100;

   262       n := 2;

   263       while (n < end) do {

   264         f := 2;

   265         tmp := 0;

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

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

   268           f := f + 1

   269         };

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

   271         n  := n + 1

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

   273 

   274 println(eval(Stmts.parse_all(primes).head))

   275 

   276 

   277 

   278 

   279 

   280 // runs with amm2 and amm3