Instantly share code, notes, and snippets.

anonymous /calc3.scala
Created Oct 1, 2008

Embed
What would you like to do?
package calc3
import scala.util.matching.Regex
import lex._
/*
変更点
●コンパイルの効率化
 リスト同士の連結をやめて、::でリストを作成するように変更。
●usageを表示するように。
●パーサコンビネータとして扱えるような形にパーサを変更。
●エラーの箇所を出力(ただし1個)
●ストリームを使って、字句解析する。
●字句解析は別パッケージ
*/
sealed abstract class Atom
case class Var(value: Int) extends Atom
case class Add(left:Atom, right:Atom) extends Atom
case class Mul(left:Atom, right:Atom) extends Atom
case class Sub(left:Atom, right:Atom) extends Atom
case class Div(left:Atom, right:Atom) extends Atom
case class Void extends Atom
object main {
// パース ------------------------------
def parse(str:String):Atom = {
val cons = Stream.cons
// 構文解析 ------------------------
/**
* 予測されたトークンを取り除く
*/
def eat(as:(Atom,Stream[Token]))(eatToken:Token,eatStr:String) = {
var (a,stm) = as
if (stm.head==eatToken)
(a,stm.tail)
else
throw new Error("syntax error: found "+stm.head+" expected '"+eatStr+"'"+stm.head.err())
}
/**
* 数字あるいは( exp )
*/
def fact(as:(Atom,Stream[Token])):(Atom,Stream[Token]) = {
as match {
case (_,cons(lex.Num(i),t)) => (Var(i) , t)
case (a,cons(lex.Spr(), t)) => eat(exp(a,t))(lex.Epr(),")")
case (_,cons(a,_)) => throw new Error("syntax error:found "+a+" expected expression "+a.err())
}
}
/**
* 掛け算か、fact
*/
def term(as:(Atom,Stream[Token])):(Atom,Stream[Token]) = {
as match {
case (Void(), t) => term(fact((Void(),t)))
case (a, cons(lex.Mul(),t)) =>
val (b, t2) = fact((Void(),t))
term(Mul(a, b), t2)
case (a, cons(lex.Div(),t)) =>
val (b, t2) = fact((Void(),t))
term(Div(a, b), t2)
case _ => as
}
}
/**
* 足し算かterm
*/
def exp(as:(Atom,Stream[Token])):(Atom,Stream[Token]) = {
as match {
case (Void(), t) => exp(term((Void(),t)))
case (a, cons(lex.Add(),t)) =>
val (b, t2) = term((Void(),t))
exp(Add(a, b), t2)
case (a, cons(lex.Sub(),t)) =>
val (b, t2) = term((Void(),t))
exp(Sub(a, b), t2)
case _ => as
}
}
val tokens = new Lex(str).tokens();
val (a,t) = eat(exp((Void(),tokens)))(lex.Eof(),"Eof")
a
}
// コンパイラ ------------------------------------------
var i = -1
val VAL, ADD, SUB, MUL, DIV, RET = {i += 1; i}
def compile(a:Atom) = {
def comp(a:Atom,rtn:List[Int]):List[Int] = {
a match {
case Var(i) => i::VAL::rtn
case Add(a,b) => ADD :: comp(a,comp(b,rtn))
case Sub(a,b) => SUB :: comp(a,comp(b,rtn))
case Mul(a,b) => MUL :: comp(a,comp(b,rtn))
case Div(a,b) => DIV :: comp(a,comp(b,rtn))
case Void() => throw new Exception("compile time error")
}
}
(RET::comp(a,List())).reverse
}
// 仮想マシン ------------------------------------------
def eval(c:List[Int]):Int = {
def eval1(s:List[Int], c:List[Int]):Int = {
(s,c) match {
case (s, VAL::a::c) => eval1(a::s, c)//
case (a::b::s, ADD::c) => eval1((a+b)::s, c)// 足し算
case (a::b::s, SUB::c) => eval1((a-b)::s, c)// 引き算
case (a::b::s, MUL::c) => eval1((a*b)::s, c)// 掛け算
case (a::b::s, DIV::c) => eval1((a/b)::s, c)// 割り算
case (a::s, RET::c) => a// リターン
case (_, _) => throw new Exception("runtime error")
}
}
eval1(List():List[Int], c)
}
// メイン関数 ---------------------------------------
def main(args: Array[String]):Unit = {
try {
if(args.length <= 0)
throw new Exception("usage: scala calc3.main expression\nexp: scala calc3.main 1+2*3");
val a = parse(args(0))
println(a)
val codes = compile(a)
println(codes)
val result = eval(codes)
println(result)
} catch {
case e => println(e.getMessage() )
}
}
}
package lex
import scala.util.matching.Regex
sealed abstract case class Token(var line:Int,var pos:Int) {
def err():String = {
"(line:"+line+",pos:"+pos+")"
}
}
case class Num(num:Int) extends Token(0,0)
case class Add() extends Token(0,0)
case class Mul() extends Token(0,0)
case class Div() extends Token(0,0)
case class Sub() extends Token(0,0)
case class Eof() extends Token(0,0)
case class Spr() extends Token(0,0)
case class Epr() extends Token(0,0)
class Lex (src:String) {
val numReg = ptn( """[0-9]+""" )
val addReg = ptn( """\+""" )
val subReg = ptn( """\-""" )
val mulReg = ptn( """\*""" )
val divReg = ptn( """\/""" )
val sprReg = ptn( """\(""" )
val eprReg = ptn( """\)""" )
val eofReg = ptn( """$""" )
val whiteSpaceReg = ptn( """[ \r\n\t]*""" )
def ptn(str:String):Regex = {
("^("+str+")(.*)").r
}
var pos = 1
var line = 1
def tokens():Stream[Token] = {
pos = 1
line = 1
var str = src.replace("\r\n","\n").replace("\r","\n")
def cut(a:String,b:String,t:Token):Token = {
t.line = line;
t.pos = pos;
str = b;
for(i <- 0 to a.length - 1) {
if(a.charAt(i)=='\n') {
line += 1;
pos = 1;
} else {
pos += 1
}
}
t
}
val dummy = Eof()
for(i <- Stream.from(0)) yield {
str match {
case whiteSpaceReg(a,b) => cut(a,b,dummy)
case _ =>
}
str match {
case numReg(a,b) => cut(a,b, Num(a.toInt))
case eofReg(a,b) => cut(a,b, Eof())
case addReg(a,b) => cut(a,b, Add())
case subReg(a,b) => cut(a,b, Sub())
case mulReg(a,b) => cut(a,b, Mul())
case divReg(a,b) => cut(a,b, Div())
case sprReg(a,b) => cut(a,b, Spr())
case eprReg(a,b) => cut(a,b, Epr())
case _ => val linestr = "(line:"+line+",pos:"+pos+")";
throw new Exception("illegal character: '"
+str.substring(0,1)+"'"+linestr
);
}
}
}
final def p(tokens:Stream[Token]){
tokens.head match {
case Eof() =>
case _ =>
println(tokens.head);
p(tokens.tail);
}
}
}
object main extends Application {
var lex = new Lex("1+2*3");
val tokens = lex.tokens()
lex.p(tokens)
}
object main2 {
def main(args:Array[String]) {
var lex = new Lex(args(0))
val tokens = lex.tokens()
lex.p(tokens)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment