--- 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")