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