1 // CW3

     2 

     3 import $file.lexer

     4 import lexer._ 

     5 

     6 

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

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

     9 

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

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

    12 

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

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

    15 }

    16 

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

    18   def parse(sb: I) = 

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

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

    21 }

    22 

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

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

    25 }

    26 

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

    28   def parse(sb: I) = 

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

    30 }

    31 

    32 // New parser that takes as input a list of tokens

    33 case class TokenListParser(ts: List[Token]) extends Parser[List[Token], List[Token]] {

    34     def parse(tsb: List[Token]) = {

    35         val (prefix, suffix) = tsb.splitAt(ts.length)

    36         if (prefix == ts) Set((prefix, suffix)) else Set()

    37     }

    38 }

    39 

    40 // Implicit definitions to go from a token 

    41 // or a list of tokens to a TokenListParser

    42 implicit def token2parser(t: Token) = TokenListParser(List(t))

    43 implicit def tokenList2parser(ts: List[Token]) = TokenListParser(ts)

    44 

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

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

    47   def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)

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

    49 }

    50 

    51 implicit def TokenOps(t: Token) = new {

    52     def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](List(t), q)

    53     def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](List(t), qs)

    54     def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](List(t), f)

    55     def ~[S](q : => Parser[List[Token], S]) =

    56         new SeqParser[List[Token], List[Token], S](List(t), q)

    57     def ~ (qs : List[Token]) =

    58         new SeqParser[List[Token], List[Token], List[Token]](List(t), qs)

    59 }

    60 

    61 implicit def TokenListOps(ts: List[Token]) = new {

    62     def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](ts, q)

    63     def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](ts, qs)

    64     def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](ts, f)

    65     def ~[S](q : => Parser[List[Token], S]) =

    66         new SeqParser[List[Token], List[Token], S](ts, q)

    67     def ~ (qs : List[Token]) =

    68         new SeqParser[List[Token], List[Token], List[Token]](ts, qs)

    69 }

    70 

    71 // Abstract Syntax Trees

    72 abstract class Stmt

    73 abstract class AExp

    74 abstract class BExp

    75 

    76 type Block = List[Stmt]

    77 

    78 case object Skip extends Stmt

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

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

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

    82 case class Read(s: String) extends Stmt

    83 case class WriteId(s: String) extends Stmt  // for printing values of variables

    84 case class WriteString(s: String) extends Stmt  // for printing words

    85 

    86 case class Var(s: String) extends AExp

    87 case class Num(i: Int) extends AExp

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

    89 

    90 case object True extends BExp

    91 case object False extends BExp

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

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

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

    95 

    96 case class IdParser() extends Parser[List[Token], String] {

    97     def parse(tsb: List[Token]) = tsb match {

    98         case T_ID(id) :: rest => Set((id, rest))

    99         case _ => Set()

   100     }

   101 }

   102 

   103 case class NumParser() extends Parser[List[Token], Int] {

   104     def parse(tsb: List[Token]) = tsb match {

   105         case T_NUM(n) :: rest => Set((n, rest))

   106         case _ => Set()

   107     }

   108 }

   109 

   110 case class StringParser() extends Parser[List[Token], String] {

   111     def parse(tsb: List[Token]) = tsb match {

   112         case T_STRING(s) :: rest => Set((s, rest))

   113         case _ => Set()

   114     }

   115 }

   116 

   117 // WHILE Language Parsing

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

   119   (Te ~ T_OP("+") ~ AExp) ==> { case x ~ _ ~ z => Aop("+", x, z): AExp } ||

   120   (Te ~ T_OP("-") ~ AExp) ==> { case x ~ _ ~ z => Aop("-", x, z): AExp } || Te

   121 lazy val Te: Parser[List[Token], AExp] = 

   122   (Fa ~ T_OP("*") ~ Te) ==> { case x ~ _ ~ z => Aop("*", x, z): AExp } || 

   123   (Fa ~ T_OP("/") ~ Te) ==> { case x ~ _ ~ z => Aop("/", x, z): AExp } || 

   124   (Fa ~ T_OP("%") ~ Te) ==> { case x ~ _ ~ z => Aop("%", x, z): AExp } || Fa  

   125 lazy val Fa: Parser[List[Token], AExp] = 

   126    (T_PAREN("(") ~ AExp ~ T_PAREN(")")) ==> { case _ ~ y ~ _ => y } || 

   127    IdParser() ==> Var  || 

   128    NumParser() ==> Num

   129 

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

   131    (AExp ~ T_OP("==") ~ AExp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } || 

   132    (AExp ~ T_OP("!=") ~ AExp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } || 

   133    (AExp ~ T_OP("<") ~ AExp) ==> { case x ~ _ ~ z => Bop("<", x, z): BExp } || 

   134    (AExp ~ T_OP(">") ~ AExp) ==> { case x ~ _ ~ z => Bop(">", x, z): BExp } ||

   135    (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("&&")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => And(y, v): BExp } ||

   136    (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("||")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => Or(y, v): BExp } ||

   137    (T_KEYWORD("true") ==> (_ => True: BExp )) || 

   138    (T_KEYWORD("false") ==> (_ => False: BExp )) ||

   139    (T_PAREN("(") ~ BExp ~ T_PAREN(")")) ==> { case _ ~ x ~ _ => x }

   140 

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

   142     T_KEYWORD("skip") ==> (_ => Skip: Stmt) ||

   143     (IdParser() ~ T_OP(":=") ~ AExp) ==> { case id ~ _ ~ z => Assign(id, z): Stmt } ||

   144     (T_KEYWORD("if") ~ BExp ~ T_KEYWORD("then") ~ Block ~ T_KEYWORD("else") ~ Block) ==> { case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w): Stmt } ||

   145     (T_KEYWORD("while") ~ BExp ~ T_KEYWORD("do") ~ Block) ==> { case _ ~ y ~ _ ~ w => While(y, w) : Stmt } ||

   146     (T_KEYWORD("read") ~ IdParser()) ==> { case _ ~ id => Read(id): Stmt} ||

   147     (T_KEYWORD("write") ~ IdParser()) ==> { case _ ~ id => WriteId(id): Stmt} ||

   148     (T_KEYWORD("write") ~ StringParser()) ==> { case _ ~ s => WriteString(s): Stmt}

   149 

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

   151     (Stmt ~ T_SEMI ~ Stmts) ==> { case x ~ _ ~ z => x :: z : Block } ||

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

   153 

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

   155     (T_PAREN("{") ~ Stmts ~ T_PAREN("}")) ==> { case x ~ y ~ z => y} ||

   156     (Stmt ==> (s => List(s)))

   157 

   158 // Testing with programs 2 & 3

   159 

   160 println("Fibonacci")

   161 println(Stmts.parse_all(tokenise(os.read(os.pwd / "fib.while"))))

   162 

   163 println("Loops")

   164 println(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))))

   165 

   166 println("Collatz")

   167 println(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))))

   168 

   169 

   170 // Interpreter

   171 

   172 // Environment to store values of variables

   173 type Env = Map[String, Int]

   174 

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

   176   case Num(i) => i

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

   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   case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env)

   182   case Aop("%", a1, a2) => eval_aexp(a1, env) % eval_aexp(a2, env)

   183 }

   184 

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

   186   case True => true

   187   case False => false

   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 Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)

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

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

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

   194 }

   195 

   196 // Import needed to take int as input from the user

   197 import scala.io.StdIn.readInt

   198 

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

   200   case Skip => env

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

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

   203   case While(b, bl) => 

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

   205     else env

   206 

   207   case WriteId(x) => { print(env(x)) ; env }

   208   case WriteString(x) => {

   209         print(x.replaceAll("\"", "").replaceAll("""\\n""", "\n")) ;

   210         env

   211        }

   212 

   213   case Read(x) => { 

   214       println("Enter an integer and press ENTER:") ; 

   215       val n = readInt() ; // Note: Does not work when using the REPL

   216       eval_stmt(Assign(x, Num(n)), env) 

   217   }

   218 }

   219 

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

   221   case Nil => env

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

   223 }

   224 

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

   226 

   227 println("Factors eval")

   228 println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "factors.while"))).head))

   229 

   230 println("Collatz2 eval")

   231 println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head))

   232 

   233 /*

   234 println("Loops eval")

   235 val start = System.nanoTime()

   236 println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))).head))

   237 val end = System.nanoTime()

   238 println("Time taken in seconds: ")

   239 println((end - start)/(1.0e9))

   240 */