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 case class TokParser(s: String) extends Parser[List[Token], String] { |
|
118 def parse(tsb: List[Token]) = tsb match { |
|
119 case T_OP(o) :: rest if s == o => Set((o, rest)) |
|
120 case T_KWD(k) :: rest if s == k => Set((k, rest)) |
|
121 case _ => Set() |
|
122 } |
|
123 } |
|
124 |
|
125 implicit def parser_interpolation(sc: StringContext) = new { |
|
126 def p(args: Any*) = TokParser(sc.s(args:_*)) |
|
127 } |
|
128 |
|
129 |
|
130 // WHILE Language Parsing |
|
131 lazy val AExp: Parser[List[Token], AExp] = |
|
132 (Te ~ T_OP("+") ~ AExp) ==> { case x ~ _ ~ z => Aop("+", x, z): AExp } || |
|
133 (Te ~ T_OP("-") ~ AExp) ==> { case x ~ _ ~ z => Aop("-", x, z): AExp } || Te |
|
134 lazy val Te: Parser[List[Token], AExp] = |
|
135 (Fa ~ T_OP("*") ~ Te) ==> { case x ~ _ ~ z => Aop("*", x, z): AExp } || |
|
136 (Fa ~ T_OP("/") ~ Te) ==> { case x ~ _ ~ z => Aop("/", x, z): AExp } || |
|
137 (Fa ~ T_OP("%") ~ Te) ==> { case x ~ _ ~ z => Aop("%", x, z): AExp } || Fa |
|
138 lazy val Fa: Parser[List[Token], AExp] = |
|
139 (T_PAREN("(") ~ AExp ~ T_PAREN(")")) ==> { case _ ~ y ~ _ => y } || |
|
140 IdParser() ==> Var || |
|
141 NumParser() ==> Num |
|
142 |
|
143 lazy val BExp: Parser[List[Token], BExp] = |
|
144 (AExp ~ T_OP("==") ~ AExp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } || |
|
145 (AExp ~ T_OP("!=") ~ AExp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } || |
|
146 (AExp ~ T_OP("<") ~ AExp) ==> { case x ~ _ ~ z => Bop("<", x, z): BExp } || |
|
147 (AExp ~ T_OP(">") ~ AExp) ==> { case x ~ _ ~ z => Bop(">", x, z): BExp } || |
|
148 (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("&&")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => And(y, v): BExp } || |
|
149 (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("||")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => Or(y, v): BExp } || |
|
150 (T_KEYWORD("true") ==> (_ => True: BExp )) || |
|
151 (T_KEYWORD("false") ==> (_ => False: BExp )) || |
|
152 (T_PAREN("(") ~ BExp ~ T_PAREN(")")) ==> { case _ ~ x ~ _ => x } |
|
153 |
|
154 lazy val Stmt: Parser[List[Token], Stmt] = |
|
155 T_KEYWORD("skip") ==> (_ => Skip: Stmt) || |
|
156 (IdParser() ~ T_OP(":=") ~ AExp) ==> { case id ~ _ ~ z => Assign(id, z): Stmt } || |
|
157 (T_KEYWORD("if") ~ BExp ~ T_KEYWORD("then") ~ Block ~ T_KEYWORD("else") ~ Block) ==> { case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w): Stmt } || |
|
158 (T_KEYWORD("while") ~ BExp ~ T_KEYWORD("do") ~ Block) ==> { case _ ~ y ~ _ ~ w => While(y, w) : Stmt } || |
|
159 (T_KEYWORD("read") ~ IdParser()) ==> { case _ ~ id => Read(id): Stmt} || |
|
160 (T_KEYWORD("write") ~ IdParser()) ==> { case _ ~ id => WriteId(id): Stmt} || |
|
161 (T_KEYWORD("write") ~ StringParser()) ==> { case _ ~ s => WriteString(s): Stmt} |
|
162 |
|
163 lazy val Stmts: Parser[List[Token], Block] = |
|
164 (Stmt ~ T_SEMI ~ Stmts) ==> { case x ~ _ ~ z => x :: z : Block } || |
|
165 (Stmt ==> (s => List(s) : Block)) |
|
166 |
|
167 lazy val Block: Parser[List[Token], Block] = |
|
168 (T_PAREN("{") ~ Stmts ~ T_PAREN("}")) ==> { case x ~ y ~ z => y} || |
|
169 (Stmt ==> (s => List(s))) |
|
170 |
|
171 // Testing with programs 2 & 3 |
|
172 |
|
173 println("Fibonacci") |
|
174 println(Stmts.parse_all(tokenise(os.read(os.pwd / "fib.while")))) |
|
175 |
|
176 println("Loops") |
|
177 println(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while")))) |
|
178 |
|
179 println("Collatz") |
|
180 println(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while")))) |
|
181 |
|
182 |
|
183 // Interpreter |
|
184 |
|
185 // Environment to store values of variables |
|
186 type Env = Map[String, Int] |
|
187 |
|
188 def eval_aexp(a: AExp, env: Env) : Int = a match { |
|
189 case Num(i) => i |
|
190 case Var(s) => env(s) |
|
191 case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env) |
|
192 case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env) |
|
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 } |
|
197 |
|
198 def eval_bexp(b: BExp, env: Env) : Boolean = b match { |
|
199 case True => true |
|
200 case False => false |
|
201 case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) |
|
202 case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env)) |
|
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 And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env) |
|
206 case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env) |
|
207 } |
|
208 |
|
209 // Import needed to take int as input from the user |
|
210 import scala.io.StdIn.readInt |
|
211 |
|
212 def eval_stmt(s: Stmt, env: Env) : Env = 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 |
|
220 case WriteId(x) => { print(env(x)) ; env } |
|
221 case WriteString(x) => { |
|
222 print(x.replaceAll("\"", "").replaceAll("""\\n""", "\n")) ; |
|
223 env |
|
224 } |
|
225 |
|
226 case Read(x) => { |
|
227 println("Enter an integer and press ENTER:") ; |
|
228 val n = readInt() ; // Note: Does not work when using the REPL |
|
229 eval_stmt(Assign(x, Num(n)), env) |
|
230 } |
|
231 } |
|
232 |
|
233 def eval_bl(bl: Block, env: Env) : Env = bl match { |
|
234 case Nil => env |
|
235 case s::bl => eval_bl(bl, eval_stmt(s, env)) |
|
236 } |
|
237 |
|
238 def eval(bl: Block) : Env = eval_bl(bl, Map()) |
|
239 |
|
240 println("Factors eval") |
|
241 println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "factors.while"))).head)) |
|
242 |
|
243 println("Primes eval") |
|
244 println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "primes.while"))).head)) |
|
245 |
|
246 |
|
247 println("Collatz2 eval") |
|
248 println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head)) |
|
249 |
|
250 println("Loops eval") |
|
251 val start = System.nanoTime() |
|
252 println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))).head)) |
|
253 val end = System.nanoTime() |
|
254 println("Time taken in seconds: ") |
|
255 println((end - start)/(1.0e9)) |
|