diff -r 141041fc76b5 -r 824ffbf66ab4 progs/fun.scala --- a/progs/fun.scala Mon Dec 02 03:57:48 2013 +0000 +++ b/progs/fun.scala Mon Dec 02 19:26:45 2013 +0000 @@ -4,6 +4,9 @@ import scala.annotation.tailrec import scala.sys.process._ +def fromFile(name: String) : String = + io.Source.fromFile(name).mkString + abstract class Rexp case object NULL extends Rexp case object EMPTY extends Rexp @@ -116,37 +119,31 @@ val DIGIT = RANGE("0123456789") val ID = SYM ~ (SYM | DIGIT).% val NUM = PLUS(DIGIT) -val KEYWORD : Rexp = "if" | "then" | "else" | "read" | "write" | "def" +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 BEGIN: Rexp = "{" -val END: Rexp = "}" val ALL = SYM | DIGIT | OP | " " | ":" | ";" | "\"" | "=" | "," | "(" | ")" val ALL2 = ALL | "\n" -val COMMENT2 = ("/*" ~ NOT(ALL.% ~ "*/" ~ ALL.%) ~ "*/") +//val COMMENT2 = ("/*" ~ NOT(ALL.% ~ "*/" ~ ALL.%) ~ "*/") val COMMENT = ("/*" ~ ALL2.% ~ "*/") | ("//" ~ ALL.% ~ "\n") -val STRING = "\"" ~ ALL.% ~ "\"" -// token for While languag +// token for 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_BEGIN extends Token -case object T_END 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_KWD(s: String) extends Token -case class T_STRING(s: String) extends Token case class T_ERR(s: String) extends Token // special error token @@ -162,9 +159,6 @@ (COMMA, (s) => T_COMMA), (LPAREN, (s) => T_LPAREN), (RPAREN, (s) => T_RPAREN), - (BEGIN, (s) => T_BEGIN), - (END, (s) => T_END), - (STRING, (s) => T_STRING(s.drop(1).dropRight(1))), (WHITESPACE, (s) => T_WHITESPACE)) @@ -204,14 +198,7 @@ case _ => true } -def fromFile(name: String) : String = - io.Source.fromFile(name).mkString -// tokenizer tests -//println(tokenizer(fromFile("loops.while")).mkString("\n")) -//println(tokenizer(fromFile("fib.while")).mkString("\n")) -//println(tokenizer(fromFile("collatz.while")).mkString("\n")) -//println(tokenizer(fromFile("defs.rec")).mkString("\n")) // Parser - Abstract syntax trees abstract class Exp @@ -223,17 +210,30 @@ case class Call(name: String, args: List[Exp]) extends Exp case class If(a: BExp, e1: Exp, e2: Exp) extends Exp -case class Read(s: String) extends Exp -case class Write(s: String) extends Exp -case class WriteS(s: String) extends Exp +case class Write(e: Exp) extends Exp 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 object True extends BExp -case object False extends BExp case class Bop(o: String, a1: Exp, a2: Exp) extends BExp +// calculating the maximal needed stack size +def max_stack_exp(e: Exp): Int = e match { + case Call(_, args) => args.map(max_stack_exp).sum + case If(a, e1, e2) => max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e1)).max) + case Write(e) => max_stack_exp(e) + 1 + 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 +} +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] { def parse(ts: I): Set[(T, I)] @@ -285,12 +285,6 @@ } } -case object StringParser extends Parser[List[Token], String] { - def parse(ts: List[Token]) = ts match { - case T_STRING(s)::ts => Set((s, ts)) - case _ => Set () - } -} implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) @@ -309,12 +303,14 @@ } -// arithmetic expressions +// expressions lazy val Exp: Parser[List[Token], Exp] = - (IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN) ==> - { case (((x, y), z), w) => Call(x, z): 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 +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] = (T ~ T_OP("+") ~ Exp) ==> { case ((x, y), z) => Aop("+", x, z): Exp } || (T ~ T_OP("-") ~ Exp) ==> { case ((x, y), z) => Aop("-", x, z): Exp } || T lazy val T: Parser[List[Token], Exp] = @@ -322,6 +318,8 @@ (F ~ T_OP("/") ~ T) ==> { case ((x, y), z) => Aop("/", x, z): Exp } || (F ~ T_OP("%") ~ T) ==> { case ((x, y), z) => Aop("%", x, z): Exp } || F lazy val F: Parser[List[Token], Exp] = + (IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN) ==> + { case (((x, y), z), w) => Call(x, z): Exp } || (T_LPAREN ~ Exp ~ T_RPAREN) ==> { case ((x, y), z) => y: Exp } || IdParser ==> { case x => Var(x): Exp } || NumParser ==> { case x => Num(x): Exp } @@ -332,8 +330,8 @@ (Exp ~ T_OP("!=") ~ Exp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || (Exp ~ T_OP("<") ~ Exp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || (Exp ~ T_OP(">") ~ Exp) ==> { case ((x, y), z) => Bop("<", z, x): BExp } || - (T_KWD("true") ==> ((_) => True)) || - (T_KWD("false") ==> ((_) => False: BExp)) + (Exp ~ T_OP("<=") ~ Exp) ==> { case ((x, y), z) => Bop("<=", x, z): BExp } || + (Exp ~ T_OP("=>") ~ Exp) ==> { case ((x, y), z) => Bop("<=", z, x): BExp } lazy val Defn: Parser[List[Token], Decl] = (T_KWD("def") ~ IdParser ~ T_LPAREN ~ ListParser(IdParser, T_COMMA) ~ T_RPAREN ~ T_OP("=") ~ Exp) ==> @@ -345,13 +343,6 @@ // parser examples -val p11 = """def zero(x) = 0""" -val p11_toks = tokenizer(p11) -val p11_ast = Defn.parse_all(p11_toks) -//println(p11_toks) -//println(p11_ast) - - val p12_toks = tokenizer(fromFile("defs.rec")) val p12_ast = Prog.parse_all(p12_toks) //println(p12_toks.mkString(",")) @@ -363,7 +354,7 @@ // copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html // -val beginning = """ +val library = """ .class public XXX.XXX .super java/lang/Object @@ -383,60 +374,6 @@ return .end method -.method public static writes(Ljava/lang/String;)V - .limit stack 2 - .limit locals 2 - getstatic java/lang/System/out Ljava/io/PrintStream; - aload 0 - invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V - return -.end method - -.method public static read()I - .limit locals 10 - .limit stack 10 - - ldc 0 - istore 1 ; this will hold our final integer -Label1: - getstatic java/lang/System/in Ljava/io/InputStream; - invokevirtual java/io/InputStream/read()I - istore 2 - iload 2 - ldc 10 ; the newline delimiter - isub - ifeq Label2 - iload 2 - ldc 32 ; the space delimiter - isub - ifeq Label2 - - iload 2 - ldc 48 ; we have our digit in ASCII, have to subtract it from 48 - isub - ldc 10 - iload 1 - imul - iadd - istore 1 - goto Label1 -Label2: - ;when we come here we have our integer computed in Local Variable 1 - iload 1 - ireturn -.end method - -.method public static main([Ljava/lang/String;)V - .limit locals 200 - .limit stack 200 - -""" - -val ending = """ - - return - -.end method """ // for generating new labels @@ -447,15 +384,17 @@ x ++ "_" ++ counter.toString() } -type Mem = Map[String, String] +type Mem = Map[String, Int] type Instrs = List[String] 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) + "\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") case If(b, a1, a2) => { val if_else = Fresh("If_else") val if_end = Fresh("If_end") @@ -466,35 +405,115 @@ compile_exp(a2, env) ++ List("\n" + if_end + ":\n\n") } - case Call(n, args) => + case Call(n, args) => { + val is = "I" * args.length args.flatMap(a => compile_exp(a, env)) ++ - List ("invokestatic XXX/XXX/" + n + "(I)I\n") - + List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") + } + case Sequ(a1, a2) => { + compile_exp(a1, env) ++ List("pop\n") ++ compile_exp(a2, env) + } + case Write(a1) => { + compile_exp(a1, env) ++ + List("dup\n", + "invokestatic XXX/XXX/write(I)V\n") + } } def compile_bexp(b: BExp, env : Mem, jmp: String) : Instrs = b match { - case True => Nil - case False => List("goto " + jmp + "\n") - case Bop("=", a1, a2) => + case Bop("==", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpne " + jmp + "\n") case Bop("!=", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpeq " + jmp + "\n") case Bop("<", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpge " + jmp + "\n") + case Bop("<=", a1, a2) => + compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpgt " + jmp + "\n") } +def compile_expT(a: Exp, env : Mem, name: String) : 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_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("iadd\n") + case Aop("-", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("isub\n") + case Aop("*", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("imul\n") + case Aop("/", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("idiv\n") + case Aop("%", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("irem\n") + case If(b, a1, a2) => { + val if_else = Fresh("If_else") + val if_end = Fresh("If_end") + compile_bexp(b, env, if_else) ++ + compile_expT(a1, env, name) ++ + List("goto " + if_end + "\n") ++ + List("\n" + if_else + ":\n\n") ++ + compile_expT(a2, env, name) ++ + List("\n" + if_end + ":\n\n") + } + case Call(n, args) => if (name == n) { + val stores = args.zipWithIndex.map { case (x, y) => "istore " + y.toString + "\n" } + args.flatMap(a => compile_expT(a, env, "")) ++ + stores.reverse ++ + List ("goto " + n + "_Start\n") + } else { + val is = "I" * args.length + args.flatMap(a => compile_expT(a, env, "")) ++ + List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") + } + case Sequ(a1, a2) => { + compile_expT(a1, env, "") ++ List("pop\n") ++ compile_expT(a2, env, name) + } + case Write(a1) => { + compile_expT(a1, env, "") ++ + List("dup\n", + "invokestatic XXX/XXX/write(I)V\n") + } +} + +def compile_bexpT(b: BExp, env : Mem, jmp: String) : Instrs = b match { + case Bop("==", a1, a2) => + compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpne " + jmp + "\n") + case Bop("!=", a1, a2) => + compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpeq " + jmp + "\n") + case Bop("<", a1, a2) => + compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpge " + jmp + "\n") + case Bop("<=", a1, a2) => + compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpgt " + jmp + "\n") +} + def compile_decl(d: Decl) : Instrs = d match { - case Def(name, args, a) => Nil - case Main(a) => compile_exp(a, Map()) + 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") ++ + //compile_exp(a, env) ++ + compile_expT(a, env, name) ++ + List("ireturn\n", + ".end method \n\n") + } + case Main(a) => { + val main_begin = + List(".method public static main([Ljava/lang/String;)V\n", + ".limit locals 200\n", + ".limit stack 200\n") + val main_end = + List("invokestatic XXX/XXX/write(I)V\n", + "return\n", + ".end method\n") + main_begin ++ compile_exp(a, Map()) ++ main_end + } } def compile(class_name: String, input: String) : String = { val tks = tokenizer(input) + //println(Prog.parse(tks)) val ast = Prog.parse_single(tks) val instructions = ast.flatMap(compile_decl).mkString - (instructions).replaceAllLiterally("XXX", class_name) + (library + instructions).replaceAllLiterally("XXX", class_name) } @@ -513,18 +532,14 @@ (end - start)/(i * 1.0e9) } - def compile_run(file_name: String) : Unit = { val class_name = file_name.split('.')(0) compile_file(file_name) - println(fromFile("defs.j")) - //val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!! - //("java " + class_name + "/" + class_name).! + val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!! + println("Time: " + time_needed(2, ("java " + class_name + "/" + class_name).!)) } //examples -//println(compile("test", p9)) -//compile_run("loops.while") compile_run("defs.rec") -//compile_run("test.while") +//compile_run("fact.rec")