diff -r 8d0af38389bc -r 6709fa87410b progs/fun.scala --- a/progs/fun.scala Sun Jul 28 14:24:46 2019 +0100 +++ b/progs/fun.scala Sun Jul 28 16:15:03 2019 +0100 @@ -1,3 +1,6 @@ +// A Small Compiler for a Simple Functional Language +// (includes a lexer and a parser) + import scala.language.implicitConversions import scala.language.reflectiveCalls import scala.util._ @@ -7,196 +10,245 @@ def fromFile(name: String) : String = io.Source.fromFile(name).mkString + abstract class Rexp -case object NULL extends Rexp -case object EMPTY extends Rexp +case object ZERO extends Rexp +case object ONE extends Rexp case class CHAR(c: Char) extends Rexp case class ALT(r1: Rexp, r2: Rexp) extends Rexp -case class RANGE(cs: List[Char]) extends Rexp case class SEQ(r1: Rexp, r2: Rexp) extends Rexp -case class PLUS(r: Rexp) extends Rexp case class STAR(r: Rexp) extends Rexp -case class NTIMES(r: Rexp, n: Int) extends Rexp -case class NUPTOM(r: Rexp, n: Int, m: Int) extends Rexp - -object RANGE { - def apply(s: String) : RANGE = RANGE(s.toList) -} -def NMTIMES(r: Rexp, n: Int, m: Int) = { - if (m < n) throw new IllegalArgumentException("the number m cannot be smaller than n.") - else NUPTOM(r, n, m - n) -} - -case class NOT(r: Rexp) extends Rexp -case class OPT(r: Rexp) extends Rexp - +case class RECD(x: String, r: Rexp) extends Rexp + +abstract class Val +case object Empty extends Val +case class Chr(c: Char) extends Val +case class Sequ(v1: Val, v2: Val) extends Val +case class Left(v: Val) extends Val +case class Right(v: Val) extends Val +case class Stars(vs: List[Val]) extends Val +case class Rec(x: String, v: Val) extends Val + // some convenience for typing in regular expressions -def charlist2rexp(s : List[Char]) : Rexp = s match { - case Nil => EMPTY +def charlist2rexp(s : List[Char]): Rexp = s match { + case Nil => ONE case c::Nil => CHAR(c) case c::s => SEQ(CHAR(c), charlist2rexp(s)) } -implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) +implicit def string2rexp(s : String) : Rexp = + charlist2rexp(s.toList) -implicit def RexpOps (r: Rexp) = new { +implicit def RexpOps(r: Rexp) = new { def | (s: Rexp) = ALT(r, s) def % = STAR(r) def ~ (s: Rexp) = SEQ(r, s) } -implicit def stringOps (s: String) = new { +implicit def stringOps(s: String) = new { def | (r: Rexp) = ALT(s, r) def | (r: String) = ALT(s, r) def % = STAR(s) def ~ (r: Rexp) = SEQ(s, r) def ~ (r: String) = SEQ(s, r) + def $ (r: Rexp) = RECD(s, r) } - -// nullable function: tests whether the regular -// expression can recognise the empty string def nullable (r: Rexp) : Boolean = r match { - case NULL => false - case EMPTY => true + case ZERO => false + case ONE => true case CHAR(_) => false case ALT(r1, r2) => nullable(r1) || nullable(r2) case SEQ(r1, r2) => nullable(r1) && nullable(r2) case STAR(_) => true - case PLUS(r) => nullable(r) - case NTIMES(r, i) => if (i == 0) true else nullable(r) - case NUPTOM(r, i, j) => if (i == 0) true else nullable(r) - case RANGE(_) => false - case NOT(r) => !(nullable(r)) - case OPT(_) => true + case RECD(_, r1) => nullable(r1) } -// derivative of a regular expression w.r.t. a character def der (c: Char, r: Rexp) : Rexp = r match { - case NULL => NULL - case EMPTY => NULL - case CHAR(d) => if (c == d) EMPTY else NULL + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) case SEQ(r1, r2) => if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) else SEQ(der(c, r1), r2) case STAR(r) => SEQ(der(c, r), STAR(r)) - case PLUS(r) => SEQ(der(c, r), STAR(r)) - case NTIMES(r, i) => - if (i == 0) NULL else der(c, SEQ(r, NTIMES(r, i - 1))) - case NUPTOM(r, i, j) => - if (i == 0 && j == 0) NULL else - if (i == 0) ALT(der(c, NTIMES(r, j)), der(c, NUPTOM(r, 0, j - 1))) - else der(c, SEQ(r, NUPTOM(r, i - 1, j))) - case RANGE(cs) => if (cs contains c) EMPTY else NULL - case NOT(r) => NOT(der (c, r)) - case OPT(r) => der(c, r) + case RECD(_, r1) => der(c, r1) +} + + +// extracts a string from value +def flatten(v: Val) : String = v match { + case Empty => "" + case Chr(c) => c.toString + case Left(v) => flatten(v) + case Right(v) => flatten(v) + case Sequ(v1, v2) => flatten(v1) + flatten(v2) + case Stars(vs) => vs.map(flatten).mkString + case Rec(_, v) => flatten(v) } -def zeroable (r: Rexp) : Boolean = r match { - case NULL => true - case EMPTY => false - case CHAR(_) => false - case ALT(r1, r2) => zeroable(r1) && zeroable(r2) - case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) - case STAR(_) => false - case PLUS(r) => zeroable(r) - case NTIMES(r, i) => if (i == 0) false else zeroable(r) - case NUPTOM(r, i, j) => if (i == 0) false else zeroable(r) - case RANGE(_) => false - case NOT(r) => !(zeroable(r)) // bug: incorrect definition for NOT - case OPT(_) => false +// extracts an environment from a value; +// used for tokenise a string +def env(v: Val) : List[(String, String)] = v match { + case Empty => Nil + case Chr(c) => Nil + case Left(v) => env(v) + case Right(v) => env(v) + case Sequ(v1, v2) => env(v1) ::: env(v2) + case Stars(vs) => vs.flatMap(env) + case Rec(x, v) => (x, flatten(v))::env(v) } -// derivative w.r.t. a string (iterates der) -def ders (s: List[Char], r: Rexp) : Rexp = s match { - case Nil => r - case c::s => ders(s, der(c, r)) +// The Injection Part of the lexer + +// calculates a value for how a nullable regex +// matches the empty string +def mkeps(r: Rexp) : Val = r match { + case ONE => Empty + case ALT(r1, r2) => + if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) + case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) + case STAR(r) => Stars(Nil) + case RECD(x, r) => Rec(x, mkeps(r)) +} + +// injects back a character into a value +def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { + case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) + case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) + case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) + case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) + case (CHAR(d), Empty) => Chr(c) + case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) } -// regular expressions for the While language -val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_".toList) -val DIGIT = RANGE("0123456789".toList) +// some "rectification" functions for simplification +def F_ID(v: Val): Val = v +def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) +def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) +def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Right(v) => Right(f2(v)) + case Left(v) => Left(f1(v)) +} +def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) +} +def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = + (v:Val) => Sequ(f1(Empty), f2(v)) +def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = + (v:Val) => Sequ(f1(v), f2(Empty)) +def F_RECD(f: Val => Val) = (v:Val) => v match { + case Rec(x, v) => Rec(x, f(v)) +} +def F_ERROR(v: Val): Val = throw new Exception("error") + +// simplification of regular expressions returns now also +// an rectification function; no simplification under STAR +def simp(r: Rexp): (Rexp, Val => Val) = r match { + case ALT(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (ZERO, _) => (r2s, F_RIGHT(f2s)) + case (_, ZERO) => (r1s, F_LEFT(f1s)) + case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) + else (ALT (r1s, r2s), F_ALT(f1s, f2s)) + } + } + case SEQ(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (ZERO, _) => (ZERO, F_ERROR) + case (_, ZERO) => (ZERO, F_ERROR) + case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) + case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) + case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) + } + } + case RECD(x, r1) => { + val (r1s, f1s) = simp(r1) + (RECD(x, r1s), F_RECD(f1s)) + } + case r => (r, F_ID) +} + +// lexing functions including simplification +def lex_simp(r: Rexp, s: List[Char]) : Val = s match { + case Nil => if (nullable(r)) mkeps(r) else { println ("Lexing Error") ; sys.exit(-1) } + case c::cs => { + val (r_simp, f_simp) = simp(der(c, r)) + inj(r, c, f_simp(lex_simp(r_simp, cs))) + } +} + +def lexing_simp(r: Rexp, s: String) = env(lex_simp(r, s.toList)) + + +// The Lexing Rules for the Fun Language + +def PLUS(r: Rexp) = r ~ r.% + +val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | + "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | + "w" | "x" | "y" | "z" | "T" | "_" +val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" val ID = SYM ~ (SYM | DIGIT).% val NUM = PLUS(DIGIT) val KEYWORD : Rexp = "if" | "then" | "else" | "write" | "def" val SEMI: Rexp = ";" -val COMMA: Rexp = "," -val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<=" | "=>" | "<" | ">" | "%" | "=" | "/" +val OP: Rexp = "=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" val WHITESPACE = PLUS(" " | "\n" | "\t") val RPAREN: Rexp = ")" val LPAREN: Rexp = "(" +val COMMA: Rexp = "," val ALL = SYM | DIGIT | OP | " " | ":" | ";" | "\"" | "=" | "," | "(" | ")" val ALL2 = ALL | "\n" val COMMENT = ("/*" ~ ALL2.% ~ "*/") | ("//" ~ ALL.% ~ "\n") -// token for While language + +val WHILE_REGS = (("k" $ KEYWORD) | + ("i" $ ID) | + ("o" $ OP) | + ("n" $ NUM) | + ("s" $ SEMI) | + ("c" $ COMMA) | + ("pl" $ LPAREN) | + ("pr" $ RPAREN) | + ("w" $ (WHITESPACE | COMMENT))).% + + + +// The tokens for the While language + abstract class Token -case object T_WHITESPACE extends Token case object T_SEMI extends Token case object T_COMMA extends Token case object T_LPAREN extends Token case object T_RPAREN extends Token -case object T_COMMENT extends Token case class T_ID(s: String) extends Token case class T_OP(s: String) extends Token -case class T_NUM(s: String) extends Token +case class T_NUM(n: Int) extends Token case class T_KWD(s: String) extends Token -case class T_ERR(s: String) extends Token // special error token - -type TokenFun = String => Token -type LexRules = List[(Rexp, TokenFun)] -val While_lexing_rules: LexRules = - List((KEYWORD, (s) => T_KWD(s)), - (ID, (s) => T_ID(s)), - (COMMENT, (s) => T_COMMENT), - (OP, (s) => T_OP(s)), - (NUM, (s) => T_NUM(s)), - (SEMI, (s) => T_SEMI), - (COMMA, (s) => T_COMMA), - (LPAREN, (s) => T_LPAREN), - (RPAREN, (s) => T_RPAREN), - (WHITESPACE, (s) => T_WHITESPACE)) +val token : PartialFunction[(String, String), Token] = { + case ("k", s) => T_KWD(s) + case ("i", s) => T_ID(s) + case ("o", s) => T_OP(s) + case ("n", s) => T_NUM(s.toInt) + case ("s", _) => T_SEMI + case ("c", _) => T_COMMA + case ("pl", _) => T_LPAREN + case ("pr", _) => T_RPAREN +} -// calculates derivatives until all of them are zeroable -@tailrec -def munch(s: List[Char], - pos: Int, - rs: LexRules, - last: Option[(Int, TokenFun)]): Option[(Int, TokenFun)] = { - rs match { - case Nil => last - case rs if (s.length <= pos) => last - case rs => { - val ders = rs.map({case (r, tf) => (der(s(pos), r), tf)}) - val rs_nzero = ders.filterNot({case (r, _) => zeroable(r)}) - val rs_nulls = ders.filter({case (r, _) => nullable(r)}) - val new_last = if (rs_nulls != Nil) Some((pos, rs_nulls.head._2)) else last - munch(s, 1 + pos, rs_nzero, new_last) - } -}} - -// iterates the munching function and returns a Token list -def tokenize(s: String, rs: LexRules) : List[Token] = munch(s.toList, 0, rs, None) match { - case None if (s == "") => Nil - case None => List(T_ERR(s"Lexing error: $s")) - case Some((n, tf)) => { - val (head, tail) = s.splitAt(n + 1) - tf(head)::tokenize(tail, rs) - } -} - -def tokenizer(s:String) : List[Token] = - tokenize(s, While_lexing_rules).filter { - case T_ERR(s) => { println(s); sys.exit(-1) } - case T_WHITESPACE => false - case T_COMMENT => false - case _ => true - } - +def tokenise(s: String) : List[Token] = + lexing_simp(WHILE_REGS, s).collect(token) // Parser - Abstract syntax trees @@ -213,7 +265,7 @@ case class Var(s: String) extends Exp case class Num(i: Int) extends Exp case class Aop(o: String, a1: Exp, a2: Exp) extends Exp -case class Sequ(e1: Exp, e2: Exp) extends Exp +case class Sequence(e1: Exp, e2: Exp) extends Exp case class Bop(o: String, a1: Exp, a2: Exp) extends BExp @@ -225,14 +277,14 @@ case Var(_) => 1 case Num(_) => 1 case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) - case Sequ(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max + case Sequence(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max } def max_stack_bexp(e: BExp): Int = e match { case Bop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2) } // Parser combinators -abstract class Parser[I <% Seq[_], T] { +abstract class Parser[I, T](implicit ev: I => Seq[_]) { def parse(ts: I): Set[(T, I)] def parse_all(ts: I) : Set[T] = @@ -240,25 +292,40 @@ def parse_single(ts: I) : T = parse_all(ts).toList match { case List(t) => t - case _ => { println ("Parse Error") ; sys.exit(-1) } + case _ => { println ("Parse Error\n") ; sys.exit(-1) } } } -class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { +class SeqParser[I, T, S](p: => Parser[I, T], + q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, (T, S)] { def parse(sb: I) = for ((head1, tail1) <- p.parse(sb); (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) } -class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { +class AltParser[I, T](p: => Parser[I, T], + q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] { def parse(sb: I) = p.parse(sb) ++ q.parse(sb) } -class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { +class FunParser[I, T, S](p: => Parser[I, T], + f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] { def parse(sb: I) = for ((head, tail) <- p.parse(sb)) yield (f(head), tail) } +implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new { + def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) + def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) + def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) +} + +def ListParser[I, T, S](p: => Parser[I, T], + q: => Parser[I, S])(implicit ev: I => Seq[_]): Parser[I, List[T]] = { + (p ~ q ~ ListParser(p, q)) ==> { case ((x, y), z) => x :: z : List[T] } || + (p ==> ((s) => List(s))) +} + case class TokParser(tok: Token) extends Parser[List[Token], Token] { def parse(ts: List[Token]) = ts match { case t::ts if (t == tok) => Set((t, ts)) @@ -268,9 +335,15 @@ implicit def token2tparser(t: Token) = TokParser(t) +implicit def TokOps(t: Token) = new { + def || (q : => Parser[List[Token], Token]) = new AltParser[List[Token], Token](t, q) + def ==>[S] (f: => Token => S) = new FunParser[List[Token], Token, S](t, f) + def ~[S](q : => Parser[List[Token], S]) = new SeqParser[List[Token], Token, S](t, q) +} + case object NumParser extends Parser[List[Token], Int] { def parse(ts: List[Token]) = ts match { - case T_NUM(s)::ts => Set((s.toInt, ts)) + case T_NUM(n)::ts => Set((n, ts)) case _ => Set () } } @@ -283,28 +356,13 @@ } -implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { - def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) - def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) - def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) -} -implicit def TokOps(t: Token) = new { - def || (q : => Parser[List[Token], Token]) = new AltParser[List[Token], Token](t, q) - def ==>[S] (f: => Token => S) = new FunParser[List[Token], Token, S](t, f) - def ~[S](q : => Parser[List[Token], S]) = new SeqParser[List[Token], Token, S](t, q) -} +// Grammar Rules -def ListParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]): Parser[I, List[T]] = { - (p ~ q ~ ListParser(p, q)) ==> { case ((x, y), z) => x :: z : List[T] } || - (p ==> ((s) => List(s))) -} - - -// expressions +// arithmetic expressions lazy val Exp: Parser[List[Token], Exp] = (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Exp ~ T_KWD("else") ~ Exp) ==> { case (((((x, y), z), u), v), w) => If(y, u, w): Exp } || - (M ~ T_SEMI ~ Exp) ==> { case ((x, y), z) => Sequ(x, z): Exp } || M + (M ~ T_SEMI ~ Exp) ==> { case ((x, y), z) => Sequence(x, z): Exp } || M lazy val M: Parser[List[Token], Exp] = (T_KWD("write") ~ L) ==> { case (x, y) => Write(y): Exp } || L lazy val L: Parser[List[Token], Exp] = @@ -372,87 +430,100 @@ x ++ "_" ++ counter.toString() } -type Mem = Map[String, Int] -type Instrs = List[String] +// convenient string interpolations +// for instructions, labels and methods +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +implicit def sring_inters(sc: StringContext) = new { + def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" + def l(args: Any*): String = sc.s(args:_*) ++ ":\n" + def m(args: Any*): String = sc.s(args:_*) ++ "\n" +} + -def compile_exp(a: Exp, env : Mem) : Instrs = a match { - case Num(i) => List("ldc " + i.toString + "\n") - case Var(s) => List("iload " + env(s).toString + "\n") - case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("iadd\n") - case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("isub\n") - case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("imul\n") - case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("idiv\n") - case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("irem\n") +type Env = Map[String, Int] + +// compile expressions +def compile_exp(a: Exp, env : Env) : String = a match { + case Num(i) => i"ldc $i" + case Var(s) => i"iload ${env(s)}" + case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"iadd" + case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"isub" + case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"imul" + case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"idiv" + case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"irem" case If(b, a1, a2) => { val if_else = Fresh("If_else") val if_end = Fresh("If_end") compile_bexp(b, env, if_else) ++ compile_exp(a1, env) ++ - List("goto " + if_end + "\n") ++ - List("\n" + if_else + ":\n\n") ++ + i"goto $if_end" ++ + l"$if_else" ++ compile_exp(a2, env) ++ - List("\n" + if_end + ":\n\n") + l"$if_end" } - case Call(n, args) => { + case Call(name, args) => { val is = "I" * args.length - args.flatMap(a => compile_exp(a, env)) ++ - List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") + args.map(a => compile_exp(a, env)).mkString ++ + i"invokestatic XXX/XXX/$name($is)I" } - case Sequ(a1, a2) => { - compile_exp(a1, env) ++ List("pop\n") ++ compile_exp(a2, env) + case Sequence(a1, a2) => { + compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env) } case Write(a1) => { compile_exp(a1, env) ++ - List("dup\n", - "invokestatic XXX/XXX/write(I)V\n") + i"dup" ++ + i"invokestatic XXX/XXX/write(I)V" } } -def compile_bexp(b: BExp, env : Mem, jmp: String) : Instrs = b match { +// compile boolean expressions +def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { case Bop("==", a1, a2) => - compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpne " + jmp + "\n") + compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp" case Bop("!=", a1, a2) => - compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpeq " + jmp + "\n") + compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpeq $jmp" case Bop("<", a1, a2) => - compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpge " + jmp + "\n") + compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp" case Bop("<=", a1, a2) => - compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpgt " + jmp + "\n") + compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp" } -def compile_decl(d: Decl) : Instrs = d match { +// compile function for declarations and main +def compile_decl(d: Decl) : String = d match { case Def(name, args, a) => { val env = args.zipWithIndex.toMap val is = "I" * args.length - List(".method public static " + name + "(" + is + ")I \n", - ".limit locals " + args.length.toString + "\n", - ".limit stack " + (1 + max_stack_exp(a)).toString + "\n", - name + "_Start:\n") ++ + m".method public static $name($is)I" ++ + m".limit locals ${args.length.toString}" ++ + m".limit stack ${1 + max_stack_exp(a)}" ++ + l"${name}_Start" ++ compile_exp(a, env) ++ - List("ireturn\n", - ".end method \n\n") + i"ireturn" ++ + m".end method\n" } case Main(a) => { - List(".method public static main([Ljava/lang/String;)V\n", - ".limit locals 200\n", - ".limit stack 200\n") ++ + m".method public static main([Ljava/lang/String;)V" ++ + m".limit locals 200" ++ + m".limit stack 200" ++ compile_exp(a, Map()) ++ - List("invokestatic XXX/XXX/write(I)V\n", - "return\n", - ".end method\n") + i"invokestatic XXX/XXX/write(I)V" ++ + i"return" ++ + m".end method\n" } } + def compile(class_name: String, input: String) : String = { - val tks = tokenizer(input) + val tks = tokenise(input) println(Prog.parse_single(tks).mkString("\n")) val ast = Prog.parse_single(tks) - val instructions = ast.flatMap(compile_decl).mkString + val instructions = ast.map(compile_decl).mkString (library + instructions).replaceAllLiterally("XXX", class_name) } - - def compile_file(file_name: String) = { val class_name = file_name.split('.')(0) val output = compile(class_name, fromFile(file_name)) @@ -471,12 +542,12 @@ def compile_run(file_name: String) : Unit = { val class_name = file_name.split('.')(0) compile_file(file_name) - val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!! - println("Time: " + time_needed(2, ("java " + class_name + "/" + class_name).!)) + val test = (s"java -jar jvm/jasmin-2.4/jasmin.jar ${class_name}.j").!! + println("Time: " + time_needed(2, (s"java ${class_name}/${class_name}").!)) } -//examples +// some examples compile_file("fact.rec") -//compile_run("defs.rec") -//compile_run("fact.rec") +compile_run("defs.rec") +compile_run("fact.rec")