1 // A Small Compiler for a Simple Functional Language |
1 // A Small Compiler for a Simple Functional Language |
2 // (includes a lexer and a parser) |
2 // - includes a lexer and a parser |
|
3 // - performs tail-call optimisations |
|
4 // |
|
5 // call with |
|
6 // |
|
7 // amm fun.sc main defs.fun |
|
8 // amm fun.sc main fact.fun |
|
9 // |
|
10 // or |
|
11 // |
|
12 // amm fun.sc run defs.fun |
|
13 // amm fun.sc run fact.fun |
|
14 // |
|
15 // the first prints out the JVM instructions |
|
16 // the second runs the generated class files |
|
17 |
3 |
18 |
4 import $file.fun_tokens, fun_tokens._ |
19 import $file.fun_tokens, fun_tokens._ |
5 import $file.fun_parser, fun_parser._ |
20 import $file.fun_parser, fun_parser._ |
6 |
21 |
7 // compiler - built-in functions |
22 // compiler - built-in functions |
24 """ |
39 """ |
25 |
40 |
26 // calculating the maximal needed stack size |
41 // calculating the maximal needed stack size |
27 def max_stack_exp(e: Exp): Int = e match { |
42 def max_stack_exp(e: Exp): Int = e match { |
28 case Call(_, args) => args.map(max_stack_exp).sum |
43 case Call(_, args) => args.map(max_stack_exp).sum |
29 case If(a, e1, e2) => max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e2)).max) |
44 case If(a, e1, e2) => |
|
45 max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e2)).max) |
30 case Write(e) => max_stack_exp(e) + 1 |
46 case Write(e) => max_stack_exp(e) + 1 |
31 case Var(_) => 1 |
47 case Var(_) => 1 |
32 case Num(_) => 1 |
48 case Num(_) => 1 |
33 case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) |
49 case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) |
34 case Sequence(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max |
50 case Sequence(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max |
59 } |
75 } |
60 |
76 |
61 |
77 |
62 type Env = Map[String, Int] |
78 type Env = Map[String, Int] |
63 |
79 |
|
80 def compile_op(op: String) = op match { |
|
81 case "+" => i"iadd" |
|
82 case "-" => i"isub" |
|
83 case "*" => i"imul" |
|
84 case "/" => i"idiv" |
|
85 case "%" => i"irem" |
|
86 } |
64 |
87 |
65 def compile_expT(a: Exp, env : Env, name: String) : String = a match { |
88 def compile_expT(a: Exp, env : Env, name: String) : String = a match { |
66 case Num(i) => i"ldc $i" |
89 case Num(i) => i"ldc $i" |
67 case Var(s) => i"iload ${env(s)}" |
90 case Var(s) => i"iload ${env(s)}" |
68 case Aop("+", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ i"iadd" |
91 case Aop(op, a1, a2) => |
69 case Aop("-", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ i"isub" |
92 compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ compile_op(op) |
70 case Aop("*", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ i"imul" |
|
71 case Aop("/", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ i"idiv" |
|
72 case Aop("%", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ i"irem" |
|
73 case If(b, a1, a2) => { |
93 case If(b, a1, a2) => { |
74 val if_else = Fresh("If_else") |
94 val if_else = Fresh("If_else") |
75 val if_end = Fresh("If_end") |
95 val if_end = Fresh("If_end") |
76 compile_bexpT(b, env, if_else) ++ |
96 compile_bexpT(b, env, if_else) ++ |
77 compile_expT(a1, env, name) ++ |
97 compile_expT(a1, env, name) ++ |
139 def compile(prog: List[Decl], class_name: String) : String = { |
159 def compile(prog: List[Decl], class_name: String) : String = { |
140 val instructions = prog.map(compile_decl).mkString |
160 val instructions = prog.map(compile_decl).mkString |
141 (library + instructions).replaceAllLiterally("XXX", class_name) |
161 (library + instructions).replaceAllLiterally("XXX", class_name) |
142 } |
162 } |
143 |
163 |
|
164 import ammonite.ops._ |
|
165 |
|
166 def compile_to_file(prog: List[Decl], class_name: String) : Unit = |
|
167 write.over(pwd / s"$class_name.j", compile(prog, class_name)) |
|
168 |
|
169 def compile_and_run(prog: List[Decl], class_name: String) : Unit = { |
|
170 println(s"Start of compilation") |
|
171 compile_to_file(prog, class_name) |
|
172 println(s"generated $class_name.j file") |
|
173 os.proc("java", "-jar", "jasmin.jar", s"$class_name.j").call() |
|
174 println(s"generated $class_name.class file") |
|
175 println(s"Run program") |
|
176 os.proc("java", s"${class_name}/${class_name}").call(stdout = os.Inherit) |
|
177 println(s"done.") |
|
178 } |
|
179 |
144 |
180 |
145 @main |
181 @main |
146 def main(fname: String) = { |
182 def main(fname: String) = { |
147 val path = os.pwd / fname |
183 val path = os.pwd / fname |
148 val class_name = fname.stripSuffix("." ++ path.ext) |
184 val class_name = fname.stripSuffix("." ++ path.ext) |
149 val tks = tokenise(os.read(path)) |
185 val tks = tokenise(os.read(path)) |
150 val ast = parse_tks(tks) |
186 val ast = parse_tks(tks) |
151 println(compile(ast, class_name)) |
187 println(compile(ast, class_name)) |
152 } |
188 } |
153 |
189 |
154 /* |
190 @main |
155 |
191 def run(fname: String) = { |
156 import scala.sys.process._ |
192 val path = os.pwd / fname |
157 |
193 val class_name = fname.stripSuffix("." ++ path.ext) |
158 def compile_run(class_name: String) : Unit = { |
194 val tks = tokenise(os.read(path)) |
159 compile_file(class_name) |
195 val ast = parse_tks(tks) |
160 (s"java -jar jvm/jasmin-2.4/jasmin.jar ${class_name}.j").!! |
196 compile_and_run(ast, class_name) |
161 println("Time: " + time_needed(2, (s"java ${class_name}/${class_name}").!)) |
|
162 } |
197 } |
163 |
|
164 |
|
165 //examples |
|
166 compile_run("defs") |
|
167 compile_run("fact") |
|
168 */ |
|