624
|
1 |
// A Small Compiler for a Simple Functional Language
|
813
|
2 |
// (includes a parser and lexer)
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
//
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
// call with
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
//
|
813
|
6 |
// amm fun.sc test
|
|
7 |
//
|
|
8 |
// or
|
|
9 |
//
|
789
|
10 |
// amm fun.sc main defs.fun
|
|
11 |
// amm fun.sc main fact.fun
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
//
|
813
|
13 |
// or
|
|
14 |
//
|
|
15 |
// amm fun.sc run defs.fun
|
|
16 |
// amm fun.sc run fact.fun
|
789
|
17 |
//
|
813
|
18 |
// the first prints out the JVM instructions for two
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
// factorial functions
|
813
|
20 |
//
|
|
21 |
// the next compile/run fun files
|
|
22 |
//
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
|
789
|
24 |
import $file.fun_tokens, fun_tokens._
|
|
25 |
import $file.fun_parser, fun_parser._
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
// calculating the maximal needed stack size
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
def max_stack_exp(e: Exp): Int = e match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
case Call(_, args) => args.map(max_stack_exp).sum
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
case If(a, e1, e2) =>
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e2)).max)
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
case Write(e) => max_stack_exp(e) + 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
case Var(_) => 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
case Num(_) => 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2)
|
789
|
37 |
case Sequence(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
}
|
789
|
39 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
def max_stack_bexp(e: BExp): Int = e match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
case Bop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
// compiler - built-in functions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
// copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
//
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
val library = """
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
.class public XXX.XXX
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
.super java/lang/Object
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
.method public static write(I)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
.limit locals 5
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
.limit stack 5
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
iload 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
getstatic java/lang/System/out Ljava/io/PrintStream;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
swap
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
58 |
invokevirtual java/io/PrintStream/println(I)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
59 |
return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
60 |
.end method
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
"""
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
// for generating new labels
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
65 |
var counter = -1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
66 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
def Fresh(x: String) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
68 |
counter += 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
69 |
x ++ "_" ++ counter.toString()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
70 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
|
628
|
72 |
// convenient string interpolations for
|
|
73 |
// generating instructions, labels etc
|
624
|
74 |
import scala.language.implicitConversions
|
|
75 |
import scala.language.reflectiveCalls
|
|
76 |
|
639
|
77 |
// convenience for code-generation (string interpolations)
|
624
|
78 |
implicit def sring_inters(sc: StringContext) = new {
|
639
|
79 |
def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" // instructions
|
|
80 |
def l(args: Any*): String = sc.s(args:_*) ++ ":\n" // labels
|
|
81 |
def m(args: Any*): String = sc.s(args:_*) ++ "\n" // methods
|
624
|
82 |
}
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
83 |
|
628
|
84 |
// variable / index environments
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
85 |
type Env = Map[String, Int]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
|
813
|
87 |
def compile_op(op: String) = op match {
|
|
88 |
case "+" => i"iadd"
|
|
89 |
case "-" => i"isub"
|
|
90 |
case "*" => i"imul"
|
|
91 |
case "/" => i"idiv"
|
|
92 |
case "%" => i"irem"
|
|
93 |
}
|
|
94 |
|
|
95 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
96 |
// compile expressions
|
813
|
97 |
def compile_exp(a: Exp, env: Env) : String = a match {
|
624
|
98 |
case Num(i) => i"ldc $i"
|
|
99 |
case Var(s) => i"iload ${env(s)}"
|
813
|
100 |
case Aop(op, a1, a2) =>
|
|
101 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ compile_op(op)
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
102 |
case If(b, a1, a2) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
103 |
val if_else = Fresh("If_else")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
104 |
val if_end = Fresh("If_end")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
105 |
compile_bexp(b, env, if_else) ++
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
106 |
compile_exp(a1, env) ++
|
624
|
107 |
i"goto $if_end" ++
|
|
108 |
l"$if_else" ++
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
109 |
compile_exp(a2, env) ++
|
624
|
110 |
l"$if_end"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
111 |
}
|
624
|
112 |
case Call(name, args) => {
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
113 |
val is = "I" * args.length
|
624
|
114 |
args.map(a => compile_exp(a, env)).mkString ++
|
|
115 |
i"invokestatic XXX/XXX/$name($is)I"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
116 |
}
|
789
|
117 |
case Sequence(a1, a2) => {
|
624
|
118 |
compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env)
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
119 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
120 |
case Write(a1) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
121 |
compile_exp(a1, env) ++
|
624
|
122 |
i"dup" ++
|
|
123 |
i"invokestatic XXX/XXX/write(I)V"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
124 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
125 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
126 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
127 |
// compile boolean expressions
|
624
|
128 |
def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
129 |
case Bop("==", a1, a2) =>
|
624
|
130 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
131 |
case Bop("!=", a1, a2) =>
|
624
|
132 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpeq $jmp"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
133 |
case Bop("<", a1, a2) =>
|
624
|
134 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
135 |
case Bop("<=", a1, a2) =>
|
624
|
136 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
138 |
|
639
|
139 |
// compile functions and declarations
|
624
|
140 |
def compile_decl(d: Decl) : String = d match {
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
141 |
case Def(name, args, a) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
142 |
val env = args.zipWithIndex.toMap
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
143 |
val is = "I" * args.length
|
624
|
144 |
m".method public static $name($is)I" ++
|
|
145 |
m".limit locals ${args.length.toString}" ++
|
|
146 |
m".limit stack ${1 + max_stack_exp(a)}" ++
|
|
147 |
l"${name}_Start" ++
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
148 |
compile_exp(a, env) ++
|
624
|
149 |
i"ireturn" ++
|
|
150 |
m".end method\n"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
151 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
152 |
case Main(a) => {
|
624
|
153 |
m".method public static main([Ljava/lang/String;)V" ++
|
813
|
154 |
m".limit locals 1" ++
|
|
155 |
m".limit stack ${1 + max_stack_exp(a)}" ++
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
156 |
compile_exp(a, Map()) ++
|
624
|
157 |
i"invokestatic XXX/XXX/write(I)V" ++
|
|
158 |
i"return" ++
|
|
159 |
m".end method\n"
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
160 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
161 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
162 |
|
625
|
163 |
// the main compilation function
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
164 |
def compile(prog: List[Decl], class_name: String) : String = {
|
624
|
165 |
val instructions = prog.map(compile_decl).mkString
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
166 |
(library + instructions).replaceAllLiterally("XXX", class_name)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
167 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
168 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
169 |
|
813
|
170 |
import ammonite.ops._
|
|
171 |
|
|
172 |
def compile_to_file(prog: List[Decl], class_name: String) : Unit =
|
|
173 |
write.over(pwd / s"$class_name.j", compile(prog, class_name))
|
|
174 |
|
|
175 |
def compile_and_run(prog: List[Decl], class_name: String) : Unit = {
|
|
176 |
println(s"Start of compilation")
|
|
177 |
compile_to_file(prog, class_name)
|
|
178 |
println(s"generated $class_name.j file")
|
|
179 |
os.proc("java", "-jar", "jasmin.jar", s"$class_name.j").call()
|
|
180 |
println(s"generated $class_name.class file")
|
|
181 |
println(s"Run program")
|
|
182 |
os.proc("java", s"${class_name}/${class_name}").call(stdout = os.Inherit)
|
|
183 |
println(s"done.")
|
|
184 |
}
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
185 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
186 |
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
// An example program (two versions of factorial)
|
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 |
// def fact(n) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
// if n == 0 then 1 else n * fact(n - 1);
|
639
|
191 |
//
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
// def facT(n, acc) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
// if n == 0 then acc else facT(n - 1, n * acc);
|
639
|
194 |
//
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
// fact(10) ; facT(10, 1)
|
639
|
196 |
//
|
|
197 |
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
198 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
199 |
val test_prog =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
200 |
List(Def("fact", List("n"),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
201 |
If(Bop("==",Var("n"),Num(0)),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
202 |
Num(1),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
203 |
Aop("*",Var("n"),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
204 |
Call("fact",List(Aop("-",Var("n"),Num(1))))))),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
205 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
206 |
Def("facT",List("n", "acc"),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
207 |
If(Bop("==",Var("n"),Num(0)),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
208 |
Var("acc"),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
209 |
Call("facT",List(Aop("-",Var("n"),Num(1)),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
210 |
Aop("*",Var("n"),Var("acc")))))),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
211 |
|
789
|
212 |
Main(Sequence(Write(Call("fact",List(Num(10)))),
|
813
|
213 |
Write(Call("facT",List(Num(10), Num(1)))))))
|
323
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
214 |
|
813
|
215 |
// prints out the JVM instructions for the factorial example
|
735
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
216 |
@main
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
217 |
def test() =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
218 |
println(compile(test_prog, "fact"))
|
789
|
219 |
|
|
220 |
|
|
221 |
@main
|
|
222 |
def main(fname: String) = {
|
|
223 |
val path = os.pwd / fname
|
|
224 |
val class_name = fname.stripSuffix("." ++ path.ext)
|
|
225 |
val tks = tokenise(os.read(path))
|
|
226 |
val ast = parse_tks(tks)
|
|
227 |
println(compile(ast, class_name))
|
|
228 |
}
|
813
|
229 |
|
|
230 |
@main
|
|
231 |
def run(fname: String) = {
|
|
232 |
val path = os.pwd / fname
|
|
233 |
val class_name = fname.stripSuffix("." ++ path.ext)
|
|
234 |
val tks = tokenise(os.read(path))
|
|
235 |
val ast = parse_tks(tks)
|
|
236 |
compile_and_run(ast, class_name)
|
|
237 |
}
|