|
1 // A Small Compiler for the WHILE Language |
|
2 // |
|
3 // - this compiler contains support for "static" integer |
|
4 // arrays (they are mutable but cannot be re-sized) |
|
5 // |
|
6 // Call with |
|
7 // |
|
8 // amm compile_arrays.sc |
|
9 |
|
10 |
|
11 // the abstract syntax trees for WHILE |
|
12 |
|
13 abstract class Stmt |
|
14 abstract class AExp |
|
15 abstract class BExp |
|
16 type Block = List[Stmt] |
|
17 |
|
18 // statements |
|
19 case object Skip extends Stmt |
|
20 case class ArrayDef(s: String, n: Int) extends Stmt // array definition |
|
21 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
|
22 case class While(b: BExp, bl: Block) extends Stmt |
|
23 case class Assign(s: String, a: AExp) extends Stmt // var := exp |
|
24 case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt // arr[exp1] := exp2 |
|
25 case class Write(s: String) extends Stmt |
|
26 |
|
27 |
|
28 // arithmetic expressions |
|
29 case class Var(s: String) extends AExp |
|
30 case class Num(i: Int) extends AExp |
|
31 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
|
32 case class Ref(s: String, a: AExp) extends AExp |
|
33 |
|
34 // boolean expressions |
|
35 case object True extends BExp |
|
36 case object False extends BExp |
|
37 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
|
38 |
|
39 |
|
40 // compiler headers needed for the JVM |
|
41 // |
|
42 // - contains a main method and a method for writing out an integer |
|
43 // |
|
44 // - the stack and locals are hard-coded |
|
45 // |
|
46 |
|
47 val beginning = """ |
|
48 .class public XXX.XXX |
|
49 .super java/lang/Object |
|
50 |
|
51 .method public static write(I)V |
|
52 .limit locals 1 |
|
53 .limit stack 2 |
|
54 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
55 iload 0 |
|
56 invokevirtual java/io/PrintStream/print(I)V |
|
57 return |
|
58 .end method |
|
59 |
|
60 .method public static main([Ljava/lang/String;)V |
|
61 .limit locals 200 |
|
62 .limit stack 200 |
|
63 |
|
64 ; COMPILED CODE STARTS |
|
65 |
|
66 """ |
|
67 |
|
68 val ending = """ |
|
69 ; COMPILED CODE ENDS |
|
70 return |
|
71 |
|
72 .end method |
|
73 """ |
|
74 |
|
75 |
|
76 |
|
77 // for generating new labels |
|
78 var counter = -1 |
|
79 |
|
80 def Fresh(x: String) = { |
|
81 counter += 1 |
|
82 x ++ "_" ++ counter.toString() |
|
83 } |
|
84 |
|
85 // environments for variables and indices |
|
86 type Env = Map[String, Int] |
|
87 |
|
88 // convenient string interpolations |
|
89 // for generating instructions and labels |
|
90 import scala.language.implicitConversions |
|
91 import scala.language.reflectiveCalls |
|
92 |
|
93 implicit def sring_inters(sc: StringContext) = new { |
|
94 def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" |
|
95 def l(args: Any*): String = sc.s(args:_*) ++ ":\n" |
|
96 } |
|
97 |
|
98 def compile_op(op: String) = op match { |
|
99 case "+" => i"iadd" |
|
100 case "-" => i"isub" |
|
101 case "*" => i"imul" |
|
102 } |
|
103 |
|
104 // arithmetic expression compilation |
|
105 def compile_aexp(a: AExp, env : Env) : String = a match { |
|
106 case Num(i) => i"ldc $i" |
|
107 case Var(s) => i"iload ${env(s)}" |
|
108 case Aop(op, a1, a2) => |
|
109 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op) |
|
110 case Ref(s, a) => |
|
111 i"aload ${env(s)}" ++ compile_aexp(a, env) ++ i"iaload" |
|
112 } |
|
113 |
|
114 // boolean expression compilation |
|
115 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { |
|
116 case True => "" |
|
117 case False => i"goto $jmp" |
|
118 case Bop("==", a1, a2) => |
|
119 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp" |
|
120 case Bop("!=", a1, a2) => |
|
121 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp" |
|
122 case Bop("<", a1, a2) => |
|
123 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp" |
|
124 } |
|
125 |
|
126 // statement compilation |
|
127 def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match { |
|
128 case Skip => ("", env) |
|
129 case Assign(x, a) => { |
|
130 val index = env.getOrElse(x, env.keys.size) |
|
131 (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index)) |
|
132 } |
|
133 case If(b, bl1, bl2) => { |
|
134 val if_else = Fresh("If_else") |
|
135 val if_end = Fresh("If_end") |
|
136 val (instrs1, env1) = compile_block(bl1, env) |
|
137 val (instrs2, env2) = compile_block(bl2, env1) |
|
138 (compile_bexp(b, env, if_else) ++ |
|
139 instrs1 ++ |
|
140 i"goto $if_end" ++ |
|
141 l"$if_else" ++ |
|
142 instrs2 ++ |
|
143 l"$if_end", env2) |
|
144 } |
|
145 case While(b, bl) => { |
|
146 val loop_begin = Fresh("Loop_begin") |
|
147 val loop_end = Fresh("Loop_end") |
|
148 val (instrs1, env1) = compile_block(bl, env) |
|
149 (l"$loop_begin" ++ |
|
150 compile_bexp(b, env, loop_end) ++ |
|
151 instrs1 ++ |
|
152 i"goto $loop_begin" ++ |
|
153 l"$loop_end", env1) |
|
154 } |
|
155 case Write(x) => |
|
156 (i"iload ${env(x)} \t\t; $x" ++ |
|
157 i"invokestatic XXX/XXX/write(I)V", env) |
|
158 case ArrayDef(s: String, n: Int) => { |
|
159 val index = if (env.isDefinedAt(s)) throw new Exception("array def error") else |
|
160 env.keys.size |
|
161 (i"ldc $n" ++ |
|
162 i"newarray int" ++ |
|
163 i"astore $index", env + (s -> index)) |
|
164 } |
|
165 case AssignA(s, a1, a2) => { |
|
166 val index = if (env.isDefinedAt(s)) env(s) else |
|
167 throw new Exception("array not defined") |
|
168 (i"aload ${env(s)}" ++ |
|
169 compile_aexp(a1, env) ++ |
|
170 compile_aexp(a2, env) ++ |
|
171 i"iastore", env) |
|
172 } |
|
173 } |
|
174 |
|
175 // compile a block (i.e. list of statements) |
|
176 def compile_block(bl: Block, env: Env) : (String, Env) = bl match { |
|
177 case Nil => ("", env) |
|
178 case s::bl => { |
|
179 val (instrs1, env1) = compile_stmt(s, env) |
|
180 val (instrs2, env2) = compile_block(bl, env1) |
|
181 (instrs1 ++ instrs2, env2) |
|
182 } |
|
183 } |
|
184 |
|
185 |
|
186 // main compile function for blocks (adds headers and proper JVM names) |
|
187 def compile(bl: Block, class_name: String) : String = { |
|
188 val instructions = compile_block(bl, Map())._1 |
|
189 (beginning ++ instructions ++ ending).replace("XXX", class_name) |
|
190 } |
|
191 |
|
192 |
|
193 |
|
194 // contrived example involving arrays |
|
195 val array_test = |
|
196 List(ArrayDef("a", 10), // array a[10] |
|
197 ArrayDef("b", 2), // array b[2] |
|
198 AssignA("a", Num(0), Num(10)), // a[0] := 10 |
|
199 Assign("x", Ref("a", Num(0))), // x := a[0] |
|
200 Write("x"), |
|
201 AssignA("b", Num(1), Num(5)), // b[1] := 5 |
|
202 Assign("x", Ref("b", Num(1))), // x := b[1] |
|
203 Write("x")) |
|
204 |
|
205 |
|
206 // prints out the JVM-assembly instructions for fib above |
|
207 // |
|
208 // println(compile(array_test, "arr")) |
|
209 // |
|
210 // can be assembled by hand with |
|
211 // |
|
212 // java -jar jasmin.jar arr.j |
|
213 // |
|
214 // and run with |
|
215 // |
|
216 // java arr/arr |
|
217 |
|
218 // automating the above |
|
219 import ammonite.ops._ |
|
220 |
|
221 def compile_to_file(bl: Block, class_name: String) : Unit = |
|
222 write.over(pwd / s"$class_name.j", compile(bl, class_name)) |
|
223 |
|
224 def compile_and_run(bl: Block, class_name: String) : Unit = { |
|
225 println(s"Start of compilation") |
|
226 compile_to_file(bl, class_name) |
|
227 println(s"generated $class_name.j file") |
|
228 os.proc("java", "-jar", "jasmin.jar", s"$class_name.j").call() |
|
229 println(s"generated $class_name.class file ") |
|
230 println(os.proc("java", s"${class_name}/${class_name}").call().out.text()) |
|
231 println(s"done.") |
|
232 } |
|
233 |
|
234 |
|
235 |
|
236 @main def main() = { |
|
237 compile_and_run(array_test, "arr") |
|
238 } |
|
239 |
|
240 |