Hatena::ブログ(Diary)

Scala で TAPLを勉強しつつ LLVM コンパイラを作る日記

2006-01-19 10分で書く構文解析器

[]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";
	}
}

通りがかり通りがかり 2007/06/28 00:58 マイナス1とかを扱えるよう、factのところに「if (c == ’-’) return -fact();」など入れるとよいかと。