627
|
1 |
// A Small Compiler for the WHILE Language with Arrays
|
471
|
2 |
// (it does not use a parser and lexer)
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
|
627
|
4 |
// the new parts are
|
|
5 |
// - declaring an array
|
|
6 |
// - references an array cell
|
|
7 |
// - assigning an array cell
|
624
|
8 |
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
// the abstract syntax trees
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
abstract class Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
abstract class AExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
abstract class BExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
type Block = List[Stmt]
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
// statements
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
case object Skip extends Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
case class While(b: BExp, bl: Block) extends Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
case class Assign(s: String, a: AExp) extends Stmt
|
627
|
20 |
case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
case class Write(s: String) extends Stmt
|
627
|
22 |
case class Array(s: String, n: Int) extends Stmt
|
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
// arithmetic expressions
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
case class Var(s: String) extends AExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
case class Num(i: Int) extends AExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
|
627
|
28 |
case class Ref(s: String, a1: AExp) extends AExp
|
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
// boolean expressions
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
case object True extends BExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
case object False extends BExp
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
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
|
34 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
// compiler headers needed for the JVM
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
// (contains an init method, as well as methods for read and write)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
val beginning = """
|
80
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
.class public XXX.XXX
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
.super java/lang/Object
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
.method public <init>()V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
aload_0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
invokenonvirtual java/lang/Object/<init>()V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
.end method
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
.method public static write(I)V
|
373
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
.limit locals 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
.limit stack 2
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
getstatic java/lang/System/out Ljava/io/PrintStream;
|
373
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
iload 0
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
invokevirtual java/io/PrintStream/println(I)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
.end method
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
.method public static main([Ljava/lang/String;)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
.limit locals 200
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
.limit stack 200
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
|
624
|
61 |
; COMPILED CODE STARTS
|
|
62 |
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
"""
|
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 |
val ending = """
|
624
|
66 |
; COMPILED CODE ENDS
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
.end method
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
"""
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
|
628
|
72 |
|
624
|
73 |
// Compiler functions
|
471
|
74 |
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
// for generating new labels
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
var counter = -1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
def Fresh(x: String) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
counter += 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
x ++ "_" ++ counter.toString()
|
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
81 |
}
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
|
624
|
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
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
type Env = Map[String, String]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
// arithmetic expression compilation
|
624
|
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)}"
|
369
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
case Aop("+", a1, a2) =>
|
624
|
102 |
compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"iadd"
|
369
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
case Aop("-", a1, a2) =>
|
624
|
104 |
compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"isub"
|
369
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
case Aop("*", a1, a2) =>
|
624
|
106 |
compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"imul"
|
627
|
107 |
case Ref(s, a1) =>
|
|
108 |
i"aload ${env(s)}" ++ compile_aexp(a1, env) ++ i"iaload"
|
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
// boolean expression compilation
|
624
|
112 |
def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
|
|
113 |
case True => ""
|
|
114 |
case False => i"goto $jmp"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
case Bop("=", a1, a2) =>
|
624
|
116 |
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
|
117 |
case Bop("!=", a1, a2) =>
|
624
|
118 |
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
|
119 |
case Bop("<", a1, a2) =>
|
624
|
120 |
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
|
121 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
// statement compilation
|
624
|
124 |
def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match {
|
|
125 |
case Skip => ("", env)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
case Assign(x, a) => {
|
369
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
val index = if (env.isDefinedAt(x)) env(x) else
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
env.keys.size.toString
|
624
|
129 |
(compile_aexp(a, env) ++ i"istore $index", env + (x -> index))
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
case If(b, bl1, bl2) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
val if_else = Fresh("If_else")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
val if_end = Fresh("If_end")
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
val (instrs1, env1) = compile_block(bl1, env)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
val (instrs2, env2) = compile_block(bl2, env1)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
(compile_bexp(b, env, if_else) ++
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
instrs1 ++
|
624
|
138 |
i"goto $if_end" ++
|
|
139 |
l"$if_else" ++
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
instrs2 ++
|
624
|
141 |
l"$if_end", env2)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
143 |
case While(b, bl) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
144 |
val loop_begin = Fresh("Loop_begin")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
val loop_end = Fresh("Loop_end")
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
val (instrs1, env1) = compile_block(bl, env)
|
624
|
147 |
(l"$loop_begin" ++
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
compile_bexp(b, env, loop_end) ++
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
instrs1 ++
|
624
|
150 |
i"goto $loop_begin" ++
|
|
151 |
l"$loop_end", env1)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
case Write(x) =>
|
624
|
154 |
(i"iload ${env(x)}" ++
|
|
155 |
i"invokestatic XXX/XXX/write(I)V", env)
|
627
|
156 |
case Array(s, n) => {
|
|
157 |
val index = if (env.isDefinedAt(s)) throw new Exception("Array already defined") else
|
369
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
env.keys.size.toString
|
627
|
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 |
}
|
69
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 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
// compilation of a block (i.e. list of instructions)
|
624
|
174 |
def compile_block(bl: Block, env: Env) : (String, Env) = bl match {
|
|
175 |
case Nil => ("", env)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
case s::bl => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
val (instrs1, env1) = compile_stmt(s, env)
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
val (instrs2, env2) = compile_block(bl, env1)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
(instrs1 ++ instrs2, env2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
// main compilation function for blocks
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
def compile(bl: Block, class_name: String) : String = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
val instructions = compile_block(bl, Map.empty)._1
|
80
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
(beginning ++ instructions.mkString ++ ending).replaceAllLiterally("XXX", class_name)
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
|
628
|
190 |
// main compiler functions
|
471
|
191 |
import scala.util._
|
|
192 |
import scala.sys.process._
|
|
193 |
import scala.io
|
|
194 |
|
|
195 |
def compile_tofile(bl: Block, class_name: String) = {
|
|
196 |
val output = compile(bl, class_name)
|
628
|
197 |
scala.tools.nsc.io.File(s"${class_name}.j").writeAll(output)
|
471
|
198 |
}
|
|
199 |
|
535
|
200 |
def compile_all(bl: Block, class_name: String) : Unit = {
|
471
|
201 |
compile_tofile(bl, class_name)
|
|
202 |
println("compiled ")
|
628
|
203 |
(s"java -jar jvm/jasmin-2.4/jasmin.jar ${class_name}.j").!!
|
471
|
204 |
println("assembled ")
|
|
205 |
}
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
206 |
|
609
|
207 |
def time_needed[T](i: Int, code: => T) = {
|
|
208 |
val start = System.nanoTime()
|
|
209 |
for (j <- 1 to i) code
|
|
210 |
val end = System.nanoTime()
|
|
211 |
(end - start)/(i * 1.0e9)
|
|
212 |
}
|
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
|
609
|
214 |
|
|
215 |
def compile_run(bl: Block, class_name: String) : Unit = {
|
|
216 |
println("Start compilation")
|
|
217 |
compile_all(bl, class_name)
|
628
|
218 |
println("Start running")
|
|
219 |
println("Time: " + time_needed(1, (s"java ${class_name}/${class_name}").!))
|
627
|
220 |
}
|
|
221 |
|
628
|
222 |
// a simple test case
|
|
223 |
val arr_test =
|
|
224 |
List(Array("a", 10), // a[10]
|
|
225 |
Array("b", 2), // b[2]
|
|
226 |
AssignA("a", Num(0), Num(10)), // a[0] := 10
|
|
227 |
Assign("x", Ref("a", Num(0))), // x := a[0]
|
|
228 |
Write("x"), // write x
|
|
229 |
AssignA("b", Num(1), Num(5)), // b[1] := 5
|
|
230 |
Assign("x", Ref("b", Num(1))), // x := b[1]
|
|
231 |
Write("x")) // write x
|
627
|
232 |
|
628
|
233 |
compile_run(arr_test, "a")
|
627
|
234 |
|