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 = "}" |
63 case class Num(i: Int) extends AExp |
63 case class Num(i: Int) extends AExp |
64 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
64 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
65 |
65 |
66 case object True extends BExp |
66 case object True extends BExp |
67 case object False extends BExp |
67 case object False extends BExp |
68 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
68 case class Relop(o: String, a1: AExp, a2: AExp) extends BExp |
69 |
69 |
70 // atomic parsers |
70 // atomic parsers |
71 case class TokParser(tok: Token) extends Parser[List[Token], Token] { |
71 case class TokParser(tok: Token) extends Parser[List[Token], Token] { |
72 def parse(ts: List[Token]) = ts match { |
72 def parse(ts: List[Token]) = ts match { |
73 case t::ts if (t == tok) => Set((t, ts)) |
73 case t::ts if (t == tok) => Set((t, ts)) |
105 // boolean expressions |
105 // boolean expressions |
106 lazy val BExp: Parser[List[Token], BExp] = |
106 lazy val BExp: Parser[List[Token], BExp] = |
107 (T_KWD("true") ==> ((_) => True: BExp)) || |
107 (T_KWD("true") ==> ((_) => True: BExp)) || |
108 (T_KWD("false") ==> ((_) => False: BExp)) || |
108 (T_KWD("false") ==> ((_) => False: BExp)) || |
109 (T_LPAREN ~> BExp <~ T_RPAREN) || |
109 (T_LPAREN ~> BExp <~ T_RPAREN) || |
110 (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || |
110 (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Relop("=", x, z): BExp } || |
111 (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || |
111 (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Relop("!=", x, z): BExp } || |
112 (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || |
112 (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Relop("<", x, z): BExp } || |
113 (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x): BExp } |
113 (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Relop("<", z, x): BExp } |
114 |
114 |
115 lazy val Stmt: Parser[List[Token], Stmt] = |
115 lazy val Stmt: Parser[List[Token], Stmt] = |
116 (T_KWD("skip") ==> ((_) => Skip: Stmt)) || |
116 (T_KWD("skip") ==> ((_) => Skip: Stmt)) || |
117 (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } || |
117 (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } || |
118 (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==> |
118 (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==> |
170 counter += 1 |
170 counter += 1 |
171 x ++ "_" ++ counter.toString() |
171 x ++ "_" ++ counter.toString() |
172 } |
172 } |
173 |
173 |
174 type Env = Map[String, String] |
174 type Env = Map[String, String] |
175 |
175 type Instrs = List[String] |
176 def compile_aexp(a: AExp, env : Env) : List[String] = a match { |
176 |
|
177 def compile_aexp(a: AExp, env : Env) : Instrs = a match { |
177 case Num(i) => List("ldc " + i.toString + "\n") |
178 case Num(i) => List("ldc " + i.toString + "\n") |
178 case Var(s) => List("iload " + env(s) + "\n") |
179 case Var(s) => List("iload " + env(s) + "\n") |
179 case Aop("+", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("iadd\n") |
180 case Aop("+", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("iadd\n") |
180 case Aop("-", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n") |
181 case Aop("-", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n") |
181 case Aop("*", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n") |
182 case Aop("*", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n") |
182 } |
183 } |
183 |
184 |
184 def compile_bexp(b: BExp, env : Env, jmp: String) : List[String] = b match { |
185 def compile_bexp(b: BExp, env : Env, jmp: String) : Instrs = b match { |
185 case Bop("=", a1, a2) => |
186 case True => Nil |
|
187 case False => List("goto " + jmp + "\n") |
|
188 case Relop("=", a1, a2) => |
186 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpne " + jmp + "\n") |
189 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpne " + jmp + "\n") |
187 case Bop("<", a1, a2) => |
190 case Relop("!=", a1, a2) => |
|
191 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpeq " + jmp + "\n") |
|
192 case Relop("<", a1, a2) => |
188 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpge " + jmp + "\n") |
193 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpge " + jmp + "\n") |
189 } |
194 } |
190 |
195 |
191 |
196 |
192 def compile_stmt(s: Stmt, env: Env) : (List[String], Env) = s match { |
197 def compile_stmt(s: Stmt, env: Env) : (Instrs, Env) = s match { |
193 case Skip => (Nil, env) |
198 case Skip => (Nil, env) |
194 case Assign(x, a) => { |
199 case Assign(x, a) => { |
195 val index = if (env.isDefinedAt(x)) env(x) else env.keys.size.toString |
200 val index = if (env.isDefinedAt(x)) env(x) else env.keys.size.toString |
196 (compile_aexp(a, env) ++ List("istore " + index + "\n"), env + (x -> index)) |
201 (compile_aexp(a, env) ++ |
|
202 List("istore " + index + "\n"), env + (x -> index)) |
197 } |
203 } |
198 case If(b, bl1, bl2) => { |
204 case If(b, bl1, bl2) => { |
199 val if_else = Fresh("If_else") |
205 val if_else = Fresh("If_else") |
200 val if_end = Fresh("If_end") |
206 val if_end = Fresh("If_end") |
201 val (instrs1, env1) = compile_bl(bl1, env) |
207 val (instrs1, env1) = compile_bl(bl1, env) |
216 instrs1 ++ |
222 instrs1 ++ |
217 List("goto " + loop_begin + "\n") ++ |
223 List("goto " + loop_begin + "\n") ++ |
218 List("\n" + loop_end + ":\n\n"), env1) |
224 List("\n" + loop_end + ":\n\n"), env1) |
219 } |
225 } |
220 case Write(x) => |
226 case Write(x) => |
221 (List("iload " + env(x) + "\n" + "invokestatic examples/HelloWorld/write(I)V\n"), env) |
227 (List("iload " + env(x) + "\n" + "invokestatic XXX/XXX/write(I)V\n"), env) |
222 } |
228 } |
223 |
229 |
224 def compile_bl(bl: Block, env: Env) : (List[String], Env) = bl match { |
230 def compile_bl(bl: Block, env: Env) : (Instrs, Env) = bl match { |
225 case Nil => (Nil, env) |
231 case Nil => (Nil, env) |
226 case s::bl => { |
232 case s::bl => { |
227 val (instrs1, env1) = compile_stmt(s, env) |
233 val (instrs1, env1) = compile_stmt(s, env) |
228 val (instrs2, env2) = compile_bl(bl, env1) |
234 val (instrs2, env2) = compile_bl(bl, env1) |
229 (instrs1 ++ instrs2, env2) |
235 (instrs1 ++ instrs2, env2) |
230 } |
236 } |
231 } |
237 } |
232 |
238 |
233 def compile(name: String) : String = { |
239 def compile(input: String) : String = { |
234 val tks = Tok.fromFile(name) |
240 val class_name = input.split('.')(0) |
|
241 val tks = Tok.fromFile(input) |
235 val ast = Stmts.parse_single(tks) |
242 val ast = Stmts.parse_single(tks) |
236 val instructions = compile_bl(ast, Map.empty)._1 |
243 val instructions = compile_bl(ast, Map.empty)._1 |
237 beginning ++ instructions.mkString ++ ending |
244 (beginning ++ instructions.mkString ++ ending).replaceAllLiterally("XXX", class_name) |
238 } |
245 } |
|
246 |
|
247 |
|
248 def compile_to(input: String, output: String) = { |
|
249 val fw = new java.io.FileWriter(output) |
|
250 fw.write(compile(input)) |
|
251 fw.close() |
|
252 } |
|
253 |
|
254 // |
|
255 val tks = Tok.fromString("x := x + 1") |
|
256 val ast = Stmt.parse_single(tks) |
|
257 println(compile_stmt(ast, Map("x" -> "n"))._1.mkString) |
|
258 |
239 |
259 |
240 |
260 |
241 //examples |
261 //examples |
242 |
262 |
243 println(compile("loops.while")) |
263 //compile_to("loops.while", "loops.j") |
244 //println(compile("fib.while")) |
264 //compile_to("fib.while", "fib.j") |
245 |
265 |
246 |
266 |
247 |
267 // testing cases for time measurements |
248 |
268 |
249 |
269 def time_needed[T](i: Int, code: => T) = { |
250 |
270 val start = System.nanoTime() |
251 |
271 for (j <- 1 to i) code |
252 |
272 val end = System.nanoTime() |
253 |
273 (end - start)/(i * 1.0e9) |
|
274 } |
|
275 |
|
276 // for testing |
|
277 import scala.sys.process._ |
|
278 |
|
279 val test_prog = """ |
|
280 start := XXX; |
|
281 x := start; |
|
282 y := start; |
|
283 z := start; |
|
284 while 0 < x do { |
|
285 while 0 < y do { |
|
286 while 0 < z do { |
|
287 z := z - 1 |
|
288 }; |
|
289 z := start; |
|
290 y := y - 1 |
|
291 }; |
|
292 y := start; |
|
293 x := x - 1 |
|
294 }; |
|
295 write x; |
|
296 write y; |
|
297 write z |
|
298 """ |
|
299 |
|
300 |
|
301 def compile_test(n: Int) : Unit = { |
|
302 val class_name = "LOOP" |
|
303 val tks = Tok.fromString(test_prog.replaceAllLiterally("XXX", n.toString)) |
|
304 val ast = Stmts.parse_single(tks) |
|
305 val instructions = compile_bl(ast, Map.empty)._1 |
|
306 val assembly = (beginning ++ instructions.mkString ++ ending).replaceAllLiterally("XXX", class_name) |
|
307 val fw = new java.io.FileWriter(class_name + ".j") |
|
308 fw.write(assembly) |
|
309 fw.close() |
|
310 val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!! |
|
311 println(n + " " + time_needed(2, ("java " + class_name + "/" + class_name).!!)) |
|
312 } |
|
313 |
|
314 List(1, 5000, 10000, 50000, 100000, 250000, 500000, 750000, 1000000).map(compile_test(_)) |
|
315 |
|
316 |
|
317 |
|
318 // javabyte code assmbler |
|
319 // |
|
320 // java -jar jvm/jasmin-2.4/jasmin.jar loops.j |
|
321 |
|
322 |
|
323 |
|
324 |
|
325 |
|
326 |
|
327 |