1 // A Small Compiler for the WHILE Language with Arrays

     2 // (it does not use a parser and lexer)

     3 

     4 // the new parts are

     5 //    - declaring an array

     6 //    - references an array cell

     7 //    - assigning an array cell

     8 

     9 // the abstract syntax trees

    10 abstract class Stmt

    11 abstract class AExp

    12 abstract class BExp 

    13 type Block = List[Stmt]

    14 

    15 // statements

    16 case object Skip extends Stmt

    17 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt

    18 case class While(b: BExp, bl: Block) extends Stmt

    19 case class Assign(s: String, a: AExp) extends Stmt

    20 case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt

    21 case class Write(s: String) extends Stmt

    22 case class Array(s: String, n: Int) extends Stmt 

    23 

    24 // arithmetic expressions

    25 case class Var(s: String) extends AExp

    26 case class Num(i: Int) extends AExp

    27 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp

    28 case class Ref(s: String, a1: AExp) extends AExp

    29 

    30 // boolean expressions

    31 case object True extends BExp

    32 case object False extends BExp

    33 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp

    34 

    35 

    36 // compiler headers needed for the JVM

    37 // (contains an init method, as well as methods for read and write)

    38 val beginning = """

    39 .class public XXX.XXX

    40 .super java/lang/Object

    41 

    42 .method public <init>()V

    43    aload_0

    44    invokenonvirtual java/lang/Object/<init>()V

    45    return

    46 .end method

    47 

    48 .method public static write(I)V 

    49     .limit locals 1 

    50     .limit stack 2 

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

    52     iload 0

    53     invokevirtual java/io/PrintStream/println(I)V 

    54     return 

    55 .end method

    56 

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

    58    .limit locals 200

    59    .limit stack 200

    60 

    61 ; COMPILED CODE STARTS

    62 

    63 """

    64 

    65 val ending = """

    66 ; COMPILED CODE ENDS

    67    return

    68 

    69 .end method

    70 """

    71 

    72 // Compiler functions

    73 

    74 

    75 // for generating new labels

    76 var counter = -1

    77 

    78 def Fresh(x: String) = {

    79   counter += 1

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

    81 }

    82 

    83 // convenient string interpolations 

    84 // for instructions and labels

    85 import scala.language.implicitConversions

    86 import scala.language.reflectiveCalls

    87 

    88 implicit def sring_inters(sc: StringContext) = new {

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

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

    91 }

    92 

    93 

    94 // environments 

    95 type Env = Map[String, String]

    96 

    97 // arithmetic expression compilation

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

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

   100   case Var(s) => i"iload ${env(s)}"

   101   case Aop("+", a1, a2) => 

   102     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"iadd"

   103   case Aop("-", a1, a2) => 

   104     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"isub"

   105   case Aop("*", a1, a2) => 

   106     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"imul"

   107   case Ref(s, a1) => 

   108     i"aload ${env(s)}" ++ compile_aexp(a1, env) ++ i"iaload"  

   109 }

   110 

   111 // boolean expression compilation

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

   113   case True => ""

   114   case False => i"goto $jmp"

   115   case Bop("=", a1, a2) => 

   116     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp"

   117   case Bop("!=", a1, a2) => 

   118     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp"

   119   case Bop("<", a1, a2) => 

   120     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp"

   121 }

   122 

   123 // statement compilation

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

   125   case Skip => ("", env)

   126   case Assign(x, a) => {

   127     val index = if (env.isDefinedAt(x)) env(x) else 

   128                     env.keys.size.toString

   129     (compile_aexp(a, env) ++ i"istore $index", env + (x -> index))

   130   } 

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

   132     val if_else = Fresh("If_else")

   133     val if_end = Fresh("If_end")

   134     val (instrs1, env1) = compile_block(bl1, env)

   135     val (instrs2, env2) = compile_block(bl2, env1)

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

   137      instrs1 ++

   138      i"goto $if_end" ++

   139      l"$if_else" ++

   140      instrs2 ++

   141      l"$if_end", env2)

   142   }

   143   case While(b, bl) => {

   144     val loop_begin = Fresh("Loop_begin")

   145     val loop_end = Fresh("Loop_end")

   146     val (instrs1, env1) = compile_block(bl, env)

   147     (l"$loop_begin" ++

   148      compile_bexp(b, env, loop_end) ++

   149      instrs1 ++

   150      i"goto $loop_begin" ++

   151      l"$loop_end", env1)

   152   }

   153   case Write(x) => 

   154     (i"iload ${env(x)}" ++ 

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

   156   case Array(s, n) => {

   157     val index = if (env.isDefinedAt(s)) throw new Exception("Array already defined") else 

   158                     env.keys.size.toString

   159     (i"ldc $n" ++

   160      i"newarray int" ++

   161      i"astore $index", env + (s -> index))

   162   } 

   163   case AssignA(s, a1, a2) => {

   164     val index = if (env.isDefinedAt(s)) env(s) else 

   165                     throw new Exception("Array not yet defined")

   166     (i"aload $index" ++

   167      compile_aexp(a1, env) ++

   168      compile_aexp(a2, env) ++

   169      i"iastore", env)

   170   } 

   171 }

   172 

   173 // compilation of a block (i.e. list of instructions)

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

   175   case Nil => ("", env)

   176   case s::bl => {

   177     val (instrs1, env1) = compile_stmt(s, env)

   178     val (instrs2, env2) = compile_block(bl, env1)

   179     (instrs1 ++ instrs2, env2)

   180   }

   181 }

   182 

   183 // main compilation function for blocks

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

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

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

   187 }

   188 

   189 // compiling and running files

   190 //

   191 // JVM files can be assembled with 

   192 //

   193 //    java -jar jvm/jasmin-2.4/jasmin.jar fib.j

   194 //

   195 // and started with

   196 //

   197 //    java fib/fib

   198 

   199 

   200 

   201 import scala.util._

   202 import scala.sys.process._

   203 import scala.io

   204 

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

   206   val output = compile(bl, class_name)

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

   208   fw.write(output) 

   209   fw.close()

   210 }

   211 

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

   213   compile_tofile(bl, class_name)

   214   println("compiled ")

   215   val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!!

   216   println("assembled ")

   217 }

   218 

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

   220   val start = System.nanoTime()

   221   for (j <- 1 to i) code

   222   val end = System.nanoTime()

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

   224 }

   225 

   226 

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

   228   println("Start compilation")

   229   compile_all(bl, class_name)

   230   println("running")

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

   232 }

   233 

   234 

   235 // BF Part

   236 

   237 // simple instructions

   238 def instr(c: Char) : String = c match {

   239   case '>' => "ptr := ptr + 1;"

   240   case '<' => "ptr := ptr - 1;"

   241   case '+' => "field[ptr] := field[ptr] + 1;"

   242   case '-' => "field[ptr] := field[ptr] - 1;"

   243   case '.' => "x := field[ptr]; write x;"

   244   case '['  => "while (field[ptr] != 0) do {"

   245   case ']'  => "skip};"

   246   case _ => ""

   247 }

   248 

   249 def instrs(prog: String) : String =

   250   prog.toList.map(instr).mkString

   251 

   252 

   253 // compound instructions

   254 def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {

   255   case (Nil, acc) => acc

   256   case (c :: cs, Nil) => splice(cs, List((c, 1)))

   257   case (c :: cs, (d, n) :: acc) => 

   258     if (c == d) splice(cs, (c, n + 1) :: acc)

   259     else splice(cs, (c, 1) :: (d, n) :: acc)

   260 }

   261 

   262 def spl(s: String) = splice(s.toList, Nil).reverse

   263 

   264 def instr2(c: Char, n: Int) : String = c match {

   265   case '>' => s"ptr := ptr + $n;"

   266   case '<' => s"ptr := ptr - $n;"

   267   case '+' => s"field[ptr] := field[ptr] + $n;"

   268   case '-' => s"field[ptr] := field[ptr] - $n;"

   269   case '.' => s"x := field[ptr]; write x;" 

   270   case '['  => s"while (field[ptr] != 0) do {" * n 

   271   case ']'  => s"skip};" * n

   272   case _ => ""

   273 }

   274 

   275 def instrs2(prog: String) : String =

   276   spl(prog).map{ case (c, n) => instr2(c, n) }.mkString

   277 

   278 

   279 def bf_str(prog: String) : String = {

   280   "\n" ++

   281   //"new field[30000];\n" ++

   282   "ptr := 15000;" ++

   283   instrs2(prog) ++

   284   "skip"

   285 }

   286 

   287 def bf_run(bfprog: String, name: String) = {

   288   println("BF processing start")

   289   val bf_string = bf_str(bfprog).replaceAll("\\s", "")

   290   println(s"BF parsing start (string length ${bf_string.length})")

   291   val bf_prog = Stmts.parse_all(bf_string).toList.head

   292   println("BF Compile start")

   293   compile_run(Array("field", 30000) :: bf_prog, name)

   294 }

   295 

   296 

   297 

   298 val bf1 = """++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[

   299       ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<

   300       ]>.>+[>>]>+]"""

   301 

   302 bf_run(bf1, "sier")

   303 

   304 bf_run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++

   305        ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", "hello")

   306 

   307 bf_run("""+++++++++++

   308       >+>>>>++++++++++++++++++++++++++++++++++++++++++++

   309       >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>

   310       +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-

   311       <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<

   312       -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]

   313       >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++

   314       +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++

   315       ++++++++++++++++++++++++++++++++++++++++++++.[-]<<

   316       <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<

   317       [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", "fibs")