1 // Parser Combinators:

     2 // Simple Version for WHILE-language

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

     4 //

     5 //

     6 // call with

     7 //

     8 //    amm comb2-simple.sc

     9 

    10 

    11 trait IsSeq[I] {

    12   extension (i: I) def isEmpty: Boolean

    13 }

    14 

    15 given IsSeq[String] = _.isEmpty

    16 given [I]: IsSeq[Seq[I]] = _.isEmpty

    17 

    18 // parser class

    19 //==============

    20 

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

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

    23 

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

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

    26         if tl.isEmpty) yield hd

    27 }

    28 

    29 // parser combinators

    30 //====================

    31 

    32 // alternative parser

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

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

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

    36 }

    37 

    38 // sequence parser

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

    40                                 q: => Parser[I, S]) extends Parser[I, (T, S)] {

    41   def parse(in: I) =

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

    43          (hd2, tl2) <- q.parse(tl1)) yield ((hd1, hd2), tl2)

    44 }

    45 

    46 // map parser

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

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

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

    50 }

    51 

    52 // more convenient syntax for parser combinators

    53 extension [I: IsSeq, T](p: Parser[I, T]) {

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

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

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

    57 }

    58 

    59 // atomic parser for (particular) strings

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

    61   def parse(sb: String) = {

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

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

    64   }

    65 }

    66 

    67 // atomic parser for identifiers (variable names)

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

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

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

    71     case None => Set()

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

    73   }

    74 }

    75 

    76 // atomic parser for numbers (transformed into Ints)

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

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

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

    80     case None => Set()

    81     case Some(s) => {

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

    83       Set((hd.toInt, tl)) 

    84     }

    85   }

    86 }

    87 

    88 // the following string interpolation allows us to write 

    89 // StrParser(_some_string_) more conveniently as 

    90 //

    91 // p"<_some_string_>" 

    92 

    93 extension (sc: StringContext) 

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

    95 

    96 // the abstract syntax trees for the WHILE language

    97 abstract class Stmt

    98 abstract class AExp

    99 abstract class BExp 

   100 

   101 type Block = List[Stmt]

   102 

   103 case object Skip extends Stmt

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

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

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

   107 case class Write(s: String) extends Stmt

   108 

   109 case class Var(s: String) extends AExp

   110 case class Num(i: Int) extends AExp

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

   112 

   113 case object True extends BExp

   114 case object False extends BExp

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

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

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

   118 

   119 

   120 // arithmetic expressions

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

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

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

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

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

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

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

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

   129    IdParser.map(Var(_)) || 

   130    NumParser.map(Num(_))

   131 

   132 // boolean expressions with some simple nesting

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

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

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

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

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

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

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

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

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

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

   143 

   144 // Stmt: a single statement

   145 // Stmts: multiple statements

   146 // Block: blocks (enclosed in curly braces)

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

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

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

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

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

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

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

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

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

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

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

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

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

   160 

   161 

   162 // Examples

   163 println(AExp.parse_all("2*2*2"))

   164 println(BExp.parse_all("5+3"))

   165 println(Stmt.parse_all("5==3"))

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

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

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

   169 

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

   171              minus1 := 0;

   172              minus2 := 1;

   173              temp := 0;

   174              while (n > 0) do {

   175                  temp := minus2;

   176                  minus2 := minus1 + minus2;

   177                  minus1 := temp;

   178                  n := n - 1

   179              };

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

   181 

   182 println("fib testcase:")

   183 println(Stmts.parse_all(fib))

   184 

   185 

   186 // an interpreter for the WHILE language

   187 type Env = Map[String, Int]

   188 

   189 def eval_aexp(a: AExp, env: Env) : Int =

   190   a match {

   191     case Num(i) => i

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

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

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

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

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

   197   }

   198 

   199 def eval_bexp(b: BExp, env: Env) : Boolean =

   200   b match {

   201     case True => true

   202     case False => false

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

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

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

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

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

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

   209   }

   210 

   211 def eval_stmt(s: Stmt, env: Env) : Env =

   212   s match {

   213     case Skip => env

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

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

   216     case While(b, bl) => 

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

   218       else env

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

   220   }

   221 def eval_bl(bl: Block, env: Env) : Env =

   222   bl match {

   223     case Nil => env

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

   225   }

   226 

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

   228 

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

   230 // stored under the variable "result" 

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

   232 

   233 

   234 // more examples

   235 

   236 // calculate and print all factors bigger 

   237 // than 1 and smaller than n

   238 println("Factors")

   239 

   240 val factors =  

   241    """n := 12;

   242       f := 2;

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

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

   245         f := f + 1

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

   247 

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

   249 

   250 

   251 // calculate all prime numbers up to a number 

   252 println("Primes")

   253 

   254 val primes =  

   255    """end := 100;

   256       n := 2;

   257       while (n < end) do {

   258         f := 2;

   259         tmp := 0;

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

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

   262           f := f + 1

   263         };

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

   265         n  := n + 1

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

   267 

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