タプルからAST作成
構文木のパーサはそこそこ出来ていて構文木を嘗め回すインタプリタは作成しました。
JVMは構文木を嘗め回すのが妙に速いのでそれなりのスピードで動いてくれます。
しかしコンパイラを作る場合は抽象構文木(AST)に変換する必要があります。
通常の構文解析なら字句解析パスの後はすぐASTが作れるわけですが1パス増えています。
その分わかりやすく、美しくマクロも可能な文法になるのだ!!
ってことでいいんですけど、動的な型なツリーから型に厳格なツリーに変換するのって慣れてないので
どう書いたらいいのか技術的課題でした。
抽象構文木をどうするかも、考えていなかったので問題だったりして。
どーしたものか悩んでいたのですが、そんな矢先にちょうどid:kmizuさんのOnion言語のASTをScalaで書いた
とtwitterでつぶやいていたのでお、見せて見せてーとお願いしたところgitにアップしてくださったので
早速その文法ファイルを読ませてもらいました。
それを参考に四則演算部分だけ取り出して変換プログラムを書いてたら調子よく四則演算の式はかけました。
このタプルからASTへの書きかえをしっかりできるようにしてしまえば
後は普通のやりかたで行ける筈です。
この調子でいけば、とりあえず課題クリアできそうです。
次は文(Statement)周りの文法に拡大して書いていこうと思います。
package t2ast object AST { case class Position(line: Int, column: Int) abstract sealed class Node{ def pos: Position } abstract sealed class Expression extends Node case class IntegerLiteral(pos: Position, value: Int) extends Expression case class Id(pos: Position, name: String) extends Expression abstract sealed class BinaryExpression(symbol: String) extends Expression { def left: Expression def right: Expression } case class Addition(pos: Position, left: Expression, right: Expression) extends BinaryExpression("+") case class Division(pos: Position, left: Expression, right: Expression) extends BinaryExpression("/") case class Multiplication(pos: Position, left: Expression, right: Expression) extends BinaryExpression("*") case class Subtraction(pos: Position, left: Expression, right: Expression) extends BinaryExpression("-") abstract sealed class UnaryExpression(symbol: String) extends Expression { def target: Expression } case class Negate(pos: Position, target: Expression) extends UnaryExpression("-") abstract sealed class Toplevel extends Node abstract sealed class Statement extends Toplevel case class BlockStatement(pos: Position, elements: List[Statement]) extends Statement } object main { def exp(a:Any):AST.Expression = { a match { case (l:Int,c:Int,a:Int) => AST.IntegerLiteral(AST.Position(l,c), a) case (_,_,_,_,_) => bin(a) case (_,_,_,_) => unary(a) case _ => throw new Exception("error") } } def bin(a:Any):AST.BinaryExpression = { a match { case (l:Int,c:Int,a,"+",b) => AST.Addition(AST.Position(l,c), exp(a), exp(b)) case (l:Int,c:Int,a,"-",b) => AST.Division(AST.Position(l,c), exp(a), exp(b)) case (l:Int,c:Int,a,"*",b) => AST.Multiplication(AST.Position(l,c), exp(a), exp(b)) case (l:Int,c:Int,a,"/",b) => AST.Subtraction(AST.Position(l,c), exp(a), exp(b)) case _ => throw new Exception("error") } } def unary(a:Any):AST.UnaryExpression = { a match { case (l:Int,c:Int,"-",a) => AST.Negate(AST.Position(l,c), exp(a)) case _ => throw new Exception("error") } } def test(a:Any) { val r = exp(p(a)) println(a +"=>"+r) } def p(a:Any):Any = { a match { case (a,b,c) => (0,0,p(a),b,p(c)) case a => (0,0,a) } } def main(argv:Array[String]) { test((1)) test((1,"+",2)) test((1,"+",(2,"*",3))) } }