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