1 // A parser and evaluator for the while language |
1 // A parser and interpreter for the While language |
2 // |
2 // |
3 |
3 |
4 import scala.language.implicitConversions |
4 import scala.language.implicitConversions |
5 import scala.language.reflectiveCalls |
5 import scala.language.reflectiveCalls |
6 |
6 |
7 |
7 |
8 abstract class Parser[I <% Seq[_], T] { |
8 abstract class Parser[I, T](implicit ev: I => Seq[_]) { |
9 def parse(ts: I): Set[(T, I)] |
9 def parse(ts: I): Set[(T, I)] |
10 |
10 |
11 def parse_all(ts: I) : Set[T] = |
11 def parse_all(ts: I) : Set[T] = |
12 for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head |
12 for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head |
13 } |
13 } |
14 |
14 |
15 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { |
15 class SeqParser[I, T, S](p: => Parser[I, T], q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, (T, S)] { |
16 def parse(sb: I) = |
16 def parse(sb: I) = |
17 for ((head1, tail1) <- p.parse(sb); |
17 for ((head1, tail1) <- p.parse(sb); |
18 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
18 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
19 } |
19 } |
20 |
20 |
21 class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { |
21 class AltParser[I, T](p: => Parser[I, T], q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] { |
22 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
22 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
23 } |
23 } |
24 |
24 |
25 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { |
25 class FunParser[I, T, S](p: => Parser[I, T], f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] { |
26 def parse(sb: I) = |
26 def parse(sb: I) = |
27 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
27 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
28 } |
28 } |
29 |
29 |
30 case class StringParser(s: String) extends Parser[String, String] { |
30 case class StringParser(s: String) extends Parser[String, String] { |
46 } |
46 } |
47 |
47 |
48 |
48 |
49 implicit def string2parser(s : String) = StringParser(s) |
49 implicit def string2parser(s : String) = StringParser(s) |
50 |
50 |
51 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { |
51 implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new { |
52 def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
52 def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
53 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
53 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
54 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
54 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
55 } |
55 } |
56 |
56 |
139 Block.parse_all(fib) |
139 Block.parse_all(fib) |
140 |
140 |
141 // an interpreter for the WHILE language |
141 // an interpreter for the WHILE language |
142 type Env = Map[String, Int] |
142 type Env = Map[String, Int] |
143 |
143 |
144 def eval_aexp(a: AExp, env : Env) : Int = a match { |
144 def eval_aexp(a: AExp, env: Env) : Int = a match { |
145 case Num(i) => i |
145 case Num(i) => i |
146 case Var(s) => env(s) |
146 case Var(s) => env(s) |
147 case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env) |
147 case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env) |
148 case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env) |
148 case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env) |
149 case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env) |
149 case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env) |