Skip to content

Instantly share code, notes, and snippets.

Created November 30, 2008 13:58
Show Gist options
  • Save anonymous/30441 to your computer and use it in GitHub Desktop.
Save anonymous/30441 to your computer and use it in GitHub Desktop.
/*
* 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
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 "==" => 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 HashMap[Any, Any])
} catch {
case e => println(e);-1
}
case class Fun(prms:Any,body:Any,e:HashMap[Any,Any]) {
override def toString():String = {
return "Fun("+prms+","+body+")"
}
}
// c like expression evaluator
def eval(a:Any, e:HashMap[Any,Any]):Any = {println("eval("+a+")");a match {
case (a,"=",b) => val r = eval(b,e); e += a -> r; println("KKKe");r
case (a,"==",b) => if(eval(a,e) == eval(b,e))-1 else 0
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 (('Fun, a, e),"(",b,")") => {
}
case (a,"(",b,")") =>
eval(a,e) match {
case a:Int =>
eval(a, e).asInstanceOf[Int] + eval(b, e).asInstanceOf[Int]
case Fun(a, body, e) =>
// arguments bind
var e2 = new HashMap[Any,Any]
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) => -(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) => println("koko"); val rc = Fun(a,b,e); print("koko"); 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