1 |
1 // A parser and evaluator for teh while language |
|
2 // |
2 //:load matcher.scala |
3 //:load matcher.scala |
3 //:load parser3.scala |
4 //:load parser3.scala |
4 |
5 |
5 // some regular expressions |
6 // some regular expressions |
6 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") |
7 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") |
7 val DIGIT = RANGE("0123456789") |
8 val DIGIT = RANGE("0123456789") |
8 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) |
9 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) |
9 val NUM = PLUS(DIGIT) |
10 val NUM = PLUS(DIGIT) |
10 val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false") |
11 val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false") |
11 val SEMI: Rexp = ";" |
12 val SEMI: Rexp = ";" |
12 val OP: Rexp = ALTS(":=", "=", "+", "-", "*") |
13 val OP: Rexp = ALTS(":=", "=", "+", "-", "*", "!=", "<", ">") |
13 val WHITESPACE = PLUS(RANGE(" \n")) |
14 val WHITESPACE = PLUS(RANGE(" \n")) |
14 val RPAREN: Rexp = ")" |
15 val RPAREN: Rexp = ")" |
15 val LPAREN: Rexp = "(" |
16 val LPAREN: Rexp = "(" |
16 val BEGIN: Rexp = "{" |
17 val BEGIN: Rexp = "{" |
17 val END: Rexp = "}" |
18 val END: Rexp = "}" |
84 case _ => Set () |
85 case _ => Set () |
85 } |
86 } |
86 } |
87 } |
87 |
88 |
88 |
89 |
|
90 // arithmetic expressions |
89 lazy val AExp: Parser[List[Token], AExp] = |
91 lazy val AExp: Parser[List[Token], AExp] = |
90 (T ~ T_OP("+") ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } || |
92 (T ~ T_OP("+") ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } || |
91 (T ~ T_OP("-") ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || T |
93 (T ~ T_OP("-") ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || T |
92 lazy val T: Parser[List[Token], AExp] = |
94 lazy val T: Parser[List[Token], AExp] = |
93 (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || F |
95 (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || F |
94 lazy val F: Parser[List[Token], AExp] = |
96 lazy val F: Parser[List[Token], AExp] = |
95 (T_LPAREN ~> AExp <~ T_RPAREN) || |
97 (T_LPAREN ~> AExp <~ T_RPAREN) || |
96 IdParser ==> Var || |
98 IdParser ==> Var || |
97 NumParser ==> Num |
99 NumParser ==> Num |
98 |
100 |
|
101 // boolean expressions |
99 lazy val BExp: Parser[List[Token], BExp] = |
102 lazy val BExp: Parser[List[Token], BExp] = |
100 (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || |
103 (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || |
|
104 (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || |
|
105 (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || |
|
106 (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop(">", x, z): BExp } || |
101 (T_KWD("true") ==> ((_) => True)) || |
107 (T_KWD("true") ==> ((_) => True)) || |
102 (T_KWD("false") ==> ((_) => False: BExp)) |
108 (T_KWD("false") ==> ((_) => False: BExp)) |
103 |
109 |
104 lazy val Stmt: Parser[List[Token], Stmt] = |
110 lazy val Stmt: Parser[List[Token], Stmt] = |
105 (T_KWD("skip") ==> ((_) => Skip: Stmt)) || |
111 (T_KWD("skip") ==> ((_) => Skip: Stmt)) || |
152 val p3b = "if false then x := 5 else x := 10" |
158 val p3b = "if false then x := 5 else x := 10" |
153 val p3b_toks = Tok.fromString(p3b) |
159 val p3b_toks = Tok.fromString(p3b) |
154 val p3b_ast = Stmt.parse_all(p3b_toks) |
160 val p3b_ast = Stmt.parse_all(p3b_toks) |
155 println(p3b_ast) |
161 println(p3b_ast) |
156 |
162 |
|
163 // multiplication |
157 val p4 = """{ x := 5; |
164 val p4 = """{ x := 5; |
158 y := 3; |
165 y := 4; |
159 r := 0; |
166 r := 0; |
160 while y = 0 do { |
167 while y > 0 do { |
161 r := r + x; |
168 r := r + x; |
162 y := y - 1 |
169 y := y - 1 |
163 } |
170 } |
164 }""" |
171 }""" |
165 val p4_toks = Tok.fromString(p4) |
172 val p4_toks = Tok.fromString(p4) |
166 val p4_ast = Block.parse_all(p4_toks) |
173 val p4_ast = Block.parse_all(p4_toks) |
167 println(p4_ast) |
174 println(p4_ast) |
168 |
175 |
|
176 // fibonacci numbers |
|
177 val p5 = |
|
178 """{ n := 9; |
|
179 minus1 := 0; |
|
180 minus2 := 1; |
|
181 temp := 0; |
|
182 while n > 0 do { |
|
183 temp := minus2; |
|
184 minus2 := minus1 + minus2; |
|
185 minus1 := temp; |
|
186 n := n - 1 |
|
187 }; |
|
188 fib_res := minus2 |
|
189 } |
|
190 """ |
|
191 val p5_toks = Tok.fromString(p5) |
|
192 val p5_ast = Block.parse_all(p5_toks) |
169 |
193 |
170 // interpreter |
194 // interpreter |
171 type Env = Map[String, Int] |
195 type Env = Map[String, Int] |
172 |
196 |
173 def eval_bexp(b: BExp, env: Env) : Boolean = b match { |
197 def eval_bexp(b: BExp, env: Env) : Boolean = b match { |
174 case True => true |
198 case True => true |
175 case False => false |
199 case False => false |
176 case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) |
200 case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) |
|
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) |
177 } |
204 } |
178 |
205 |
179 def eval_aexp(a: AExp, env : Env) : Int = a match { |
206 def eval_aexp(a: AExp, env : Env) : Int = a match { |
180 case Num(i) => i |
207 case Num(i) => i |
181 case Var(s) => env(s) |
208 case Var(s) => env(s) |
186 |
213 |
187 def eval_stmt(s: Stmt, env: Env) : Env = s match { |
214 def eval_stmt(s: Stmt, env: Env) : Env = s match { |
188 case Skip => env |
215 case Skip => env |
189 case Assign(x, a) => env + (x -> eval_aexp(a, env)) |
216 case Assign(x, a) => env + (x -> eval_aexp(a, env)) |
190 case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) |
217 case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) |
|
218 case While(b, bl) => |
|
219 if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env)) |
|
220 else env |
191 } |
221 } |
192 |
222 |
193 def eval_bl(bl: Block, env: Env) : Env = bl match { |
223 def eval_bl(bl: Block, env: Env) : Env = bl match { |
194 case Nil => env |
224 case Nil => env |
195 case s::bl => eval_bl(bl, eval_stmt(s, env)) |
225 case s::bl => eval_bl(bl, eval_stmt(s, env)) |
196 } |
226 } |
197 |
227 |
198 //println(eval_stmt(p3a_ast.head, Nil.toMap)) |
228 //examples |
199 //println(eval_stmt(p3b_ast.head, Nil.toMap)) |
229 println(eval_stmt(p3a_ast.head, Map.empty)) |
|
230 println(eval_stmt(p3b_ast.head, Map.empty)) |
|
231 println(eval_bl(p4_ast.head, Map.empty)) |
|
232 println(eval_bl(p5_ast.head, Map.empty)) |