で四則演算コンパイラ
自分のライフワークである、言語作りですが、いよいよオリジナルコンパイラを作っていこうと思っています。
で、まずは、四則演算できるだけのコンパイラだよなってことで以下のサイトを参考に作ってみました。
http://www.sol.dti.ne.jp/~yoshinor/mysoft/
Scala版にするにあたっては、以下の点を変更しました。
・バイナリ出力は止める
・0で割る例外処理はしない。
・構文木を作ってから、コード出力する。
・パーサは関数的に
・ネームスペースに気を付けて拡張可能な作りに。
移植してみてわかったことは、このコンパイラはスタックマシン的に動作するものだということです。
CPUのスタックを使って計算するのでC言語で自分で作ったスタック構造を使ったスタックマシンよりはずっと高速なはずです。
しかし自分が作ろうとしているレジスタマシンのコンパイラとは若干異なる作りになっています。
import scala.util.matching.Regex class Ast { abstract class T case class Var(value:Int) extends T case class Add(left:T, right:T) extends T case class Mul(left:T, right:T) extends T case class Sub(left:T, right:T) extends T case class Div(left:T, right:T) extends T case class Mod(left:T, right:T) extends T case class Paren(ast:T) extends T case class Camma(left:T, right:T) extends T } object Parse extends Ast { /** * 字句解析 */ def ptn(str:String):Regex = { // 空白を取り除くようにして正規表現オブジェクトを返す ("""^[ \r\n\t]*"""+str).r } val numReg = ptn( """([0-9]+)(.*)""" ) val eofReg = ptn( """$""" ) val addReg = ptn( """\+(.*)""" ) val subReg = ptn( """\-(.*)""" ) val mulReg = ptn( """\*(.*)""" ) val modReg = ptn( """%(.*)""" ) val cammaReg = ptn( """,(.*)""" ) val divReg = ptn( """\/(.*)""" ) val prnReg = ptn( """\((.*)""" ) /** * 予測されたトークンを取り除く */ def eat(as:(T,String))(eatStr:String):(T,String) = { val eatReg = ptn(eatStr+"(.*)$") as match { case (a,eatReg(str)) => (a, str) case _ => throw new Error("error") } } /** * 数字あるいは( exp ) */ def fact(str:String):(T,String) = { str match { case numReg(i, str) => (Var(i.toInt) ,str) case prnReg(str) => eat(exp(str))("""\)""") case _ => throw new Error("error") } } /** * 掛け算か、fact */ def term(str:String):(T,String) = { def term2(as:(T,String)):(T,String) = { as match { case (a, mulReg(str)) => val (b, str2) = fact(str) term2(Mul(a, b), str2) case (a, divReg(str)) => val (b, str2) = fact(str) term2(Div(a, b), str2) case (a, modReg(str)) => val (b, str2) = fact(str) term2(Mod(a, b), str2) case _ => as } } term2(fact(str)) } /** * 足し算かterm */ def exp(str:String):(T,String) = { def exp2(as:(T,String)):(T,String) = { as match { case (a, addReg(str)) => val (b, str2) = term(str) exp2(Add(a, b), str2) case (a, subReg(str)) => val (b, str2) = term(str) exp2(Sub(a, b), str2) case _ => as } } exp2(term(str)) } // パース ------------------------------ def apply(str:String):T = { // expの呼び出しとエラーの処理 exp(str) match { case (a, eofReg()) => a case _ => throw new Error("syntax error") } } } object Emit_X86 extends Ast { var code = "" def code_string(str:String) { code += "\t" + str + "\n" } def enter_code() { code_string("push\t\tebp") code_string("mov \t\tebp,esp") code_string("sub \t\tesp,0x00000000") } def leave_code() { code_string("mov \t\tesp,ebp") code_string("pop \t\tebp") code_string("ret") } def push_value(nValue:Int) { code_string("push\t\tdword\t" + nValue) } def push_eax() { code_string("push\t\teax") } def push_ebx() { code_string("push\t\tebx") } def push_edx() { code_string("push\t\tedx") } def pop_eax() { code_string("pop \t\teax") } def pop_ebx() { code_string("pop \t\tebx") } def add_eax_ebx() { code_string("add \t\teax,ebx") } def sub_eax_ebx() { code_string("sub \t\teax,ebx") } def idiv_ebx() { code_string("idiv\t\tebx") } def imul_ebx() { code_string("imul\t\tebx") } def xor_edx_edx() { code_string("xor \t\tedx,edx") } def expr(c:T) { c match { case Camma(a, b) => expr(a) expr(b) pop_eax() pop_ebx() push_eax() case Add(a, b) => expr(a) expr(b) pop_ebx() pop_eax() add_eax_ebx() push_eax() case Sub(a, b) => expr(a) expr(b) pop_ebx() pop_eax() sub_eax_ebx() push_eax() case Mul(a, b) => expr(a) expr(b) pop_ebx() pop_eax() imul_ebx() push_eax() case Div(a, b) => expr(a) expr(b) pop_ebx() pop_eax() xor_edx_edx() idiv_ebx() push_eax() case Mod(a, b) => expr(a) expr(b) pop_ebx() pop_eax() xor_edx_edx() idiv_ebx() push_edx() case Paren(a) => expr(a) case Var(v) => push_value(v) } } def apply(ast:T):String = { enter_code() // プロローグ・コードの生成 expr(ast) pop_eax() // 式の値を取得 leave_code() // エピローグ・コードの生成 code } } object Calc { /** * 数式のコンパイル */ def compile(string:String) { val ast = Parse(string).asInstanceOf[Emit_X86.T] println(Emit_X86(ast)) } /** * エントリーポイント */ def main(argv:Array[String]) { compile(argv(0)) } }