10分で書く構文解析器

10分で書く構文解析器をやってみました。
再帰下降法を使っています。
四則演算して結果を返します。
最初に、簡単なスタックのように使える文字読み込み関数pop(),push(),peek()をつくり、
その関数を利用して、再帰下降構文解析の関数expr,term,factを作成しています。
字句解析は、pop()とfact()関数内でやってる感じです。
時間が余った分、空白の処理を入れています。
htmlはありものを使ってるので、実質、作ってる時間は5,6分です。

ムービー
http://sakurai.s59.xrea.com/10min/10minparse.html

できあがったもの
http://sakurai.s59.xrea.com/10min/parse.html

詳しいところは、id:tanakhさんの
10分で書ける、お手軽パーザーを見てください。

http://fxp.hp.infoseek.co.jp/arti/parser.html

追記：一箇所間違えてました。t = c + t じゃなくて、 t = t + cでした。

ソース

function parse(str) {
//	expr : term { (+|-) term }
//	term : fact { (*|/) fact }
//	fact : number | '(' expr ')'
	var buf = str;
	function pop() {
		var c;
		do {
			c = buf.charAt(0);
			buf = buf.substring(1);
		} while (c.match(/[ \t\r\n]/));
		return c;
	}
	function push(s) {
		buf = s + buf;
	}
	function peek() {
		var c = pop();
		push(c);
		return c;
	}
	try {
		return expr();
	} catch (e) {
		return e;
	}
	
	function expr() {
		var c = term();
		while (peek() == "+" || peek() == "-") {
			if (pop() == "+") c = c + term();
			else              c = c - term();
		}
		return c;
	}

	function term() {
		var c = fact();
		while (peek() == "*" || peek() == "/") {
			if (pop() == "*") c = c * fact();
			else              c = c / fact();
		}
		return c;
	}
	
	function fact() {
		var c = pop();
		if (c.match(/[0-9]/)) {
			var t = "";
			while(c.match(/[0-9]/)) {
				t = t + c;
				c = pop();
			}
			push(c);
			return Number(t);
		}
		if (c == "(") {
			c = expr();
			if (pop() != ")") throw "invalid error";
			return c;
		}
		return "invalid error";
	}
}