haXeで作るプログラミング言語(4)

haXe

さて、今回はさらに簡略化しまっす。
パーサを手書きでどんどん増やすのも手なのですけど、メンドクサイので再帰下降型の演算子順位法を使って、演算子をいくらでも追加できるようなパーサの構造に変えます。

今回作ったのは以下のソースです。

enum Exp {
	nil;
	num(d:Int);
	op(l:Exp, tag:String, r:Exp);
}

class Calc4 {
	static function main() {
		var c = new Calc4();
		trace(c.eval("1+2*3"));
	}
	var operators:Hash<Int>;
	function new(){
		operators = new Hash<Int>();
		operators.set("+", 10);
		operators.set("-", 10);
		operators.set("*", 20);
		operators.set("/", 20);
	}

	var src:String;
	var token:String;
	var token2:String;

	function lex():String {
		var r : EReg = ~/^[\r\n\t ]*([0-9]+|[+*\-\/])/;
		token2 = token;
		if(r.match(src)){
			token = r.matched(1);
			src = src.substr(r.matched(0).length);
			return token2;
		}
		token = "";
		return token2;
	}

	function eval(str:String):Int {
		var exp = parse(str);
		return execute(exp);
	}

	function parse(str:String):Exp {
		src = str;
		lex();
		return expn(0);
	}

	function expn(p:Int):Exp {
		var t = fact();
		var tagp:Int;
		while(operators.exists(token) && (tagp = operators.get(token)) > p) {
			var tag = lex();
			t = op(t, tag, expn(tagp));
		}
		return t;
	}

	function fact():Exp {
		var t = lex();
		if(t == "(") {
			var t2 = expn(0);
			if(lex() != ")") throw ("error");
			return t2;
		} else {
			return num(Std.parseInt(t));
		}
	}
	
	function execute(exp:Exp):Int {
		switch(exp) {
		case nil: return 0;
		case num(d): return d;
		case op(l, tag, r):
			switch(tag){
			case "+": return execute(l)+execute(r);
			case "-": return execute(l)-execute(r);
			case "*": return execute(l)*execute(r);
			case "/": return cast(execute(l)/execute(r),Int);
			default: return 0;
			}
		}
	}
}

Calc4.hxml

-swf Calc4.swf
-main Calc4

まずは、演算子の優先順位表を作ります。
優先順位表というとなんだか難しそうですけど以下のようなただの連想配列です。

	var operators:Hash<Int>;
	function new(){
		operators = new Hash<Int>();
		operators.set("+", 10);
		operators.set("-", 10);
		operators.set("*", 20);
		operators.set("/", 20);
	}

haXeではこのへんJavaScriptやActionScriptと違って、Hashオブジェクトを使って、setメソッド
で値を設定するという、Javaのような書き方をしないといけないようです。

	var operators = {"+":10,"-":10,"*":20,"/":20};

のように書くとこのoperatorsは匿名オブジェクト構文で型推論によって厳密に型を決められるそうなので
ハッシュテーブルとしては使えません。

さて、この表を元に演算子の優先順位を比較して構文解析するように、exp関数を書き換えると以下のようになります。

	function expn(p:Int):Exp {
		var t = fact();
		var tagp:Int;
		while(operators.exists(token) && (tagp = operators.get(token)) > p) {
			var tag = lex();
			t = op(t, tag, expn(tagp));
		}
		return t;
	}

まず、関数にプライオリティをあらわすpという引数をつけます。
そして最初にfactで左辺の値を取り出します。
次に演算子が来るはずなので、表に存在していてかつ、優先順位が関数のプライオリティより高ければ
演算子として採用して、tagpの優先順位でexpnを再帰呼び出しします。
たったこれだけで、うまいこと、1+2 * 3がop(num(1),"+",op(num(2),"*",num(3)))
として計算してくれます。これで、好きな優先順位を持った２項演算子をいくらでも増やせるようになりました！
演算子順位法ってすごい！
しかも、優先順位がたくさんある場合たとえば、１０個あった場合に、
１０回も再帰呼び出しすることになるところを１回の再帰呼び出しで済みます。
その分このアルゴリズムは高速に動作するアルゴリズムです。
ってことで、TODO:この関数のオーダーを示す。


Top Down Operator Precedence:
http://javascript.crockford.com/tdop/tdop.html