Revisions
-
Kota Mizushima revised this gist
Nov 14, 2011 . 1 changed file with 15 additions and 0 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,15 @@ val factorial = (n) => { if(n < 2) 1 else (n * factorial(n - 1)); }; println("factorial(3) = " + factorial(3)); def mkcounter(n) = () => { n = n + 1; n }; val counter = mkcounter(6); println("counter() = " + counter()); println("counter() = " + counter()); val Y = (f) => ((proc) => f((arg) => (proc(proc))(arg)))((proc) => f((arg) => (proc(proc))(arg))); val fact = (f) => ((n) => if(n < 2) 1 else n * f(n - 1)); println("fact(5) = " + (Y(fact))(5)) -
Kota Mizushima revised this gist
Nov 14, 2011 . 1 changed file with 113 additions and 79 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -2,117 +2,125 @@ package miniparser import scala.util.parsing.combinator.RegexParsers import scala.collection.mutable.Map import java.io._ object Main { def main(args: Array[String]): Unit = { val parser = new MiniParser val (flag, ast) = args match { case Array("-e", line) => ("-e", parser.parse(line).get) case Array(fileName) => val in = new BufferedReader(new InputStreamReader(new FileInputStream(fileName))) try { val program = Iterator.continually(in.readLine()).takeWhile(_ != null).mkString("\r\n") parser.parse(program) match { case parser.Success(v, _) => ("-f", v) case parser.Failure(m, n) => sys.error(m) case parser.Error(m, n) => sys.error(m) } } finally { in.close() } } val interpreter = new Interpreter val result = interpreter.eval(new Environment(None), ast) flag match { case "-e" => println(result) case _ => } } } class Environment(val parent:Option[Environment]){ import Runtime._ val variables = Map[String, Value]() def apply(key: String): Value = { variables.get(key).getOrElse { parent.map(_.apply(key)).getOrElse { throw new Exception("symbol'%s' not found".format(key)) } } } def set(key: String, value: Value): Value = { def iset(optEnv: Option[Environment]): Unit = optEnv match { case Some(env) => if(env.variables.contains(key)) env(key) = value else iset(env.parent) case None => () } iset(Some(this)) value } def update(key: String, value: Value): Value = { variables(key) = value value } } class Interpreter { import Runtime._ def eval(env:Environment, ast:AST): Value = { def visit(ast:AST): Value = { ast match{ case Lines(exprs) =>{ val local = new Environment(Some(env)) exprs.foldLeft(UnitValue:Value){(result, x) => eval(local, x)} } case IfExpr(cond, pos, neg) =>{ visit(cond) match { case BooleanValue(true) => visit(pos) case BooleanValue(false) => visit(neg) case _ => sys.error("Runtime Error!") } } case LessOp(left, right) =>{ (visit(left), visit(right)) match { case (IntValue(lval), IntValue(rval)) => BooleanValue(lval < rval) case _ => sys.error("Runtime Error!") } } case AddOp(left, right) =>{ (visit(left), visit(right)) match{ case (IntValue(lval), IntValue(rval)) => IntValue(lval + rval) case (StringValue(lval), rval) => StringValue(lval + rval) case (lval, StringValue(rval)) => StringValue(lval + rval) case _ => sys.error("Runtime Error!") } } case SubOp(left, right) =>{ (visit(left), visit(right)) match{ case (IntValue(lval), IntValue(rval)) => IntValue(lval - rval) case _ => sys.error("Runtime Error!") } } case MulOp(left, right) =>{ (visit(left), visit(right)) match{ case (IntValue(lval), IntValue(rval)) => IntValue(lval * rval) case _ => sys.error("Runtime Error!") } } case IntVal(value) => IntValue(value) case StringVal(value) => StringValue(value) case PrintLine(value) => { val v = visit(value); println(v); v } case Ident(name) => env(name) case ValDeclaration(vr, value) => env(vr) = visit(value) case Assignment(vr, value) => env.set(vr, visit(value)) case func@Func(_, _) => FunctionValue(func, Some(env)) case FuncDef(name, func) => env(name) = FunctionValue(func, Some(env)) case FuncCall(func, params) =>{ visit(func) match{ case FunctionValue(Func(fparams, proc), cenv) => { val local = new Environment(cenv) (fparams zip params).foreach{ case (fp, ap) => local(fp) = visit(ap) } eval(local, proc) } case _ => sys.error("Runtime Error!") } } } @@ -121,6 +129,25 @@ class ExprVisitor{ } } object Runtime { sealed abstract class Value case class StringValue(value: String) extends Value { override def toString() = value } case class IntValue(value: Int) extends Value { override def toString() = value.toString } case class BooleanValue(value: Boolean) extends Value { override def toString() = value.toString } case class FunctionValue(value: Func, env: Option[Environment]) extends Value { override def toString() = "function" } case object UnitValue extends Value { override def toString() = "unit" } } trait AST case class Lines(exprs:List[AST]) extends AST case class IfExpr(cond:AST, pos:AST, neg:AST) extends AST @@ -133,6 +160,7 @@ case class PrintLine(value: AST) extends AST case class IntVal(value: Int) extends AST case class Ident(name: String) extends AST case class Assignment(variable: String, value: AST) extends AST case class ValDeclaration(variable: String, value: AST) extends AST case class Func(params:List[String], proc:AST) extends AST case class FuncDef(name: String, func: Func) extends AST @@ -142,22 +170,22 @@ class MiniParser extends RegexParsers{ //lines ::= expr {";" expr} [";"] def lines: Parser[AST] = repsep(line, ";")<~opt(";")^^Lines def line: Parser[AST] = expr | val_declaration | funcDef //expr ::= cond | if | printLine def expr: Parser[AST] = assignment|condOp|ifExpr|printLine //if ::= "if" "(" expr ")" expr "else" expr def ifExpr: Parser[AST] = "if"~"("~>expr~")"~expr~"else"~expr^^{ case cond~_~pos~_~neg => IfExpr(cond, pos, neg) } //cond ::= add {"<" add} def condOp: Parser[AST] = chainl1(add, "<"^^{op => (left:AST, right:AST) => LessOp(left, right)}) //add ::= term {"+" term | "-" term}. def add: Parser[AST] = chainl1(term, "+"^^{op => (left:AST, right:AST) => AddOp(left, right)}| "-"^^{op => (left:AST, right:AST) => SubOp(left, right)}) //term ::= factor {"*" factor} def term : Parser[AST] = chainl1(funcCall, "*"^^{op => (left:AST, right:AST) => MulOp(left, right)}) def funcCall: Parser[AST] = factor~opt("("~>repsep(expr, ",")<~")")^^{ case fac~param =>{ @@ -169,33 +197,39 @@ class MiniParser extends RegexParsers{ } //factor ::= intLiteral | stringLiteral | "(" expr ")" | "{" lines "}" def factor: Parser[AST] = intLiteral | stringLiteral | ident | anonFun | "("~>expr<~")" | "{"~>lines<~"}" //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{ value => IntVal(value.toInt)} //stringLiteral ::= "\"" {"a-zA-Z0-9.."} "\"" def stringLiteral : Parser[AST] = "\""~> """((?!")(\[rnfb"'\\]|[^\\]))*""".r <~"\"" ^^ StringVal def ident :Parser[Ident] = """[A-Za-z_][a-zA-Z0-9]*""".r^?{ case n if n != "if" && n!= "val" && n!= "println" && n != "def" => n}^^Ident def assignment: Parser[Assignment] = (ident <~ "=") ~ expr ^^ { case v ~ value => Assignment(v.name, value) } def val_declaration:Parser[ValDeclaration] = ("val" ~> ident <~ "=") ~ expr ^^ { case v ~ value => ValDeclaration(v.name, value) } // printLine ::= "printLn" "(" expr ")" def printLine: Parser[AST] = "println"~"("~>expr<~")"^^PrintLine def anonFun:Parser[AST] = (("(" ~> repsep(ident, ",") <~ ")") <~ "=>") ~ expr ^^ { case params ~ proc => Func(params.map{_.name}, proc) } def funcDef:Parser[FuncDef] = "def"~>ident~opt("("~>repsep(ident, ",")<~")")~"="~expr^^{ case v~params~_~proc => { val p = params match{ case Some(pr) => pr case None => Nil } FuncDef(v.name, Func(p.map{_.name}, proc)) } } def parse(str:String) = parseAll(lines, str) } -
kishida revised this gist
Nov 14, 2011 . 1 changed file with 61 additions and 15 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -7,16 +7,19 @@ object Main { def main(args: Array[String]): Unit = { val expr = """ def twice(x) = x * 2; println("twice 3:" + twice(3)); def rec(x) = { if(0 < x){ println(x); rec(x - 1) }else{ 0 } }; rec(3); val tw = twice; println("tw 5:" + tw(5)); """ val parser = new MiniParser val ast = parser.parse(expr).get @@ -93,7 +96,24 @@ class ExprVisitor{ } case Assignment(vr, value) =>{ val v = visit(value) env.set(vr, v) } case FuncDef(name, func) =>{ env.set(name, func) } case FuncCall(func, params) =>{ visit(func) match{ case f:Func => { val local = new Environment(Some(env)) var arg = params for(pn <- f.params){ val a::suc = arg local.set(pn, visit(a)) arg = suc } eval(local, f.proc) } } } } } @@ -112,12 +132,17 @@ case class StringVal(value: String) extends AST case class PrintLine(value: AST) extends AST case class IntVal(value: Int) extends AST case class Ident(name: String) extends AST case class Assignment(variable: String, value: AST) extends AST case class Func(params:List[String], proc:AST) extends AST case class FuncDef(name: String, func: Func) extends AST case class FuncCall(func:AST, params:List[AST]) extends AST class MiniParser extends RegexParsers{ //lines ::= expr {";" expr} [";"] def lines: Parser[AST] = repsep(line, ";")<~opt(";")^^Lines def line: Parser[AST] = expr | assignment | funcDef //expr ::= cond | if | printLine def expr: Parser[AST] = condOp|ifExpr|printLine //if ::= "if" "(" expr ")" expr "else" expr @@ -132,8 +157,17 @@ class MiniParser extends RegexParsers{ "+"^^{op => (left:AST, right:AST) => AddOp(left, right)}| "-"^^{op => (left:AST, right:AST) => SubOp(left, right)}) //term ::= factor {"*" factor} def term : Parser[AST] = chainl1(funcCall, "*"^^{op => (left:AST, right:AST) => MulOp(left, right)}) def funcCall: Parser[AST] = factor~opt("("~>repsep(expr, ",")<~")")^^{ case fac~param =>{ param match{ case Some(p) => FuncCall(fac, p) case None => fac } } } //factor ::= intLiteral | stringLiteral | "(" expr ")" | "{" lines "}" def factor: Parser[AST] = intLiteral | stringLiteral | ident | "("~>expr<~")" | "{"~>lines<~"}" @@ -142,14 +176,26 @@ class MiniParser extends RegexParsers{ value => IntVal(value.toInt)} //stringLiteral ::= "\"" {"a-zA-Z0-9.."} "\"" def stringLiteral : Parser[AST] = "\""~>"""[a-zA-Z0-9:*/+\- ]*""".r<~"\""^^StringVal def ident :Parser[Ident] = """[A-Za-z_][a-zA-Z0-9]*""".r^?{ case n if n != "if" && n!= "val" && n!= "println" && n != "def" => n}^^Ident def assignment:Parser[Assignment] = "val"~>ident~"="~expr^^{ case v~_~value => Assignment(v.name, value) } // printLine ::= "printLn" "(" expr ")" def printLine: Parser[AST] = "println"~"("~>expr<~")"^^PrintLine def funcDef:Parser[FuncDef] = "def"~>ident~opt("("~>repsep(ident, ",")<~")")~"="~expr^^{ case v~params~_~proc => { val p = params match{ case Some(pr) => pr case None => Nil } FuncDef(v.name, Func(for(pm <- p) yield{pm.name}, proc)) } } def parse(str:String) = parseAll(lines, str) } -
kishida revised this gist
Nov 11, 2011 . 1 changed file with 32 additions and 37 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -7,30 +7,37 @@ object Main { def main(args: Array[String]): Unit = { val expr = """ val aa = 23; println("pre block:" + aa); { val aa = 4; println("in block:" + aa); val bb = 3; println(bb); }; println("post block:" + aa); println(bb); """ val parser = new MiniParser val ast = parser.parse(expr).get val visitor = new ExprVisitor var result = visitor.eval(new Environment(None), ast); } } class Environment(parent:Option[Environment]){ val variables = Map[String, Any]() def get(key:String):Any = { if(variables.contains(key)){ variables(key) }else{ parent match{ case Some(p) => p.get(key) case None => throw new Exception("symbol'%s' not found".format(key)) } } } def set(key:String, value:Any){ variables(key) = value @@ -39,15 +46,12 @@ class Environment{ class ExprVisitor{ def eval(env:Environment, ast:AST):Any = { def visit(ast:AST):Any = { ast match{ case Lines(exprs) =>{ val local = new Environment(Some(env)) exprs.foldLeft(Unit:Any){(result, x) => eval(local, x)} } case IfExpr(cond, pos, neg) =>{ visit(cond) match{ @@ -89,7 +93,7 @@ class ExprVisitor{ } case Assignment(vr, value) =>{ val v = visit(value) env.set(vr.name, v) } } } @@ -108,13 +112,11 @@ case class StringVal(value: String) extends AST case class PrintLine(value: AST) extends AST case class IntVal(value: Int) extends AST case class Ident(name: String) extends AST case class Assignment(variable: Ident, value: AST) extends AST class MiniParser extends RegexParsers{ //lines ::= expr {";" expr} [";"] def lines: Parser[AST] = repsep(line, ";")<~opt(";")^^Lines def line: Parser[AST] = expr | assignment //expr ::= cond | if | printLine def expr: Parser[AST] = condOp|ifExpr|printLine @@ -134,26 +136,19 @@ class MiniParser extends RegexParsers{ "*"^^{op => (left:AST, right:AST) => MulOp(left, right)}) //factor ::= intLiteral | stringLiteral | "(" expr ")" | "{" lines "}" def factor: Parser[AST] = intLiteral | stringLiteral | ident | "("~>expr<~")" | "{"~>lines<~"}" //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{ value => IntVal(value.toInt)} //stringLiteral ::= "\"" {"a-zA-Z0-9.."} "\"" def stringLiteral : Parser[AST] = "\""~>"""[a-zA-Z0-9:*/+\- ]*""".r<~"\""^^StringVal def ident :Parser[Ident] = """[A-Za-z_][a-zA-Z0-9]*""".r^?{ case n if n != "if" && n!= "val" && n!= "println" => n}^^Ident def assignment:Parser[Assignment] = "val"~>ident~"="~expr^^{ case v~_~value => Assignment(v, value) } // printLine ::= "printLn" "(" expr ")" def printLine: Parser[AST] = "println"~"("~>expr<~")"^^PrintLine def parse(str:String) = parseAll(lines, str) } -
kishida revised this gist
Nov 10, 2011 . 1 changed file with 84 additions and 48 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,6 +1,7 @@ package miniparser import scala.util.parsing.combinator.RegexParsers import scala.collection.mutable.Map object Main { @@ -10,65 +11,89 @@ println("result: "+(3+(if ({ println("cond"); 3 < 5 }) println(12 * 2) else if(3+2) 15 + 3 else 0))); val aa = 23; aa * 2 """ /* println(A * 3) */ val parser = new MiniParser val ast = parser.parse(expr).get val visitor = new ExprVisitor var result = visitor.eval(new Environment(), ast); println(result) } } class Environment{ val variables = Map[String, Any]() def get(key:String) = { variables(key) } def set(key:String, value:Any){ variables(key) = value } } class ExprVisitor{ def eval(env:Environment, ast:AST) = { def visit(ast:AST):Any = { ast match{ case Lines(exprs) =>{ var result:Any = Unit for(x <- exprs){ result = visit(x) } result } case IfExpr(cond, pos, neg) =>{ visit(cond) match{ case true => visit(pos) case false => visit(neg) } } case LessOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval < rval } } case AddOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval + rval case (lval:String, rval) => lval + rval case (lval, rval:String) => lval + rval } } case SubOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval - rval } } case MulOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval * rval } } case IntVal(value) => value case StringVal(value) => value case PrintLine(value) => { val v = visit(value); println(v); v } case Ident(name) => { env.get(name) } case Assignment(vr, value) =>{ val v = visit(value) env.set(vr, v) } } } visit(ast) } } @@ -82,12 +107,15 @@ case class MulOp(left: AST, right:AST) extends AST case class StringVal(value: String) extends AST case class PrintLine(value: AST) extends AST case class IntVal(value: Int) extends AST case class Ident(name: String) extends AST case class Assignment(variable: String, value: AST) extends AST class MiniParser extends RegexParsers{ //lines ::= expr {";" expr} [";"] def lines: Parser[AST] = repsep(line, ";")<~opt(";")^^{ values => Lines(values) } def line: Parser[AST] = expr | assignment //expr ::= cond | if | printLine def expr: Parser[AST] = condOp|ifExpr|printLine //if ::= "if" "(" expr ")" expr "else" expr @@ -105,7 +133,7 @@ class MiniParser extends RegexParsers{ def term : Parser[AST] = chainl1(factor, "*"^^{op => (left:AST, right:AST) => MulOp(left, right)}) //factor ::= intLiteral | stringLiteral | "(" expr ")" | "{" lines "}" def factor: Parser[AST] = intLiteral | stringLiteral | ident | "("~>expr<~")"^^{ x=>x } | "{"~>lines<~"}"^^{x=>x} //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{ @@ -114,6 +142,14 @@ class MiniParser extends RegexParsers{ def stringLiteral : Parser[AST] = "\""~>"""[a-zA-Z0-9:*/+\- ]*""".r<~"\""^^{ value => StringVal(value) } def ident :Parser[Ident] = """[A-Za-z_][a-zA-Z0-9]*""".r^?{ case n if n != "if" && n!= "val" && n!= "println" => n}^^ { value => Ident(value) } def assignment:Parser[Assignment] = "val"~>ident~"="~expr^^{ case v~_~value => Assignment(v.name, value) } // printLine ::= "printLn" "(" expr ")" def printLine: Parser[AST] = "println"~"("~>expr<~")"^^{ value => PrintLine(value) -
kishida revised this gist
Nov 8, 2011 . 1 changed file with 26 additions and 6 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -5,7 +5,13 @@ import scala.util.parsing.combinator.RegexParsers object Main { def main(args: Array[String]): Unit = { val expr = """ println("result: "+(3+(if ({ println("cond"); 3 < 5 }) println(12 * 2) else if(3+2) 15 + 3 else 0))); 12+6; """ val parser = new MiniParser val ast = parser.parse(expr).get @@ -20,6 +26,13 @@ object Main { class ExprVisitor{ def visit(ast:AST):Any = { ast match{ case Lines(exprs) =>{ var result:Any = Unit for(x <- exprs){ result = visit(x) } result } case IfExpr(cond, pos, neg) =>{ visit(cond) match{ case true => visit(pos) @@ -60,6 +73,7 @@ class ExprVisitor{ } trait AST case class Lines(exprs:List[AST]) extends AST case class IfExpr(cond:AST, pos:AST, neg:AST) extends AST case class LessOp(left: AST, right:AST) extends AST case class AddOp(left: AST, right:AST) extends AST @@ -70,7 +84,11 @@ case class PrintLine(value: AST) extends AST case class IntVal(value: Int) extends AST class MiniParser extends RegexParsers{ //lines ::= expr {";" expr} [";"] def lines: Parser[AST] = repsep(expr, ";")<~opt(";")^^{ values => Lines(values) } //expr ::= cond | if | printLine def expr: Parser[AST] = condOp|ifExpr|printLine //if ::= "if" "(" expr ")" expr "else" expr def ifExpr: Parser[AST] = "if"~"("~>expr~")"~expr~"else"~expr^^{ @@ -86,19 +104,21 @@ class MiniParser extends RegexParsers{ //term ::= factor {"*" factor} def term : Parser[AST] = chainl1(factor, "*"^^{op => (left:AST, right:AST) => MulOp(left, right)}) //factor ::= intLiteral | stringLiteral | "(" expr ")" | "{" lines "}" def factor: Parser[AST] = intLiteral | stringLiteral | "("~>expr<~")"^^{ x=>x } | "{"~>lines<~"}"^^{x=>x} //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{ value => IntVal(value.toInt)} //stringLiteral ::= "\"" {"a-zA-Z0-9.."} "\"" def stringLiteral : Parser[AST] = "\""~>"""[a-zA-Z0-9:*/+\- ]*""".r<~"\""^^{ value => StringVal(value) } // printLine ::= "printLn" "(" expr ")" def printLine: Parser[AST] = "println"~"("~>expr<~")"^^{ value => PrintLine(value) } def parse(str:String) = parseAll(lines, str) } -
kishida revised this gist
Nov 7, 2011 . 1 changed file with 21 additions and 4 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -5,7 +5,7 @@ import scala.util.parsing.combinator.RegexParsers object Main { def main(args: Array[String]): Unit = { val expr = "\"result: \"+(3+(if (3 < 5) println(12 * 2) else if(3+2) 15 + 3 else 0))"//"12-5*3+7*(2+5)*1+0" val parser = new MiniParser val ast = parser.parse(expr).get @@ -34,6 +34,8 @@ class ExprVisitor{ case AddOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval + rval case (lval:String, rval) => lval + rval case (lval, rval:String) => lval + rval } } case SubOp(left, right) =>{ @@ -47,6 +49,12 @@ class ExprVisitor{ } } case IntVal(value) => value case StringVal(value) => value case PrintLine(value) => { val v = visit(value); println(v); v } } } } @@ -57,15 +65,18 @@ case class LessOp(left: AST, right:AST) extends AST case class AddOp(left: AST, right:AST) extends AST case class SubOp(left: AST, right:AST) extends AST case class MulOp(left: AST, right:AST) extends AST case class StringVal(value: String) extends AST case class PrintLine(value: AST) extends AST case class IntVal(value: Int) extends AST class MiniParser extends RegexParsers{ //expr ::= cond | if def expr: Parser[AST] = condOp|ifExpr|printLine //if ::= "if" "(" expr ")" expr "else" expr def ifExpr: Parser[AST] = "if"~"("~>expr~")"~expr~"else"~expr^^{ case cond~_~pos~_~neg => IfExpr(cond, pos, neg) } //cond ::= add {"<" add} def condOp: Parser[AST] = chainl1(add, "<"^^{op => (left:AST, right:AST) => LessOp(left, right)}) //add ::= term {"+" term | "-" term}. @@ -76,11 +87,17 @@ class MiniParser extends RegexParsers{ def term : Parser[AST] = chainl1(factor, "*"^^{op => (left:AST, right:AST) => MulOp(left, right)}) //factor ::= intLiteral | "(" expr ")" def factor: Parser[AST] = intLiteral | stringLiteral | "("~>expr<~")"^^{ x=>x} //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{ value => IntVal(value.toInt)} def stringLiteral : Parser[AST] = "\""~>"""[a-zA-Z0-9:*/+\- ]*""".r<~"\""^^{ value => StringVal(value) } def printLine: Parser[AST] = "println"~"("~>expr<~")"^^{ value => PrintLine(value) } def parse(str:String) = parseAll(expr, str) } -
kishida revised this gist
Nov 7, 2011 . 1 changed file with 22 additions and 3 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -5,7 +5,7 @@ import scala.util.parsing.combinator.RegexParsers object Main { def main(args: Array[String]): Unit = { val expr = "3+(if (3 < 5) 12 * 2 else if(3+2) 15 + 3 else 0)"//"12-5*3+7*(2+5)*1+0" val parser = new MiniParser val ast = parser.parse(expr).get @@ -20,6 +20,17 @@ object Main { class ExprVisitor{ def visit(ast:AST):Any = { ast match{ case IfExpr(cond, pos, neg) =>{ visit(cond) match{ case true => visit(pos) case false => visit(neg) } } case LessOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval < rval } } case AddOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval + rval @@ -41,15 +52,23 @@ class ExprVisitor{ } trait AST case class IfExpr(cond:AST, pos:AST, neg:AST) extends AST case class LessOp(left: AST, right:AST) extends AST case class AddOp(left: AST, right:AST) extends AST case class SubOp(left: AST, right:AST) extends AST case class MulOp(left: AST, right:AST) extends AST case class IntVal(value: Int) extends AST class MiniParser extends RegexParsers{ //expr ::= add def expr: Parser[AST] = condOp|ifExpr //if ::= "if" "(" expr ")" expr "else" expr def ifExpr: Parser[AST] = "if"~"("~>expr~")"~expr~"else"~expr^^{ case cond~_~pos~_~neg => IfExpr(cond, pos, neg) } def condOp: Parser[AST] = chainl1(add, "<"^^{op => (left:AST, right:AST) => LessOp(left, right)}) //add ::= term {"+" term | "-" term}. def add: Parser[AST] = chainl1(term, "+"^^{op => (left:AST, right:AST) => AddOp(left, right)}| "-"^^{op => (left:AST, right:AST) => SubOp(left, right)}) -
kishida revised this gist
Nov 7, 2011 . 1 changed file with 12 additions and 21 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -17,25 +17,21 @@ object Main { } } class ExprVisitor{ def visit(ast:AST):Any = { ast match{ case AddOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval + rval } } case SubOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval - rval } } case MulOp(left, right) =>{ (visit(left), visit(right)) match{ case (lval:Int, rval:Int) => lval * rval } } @@ -44,12 +40,7 @@ class ExprVisitor extends Visitor{ } } trait AST case class AddOp(left: AST, right:AST) extends AST case class SubOp(left: AST, right:AST) extends AST case class MulOp(left: AST, right:AST) extends AST @@ -60,17 +51,17 @@ class MiniParser extends RegexParsers{ def expr: Parser[AST] = add //expr ::= term {"+" term | "-" term}. def add: Parser[AST] = chainl1(term, "+"^^{op => (left:AST, right:AST) => AddOp(left, right)}| "-"^^{op => (left:AST, right:AST) => SubOp(left, right)}) //term ::= factor {"*" factor} def term : Parser[AST] = chainl1(factor, "*"^^{op => (left:AST, right:AST) => MulOp(left, right)}) //factor ::= intLiteral | "(" expr ")" def factor: Parser[AST] = intLiteral | "("~>expr<~")"^^{ x=>x} //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{ value => IntVal(value.toInt)} def parse(str:String) = parseAll(expr, str) } -
kishida revised this gist
Nov 7, 2011 . 1 changed file with 60 additions and 36 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -5,49 +5,73 @@ import scala.util.parsing.combinator.RegexParsers object Main { def main(args: Array[String]): Unit = { val expr = "12-5*3+7*(2+5)*1+0" val parser = new MiniParser val ast = parser.parse(expr).get val visitor = new ExprVisitor var result = visitor.visit(ast); println(result) } } trait Visitor{ def visit(ast:AST):Any } class ExprVisitor extends Visitor{ def visit(ast:AST):Any = { ast match{ case AddOp(left, right) =>{ (left.accept(this), right.accept(this)) match{ case (lval:Int, rval:Int) => lval + rval } } case SubOp(left, right) =>{ (left.accept(this), right.accept(this)) match{ case (lval:Int, rval:Int) => lval - rval } } case MulOp(left, right) =>{ (left.accept(this), right.accept(this)) match{ case (lval:Int, rval:Int) => lval * rval } } case IntVal(value) => value } } } trait AST{ def accept(visitor:Visitor) = { visitor.visit(this) } } case class AddOp(left: AST, right:AST) extends AST case class SubOp(left: AST, right:AST) extends AST case class MulOp(left: AST, right:AST) extends AST case class IntVal(value: Int) extends AST class MiniParser extends RegexParsers{ //expr ::= add def expr: Parser[AST] = add //expr ::= term {"+" term | "-" term}. def add: Parser[AST] = chainl1(term, "+"^^{case op => (left:AST, right:AST) => AddOp(left, right)}| "-"^^{case op => (left:AST, right:AST) => SubOp(left, right)}) //term ::= factor {"*" factor} def term : Parser[AST] = chainl1(factor, "*"^^{case op => (left:AST, right:AST) => MulOp(left, right)}) //factor ::= intLiteral | "(" expr ")" def factor: Parser[AST] = intLiteral | "("~>expr<~")"^^( x=>x) //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^( value => IntVal(value.toInt)) def parse(str:String) = parseAll(expr, str) } -
kishida revised this gist
Nov 7, 2011 . 1 changed file with 31 additions and 10 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -10,22 +10,43 @@ object Main { } trait AST case class AddOp(left: AST, right:AST) extends AST case class SubOp(left: AST, right:AST) extends AST case class MulOp(left: AST, right:AST) extends AST case class IntVal(value: Int) extends AST class MiniParser extends RegexParsers{ //expr ::= add def expr: Parser[AST] = add //expr ::= term {"+" term | "-" term}. def add: Parser[AST] = term~rep("+"~term|"-"~term)^^{ case left~rest => { var ast = left rest.foreach{ case "+"~right => {ast = AddOp(ast, right)} case "-"~right => {ast = SubOp(ast, right)} } ast } } //term ::= factor {"*" factor} def term : Parser[AST] = factor~rep("*"~factor)^^{ case left~rest => { var ast = left rest.foreach{ case _~right => {ast = MulOp(ast, right)} } ast } } //factor ::= intLiteral | "(" expr ")" def factor: Parser[AST] = intLiteral | "("~expr~")"^^{ case _~exp~_ => exp } //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{ case value => IntVal(value.toInt) } def parse(str:String) = parseAll(expr, str) } -
kishida created this gist
Nov 7, 2011 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,32 @@ package miniparser import scala.util.parsing.combinator.RegexParsers object Main { def main(args: Array[String]): Unit = { val parser = new MiniParser println(parser.parse("12-5*3+7*(2+5)+0")) } trait AST case class AddOp(left: AST, right:AST) case class SubOp(left: AST, right:AST) case class MulOp(left: AST, right:AST) case class IntVal(value: Int) class MiniParser extends RegexParsers{ //expr ::= add def expr: Parser[Any] = add //expr ::= term ["+" term | "-" term}. def add: Parser[Any] = term~rep("+"~term|"-"~term) //term ::= factor {"*" factor} def term : Parser[Any] = factor~rep("*"~factor) //factor ::= intLiteral | "(" expr ")" def factor: Parser[Any] = intLiteral | "("~expr~")" //intLiteral ::= ["1"-"9"] {"0"-"9"} def intLiteral : Parser[Any] = """[1-9][0-9]*|0""".r def parse(str:String) = parseAll(expr, str) } }