-
-
Save hsak/35629 to your computer and use it in GitHub Desktop.
ftdop3
This file contains 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 characters
/* | |
* Copyright (c) 2008 h_sakurai, freecluster.net. All rights reserved. | |
* | |
* ftdop3.scala | |
* Functional Top Down Operator Precedence | |
* This program is Tiny programming language C Like eXpression Processor (TCLXP). | |
* | |
*/ | |
package ftdop3 | |
import scala.util.matching.Regex | |
import scala.collection.mutable.HashMap | |
class Env { | |
var e:HashMap[Any, Any] = new HashMap | |
var parent:Env = null | |
def apply(a:Any):Any = { | |
if (e.contains(a)) e(a) | |
else if(parent != null)parent(a) | |
else null | |
} | |
def +(kv : (Any, Any)) : Env = { | |
e + kv | |
this | |
} | |
} | |
object main { | |
def main(argv:Array[String]) { | |
println(parse(argv(0))) | |
println(eval(argv(0))) | |
} | |
// c like expression reader | |
def parse(src:String) = { | |
var str = src | |
var connectf = true | |
val tokens = for(i <- Stream.from(0)) yield { | |
def t ():Any = { | |
val num = """^([0-9]+)(.*$)""".r | |
val ptn = """^([-\+*\/\=<]+|[\:\(\)\[\]\{\},]|[^-\+*\/\(\)\[\]\{\}\s\=\;\:<,]+|$)(.*$)""".r | |
val eol = """^(;)(.*$)""".r | |
val spc1 = """^[\s]*[\r\n]+[\s]*(.*$)""".r | |
val spc = """^[\s]+(.*$)""".r | |
val eof = """^[\s]*($)""".r | |
str match { | |
case eol(a,e) => str = e; connectf = false; a | |
case eof(e) => str = ""; Nil | |
case num(a,e) => str = e; a.toInt | |
case ptn(a,e) => str = e; a | |
case spc1(e) => str = e; connectf = false; t() | |
case spc(e) => str = e; t() | |
case _ => throw new Error("error") | |
} | |
} | |
connectf = true | |
t() | |
} | |
val eox:(Any => Int) = { | |
case ")" => 1 | |
case "}" => 1 | |
case "]" => 1 | |
case Nil => 1 | |
case _ => -1 | |
} | |
val infixs:(Any => Int) = { | |
case "*" => 20 | |
case "/" => 20 | |
case "-" => 10 | |
case "+" => 10 | |
case "<=" => 6 | |
case "==" => 5 | |
case "," => 1 | |
case "else" => 3 | |
case _ => -1 | |
} | |
val infixrs:(Any => Int) = { | |
case "=" => 5 | |
case _ => -1 | |
} | |
val prefixs:(Any => Int) = { | |
case "-" => 100 | |
case _ => -1 | |
} | |
val postfixs:(Any => Int) = { | |
case "++" => 100 | |
case ";" => 0 | |
case _ => -1 | |
} | |
val parens:(Any => Int) = { | |
case "(" => 100 | |
case "{" => 100 | |
case "[" => 100 | |
case _ => -1 | |
} | |
val endParens:(Any => Any) = { | |
case "(" => ")" | |
case "{" => "}" | |
case "[" => "]" | |
case _ => Nil | |
} | |
val sts:( (Any, Any) => Int ) = { | |
case ("if","(") => 2 | |
case ("fun","(") => 2 | |
case _ => -1 | |
} | |
sealed case class AS(a:Any, s:Stream[Any]) | |
def eat(t:Any)(as:AS):AS = as.s match { | |
case cons(x,xs) if(x==t) => AS(x, xs) | |
case _ => throw new Error("error") | |
} | |
val cons = Stream.cons | |
def exp(p:Int)(as:AS):AS = { | |
//println("exp("+p+")("+as+")"); | |
as match { | |
case AS(null, cons(p1, xs)) if (p < parens(p1)) => | |
val AS(y, ys) = exp(0)(AS(null, xs)) | |
val AS(p2, zs) = eat(endParens(p1))(AS(null, ys)) | |
exp(p)(AS((p1,y,p2),zs)) | |
case AS(null, cons(op, xs)) if (p < prefixs(op)) => | |
val AS(y, ys) = exp(prefixs(op))(AS(null, xs)) | |
exp(p)(AS((op,y),ys)) | |
case AS(null, cons(x, xs)) => exp(p)(AS(x, xs)) | |
case AS(x, cons(p1, xs)) if (0 < sts(x,p1)) => | |
val AS(y, ys) = exp(0)(AS(null, xs)) | |
val AS(p2, zs) = eat(endParens(p1))(AS(null, ys)) | |
val AS(w, ws) = exp(sts(x,p1))(AS(null, zs)) | |
exp(p)(AS((x,p1,y,p2,w), ws)) | |
case AS(x, cons(p1, xs)) | |
if (sts(x,p1) < 0 && p < parens(p1) && connectf) => | |
val AS(y, ys) = exp(0)(AS(null, xs)) | |
val AS(p2, zs) = eat(endParens(p1))(AS(null, ys)) | |
exp(p)(AS((x,p1,y,p2), zs)) | |
case AS(x, cons(op, xs)) if (p <= postfixs(op) && postfixs(op) == 0) => | |
val AS(y, ys) = exp(0)(AS(null, xs)) | |
if(y==null)AS((x,op),xs) | |
else exp(0)(AS(((x,op), "@", y), ys)) | |
case AS(x, cons(op, xs)) if (p <= postfixs(op)) => | |
AS((x,op),xs) | |
case AS(x, cons(op, xs)) if (p < infixs(op)) => | |
val AS(y, ys) = exp(infixs(op))(AS(null, xs)) | |
exp(p)(AS((x, op, y), ys)) | |
case AS(x, cons(op, xs)) if (p <=infixrs(op))=> | |
val AS(y, ys) = exp(infixrs(op))(AS(null, xs)) | |
exp(p)(AS((x, op, y), ys)) | |
case AS(_, cons(x,xs)) if(eox(x)>0) => as | |
case AS(null, xs) => as | |
case AS(x, xs) if(xs == Nil) => as | |
case AS(x, xs) if (p <= 0) => | |
val AS(y, ys) = exp(0)(AS(null, xs)) | |
if(y != Nil) exp(0)(AS((x, "@", y), ys)) | |
else AS(x, xs) | |
case as => as | |
} | |
} | |
exp(0)(AS(null, tokens)).a | |
} | |
def eval(s:String):Any = try { | |
eval(parse(s),new Env) | |
} catch { | |
case e => println(e);-1 | |
} | |
case class Fun(prms:Any,body:Any,e:Env) { | |
override def toString():String = { | |
return "Fun("+prms+","+body+")" | |
} | |
} | |
// c like expression evaluator | |
def eval(a:Any, e:Env):Any = { | |
//println("eval("+a+")"); | |
a match { | |
case (a,"=",b) => val r = eval(b,e); e + (a -> r); r | |
case (a,"==",b) => if(eval(a,e) == eval(b,e))-1 else 0 | |
case (a,"<=",b) => (eval(a,e),eval(b,e)) match { | |
case (a:Int, b:Int) => if(a <= b) -1 else 0 | |
case (a1, b1) => throw new Error("unknown "+a +"<= "+ b +" -> " + a1 + "<= "+ b1) | |
} | |
case (a,"++") => val r = e(a); e + (a -> (r.asInstanceOf[Int] + 1)); r | |
case (a,"@", b) => eval(a, e); eval(b, e) | |
case ("print","(", a,")") => val r = eval(a, e); println(r);r | |
case (a,"(",b,")") => | |
(eval(a,e),eval(b,e)) match { | |
case (a:Int,b:Int) => | |
eval(a, e).asInstanceOf[Int] + eval(b, e).asInstanceOf[Int] | |
case (Fun(a, body, e),b) => | |
// arguments bind | |
var e2 = new Env | |
e2.parent = e | |
def bind(a:Any,b:Any) { | |
(a,b) match { | |
case ((a,",",as),(b,",",bs)) => e2 + (a -> b); bind(as,bs) | |
case (a,b)=> e2 + (a -> b) | |
} | |
} | |
bind(a, b) | |
eval(body, e2) | |
} | |
case (a,"{",b,"}") => eval(a, e).asInstanceOf[Int] * eval(b, e).asInstanceOf[Int] | |
case (a,"[",b,"]") => eval(a, e).asInstanceOf[Int] - eval(b, e).asInstanceOf[Int] | |
case ("(",a,")") => eval(a, e) | |
case ("{",a,"}") => eval(a, e) | |
case (a,"+",b) => eval(a, e).asInstanceOf[Int] + eval(b, e).asInstanceOf[Int] | |
case (a,"*",b) => eval(a, e).asInstanceOf[Int] * eval(b, e).asInstanceOf[Int] | |
case (a,"-",b) => eval(a, e).asInstanceOf[Int] - eval(b, e).asInstanceOf[Int] | |
case (a,"/",b) => eval(a, e).asInstanceOf[Int] / eval(b, e).asInstanceOf[Int] | |
case (a,",",b) => (eval(a, e),",",eval(b,e)) | |
case ("-",a) => -(eval(a, e).asInstanceOf[Int]) | |
case (a, ";") => eval(a, e) | |
case ("if","(",a,")",(b,"else",c)) => if(eval(a,e) != 0) eval(b, e) else eval(c, e) | |
case ("if","(",a,")", b) => if(eval(a, e) != 0) eval(b, e) else 0 | |
case ("fun","(",a,")",b) => val rc = Fun(a,b,e); rc | |
case a:Fun => a | |
case a:String => e(a) | |
case a:Int => a | |
case a => throw new Error("runtime error " + a) | |
}} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment