diff -r 908e4f6cdf7c -r 4d5058706f1b solution/cw4/compiler.sc --- a/solution/cw4/compiler.sc Fri Oct 28 09:08:13 2022 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,277 +0,0 @@ -// Compiler for JVM - -import $file.lexer -import lexer._ - -import $file.parser -import parser._ - - -val beginning = """ -.class public XXX.XXX -.super java/lang/Object - -.method public static write(I)V - .limit locals 1 - .limit stack 2 - getstatic java/lang/System/out Ljava/io/PrintStream; - iload 0 - invokevirtual java/io/PrintStream/print(I)V - return -.end method - -.method public static writes(Ljava/lang/String;)V - .limit stack 2 - .limit locals 1 - getstatic java/lang/System/out Ljava/io/PrintStream; - aload 0 - invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V - return -.end method - -.method public static read()I - .limit locals 10 - .limit stack 10 - - ldc 0 - istore 1 ; this will hold our final integer -Label1: - getstatic java/lang/System/in Ljava/io/InputStream; - invokevirtual java/io/InputStream/read()I - istore 2 - iload 2 - ldc 10 ; the newline delimiter - isub - ifeq Label2 - iload 2 - ldc 32 ; the space delimiter - isub - ifeq Label2 - - iload 2 - ldc 48 ; we have our digit in ASCII, have to subtract it from 48 - isub - ldc 10 - iload 1 - imul - iadd - istore 1 - goto Label1 -Label2: - ;when we come here we have our integer computed in local variable 1 - iload 1 - ireturn -.end method - -.method public static main([Ljava/lang/String;)V - .limit locals 200 - .limit stack 200 - -; COMPILED CODE STARTS - -""" - -val ending = """ -; COMPILED CODE ENDS - return - -.end method -""" - -// Compiler - -var counter = -1 - -def Fresh(x: String) = { - counter += 1 - x ++ "_" ++ counter.toString() -} - -implicit def string_interpolations(sc: StringContext) = new { - def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" - def l(args: Any*): String = sc.s(args:_*) ++ ":\n" -} - -type Env = Map[String, Int] - -def compile_op(op: String) = op match { - case "+" => i"iadd" - case "-" => i"isub" - case "*" => i"imul" - case "/" => i"idiv" - case "%" => i"irem" -} - -def compile_aexp(a: AExp, env : Env) : String = a match { - case Num(i) => i"ldc $i" - case Var(s) => i"iload ${env(s)} \t\t; $s" - case Aop(op, a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op) -} - -def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { - case True => "" - case False => i"goto $jmp" - case And(b1, b2) => compile_bexp(b1, env, jmp) ++ compile_bexp(b2, env, jmp) - case Or(b1, b2) => { - val b1_false = Fresh("Or_second"); - val or_end = Fresh("Or_end"); - compile_bexp(b1, env, b1_false) ++ - i"goto $or_end" ++ - l"$b1_false" ++ - compile_bexp(b2, env, jmp) ++ - l"$or_end" - } - case Bop("==", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp" - case Bop("!=", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp" - case Bop("<", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp" - case Bop(">", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmple $jmp" -} - -def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match { - case Skip => ("", env) - case Assign(x, a) => { - val index = env.getOrElse(x, env.keys.size) - (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index)) - } - case If(b, bl1, bl2) => { - val if_else = Fresh("If_else") - val if_end = Fresh("If_end") - val (instrs1, env1) = compile_block(bl1, env) - val (instrs2, env2) = compile_block(bl2, env1) - (compile_bexp(b, env, if_else) ++ - instrs1 ++ - i"goto $if_end" ++ - l"$if_else" ++ - instrs2 ++ - l"$if_end", env2) - } - case While(b, bl) => { - val loop_begin = Fresh("Loop_begin") - val loop_end = Fresh("Loop_end") - val (instrs1, env1) = compile_block(bl, env) - (l"$loop_begin" ++ - compile_bexp(b, env, loop_end) ++ - instrs1 ++ - i"goto $loop_begin" ++ - l"$loop_end", env1) - } - case For(id, lower, upper, code) => { - val (assignment_code, env1) = compile_stmt(Assign(id, lower), env) // id := lower; - val while_equivalent = While( - Or(Bop("<", Var(id), upper), Bop("==", Var(id), upper)), // while id <= upper do { - code ++ // code - List( - Assign(id, Aop("+", Var(id), Num(1))) // id := id + 1 - )) // }; - - val (while_code, env2) = compile_stmt(while_equivalent, env1) - (assignment_code ++ while_code, env2) - } - case WriteId(x) => (i"iload ${env(x)} \t\t; $x" ++ - i"invokestatic XXX/XXX/write(I)V", env) - case WriteString(x) => (s" ldc ${x}\n" ++ - i"invokestatic XXX/XXX/writes(Ljava/lang/String;)V", env) - case Read(x) => { - val index = env.getOrElse(x, env.keys.size) - (i"invokestatic XXX/XXX/read()I" ++ - i"istore $index \t\t; $x", env + (x -> index)) - } -} - -def compile_block(bl: Block, env: Env) : (String, Env) = bl match { - case Nil => ("", env) - case s::bl => { - val (instrs1, env1) = compile_stmt(s, env) - val (instrs2, env2) = compile_block(bl, env1) - (instrs1 ++ instrs2, env2) - } -} - -def compile(bl: Block, class_name: String) : String = { - val instructions = compile_block(bl, Map.empty)._1 - (beginning ++ instructions ++ ending).replaceAllLiterally("XXX", class_name) -} - -// Compiling and running - -import scala.util._ -import scala.sys.process._ -import scala.io - -def compile_tofile(bl: Block, class_name: String) = { - val output = compile(bl, class_name) - val fw = new java.io.FileWriter(class_name + ".j") - fw.write(output) - fw.close() -} - -def compile_all(bl: Block, class_name: String) : Unit = { - compile_tofile(bl, class_name) - println("compiled ") - val test = ("java -jar jasmin.jar " + class_name + ".j").!! - println("assembled ") -} - -def time_needed[T](i: Int, code: => T) = { - val start = System.nanoTime() - for (j <- 1 to i) code - val end = System.nanoTime() - (end - start)/(i * 1.0e9) -} - -def compile_run(bl: Block, class_name: String) : Unit = { - println("Start compilation") - compile_all(bl, class_name) - println("running") - println("Time: " + time_needed(1, ("java " + class_name + "/" + class_name).!)) -} - -// ---- Q1 - -// Fibonacci - -val fibonacciProgram = """write "Fib"; -read n; -minus1 := 0; -minus2 := 1; -while n > 0 do { - temp := minus2; - minus2 := minus1 + minus2; - minus1 := temp; - n := n - 1 -}; -write "Result"; -write minus2""" - -//compile_all(Stmts.parse_all(tokenise(fibonacciProgram)).head, "fib") - -val factorialProgram = """write "Factorial"; -read n; -fact := 1; - -while n > 0 do { - fact := n * fact; - n := n - 1 -}; - -write "Result"; -write fact -""" - -compile_all(Stmts.parse_all(tokenise(factorialProgram)).head, "factorial") - -// ---- Q3 - -/* compile_run(Stmts.parse_all(tokenise("""for i := 1 upto 10 do { - for i := 1 upto 10 do { - write i - } -}""")).head, "nestedloop") */ - - -compile_run(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head, "collatz2")