優先順位付き演算子定義の可能な小さな構文解析器

以下のような簡単な構文解析器を作ります。

前も書いたような気がしますが、
たまに、やらないと忘れて難しいことになってしまうし。
あろはさんが面白そう言ってたのでまぁ、のせて見ます。

出来たもののアドレス、、、。
http://sakurai.s59.xrea.com/diary/prefixs.html

<script>
Array.prototype.toString = function(){return "("+this.join(" ")+")"}
function c() {
	document.getElementById("out").value =
	eval(document.getElementById("in").value)
}

function eval(str){
	function peek() {
		return str.match(/^[ \r\n\t]*([0-9]+|\+|\-|\*|\/|\(|\)|$)/)[1]
	}
	function pop() {
		return peek(),str = RegExp.rightContext,RegExp.$1
	}
	function exp() {
		var c = term()
		if(peek()=="+"){pop();return [c, "+", exp()]}
		if(peek()=="-"){pop();return [c, "-", exp()]}
		return c
	}
	function term() {
		var c = fact()
		if(peek()=="*"){pop();return [c, "*", term()]}
		if(peek()=="/"){pop();return [c, "/", term()]}
		return c
	}
	function fact() {
		var c = pop()
		if(Number(c))return Number(c)
		if(c == "("){c = exp(); if(pop() == ")")return c}
		throw new Error("error")
	}
	try{return exp()}catch(e){return e}
}
</script>
<input id=in>
<input id=out>
<input type=button onclick=c()>

これを演算子が登録できるように変更すると以下のようになります。

まず、prifixsという配列を用意して、その中に、
演算子とその演算子を見つけた場合に動く処理の連想配列を入れておきます。

	var prifixs = [
		{
			"+":function(a,b){return[a,"+",b]},
			"-":function(a,b){return[a,"-",b]}
		},
		{
			"*":function(a,b){return[a,"*",b]},
			"/":function(a,b){return[a,"/",b]}
		}
	];

expは優先順位0番の2項演算子の処理を呼ぶだけです。

	function exp() {
		return expn(0)
	}

優先順位付き、優先順位nの処理は以下のようになります。

	function expn(int n) {
		if (prifixs.length == n) return fact();
		var c = expn(n+1);
		var f = prifixs[n][peek()];
		if(f) return pop(), f(c,expn(n))
		return c
	}

prifixsの長さと同じになったのであれば、factを、そうでなければ、
1つ優先順位の高いものを求めます。

var c = (prifixs.length == n) ? fact() : expn(n+1);

次に、優先順位に対応する演算子の処理関数を求めます。

var f = prifixs[n][peek()];

もしも、処理関数があれば、その字句を捨てて、その関数を呼びます。
そうでなければ、cをそのまま返します。

if(f) return pop(), f(c,expn(n))
return c

これだけです。
全体のソースは以下のようになります。

<script>
Array.prototype.toString = function(){return "("+this.join(" ")+")"}
function c() {
	document.getElementById("out").value =
	eval(document.getElementById("in").value)
}
function eval(str){
	function peek() {
		return str.match(/^[ \r\n\t]*([0-9]+|\+|\-|\*|\/|\(|\)|$)/)[1]
	}
	function pop() {
		return peek(),str = RegExp.rightContext,RegExp.$1
	}
	function exp() {
		return expn(0)
	}
	var prifixs = [
		{
			"+":function(a,b){return [a,"+",b]},
			"-":function(a,b){return [a,"-",b]}
		},
		{
			"*":function(a,b){return [a,"*",b]},
			"/":function(a,b){return [a,"/",b]}
		}
	]
	function expn(n) {
		if (prifixs.length == n) return fact()
		var c = expn(n+1)
		var f = prifixs[n][peek()]
		if(f) return pop(), f(c,expn(n))
		return c
	}
	function fact() {
		var c = pop()
		if(Number(c))return Number(c)
		if(c == "("){c = exp(); if(pop() == ")")return c}
		throw new Error("error")
	}
	return exp()
}
</script>
<input id=in>
<input id=out>
<input type=button onclick=c()>