エラー復帰機能付きパーサを考える。

下降型演算子順位法のパーサにエラー復帰機能をつけてみました。

実装したのは以下の２つです。

•字句解析時にマッチしなかったら、１文字読み飛ばす
•構文解析時に予測した括弧まで、読み飛ばす

四則演算に関係のない文字があったら読み飛ばすようにしたのが、字句解析のエラー復帰機能です。

abc(1+2*a3b)

このような式は

(1+2*3)

と同じ意味になります。というのが、字句解析時のエラー復帰機能です。

括弧まで、読み飛ばし機能は、予測される括弧が見つかるまで、読み飛ばして、なくてもあったことにする機能です。

(1+2**3

という式は

(1+(2* *))

という意味で構文解析されます。

以下、ソースコードになります。

<script>
Array.prototype.toString=function(){
	return "["+this.join(",")+"]";
}

var Exp = {
	run: function(){
		var src =document.getElementById("in").value;
		document.getElementById("out").value = Exp.exec(src);
	},
	exec: function(src) {
		try {
			Exp.src = src;
			return Exp.parse();	
		} catch (e) {
			return e;
		}
	},
	src:"",
	token:"",
	ptoken:"",
	parse: function () {
		Exp.advance();
		return Exp.exp(0);
	},
	advance: function() {
		Exp.ptoken = Exp.token;
		var m;
		while ((m = Exp.src.match(/^[ \r\n\t]*([0-9]+|[+\-*/\(\)]|$)/)) == null) {
			Exp.errors.push("found not expected charactor "+Exp.src.charCodeAt(0));
			Exp.src = Exp.src.substring(1);
		}
		Exp.src = Exp.src.substring(m[0].length);
		Exp.token = m[1];
		return Exp.ptoken;
	},
	infixs: {
		"+":10, "-":10,
		"*":20, "/":20
	},
	parens: {
		"(":")",
		"{":"}",
		"[":"]"
	},
	exp: function(p) {
		var t = Exp.advance();
		if(t in Exp.parens) {
			var startParen = t;
			var endParen = Exp.parens[t];
			t = Exp.exp(0);
			if(endParen != Exp.advance()) {
				Exp.errors.push("syntax error expected "+endParen);
				do{
					Exp.advance();
				} while(!Exp.token in Exp.parens);
			}
			t = [startParen, t, endParen];
			
		}
		while (true) {
			if (Exp.token in Exp.infixs && Exp.infixs[Exp.token] > p) {
				var op = Exp.advance();
				t = [t, op, Exp.exp(Exp.infixs[op])];
				continue;
			}
			break;
		}
		return t;
	},
	errors:[],
	"":""
};

</script>
<input id="in" value="abc(def(1+2*3**4)+5*6**7)+8"/>
<input id="out" value=""/>
<input type="button" value="run" onclick="Exp.run()" />