1 // A Small Compiler for a Simple Functional Language |
1 // A Small Compiler for a Simple Functional Language |
2 // (it does not include a parser and lexer) |
2 // (it does not include a parser and lexer) |
3 // |
3 // |
4 // call with |
4 // call with |
5 // |
5 // |
6 // amm fun.sc |
6 // amm fun.sc main defs.fun |
7 // |
7 // |
8 // this will print out the JVM instructions for two |
8 // amm fun.sc main fact.fun |
|
9 // |
|
10 // or |
|
11 // amm fun.sc test |
|
12 // |
|
13 // the latter will print out the JVM instructions for two |
9 // factorial functions |
14 // factorial functions |
10 |
15 |
|
16 import $file.fun_tokens, fun_tokens._ |
|
17 import $file.fun_parser, fun_parser._ |
11 |
18 |
12 // abstract syntax trees |
|
13 abstract class Exp |
|
14 abstract class BExp |
|
15 abstract class Decl |
|
16 |
|
17 // functions and declarations |
|
18 case class Def(name: String, args: List[String], body: Exp) extends Decl |
|
19 case class Main(e: Exp) extends Decl |
|
20 |
|
21 // expressions |
|
22 case class Call(name: String, args: List[Exp]) extends Exp |
|
23 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
|
24 case class Write(e: Exp) extends Exp |
|
25 case class Var(s: String) extends Exp |
|
26 case class Num(i: Int) extends Exp |
|
27 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
|
28 case class Sequ(e1: Exp, e2: Exp) extends Exp |
|
29 |
|
30 // boolean expressions |
|
31 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
|
32 |
19 |
33 // calculating the maximal needed stack size |
20 // calculating the maximal needed stack size |
34 def max_stack_exp(e: Exp): Int = e match { |
21 def max_stack_exp(e: Exp): Int = e match { |
35 case Call(_, args) => args.map(max_stack_exp).sum |
22 case Call(_, args) => args.map(max_stack_exp).sum |
36 case If(a, e1, e2) => |
23 case If(a, e1, e2) => |
37 max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e2)).max) |
24 max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e2)).max) |
38 case Write(e) => max_stack_exp(e) + 1 |
25 case Write(e) => max_stack_exp(e) + 1 |
39 case Var(_) => 1 |
26 case Var(_) => 1 |
40 case Num(_) => 1 |
27 case Num(_) => 1 |
41 case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) |
28 case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) |
42 case Sequ(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max |
29 case Sequence(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max |
43 } |
30 } |
|
31 |
44 def max_stack_bexp(e: BExp): Int = e match { |
32 def max_stack_bexp(e: BExp): Int = e match { |
45 case Bop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) |
33 case Bop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) |
46 } |
34 } |
47 |
35 |
48 // compiler - built-in functions |
36 // compiler - built-in functions |
110 case Call(name, args) => { |
98 case Call(name, args) => { |
111 val is = "I" * args.length |
99 val is = "I" * args.length |
112 args.map(a => compile_exp(a, env)).mkString ++ |
100 args.map(a => compile_exp(a, env)).mkString ++ |
113 i"invokestatic XXX/XXX/$name($is)I" |
101 i"invokestatic XXX/XXX/$name($is)I" |
114 } |
102 } |
115 case Sequ(a1, a2) => { |
103 case Sequence(a1, a2) => { |
116 compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env) |
104 compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env) |
117 } |
105 } |
118 case Write(a1) => { |
106 case Write(a1) => { |
119 compile_exp(a1, env) ++ |
107 compile_exp(a1, env) ++ |
120 i"dup" ++ |
108 i"dup" ++ |
190 If(Bop("==",Var("n"),Num(0)), |
178 If(Bop("==",Var("n"),Num(0)), |
191 Var("acc"), |
179 Var("acc"), |
192 Call("facT",List(Aop("-",Var("n"),Num(1)), |
180 Call("facT",List(Aop("-",Var("n"),Num(1)), |
193 Aop("*",Var("n"),Var("acc")))))), |
181 Aop("*",Var("n"),Var("acc")))))), |
194 |
182 |
195 Main(Sequ(Write(Call("fact",List(Num(10)))), |
183 Main(Sequence(Write(Call("fact",List(Num(10)))), |
196 Write(Call("facT",List(Num(10), Num(1))))))) |
184 Write(Call("facT",List(Num(10), Num(1))))))) |
197 |
185 |
198 // prints out the JVM instructions |
186 // prints out the JVM instructions |
199 @main |
187 @main |
200 def test() = |
188 def test() = |
201 println(compile(test_prog, "fact")) |
189 println(compile(test_prog, "fact")) |
|
190 |
|
191 |
|
192 @main |
|
193 def main(fname: String) = { |
|
194 val path = os.pwd / fname |
|
195 val class_name = fname.stripSuffix("." ++ path.ext) |
|
196 val tks = tokenise(os.read(path)) |
|
197 val ast = parse_tks(tks) |
|
198 println(compile(ast, class_name)) |
|
199 } |