1 // A parser and interpreter for the While language |
|
2 // |
|
3 |
|
4 import scala.language.implicitConversions |
|
5 import scala.language.reflectiveCalls |
|
6 import scala.collection.immutable._ |
|
7 |
|
8 // more convenience for the semantic actions later on |
|
9 case class ~[+A, +B](_1: A, _2: B) |
|
10 |
|
11 |
|
12 type IsSeq[A] = A => Seq[_] |
|
13 |
|
14 abstract class Parser[I : IsSeq, T] { |
|
15 def parse(ts: I): Set[(T, I)] |
|
16 |
|
17 def parse_all(ts: I) : Set[T] = |
|
18 for ((head, tail) <- parse(ts); if tail.isEmpty) yield head |
|
19 } |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, ~[T, S]] { |
|
25 def parse(sb: I) = |
|
26 for ((head1, tail1) <- p.parse(sb); |
|
27 (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2) |
|
28 } |
|
29 |
|
30 class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { |
|
31 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
|
32 } |
|
33 |
|
34 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { |
|
35 def parse(sb: I) = |
|
36 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
|
37 } |
|
38 |
|
39 case class StrParser(s: String) extends Parser[String, String] { |
|
40 def parse(sb: String) = { |
|
41 val (prefix, suffix) = sb.splitAt(s.length) |
|
42 if (prefix == s) Set((prefix, suffix)) else Set() |
|
43 } |
|
44 } |
|
45 |
|
46 case object NumParser extends Parser[String, Int] { |
|
47 val reg = "[0-9]+".r |
|
48 def parse(sb: String) = reg.findPrefixOf(sb) match { |
|
49 case None => Set() |
|
50 case Some(s) => { |
|
51 val (head, tail) = sb.splitAt(s.length) |
|
52 Set((head.toInt, tail)) |
|
53 } |
|
54 } |
|
55 } |
|
56 |
|
57 |
|
58 implicit def parser_interpolation(sc: StringContext) = new { |
|
59 def p(args: Any*) = StrParser(sc.s(args:_*)) |
|
60 } |
|
61 |
|
62 // this string interpolation allows us to write |
|
63 // things like the following for a StrParser |
|
64 // |
|
65 // p"<_some_string_>" |
|
66 // |
|
67 // instead of StrParser(<_some_string_>) |
|
68 |
|
69 |
|
70 implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new { |
|
71 def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) |
|
72 def ~[S](q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
|
73 def map[S](f: => T => S) = new MapParser[I, T, S](p, f) |
|
74 } |
|
75 |
|
76 // these implicits allow us to use infic notation for |
|
77 // sequences and alternatives; we also can write map |
|
78 // for a parser |
|
79 |
|
80 |
|
81 // the abstract syntax trees for the WHILE language |
|
82 abstract class Stmt |
|
83 abstract class AExp |
|
84 abstract class BExp |
|
85 |
|
86 type Block = List[Stmt] |
|
87 |
|
88 case object Skip extends Stmt |
|
89 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
|
90 case class While(b: BExp, bl: Block) extends Stmt |
|
91 case class Assign(s: String, a: AExp) extends Stmt |
|
92 case class Write(s: String) extends Stmt |
|
93 |
|
94 |
|
95 case class Var(s: String) extends AExp |
|
96 case class Num(i: Int) extends AExp |
|
97 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
|
98 |
|
99 case object True extends BExp |
|
100 case object False extends BExp |
|
101 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
|
102 case class And(b1: BExp, b2: BExp) extends BExp |
|
103 case class Or(b1: BExp, b2: BExp) extends BExp |
|
104 |
|
105 case object IdParser extends Parser[String, String] { |
|
106 val reg = "[a-z][a-z,0-9]*".r |
|
107 def parse(sb: String) = reg.findPrefixOf(sb) match { |
|
108 case None => Set() |
|
109 case Some(s) => Set(sb.splitAt(s.length)) |
|
110 } |
|
111 } |
|
112 |
|
113 // arithmetic expressions |
|
114 lazy val AExp: Parser[String, AExp] = |
|
115 (Te ~ p"+" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } || |
|
116 (Te ~ p"-" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te |
|
117 lazy val Te: Parser[String, AExp] = |
|
118 (Fa ~ p"*" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } || |
|
119 (Fa ~ p"/" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa |
|
120 lazy val Fa: Parser[String, AExp] = |
|
121 (p"(" ~ AExp ~ p")").map{ case _ ~ y ~ _ => y } || |
|
122 IdParser.map(Var) || |
|
123 NumParser.map(Num) |
|
124 |
|
125 // boolean expressions with some simple nesting |
|
126 lazy val BExp: Parser[String, BExp] = |
|
127 (AExp ~ p"==" ~ AExp).map { case x ~ _ ~ z => Bop("==", x, z): BExp } || |
|
128 (AExp ~ p"!=" ~ AExp).map { case x ~ _ ~ z => Bop("!=", x, z): BExp } || |
|
129 (AExp ~ p"<" ~ AExp).map { case x ~ _ ~ z => Bop("<", x, z): BExp } || |
|
130 (AExp ~ p">" ~ AExp).map { case x ~ _ ~ z => Bop(">", x, z): BExp } || |
|
131 (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).map { case _ ~ y ~ _ ~ _ ~ v => And(y, v): BExp } || |
|
132 (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).map { case _ ~ y ~ _ ~ _ ~ v => Or(y, v): BExp } || |
|
133 (p"true".map { _ => True: BExp }) || |
|
134 (p"false".map { _ => False: BExp }) || |
|
135 (p"(" ~ BExp ~ p")").map { case _ ~ x ~ _ => x } |
|
136 |
|
137 // statement / statements |
|
138 lazy val Stmt: Parser[String, Stmt] = |
|
139 ((p"skip".map {_ => Skip: Stmt}) || |
|
140 (IdParser ~ p":=" ~ AExp).map { case x ~ _ ~ z => Assign(x, z): Stmt } || |
|
141 (p"write(" ~ IdParser ~ p")").map { case _ ~ y ~ _ => Write(y): Stmt } || |
|
142 (p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block) |
|
143 .map{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w): Stmt } || |
|
144 (p"while" ~ BExp ~ p"do" ~ Block).map { case _ ~ y ~ _ ~ w => While(y, w) }) |
|
145 |
|
146 lazy val Stmts: Parser[String, Block] = |
|
147 (Stmt ~ p";" ~ Stmts).map { case x ~ _ ~ z => x :: z : Block } || |
|
148 (Stmt.map { s => List(s) : Block}) |
|
149 |
|
150 // blocks (enclosed in curly braces) |
|
151 lazy val Block: Parser[String, Block] = |
|
152 ((p"{" ~ Stmts ~ p"}").map{ case _ ~ y ~ _ => y } || |
|
153 (Stmt.map(s => List(s)))) |
|
154 |
|
155 |
|
156 Stmts.parse_all("x2:=5+3;") |
|
157 Block.parse_all("{x:=5;y:=8}") |
|
158 Block.parse_all("if(false)then{x:=5}else{x:=10}") |
|
159 |
|
160 val fib = """n := 10; |
|
161 minus1 := 0; |
|
162 minus2 := 1; |
|
163 temp := 0; |
|
164 while (n > 0) do { |
|
165 temp := minus2; |
|
166 minus2 := minus1 + minus2; |
|
167 minus1 := temp; |
|
168 n := n - 1 |
|
169 }; |
|
170 result := minus2""".replaceAll("\\s+", "") |
|
171 |
|
172 Stmts.parse_all(fib) |
|
173 |
|
174 |
|
175 // an interpreter for the WHILE language |
|
176 type Env = Map[String, Int] |
|
177 |
|
178 def eval_aexp(a: AExp, env: Env) : Int = a match { |
|
179 case Num(i) => i |
|
180 case Var(s) => env(s) |
|
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 case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env) |
|
184 case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env) |
|
185 } |
|
186 |
|
187 def eval_bexp(b: BExp, env: Env) : Boolean = b match { |
|
188 case True => true |
|
189 case False => false |
|
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 Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env) |
|
193 case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) |
|
194 case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env) |
|
195 case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env) |
|
196 } |
|
197 |
|
198 def eval_stmt(s: Stmt, env: Env) : Env = s match { |
|
199 case Skip => env |
|
200 case Assign(x, a) => env + (x -> eval_aexp(a, env)) |
|
201 case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) |
|
202 case While(b, bl) => |
|
203 if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env)) |
|
204 else env |
|
205 case Write(x) => { println(env(x)) ; env } |
|
206 } |
|
207 |
|
208 def eval_bl(bl: Block, env: Env) : Env = bl match { |
|
209 case Nil => env |
|
210 case s::bl => eval_bl(bl, eval_stmt(s, env)) |
|
211 } |
|
212 |
|
213 def eval(bl: Block) : Env = eval_bl(bl, Map()) |
|
214 |
|
215 // parse + evaluate fib program; then lookup what is |
|
216 // stored under the variable result |
|
217 println(eval(Stmts.parse_all(fib).head)("result")) |
|
218 |
|
219 |
|
220 // more examles |
|
221 |
|
222 // calculate and print all factors bigger |
|
223 // than 1 and smaller than n |
|
224 println("Factors") |
|
225 |
|
226 val factors = |
|
227 """n := 12; |
|
228 f := 2; |
|
229 while (f < n / 2 + 1) do { |
|
230 if ((n / f) * f == n) then { write(f) } else { skip }; |
|
231 f := f + 1 |
|
232 }""".replaceAll("\\s+", "") |
|
233 |
|
234 eval(Stmts.parse_all(factors).head) |
|
235 |
|
236 // calculate all prime numbers up to a number |
|
237 println("Primes") |
|
238 |
|
239 val primes = |
|
240 """end := 100; |
|
241 n := 2; |
|
242 while (n < end) do { |
|
243 f := 2; |
|
244 tmp := 0; |
|
245 while ((f < n / 2 + 1) && (tmp == 0)) do { |
|
246 if ((n / f) * f == n) then { tmp := 1 } else { skip }; |
|
247 f := f + 1 |
|
248 }; |
|
249 if (tmp == 0) then { write(n) } else { skip }; |
|
250 n := n + 1 |
|
251 }""".replaceAll("\\s+", "") |
|
252 |
|
253 eval(Stmts.parse_all(primes).head) |
|