8 val DIGIT = RANGE("0123456789") |
8 val DIGIT = RANGE("0123456789") |
9 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) |
9 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) |
10 val NUM = PLUS(DIGIT) |
10 val NUM = PLUS(DIGIT) |
11 val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") |
11 val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") |
12 val SEMI: Rexp = ";" |
12 val SEMI: Rexp = ";" |
13 val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!", "<", ">") |
13 val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!=", "<", ">") |
14 val WHITESPACE = PLUS(RANGE(" \n")) |
14 val WHITESPACE = PLUS(RANGE(" \n")) |
15 val RPAREN: Rexp = ")" |
15 val RPAREN: Rexp = ")" |
16 val LPAREN: Rexp = "(" |
16 val LPAREN: Rexp = "(" |
17 val BEGIN: Rexp = "{" |
17 val BEGIN: Rexp = "{" |
18 val END: Rexp = "}" |
18 val END: Rexp = "}" |
135 case True => true |
135 case True => true |
136 case False => false |
136 case False => false |
137 case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) |
137 case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) |
138 case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env)) |
138 case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env)) |
139 case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) |
139 case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) |
140 case Bop("&&", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env) |
|
141 case Bop("||", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) |
|
142 } |
140 } |
143 |
141 |
144 def eval_aexp(a: AExp, env : Env) : Int = a match { |
142 def eval_aexp(a: AExp, env : Env) : Int = a match { |
145 case Num(i) => i |
143 case Num(i) => i |
146 case Var(s) => env(s) |
144 case Var(s) => env(s) |
171 } |
169 } |
172 |
170 |
173 |
171 |
174 //examples |
172 //examples |
175 |
173 |
176 eval_prog("loops.while") |
174 //eval_prog("loops.while") |
177 //eval_prog("fib.while") |
175 //eval_prog("fib.while") |
178 |
176 |
179 |
177 |
180 |
178 def time_needed[T](i: Int, code: => T) = { |
181 |
179 val start = System.nanoTime() |
182 |
180 for (j <- 1 to i) code |
183 |
181 val end = System.nanoTime() |
184 |
182 (end - start)/(i * 1.0e9) |
185 |
183 } |
186 |
184 |
|
185 |
|
186 val test_prog = """ |
|
187 start := XXX; |
|
188 x := start; |
|
189 y := start; |
|
190 z := start; |
|
191 while 0 < x do { |
|
192 while 0 < y do { |
|
193 while 0 < z do { |
|
194 z := z - 1 |
|
195 }; |
|
196 z := start; |
|
197 y := y - 1 |
|
198 }; |
|
199 y := start; |
|
200 x := x - 1 |
|
201 } |
|
202 """ |
|
203 |
|
204 |
|
205 |
|
206 def eval_test(n: Int) : Unit = { |
|
207 val tks = Tok.fromString(test_prog.replaceAllLiterally("XXX", n.toString)) |
|
208 val ast = Stmts.parse_single(tks) |
|
209 println(n + " " + time_needed(2, eval_bl(ast, Map.empty))) |
|
210 } |
|
211 |
|
212 List(1, 200, 400, 600, 800, 1000, 1200, 1400, 1600).map(eval_test(_)) |
|
213 |
|
214 |
|
215 |
|
216 |
|
217 |
|
218 |
|
219 |