具体的な成長するパーサの例 - Scala で TAPLを勉強しつつ LLVM コンパイラを作る日記

最初は、数字だけ読むパーサexpがあるとする。

var exp = function() {
	return match?_
		: $(/^[0-9]+/) ? Number(get())
		: _            ? error("error")
	:match;
};
alert(parse("1+2*3"));

これは実行すると、

が返る。

これを拡張して、足し算が出来るようにする。

var fact = exp;
exp = function() {
	var c = fact();
	while($(/^\+/)|| $(/^\-/))
		c = [get(),c,fact()];
	return c;
};
alert(parse("1+2*3"));

これは実行すると、

[+,1,2]

が返る。

さらに、掛け算も拡張する。

var term = exp;
exp = function() {
	var c = term();
	while($(/^\*/)|| $(/^\//))
		c = [get(),c,term()];
	return c;
};
alert(parse("1+2*3"));

すると、

[*,[+,1,2],3]

が返る。
このように、対応する文法を拡張していける。

以下ソース

<html>
<script>
Array.prototype.toString = function() { return "["+this.join(",")+"]";}
var match = false;
var _ = true;
var m;
var str;
function parse(s) {
	str = s;
	return exp();
}
function $(r) {
	return m = str.match(r);
}
function get() {
	str = str.substring(m[0].length);
	return m[0];
}
function error(s){
	throw s;
}
var exp = function() {
	return match?_
		: $(/^[0-9]+/) ? Number(get())
		: _            ? error("error")
	:match;
};
alert(parse("1+2*3"));

var fact = exp;
exp = function() {
	var c = fact();
	while($(/^\+/)|| $(/^\-/))
		c = [get(),c,fact()];
	return c;
};

alert(parse("1+2*3"));

var term = exp;
exp = function() {
	var c = term();
	while($(/^\*/)|| $(/^\//))
		c = [get(),c,term()];
	return c;
};
alert(parse("1+2*3"));

</script>
<body>
成長する、パーサー。
</body>
</html>