Skip to content

Instantly share code, notes, and snippets.

@kmizu
Forked from kishida/MiniParser.scala
Created November 14, 2011 16:22

Revisions

  1. Kota Mizushima revised this gist Nov 14, 2011. 1 changed file with 15 additions and 0 deletions.
    15 changes: 15 additions & 0 deletions Example.mini
    Original 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))
  2. Kota Mizushima revised this gist Nov 14, 2011. 1 changed file with 113 additions and 79 deletions.
    192 changes: 113 additions & 79 deletions MiniParser.scala
    Original 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 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

    val visitor = new ExprVisitor
    var result = visitor.eval(new Environment(None), ast);
    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(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))
    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:Any){
    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 ExprVisitor{
    def eval(env:Environment, ast:AST):Any = {
    def visit(ast:AST):Any = {
    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(Unit:Any){(result, x) => eval(local, x)}
    exprs.foldLeft(UnitValue:Value){(result, x) => eval(local, x)}
    }
    case IfExpr(cond, pos, neg) =>{
    visit(cond) match{
    case true => visit(pos)
    case false => visit(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 (lval:Int, rval:Int) => lval < rval
    (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 (lval:Int, rval:Int) => lval + rval
    case (lval:String, rval) => lval + rval
    case (lval, rval:String) => lval + rval
    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 (lval:Int, rval:Int) => lval - rval
    case (IntValue(lval), IntValue(rval)) => IntValue(lval - rval)
    case _ => sys.error("Runtime Error!")
    }
    }
    case MulOp(left, right) =>{
    (visit(left), visit(right)) match{
    case (lval:Int, rval:Int) => lval * rval
    case (IntValue(lval), IntValue(rval)) => IntValue(lval * rval)
    case _ => sys.error("Runtime Error!")
    }
    }
    case IntVal(value) => value
    case StringVal(value) => value
    case IntVal(value) => IntValue(value)
    case StringVal(value) => StringValue(value)
    case PrintLine(value) => {
    val v = visit(value);
    println(v);
    println(v);
    v
    }
    case Ident(name) => {
    env.get(name)
    }
    case Assignment(vr, value) =>{
    val v = visit(value)
    env.set(vr, v)
    }
    case FuncDef(name, func) =>{
    env.set(name, func)
    }
    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 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)
    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 | assignment | funcDef
    def line: Parser[AST] = expr | val_declaration | funcDef
    //expr ::= cond | if | printLine
    def expr: Parser[AST] = condOp|ifExpr|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,
    def condOp: Parser[AST] = chainl1(add,
    "<"^^{op => (left:AST, right:AST) => LessOp(left, right)})
    //add ::= term {"+" term | "-" term}.
    def add: Parser[AST] = chainl1(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,
    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 |
    "("~>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] = "\""~>"""[a-zA-Z0-9:*/+\- ]*""".r<~"\""^^StringVal
    //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] = "val"~>ident~"="~expr^^{
    case v~_~value => Assignment(v.name, value)
    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(for(pm <- p) yield{pm.name}, proc))
    FuncDef(v.name, Func(p.map{_.name}, proc))
    }
    }

    def parse(str:String) = parseAll(lines, str)
    }

  3. @kishida kishida revised this gist Nov 14, 2011. 1 changed file with 61 additions and 15 deletions.
    76 changes: 61 additions & 15 deletions MiniParser.scala
    Original file line number Diff line number Diff line change
    @@ -7,16 +7,19 @@ 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);
    def twice(x) = x * 2;
    println("twice 3:" + twice(3));
    def rec(x) = {
    if(0 < x){
    println(x);
    rec(x - 1)
    }else{
    0
    }
    };
    println("post block:" + aa);
    println(bb);
    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.name, v)
    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: Ident, value: AST) 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

    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(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}^^Ident
    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, value)
    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)
    }

  4. @kishida kishida revised this gist Nov 11, 2011. 1 changed file with 32 additions and 37 deletions.
    69 changes: 32 additions & 37 deletions MiniParser.scala
    Original file line number Diff line number Diff line change
    @@ -7,30 +7,37 @@ 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)));
    val aa = 23;
    aa * 2
    println("pre block:" + aa);
    {
    val aa = 4;
    println("in block:" + aa);
    val bb = 3;
    println(bb);
    };
    println("post block:" + aa);
    println(bb);
    """
    /*
    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)
    var result = visitor.eval(new Environment(None), ast);
    }
    }

    class Environment{
    class Environment(parent:Option[Environment]){
    val variables = Map[String, Any]()
    def get(key:String) = {
    variables(key)
    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) = {
    def eval(env:Environment, ast:AST):Any = {
    def visit(ast:AST):Any = {
    ast match{
    case Lines(exprs) =>{
    var result:Any = Unit
    for(x <- exprs){
    result = visit(x)
    }
    result
    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, v)
    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: String, value: AST) 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(";")^^{
    values => Lines(values)
    }
    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<~")"^^{ x=>x } | "{"~>lines<~"}"^^{x=>x}
    "("~>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<~"\""^^{
    value => StringVal(value)
    }
    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}^^
    {
    value => Ident(value)
    }
    case n if n != "if" && n!= "val" && n!= "println" => n}^^Ident
    def assignment:Parser[Assignment] = "val"~>ident~"="~expr^^{
    case v~_~value => Assignment(v.name, value)
    case v~_~value => Assignment(v, value)
    }
    // printLine ::= "printLn" "(" expr ")"
    def printLine: Parser[AST] = "println"~"("~>expr<~")"^^{
    value => PrintLine(value)
    }
    def printLine: Parser[AST] = "println"~"("~>expr<~")"^^PrintLine

    def parse(str:String) = parseAll(lines, str)
    }
  5. @kishida kishida revised this gist Nov 10, 2011. 1 changed file with 84 additions and 48 deletions.
    132 changes: 84 additions & 48 deletions MiniParser.scala
    Original 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)));
    12+6;
    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.visit(ast);
    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 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
    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(expr, ";")<~opt(";")^^{
    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 |
    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)
  6. @kishida kishida revised this gist Nov 8, 2011. 1 changed file with 26 additions and 6 deletions.
    32 changes: 26 additions & 6 deletions MiniParser.scala
    Original 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 = "\"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 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{
    //expr ::= cond | if
    //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 | "(" expr ")"
    def factor: Parser[AST] = intLiteral | stringLiteral | "("~>expr<~")"^^{
    x=>x}
    //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(expr, str)
    def parse(str:String) = parseAll(lines, str)
    }

  7. @kishida kishida revised this gist Nov 7, 2011. 1 changed file with 21 additions and 4 deletions.
    25 changes: 21 additions & 4 deletions MiniParser.scala
    Original 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 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 ::= add
    def expr: Parser[AST] = condOp|ifExpr
    //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 | "("~>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)
    }
  8. @kishida kishida revised this gist Nov 7, 2011. 1 changed file with 22 additions and 3 deletions.
    25 changes: 22 additions & 3 deletions MiniParser.scala
    Original 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 = "12-5*3+7*(2+5)*1+0"
    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] = add
    //expr ::= term {"+" term | "-" term}.
    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)})
  9. @kishida kishida revised this gist Nov 7, 2011. 1 changed file with 12 additions and 21 deletions.
    33 changes: 12 additions & 21 deletions MiniParser.scala
    Original file line number Diff line number Diff line change
    @@ -17,25 +17,21 @@ object Main {
    }
    }

    trait Visitor{
    def visit(ast:AST):Any
    }

    class ExprVisitor extends Visitor{
    class ExprVisitor{
    def visit(ast:AST):Any = {
    ast match{
    case AddOp(left, right) =>{
    (left.accept(this), right.accept(this)) match{
    (visit(left), visit(right)) match{
    case (lval:Int, rval:Int) => lval + rval
    }
    }
    case SubOp(left, right) =>{
    (left.accept(this), right.accept(this)) match{
    (visit(left), visit(right)) match{
    case (lval:Int, rval:Int) => lval - rval
    }
    }
    case MulOp(left, right) =>{
    (left.accept(this), right.accept(this)) match{
    (visit(left), visit(right)) match{
    case (lval:Int, rval:Int) => lval * rval
    }
    }
    @@ -44,12 +40,7 @@ class ExprVisitor extends Visitor{
    }
    }

    trait AST{
    def accept(visitor:Visitor) = {
    visitor.visit(this)
    }
    }

    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,
    "+"^^{case op => (left:AST, right:AST) => AddOp(left, right)}|
    "-"^^{case op => (left:AST, right:AST) => SubOp(left, right)})
    "+"^^{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,
    "*"^^{case op => (left:AST, right:AST) => MulOp(left, right)})
    "*"^^{op => (left:AST, right:AST) => MulOp(left, right)})
    //factor ::= intLiteral | "(" expr ")"
    def factor: Parser[AST] = intLiteral | "("~>expr<~")"^^(
    x=>x)
    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 intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{
    value => IntVal(value.toInt)}

    def parse(str:String) = parseAll(expr, str)
    }
  10. @kishida kishida revised this gist Nov 7, 2011. 1 changed file with 60 additions and 36 deletions.
    96 changes: 60 additions & 36 deletions MiniParser.scala
    Original 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
    println(parser.parse("12-5*3+7*(2+5)+0"))
    val ast = parser.parse(expr).get

    val visitor = new ExprVisitor
    var result = visitor.visit(ast);

    println(result)
    }
    }

    trait Visitor{
    def visit(ast:AST):Any
    }

    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)}
    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
    }
    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)}
    case SubOp(left, right) =>{
    (left.accept(this), right.accept(this)) match{
    case (lval:Int, rval:Int) => lval - rval
    }
    ast
    }
    case MulOp(left, right) =>{
    (left.accept(this), right.accept(this)) match{
    case (lval:Int, rval:Int) => lval * rval
    }
    }
    case IntVal(value) => value
    }
    //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)
    }
    }

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

  11. @kishida kishida revised this gist Nov 7, 2011. 1 changed file with 31 additions and 10 deletions.
    41 changes: 31 additions & 10 deletions MiniParser.scala
    Original file line number Diff line number Diff line change
    @@ -10,22 +10,43 @@ object Main {
    }

    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)
    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[Any] = add
    //expr ::= term ["+" term | "-" term}.
    def add: Parser[Any] = term~rep("+"~term|"-"~term)
    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[Any] = factor~rep("*"~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[Any] = intLiteral | "("~expr~")"
    def factor: Parser[AST] = intLiteral | "("~expr~")"^^{
    case _~exp~_ => exp
    }
    //intLiteral ::= ["1"-"9"] {"0"-"9"}
    def intLiteral : Parser[Any] = """[1-9][0-9]*|0""".r
    def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{
    case value => IntVal(value.toInt)
    }

    def parse(str:String) = parseAll(expr, str)
    }
  12. @kishida kishida created this gist Nov 7, 2011.
    32 changes: 32 additions & 0 deletions MiniParser.scala
    Original 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)
    }
    }