# HG changeset patch # User Christian Urban # Date 1586517079 -3600 # Node ID 9a431d1eac85296e32ce72c4b192894e22875e03 # Parent df7d47a507f8ece2281c940237907ba3475190b9 added parser file diff -r df7d47a507f8 -r 9a431d1eac85 progs/c.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/c.scala Fri Apr 10 12:11:19 2020 +0100 @@ -0,0 +1,250 @@ +// A parser and interpreter for the While language +// + +import scala.language.implicitConversions +import scala.language.reflectiveCalls +import scala.collection.immutable._ + +// more convenience for the semantic actions later on +case class ~[+A, +B](_1: A, _2: B) + + +type IsSeq[A] = A => Seq[_] + +abstract class Parser[I : IsSeq, T] { + def parse(ts: I): Set[(T, I)] + + def parse_all(ts: I) : Set[T] = + for ((head, tail) <- parse(ts); if tail.isEmpty) yield head +} + +class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, ~[T, S]] { + def parse(sb: I) = + for ((head1, tail1) <- p.parse(sb); + (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2) +} + +class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { + def parse(sb: I) = p.parse(sb) ++ q.parse(sb) +} + +class MapParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { + def parse(sb: I) = + for ((head, tail) <- p.parse(sb)) yield (f(head), tail) +} + +case class StrParser(s: String) extends Parser[String, String] { + def parse(sb: String) = { + val (prefix, suffix) = sb.splitAt(s.length) + if (prefix == s) Set((prefix, suffix)) else Set() + } +} + +case object NumParser extends Parser[String, Int] { + val reg = "[0-9]+".r + def parse(sb: String) = reg.findPrefixOf(sb) match { + case None => Set() + case Some(s) => { + val (head, tail) = sb.splitAt(s.length) + Set((head.toInt, tail)) + } + } +} + + +implicit def parser_interpolation(sc: StringContext) = new { + def p(args: Any*) = StrParser(sc.s(args:_*)) +} + +// this string interpolation allows us to write +// things like the following for a StrParser +// +// p"<_some_string_>" +// +// instead of StrParser(<_some_string_>) + + +implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new { + def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) + def ~[S](q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) + def map[S](f: => T => S) = new MapParser[I, T, S](p, f) +} + +// these implicits allow us to use infic notation for +// sequences and alternatives; we also can write map +// for a parser + + +// the abstract syntax trees for the WHILE language +abstract class Stmt +abstract class AExp +abstract class BExp + +type Block = List[Stmt] + +case object Skip extends Stmt +case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt +case class While(b: BExp, bl: Block) extends Stmt +case class Assign(s: String, a: AExp) extends Stmt +case class Write(s: String) extends Stmt + + +case class Var(s: String) extends AExp +case class Num(i: Int) extends AExp +case class Aop(o: String, a1: AExp, a2: AExp) extends AExp + +case object True extends BExp +case object False extends BExp +case class Bop(o: String, a1: AExp, a2: AExp) extends BExp +case class And(b1: BExp, b2: BExp) extends BExp +case class Or(b1: BExp, b2: BExp) extends BExp + +case object IdParser extends Parser[String, String] { + val reg = "[a-z][a-z,0-9]*".r + def parse(sb: String) = reg.findPrefixOf(sb) match { + case None => Set() + case Some(s) => Set(sb.splitAt(s.length)) + } +} + +// arithmetic expressions +lazy val AExp: Parser[String, AExp] = + (Te ~ p"+" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } || + (Te ~ p"-" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te +lazy val Te: Parser[String, AExp] = + (Fa ~ p"*" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } || + (Fa ~ p"/" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa +lazy val Fa: Parser[String, AExp] = + (p"(" ~ AExp ~ p")").map{ case _ ~ y ~ _ => y } || + IdParser.map(Var) || + NumParser.map(Num) + +// boolean expressions with some simple nesting +lazy val BExp: Parser[String, BExp] = + (AExp ~ p"==" ~ AExp).map { case x ~ _ ~ z => Bop("==", x, z): BExp } || + (AExp ~ p"!=" ~ AExp).map { case x ~ _ ~ z => Bop("!=", x, z): BExp } || + (AExp ~ p"<" ~ AExp).map { case x ~ _ ~ z => Bop("<", x, z): BExp } || + (AExp ~ p">" ~ AExp).map { case x ~ _ ~ z => Bop(">", x, z): BExp } || + (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).map { case _ ~ y ~ _ ~ _ ~ v => And(y, v): BExp } || + (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).map { case _ ~ y ~ _ ~ _ ~ v => Or(y, v): BExp } || + (p"true".map { _ => True: BExp }) || + (p"false".map { _ => False: BExp }) || + (p"(" ~ BExp ~ p")").map { case _ ~ x ~ _ => x } + +// statement / statements +lazy val Stmt: Parser[String, Stmt] = + ((p"skip".map {_ => Skip: Stmt}) || + (IdParser ~ p":=" ~ AExp).map { case x ~ _ ~ z => Assign(x, z): Stmt } || + (p"write(" ~ IdParser ~ p")").map { case _ ~ y ~ _ => Write(y): Stmt } || + (p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block) + .map{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w): Stmt } || + (p"while" ~ BExp ~ p"do" ~ Block).map { case _ ~ y ~ _ ~ w => While(y, w) }) + +lazy val Stmts: Parser[String, Block] = + (Stmt ~ p";" ~ Stmts).map { case x ~ _ ~ z => x :: z : Block } || + (Stmt.map { s => List(s) : Block}) + +// blocks (enclosed in curly braces) +lazy val Block: Parser[String, Block] = + ((p"{" ~ Stmts ~ p"}").map{ case _ ~ y ~ _ => y } || + (Stmt.map(s => List(s)))) + + +Stmts.parse_all("x2:=5+3;") +Block.parse_all("{x:=5;y:=8}") +Block.parse_all("if(false)then{x:=5}else{x:=10}") + +val fib = """n := 10; + minus1 := 0; + minus2 := 1; + temp := 0; + while (n > 0) do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1 + }; + result := minus2""".replaceAll("\\s+", "") + +Stmts.parse_all(fib) + + +// an interpreter for the WHILE language +type Env = Map[String, Int] + +def eval_aexp(a: AExp, env: Env) : Int = a match { + case Num(i) => i + case Var(s) => env(s) + case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env) + case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env) + case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env) + case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env) +} + +def eval_bexp(b: BExp, env: Env) : Boolean = b match { + case True => true + case False => false + case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) + case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env)) + case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env) + case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) + case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env) + case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env) +} + +def eval_stmt(s: Stmt, env: Env) : Env = s match { + case Skip => env + case Assign(x, a) => env + (x -> eval_aexp(a, env)) + case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) + case While(b, bl) => + if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env)) + else env + case Write(x) => { println(env(x)) ; env } +} + +def eval_bl(bl: Block, env: Env) : Env = bl match { + case Nil => env + case s::bl => eval_bl(bl, eval_stmt(s, env)) +} + +def eval(bl: Block) : Env = eval_bl(bl, Map()) + +// parse + evaluate fib program; then lookup what is +// stored under the variable result +println(eval(Stmts.parse_all(fib).head)("result")) + + +// more examles + +// calculate and print all factors bigger +// than 1 and smaller than n +println("Factors") + +val factors = + """n := 12; + f := 2; + while (f < n / 2 + 1) do { + if ((n / f) * f == n) then { write(f) } else { skip }; + f := f + 1 + }""".replaceAll("\\s+", "") + +eval(Stmts.parse_all(factors).head) + +// calculate all prime numbers up to a number +println("Primes") + +val primes = + """end := 100; + n := 2; + while (n < end) do { + f := 2; + tmp := 0; + while ((f < n / 2 + 1) && (tmp == 0)) do { + if ((n / f) * f == n) then { tmp := 1 } else { skip }; + f := f + 1 + }; + if (tmp == 0) then { write(n) } else { skip }; + n := n + 1 + }""".replaceAll("\\s+", "") + +eval(Stmts.parse_all(primes).head)