108 IdParser ==> Var || |
108 IdParser ==> Var || |
109 NumParser ==> Num |
109 NumParser ==> Num |
110 |
110 |
111 // boolean expressions with some simple nesting |
111 // boolean expressions with some simple nesting |
112 lazy val BExp: Parser[String, BExp] = |
112 lazy val BExp: Parser[String, BExp] = |
113 (AExp ~ "==" ~ AExp) ==> { case ((x, y), z) => Bop("==", x, z) }: Bexp || |
113 (AExp ~ "==" ~ AExp) ==> { case ((x, y), z) => Bop("==", x, z): BExp } || |
114 (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || |
114 (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || |
115 (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 } || |
116 (AExp ~ ">" ~ AExp) ==> { case ((x, y), z) => Bop(">", x, z): BExp } || |
117 ("(" ~ BExp ~ ")" ~ "&&" ~ BExp) ==> { case ((((x, y), z), u), v) => And(y, v): 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 } || |
118 ("(" ~ BExp ~ ")" ~ "||" ~ BExp) ==> { case ((((x, y), z), u), v) => Or(y, v): BExp } || |
119 ("true" ==> ((_) => True: BExp )) || |
119 ("true" ==> ((_) => True: BExp )) || |
120 ("false" ==> ((_) => False: BExp )) || |
120 ("false" ==> ((_) => False: BExp )) || |
121 ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y} |
121 ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y} |
122 |
122 |
123 // statements |
123 // statement / statements |
124 lazy val Stmt: Parser[String, Stmt] = |
124 lazy val Stmt: Parser[String, Stmt] = |
125 (("skip" ==> ((_) => Skip: Stmt)) || |
125 (("skip" ==> ((_) => Skip: Stmt)) || |
126 (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } || |
126 (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } || |
127 ("write(" ~ IdParser ~ ")") ==> { case ((x, y), z) => Write(y): Stmt } || |
127 ("write(" ~ IdParser ~ ")") ==> { case ((x, y), z) => Write(y): Stmt } || |
128 ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==> |
128 ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==> |
131 |
131 |
132 lazy val Stmts: Parser[String, Block] = |
132 lazy val Stmts: Parser[String, Block] = |
133 (Stmt ~ ";" ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } || |
133 (Stmt ~ ";" ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } || |
134 (Stmt ==> ((s) => List(s) : Block)) |
134 (Stmt ==> ((s) => List(s) : Block)) |
135 |
135 |
|
136 // blocks (enclosed in curly braces) |
136 lazy val Block: Parser[String, Block] = |
137 lazy val Block: Parser[String, Block] = |
137 (("{" ~ Stmts ~ "}") ==> { case ((x, y), z) => y} || |
138 (("{" ~ Stmts ~ "}") ==> { case ((x, y), z) => y} || |
138 (Stmt ==> ((s) => List(s)))) |
139 (Stmt ==> ((s) => List(s)))) |
139 |
140 |
140 |
141 |
141 Stmts.parse_all("x2:=5+3;") |
142 Stmts.parse_all("x2:=5+3;") |
142 Block.parse_all("{x:=5;y:=8}") |
143 Block.parse_all("{x:=5;y:=8}") |
143 Block.parse_all("if(false)then{x:=5}else{x:=10}") |
144 Block.parse_all("if(false)then{x:=5}else{x:=10}") |
144 |
145 |
145 val fib = """{n := 10; |
146 val fib = """n := 10; |
146 minus1 := 0; |
147 minus1 := 0; |
147 minus2 := 1; |
148 minus2 := 1; |
148 temp := 0; |
149 temp := 0; |
149 while (n > 0) do { |
150 while (n > 0) do { |
150 temp := minus2; |
151 temp := minus2; |
151 minus2 := minus1 + minus2; |
152 minus2 := minus1 + minus2; |
152 minus1 := temp; |
153 minus1 := temp; |
153 n := n - 1 |
154 n := n - 1 |
154 }; |
155 }; |
155 result := minus2}""".replaceAll("\\s+", "") |
156 result := minus2""".replaceAll("\\s+", "") |
156 |
157 |
157 Block.parse_all(fib) |
158 Stmts.parse_all(fib) |
|
159 |
158 |
160 |
159 // an interpreter for the WHILE language |
161 // an interpreter for the WHILE language |
160 type Env = Map[String, Int] |
162 type Env = Map[String, Int] |
161 |
163 |
162 def eval_aexp(a: AExp, env: Env) : Int = a match { |
164 def eval_aexp(a: AExp, env: Env) : Int = a match { |
196 |
198 |
197 def eval(bl: Block) : Env = eval_bl(bl, Map()) |
199 def eval(bl: Block) : Env = eval_bl(bl, Map()) |
198 |
200 |
199 // parse + evaluate fib program; then lookup what is |
201 // parse + evaluate fib program; then lookup what is |
200 // stored under the variable result |
202 // stored under the variable result |
201 println(eval(Block.parse_all(fib).head)("result")) |
203 println(eval(Stmts.parse_all(fib).head)("result")) |
202 |
204 |
203 |
205 |
204 // more examles |
206 // more examles |
205 |
207 |
206 // calculate and print all factors bigger |
208 // calculate and print all factors bigger |
207 // than 1 and smaller than n |
209 // than 1 and smaller than n |
208 println("Factors") |
210 println("Factors") |
209 |
211 |
210 val factors = |
212 val factors = |
211 """{n := 12; |
213 """n := 12; |
212 f := 2; |
214 f := 2; |
213 while (f < n / 2 + 1) do { |
215 while (f < n / 2 + 1) do { |
214 if ((n / f) * f == n) then { write(f) } else { skip }; |
216 if ((n / f) * f == n) then { write(f) } else { skip }; |
215 f := f + 1 |
217 f := f + 1 |
216 }}""".replaceAll("\\s+", "") |
218 }""".replaceAll("\\s+", "") |
217 |
219 |
218 eval(Block.parse_all(factors).head) |
220 eval(Stmts.parse_all(factors).head) |
219 |
221 |
220 // calculate all prime numbers up to a number |
222 // calculate all prime numbers up to a number |
221 println("Primes") |
223 println("Primes") |
222 |
224 |
223 val primes = |
225 val primes = |
224 """{end := 100; |
226 """end := 100; |
225 n := 2; |
227 n := 2; |
226 while (n < end) do { |
228 while (n < end) do { |
227 f := 2; |
229 f := 2; |
228 tmp := 0; |
230 tmp := 0; |
229 while ((f < n / 2 + 1) && (tmp == 0)) do { |
231 while ((f < n / 2 + 1) && (tmp == 0)) do { |
230 if ((n / f) * f == n) then { tmp := 1 } else { skip }; |
232 if ((n / f) * f == n) then { tmp := 1 } else { skip }; |
231 f := f + 1 |
233 f := f + 1 |
232 }; |
234 }; |
233 if (tmp == 0) then { write(n) } else { skip }; |
235 if (tmp == 0) then { write(n) } else { skip }; |
234 n := n + 1 |
236 n := n + 1 |
235 }}""".replaceAll("\\s+", "") |
237 }""".replaceAll("\\s+", "") |
236 |
238 |
237 eval(Block.parse_all(primes).head) |
239 eval(Stmts.parse_all(primes).head) |