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

haXe

さて今回は、２パスの計算機を作ります。
パスってのはプログラムを動かす上での段階ってかんじで、何段に分かれてるかをあらわすのにいいます。
前回は、パースしながら計算してたので１パスでした。
今回は、

１パースした結果を構文木に保存する
２構文木を実行する

という２つの段階（パス）に分けて作成します。
ということで、まずはソースを見てみてください。こんなかんじです。


Calc2.hx

enum Exp {
	nil;
	add(l:Exp, r:Exp);
	sub(l:Exp, r:Exp);
	mul(l:Exp, r:Exp);
	div(l:Exp, r:Exp);
	num(d:Int);
}

class Calc2 {
	static function main() {
		var c = new Calc2();
		trace(c.eval("1+2*3"));
	}

	function new(){}
	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 ast = parse(str);
		return execute(ast);
	}
	function parse(str:String):Exp {
		src = str;
		lex();
		return exp();
	}

	function exp():Exp {
		var t = term();
		while(token=="+"||token=="-") {
			switch(lex()){
			case "+": t = add(t, term());
			case "-": t = sub(t, term());
			}
		}
		return t;
	}

	function term():Exp {
		var t = fact();
		while(token=="*"||token=="/") {
			switch(lex()){
			case "*": t = mul(t, fact());
			case "/": t = div(t, fact());
			}
		}
		return t;
	}

	function fact():Exp {
		var t = lex();
		if(t == "(") {
			var t2 = exp();
			if(lex() != ")") throw ("error");
			return t2;
		} else {
			return num(Std.parseInt(t));
		}
	}

	function execute(ast:Exp):Int {
		switch(ast) {
		case nil: return 0;
		case num(d): return d;
		case add(l,r): return execute(l)+execute(r);
		case sub(l,r): return execute(l)-execute(r);
		case mul(l,r): return execute(l)*execute(r);
		case div(l,r): return cast(execute(l)/execute(r),Int);
		}
	}
}

Calc2.hxml

-swf9 Calc2.swf
-main Calc2

前回と変わったところというと、まずenumです。

enum Exp {
	nil;
	add(l:Exp, r:Exp);
	sub(l:Exp, r:Exp);
	mul(l:Exp, r:Exp);
	div(l:Exp, r:Exp);
	num(d:Int);
}

Expという名前のenumを作っています。ExpはExpression(式)の略です。
haXeのenumはちょっと強力です。add(l:Exp, r:Exp)のようにパラメータを持つことが出来ます。
おかげで、式はすべてこのenumであらわすことができます。
たとえば、1+1はadd(num(1),num(1))とあらわすことができます。1+1は2ではありませんｗｗｗ
1+2*3はadd(num(1),mul(num(2),num(3)))です。
いわゆる関数型言語のvariantデータ的なやつですね。
ということで、このenum Expをパーサが返すように書き換えます。
まず、fact関数のIntを返していたところを以下のように

			return num(Std.parseInt(t));

Expのnumを返すようにします。
そして、関数（メソッド）の型も

	function fact():Exp {

このようにExp型に変えます。

term関数も、掛け算と割り算をしてIntをtに入れていた箇所を

			case "*": t = mul(t, fact());
			case "/": t = div(t, fact());

このように書き換えて関数の返り値の型をExpに

	function term():Exp {

exp関数も、掛け算と割り算をしてIntをtに入れていた箇所を

			case "+": t = add(t, term());
			case "-": t = sub(t, term());

このように書き換えて関数の返り値の型をExpに

	function exp():Exp {

と変えると構文木を返すようになります。
これを開始させる関数はparseという名前にしましょう。

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


eval関数を書き換えます。最初にparseを呼び出して構文木を取得して、execute関数を呼び出して実行するようにします。

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

あとは、execute関数を作れば元通り計算できるようになります。

	function execute(ast:Exp):Int {
		switch(ast) {
		case nil: return 0;
		case num(d): return d;
		case add(l,r): return execute(l)+execute(r);
		case sub(l,r): return execute(l)-execute(r);
		case mul(l,r): return execute(l)*execute(r);
		case div(l,r): return cast(execute(l)/execute(r),Int);
		}
	}

こんなかんじで、haXeのenumはswitch文の中でパラメータを変数に割り当てる（バインディングする）ことができます。
したがって、こんな簡単なswitch文だけで構文木を走査して計算を行うことが出来ます。
このように、パスを分けることで、計算箇所は非常にシンプルになりました。
メモリを食うようにはなりましたが、このようにパスをわけることで計算部分は計算することだけを考えることができるようになりました。
また、switch文はすべての、enumの値を網羅してないと怒られるのでチェックにも役立ちます。
これで、２パスの計算機ができました。