|
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") |