1 // Compiler for JVM

     2 // 

     3 // call with 

     4 //

     5 //     amm2 compiler.sc 

     6 //

     7 

     8 import $file.lexer

     9 import lexer._

    10 

    11 import $file.parser

    12 import parser._

    13 

    14 

    15 val beginning = """

    16 .class public XXX.XXX

    17 .super java/lang/Object

    18 

    19 .method public static write(I)V 

    20     .limit locals 1 

    21     .limit stack 2 

    22     getstatic java/lang/System/out Ljava/io/PrintStream; 

    23     iload 0

    24     invokevirtual java/io/PrintStream/print(I)V 

    25     return 

    26 .end method

    27 

    28 .method public static writes(Ljava/lang/String;)V

    29     .limit stack 2

    30     .limit locals 1

    31     getstatic java/lang/System/out Ljava/io/PrintStream;

    32     aload 0

    33     invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V

    34     return

    35 .end method

    36 

    37 .method public static read()I 

    38     .limit locals 10 

    39     .limit stack 10

    40 

    41     ldc 0 

    42     istore 1  ; this will hold our final integer 

    43 Label1: 

    44     getstatic java/lang/System/in Ljava/io/InputStream; 

    45     invokevirtual java/io/InputStream/read()I 

    46     istore 2 

    47     iload 2 

    48     ldc 10   ; the newline delimiter 

    49     isub 

    50     ifeq Label2 

    51     iload 2 

    52     ldc 32   ; the space delimiter 

    53     isub 

    54     ifeq Label2

    55 

    56     iload 2 

    57     ldc 48   ; we have our digit in ASCII, have to subtract it from 48 

    58     isub 

    59     ldc 10 

    60     iload 1 

    61     imul 

    62     iadd 

    63     istore 1 

    64     goto Label1 

    65 Label2: 

    66     ;when we come here we have our integer computed in local variable 1 

    67     iload 1 

    68     ireturn 

    69 .end method

    70 

    71 .method public static main([Ljava/lang/String;)V

    72    .limit locals 200

    73    .limit stack 200

    74 

    75 ; COMPILED CODE STARTS

    76 

    77 """

    78 

    79 val ending = """

    80 ; COMPILED CODE ENDS

    81    return

    82 

    83 .end method

    84 """

    85 

    86 // Compiler

    87 

    88 var counter = -1

    89 

    90 def Fresh(x: String) = {

    91   counter += 1

    92   x ++ "_" ++ counter.toString()

    93 }

    94 

    95 implicit def string_interpolations(sc: StringContext) = new {

    96     def i(args: Any*): String = "   " ++ sc.s(args:_*) ++ "\n"

    97     def l(args: Any*): String = sc.s(args:_*) ++ ":\n"

    98 }

    99 

   100 type Env = Map[String, Int]

   101 

   102 def compile_op(op: String) = op match {

   103   case "+" => i"iadd"

   104   case "-" => i"isub"

   105   case "*" => i"imul"

   106   case "/" => i"idiv"

   107   case "%" => i"irem"

   108 }

   109 

   110 def compile_aexp(a: AExp, env : Env) : String = a match {

   111   case Num(i) => i"ldc $i"

   112   case Var(s) => i"iload ${env(s)} \t\t; $s"

   113   case Aop(op, a1, a2) => 

   114     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op)

   115 }

   116 

   117 def compile_bop(op: String) = op match {

   118   case "==" => "if_icmpne"

   119   case "!=" => "if_icmpeq"

   120   case "<" => "if_icmpge"

   121   case ">" => "if_icmple"

   122 }

   123 

   124 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {

   125   case True => ""

   126   case False => i"goto $jmp"

   127   case And(b1, b2) => compile_bexp(b1, env, jmp) ++ compile_bexp(b2, env, jmp)

   128   case Or(b1, b2) => {

   129     val b1_false = Fresh("Or_second");

   130     val or_end = Fresh("Or_end");

   131     compile_bexp(b1, env, b1_false) ++

   132     i"goto $or_end" ++

   133     l"$b1_false" ++

   134     compile_bexp(b2, env, jmp) ++

   135     l"$or_end"

   136   }

   137   case Bop(op, a1, a2) => 

   138     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"${compile_bop(op)} $jmp"

   139 }

   140 

   141 def compile_stmt(s: Stmt, env: Env, jmp: String) : (String, Env) = s match {

   142   case Skip => ("", env)

   143   case Break => (i"goto $jmp", env)

   144   case Assign(x, a) => {

   145     val index = env.getOrElse(x, env.keys.size)

   146     (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index))

   147   } 

   148   case If(b, bl1, bl2) => {

   149     val if_else = Fresh("If_else")

   150     val if_end = Fresh("If_end")

   151     val (instrs1, env1) = compile_block(bl1, env, jmp)

   152     val (instrs2, env2) = compile_block(bl2, env1, jmp)

   153     (compile_bexp(b, env, if_else) ++

   154      instrs1 ++

   155      i"goto $if_end" ++

   156      l"$if_else" ++

   157      instrs2 ++

   158      l"$if_end", env2)

   159   }

   160   case While(b, bl) => {

   161     val loop_begin = Fresh("Loop_begin")

   162     val loop_end = Fresh("Loop_end")

   163     val (instrs1, env1) = compile_block(bl, env, loop_end)

   164     (l"$loop_begin" ++

   165      compile_bexp(b, env, loop_end) ++

   166      instrs1 ++

   167      i"goto $loop_begin" ++

   168      l"$loop_end", env1)

   169   }

   170   case For(id, lower, upper, code) => {

   171       val (assignment_code, env1) = compile_stmt(Assign(id, lower), env, jmp)  // id := lower;

   172       val while_equivalent = While(

   173           Or(Bop("<", Var(id), upper), Bop("==", Var(id), upper)),    // while id <= upper do {

   174           code ++                                                     //    code  

   175           List(

   176             Assign(id, Aop("+", Var(id), Num(1)))                     //    id := id + 1

   177           ))                                                          // };

   178 

   179       val (while_code, env2) = compile_stmt(while_equivalent, env1, jmp)

   180       (assignment_code ++ while_code, env2)

   181   }

   182   case WriteId(x) => (i"iload ${env(x)} \t\t; $x" ++ 

   183      i"invokestatic XXX/XXX/write(I)V", env)

   184   case WriteString(x) => (s"   ldc ${x}\n" ++

   185      i"invokestatic XXX/XXX/writes(Ljava/lang/String;)V", env)

   186   case Read(x) => {

   187     val index = env.getOrElse(x, env.keys.size) 

   188     (i"invokestatic XXX/XXX/read()I" ++ 

   189      i"istore $index \t\t; $x", env + (x -> index))

   190   }

   191 }

   192 

   193 def compile_block(bl: Block, env: Env, jmp: String) : (String, Env) = bl match {

   194   case Nil => ("", env)

   195   case s::bl => {

   196     val (instrs1, env1) = compile_stmt(s, env, jmp)

   197     val (instrs2, env2) = compile_block(bl, env1, jmp)

   198     (instrs1 ++ instrs2, env2)

   199   }

   200 }

   201 

   202 def compile(bl: Block, class_name: String) : String = {

   203   val instructions = compile_block(bl, Map.empty, "")._1

   204   (beginning ++ instructions ++ ending).replaceAllLiterally("XXX", class_name)

   205 }

   206 

   207 // Compiling and running

   208 

   209 import scala.util._

   210 import scala.sys.process._

   211 import scala.io

   212 

   213 def compile_tofile(bl: Block, class_name: String) = {

   214   val output = compile(bl, class_name)

   215   val fw = new java.io.FileWriter(class_name + ".j") 

   216   fw.write(output) 

   217   fw.close()

   218 }

   219 

   220 def compile_all(bl: Block, class_name: String) : Unit = {

   221   compile_tofile(bl, class_name)

   222   println("compiled ")

   223   val test = ("java -jar jasmin.jar " + class_name + ".j").!!

   224   println("assembled ")

   225 }

   226 

   227 def time_needed[T](i: Int, code: => T) = {

   228   val start = System.nanoTime()

   229   for (j <- 1 to i) code

   230   val end = System.nanoTime()

   231   (end - start)/(i * 1.0e9)

   232 }

   233 

   234 def compile_run(bl: Block, class_name: String) : Unit = {

   235   println("Start compilation")

   236   compile_all(bl, class_name)

   237   println("running")

   238   println("Time: " + time_needed(1, ("java " + class_name + "/" + class_name).!))

   239 }

   240 

   241 // ---- Q1

   242 

   243 // Fibonacci

   244 

   245 val fibonacciProgram = """write "Fib";

   246 read n;

   247 minus1 := 0;

   248 minus2 := 1;

   249 while n > 0 do {

   250   temp := minus2;

   251   minus2 := minus1 + minus2;

   252   minus1 := temp;

   253   n := n - 1

   254 };

   255 write "Result";

   256 write minus2"""

   257 

   258 compile_all(Stmts.parse_all(tokenise(fibonacciProgram)).head, "fib")

   259 

   260 val factorialProgram = """write "Factorial";

   261 read n;

   262 fact := 1;

   263 

   264 while n > 0 do {

   265   fact := n * fact;

   266   n := n - 1

   267 };

   268 

   269 write "Result";

   270 write fact

   271 """

   272 

   273 compile_all(Stmts.parse_all(tokenise(factorialProgram)).head, "factorial")

   274 

   275 // ---- Q3

   276 

   277 /* compile_run(Stmts.parse_all(tokenise("""for i := 1 upto 10 do {

   278   for i := 1 upto 10 do {

   279     write i

   280   }

   281 }""")).head, "nestedloop") */

   282 

   283 

   284 compile_run(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head, "collatz2")

   285 

   286 

   287 

   288 compile_run(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz3.while"))).head, "collatz3")