1 // A Small Compiler for the WHILE Language |
|
2 // (it does not use a parser nor lexer) |
|
3 |
|
4 |
|
5 // the abstract syntax trees |
|
6 abstract class Stmt |
|
7 abstract class AExp |
|
8 abstract class BExp |
|
9 type Block = List[Stmt] |
|
10 |
|
11 // statements |
|
12 case object Skip extends Stmt |
|
13 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
|
14 case class While(b: BExp, bl: Block) extends Stmt |
|
15 case class Assign(s: String, a: AExp) extends Stmt |
|
16 case class Write(s: String) extends Stmt |
|
17 case class Read(s: String) extends Stmt |
|
18 |
|
19 // arithmetic expressions |
|
20 case class Var(s: String) extends AExp |
|
21 case class Num(i: Int) extends AExp |
|
22 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
|
23 |
|
24 // boolean expressions |
|
25 case object True extends BExp |
|
26 case object False extends BExp |
|
27 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
|
28 |
|
29 |
|
30 // compiler headers needed for the JVM |
|
31 // (contains methods for read and write) |
|
32 val beginning = """ |
|
33 .class public XXX.XXX |
|
34 .super java/lang/Object |
|
35 |
|
36 .method public static write(I)V |
|
37 .limit locals 1 |
|
38 .limit stack 2 |
|
39 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
40 iload 0 |
|
41 invokevirtual java/io/PrintStream/println(I)V |
|
42 return |
|
43 .end method |
|
44 |
|
45 .method public static read()I |
|
46 .limit locals 10 |
|
47 .limit stack 10 |
|
48 |
|
49 ldc 0 |
|
50 istore 1 ; this will hold our final integer |
|
51 Label1: |
|
52 getstatic java/lang/System/in Ljava/io/InputStream; |
|
53 invokevirtual java/io/InputStream/read()I |
|
54 istore 2 |
|
55 iload 2 |
|
56 ldc 10 ; the newline delimiter |
|
57 isub |
|
58 ifeq Label2 |
|
59 iload 2 |
|
60 ldc 32 ; the space delimiter |
|
61 isub |
|
62 ifeq Label2 |
|
63 |
|
64 iload 2 |
|
65 ldc 48 ; we have our digit in ASCII, have to subtract it from 48 |
|
66 isub |
|
67 ldc 10 |
|
68 iload 1 |
|
69 imul |
|
70 iadd |
|
71 istore 1 |
|
72 goto Label1 |
|
73 Label2: |
|
74 ;when we come here we have our integer computed in local variable 1 |
|
75 iload 1 |
|
76 ireturn |
|
77 .end method |
|
78 |
|
79 .method public static main([Ljava/lang/String;)V |
|
80 .limit locals 200 |
|
81 .limit stack 200 |
|
82 |
|
83 ; COMPILED CODE STARTS |
|
84 |
|
85 """ |
|
86 |
|
87 val ending = """ |
|
88 ; COMPILED CODE ENDS |
|
89 return |
|
90 |
|
91 .end method |
|
92 """ |
|
93 |
|
94 // Compiler functions |
|
95 |
|
96 |
|
97 // for generating new labels |
|
98 var counter = -1 |
|
99 |
|
100 def Fresh(x: String) = { |
|
101 counter += 1 |
|
102 x ++ "_" ++ counter.toString() |
|
103 } |
|
104 |
|
105 // convenient string interpolations |
|
106 // for instructions and labels |
|
107 import scala.language.implicitConversions |
|
108 import scala.language.reflectiveCalls |
|
109 |
|
110 implicit def sring_inters(sc: StringContext) = new { |
|
111 def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" |
|
112 def l(args: Any*): String = sc.s(args:_*) ++ ":\n" |
|
113 } |
|
114 |
|
115 // this allows us to write things like |
|
116 // i"add" and l"Label" |
|
117 |
|
118 |
|
119 // environments |
|
120 type Env = Map[String, Int] |
|
121 |
|
122 |
|
123 def compile_op(op: String) = op match { |
|
124 case "+" => i"iadd" |
|
125 case "-" => i"isub" |
|
126 case "*" => i"imul" |
|
127 } |
|
128 |
|
129 // arithmetic expression compilation |
|
130 def compile_aexp(a: AExp, env : Env) : String = a match { |
|
131 case Num(i) => i"ldc $i" |
|
132 case Var(s) => i"iload ${env(s)} \t\t; $s" |
|
133 case Aop(op, a1, a2) => |
|
134 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op) |
|
135 } |
|
136 |
|
137 // boolean expression compilation |
|
138 // - the jump-label is for where to jump if the condition is not true |
|
139 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { |
|
140 case True => "" |
|
141 case False => i"goto $jmp" |
|
142 case Bop("==", a1, a2) => |
|
143 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp" |
|
144 case Bop("!=", a1, a2) => |
|
145 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp" |
|
146 case Bop("<", a1, a2) => |
|
147 compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp" |
|
148 } |
|
149 |
|
150 // statement compilation |
|
151 def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match { |
|
152 case Skip => ("", env) |
|
153 case Assign(x, a) => { |
|
154 val index = env.getOrElse(x, env.keys.size) |
|
155 (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index)) |
|
156 } |
|
157 case If(b, bl1, bl2) => { |
|
158 val if_else = Fresh("If_else") |
|
159 val if_end = Fresh("If_end") |
|
160 val (instrs1, env1) = compile_block(bl1, env) |
|
161 val (instrs2, env2) = compile_block(bl2, env1) |
|
162 (compile_bexp(b, env, if_else) ++ |
|
163 instrs1 ++ |
|
164 i"goto $if_end" ++ |
|
165 l"$if_else" ++ |
|
166 instrs2 ++ |
|
167 l"$if_end", env2) |
|
168 } |
|
169 case While(b, bl) => { |
|
170 val loop_begin = Fresh("Loop_begin") |
|
171 val loop_end = Fresh("Loop_end") |
|
172 val (instrs1, env1) = compile_block(bl, env) |
|
173 (l"$loop_begin" ++ |
|
174 compile_bexp(b, env, loop_end) ++ |
|
175 instrs1 ++ |
|
176 i"goto $loop_begin" ++ |
|
177 l"$loop_end", env1) |
|
178 } |
|
179 case Write(x) => |
|
180 (i"iload ${env(x)} \t\t; $x" ++ |
|
181 i"invokestatic XXX/XXX/write(I)V", env) |
|
182 case Read(x) => { |
|
183 val index = env.getOrElse(x, env.keys.size) |
|
184 (i"invokestatic XXX/XXX/read()I" ++ |
|
185 i"istore $index \t\t; $x", env + (x -> index)) |
|
186 } |
|
187 } |
|
188 |
|
189 // compilation of a block (i.e. list of instructions) |
|
190 def compile_block(bl: Block, env: Env) : (String, Env) = bl match { |
|
191 case Nil => ("", env) |
|
192 case s::bl => { |
|
193 val (instrs1, env1) = compile_stmt(s, env) |
|
194 val (instrs2, env2) = compile_block(bl, env1) |
|
195 (instrs1 ++ instrs2, env2) |
|
196 } |
|
197 } |
|
198 |
|
199 // main compilation function for blocks |
|
200 def compile(bl: Block, class_name: String) : String = { |
|
201 val instructions = compile_block(bl, Map.empty)._1 |
|
202 (beginning ++ instructions ++ ending).replaceAllLiterally("XXX", class_name) |
|
203 } |
|
204 |
|
205 |
|
206 // compiling and running files |
|
207 // |
|
208 // JVM files can be assembled with |
|
209 // |
|
210 // java -jar jvm/jasmin-2.4/jasmin.jar fib.j |
|
211 // |
|
212 // and started with |
|
213 // |
|
214 // java fib/fib |
|
215 |
|
216 |
|
217 |
|
218 import scala.util._ |
|
219 import scala.sys.process._ |
|
220 import scala.io |
|
221 |
|
222 def compile_tofile(bl: Block, class_name: String) = { |
|
223 val output = compile(bl, class_name) |
|
224 val fw = new java.io.FileWriter(class_name + ".j") |
|
225 fw.write(output) |
|
226 fw.close() |
|
227 } |
|
228 |
|
229 def compile_all(bl: Block, class_name: String) : Unit = { |
|
230 compile_tofile(bl, class_name) |
|
231 println("compiled ") |
|
232 val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!! |
|
233 println("assembled ") |
|
234 } |
|
235 |
|
236 def time_needed[T](i: Int, code: => T) = { |
|
237 val start = System.nanoTime() |
|
238 for (j <- 1 to i) code |
|
239 val end = System.nanoTime() |
|
240 (end - start)/(i * 1.0e9) |
|
241 } |
|
242 |
|
243 |
|
244 def compile_run(bl: Block, class_name: String) : Unit = { |
|
245 println("Start compilation") |
|
246 compile_all(bl, class_name) |
|
247 println("running") |
|
248 println("Time: " + time_needed(1, ("java " + class_name + "/" + class_name).!)) |
|
249 } |
|
250 |
|
251 |
|
252 // Fibonacci numbers as a bare-bone test-case |
|
253 val fib_test = |
|
254 List(Assign("n", Num(9)), // n := 10; |
|
255 Assign("minus1",Num(0)), // minus1 := 0; |
|
256 Assign("minus2",Num(1)), // minus2 := 1; |
|
257 Assign("temp",Num(0)), // temp := 0; |
|
258 While(Bop("<",Num(0),Var("n")), // while n > 0 do { |
|
259 List(Assign("temp",Var("minus2")), // temp := minus2; |
|
260 Assign("minus2",Aop("+",Var("minus1"),Var("minus2"))), |
|
261 // minus2 := minus1 + minus2; |
|
262 Assign("minus1",Var("temp")), // minus1 := temp; |
|
263 Assign("n",Aop("-",Var("n"),Num(1))))), // n := n - 1 }; |
|
264 Write("minus1")) // write minus1 |
|
265 |
|
266 |
|
267 // the compiled file as string |
|
268 // |
|
269 //println(compile(fib_test, "fib")) |
|
270 |
|
271 |
|
272 compile_run(fib_test, "fib") |
|
273 |
|
274 |
|