演算子順位付きの再帰下降パーサ

javascript

なんか、プレビューを押したら固まった。そして、書いていた日記が消えてしまった。（泣


ここのところ、演算子順位法を使ったパーサは難しい。
ウームと思ってて、再帰下降パーサで優先順位付きの演算子をうまく扱えないかなぁと
考えてみたり、調べてみたりしてました。
で、


http://javascript.crockford.com/tdop/tdop.html


このへんのページを発見。すごく、やりたいことに近いことが書いてあるわけですが、
これだこれ。ってことで、ソース見てみました。
要は、exp0,exp10,exp20という演算子の関数を呼び出して同じように再帰下降でパーサを書くとするなら、その数字をパラメータ化します。exp(0),exp(10),exp(20)というように。
それだけだと、呼び出しはexp(0),exp(10),exp(20)のように呼んでいかないといけません。
でもここで、演算子の順位を演算子順位法でやったときのように、比較してやりますと
exp(0)の次にexp(20)をイキナリ呼び出して使ったり出来るようになります。
その分高速で、かつシンプルになるようです。


自分が作ったものは、以下のアドレスで試せます。
http://sakurai.s59.xrea.com/compact/op/t.html


以下ソースです。

<html>
<script>
function run() {
	var t = document.getElementById("in").value;
	try {
		t = parse(t);
	} catch(e){t = e}
	document.getElementById("out").value = t;
}

Array.prototype.toString = function() { return "[" + this.join(",") + "]"; }
function parse(str) {
	var tokens = [];
	str.replace(/\+\+|[\r\n]+|[-\+*\/\(\)\[\]\{\}\=\;\:]|[^-\+*\/\(\)\[\]\{\}\s\=\;\:]+|[\s]+/g,function(s) {
		if(s.match(/^[^\s]+/)) tokens.push(s);
	});
	function xpxp(n) {
		var t1 = t;
		var op = token;
		var p = infixs[op][0];
		if(p <= n) return false;
		advance();
		var e = ex();
		var op2 = token;
		advance();
		if (infixs[op][2] != op2) throw "error "+infixs[op][2] + " "+op2;
		t = [t1, op, e, op2];
		return true;
	}
	function xox(n) {
		var op = token;
		var p = infixs[op][0];
		if(p <= n) return false;
		advance();
		t = [t, op, exp(p)];
		return true;
	}
	function xoy(n) {
		var op = token;
		var p = infixs[op][0];
		if(p < n) return false;
		advance();
		t = [t, op, exp(p)];
		return true;
	}
	function xo(n) {
		var op = token;
		var p = infixs[op][0];
		if(p <= n) return false;
		advance();
		t = [t, op];
		return true;
	}

	function pxp(n) {
		var p1 = t;
		var e = ex();
		if(prefixs[p1][2] != token) throw "error "+prefixs[p1][2]+" "+token;
		t = [p1, e, token];
		advance();
	}
	function opxpx(n) {
		var op = t;
		if(prefixs[op][2] != token) throw "error "+prefixs[op][2]+" "+token;
		var p1 = token;
		advance();
		var e = ex();
		if(prefixs[op][3] != token) throw "error "+prefixs[op][3]+" "+token;
		var p2 = token;
		advance();
		t = [op, p1, e, p2, ex()];
		advance();
	}
	function oy(n) {
		t = [t, exp(prefixs[t][0])];
	}

	var infixs = {"*":[20, xox], "/":[20, xox], "-":[10, xox], "+": [10, xox], "=":[1, xoy],":":[1, xoy], "++":[70,xo], ";":[5,xo], "(":[70,xpxp,")"],"[":[70,xpxp,"]"],"{":[70,xpxp,"}"]};
	var prefixs = {"-":[70, oy], "(":[70,pxp,")"], "{":[70,pxp,"}"], "[":[70,pxp,"]"],"if":[80,opxpx,"(",")"]};

	var pxpe = {};
	for(var i in prefixs) {
		if(prefixs[i][1]==pxp) pxpe[prefixs[i][2]]=i;
		if(prefixs[i][1]==opxpx) pxpe[prefixs[i][3]]=prefixs[i][2];
	}
	for(var i in infixs) if(infixs[i][1]==xpxp) pxpe[infixs[i][2]]=i;

	var token;
	var t;
	var index = 0;
	function advance() { token = tokens[index++]; }
	function ex() {
		var e = exp(0);
		while(token != undefined && !(token in pxpe) && !(token in infixs) && !(token in prefixs)) {
			var e2 = e;
			e = [e2,"@", exp(0)];
		}
		return e;
	}
	function exp(n) {
		t = token;
		if (t in pxpe) return null;
		advance();
		if (t in prefixs) prefixs[t][1](n);
		while(token in infixs && infixs[token][1](n)){}
		return t;
	}
	advance();
	return ex();
	return e;
}
</script>

<body>
<input type=button onclick=run()><br />
<textarea id=in cols=80 rows=5>add:function(a;b){a+b}
sub:function(a;b){a-b}
</textarea><br />
<textarea id=out cols=80 rows=25>
</textarea><br />
</body>
</html>