javascriptでパーサジェネレータを書いてみました
BASICのトランスレータを書く途上、パーサを一々手書きするのは面倒なので、ジェネレータを作成しました。
といっても、楽天が運営するポータルサイト : 【インフォシーク】Infoseekで解説されているようなパーサを自動生成するものなので、左再帰は対応できませんし、構文解析の前に字句解析を行わなくてはなりません。
文法定義
以下は、加減乗除冪を含む数式の文法定義です。
var parser = new Parse.Parser(); parser.def({ expr: "add %end", add: "mul (($+ | $-) mul)*", mul: "pow (($* | $/) pow)*", pow: "fact ($^ fact)*", fact: "($+ | $-)?:sign ( $num | $( add $))", }); var tokens = tokenize("1 + 2 * 3");//字句解析は別に用意 parser.parse(tokens, "expr");
defメソッドに生成規則の文字列を渡して、文法を定義します。
正規表現と同様に、+、*、?、|、等を使う事が出来ます。$で始まる名前はトークンを、%endはトークン列の終端を表します。また:signのように、:nameで名前を付ける事が出来ます。
文法定義(オブジェクト)
生成規則に文字列ではなく、objectを渡す事も出来ます。with文を使うと、DSLっぽく書けます。
新たな項を追加する事も可能です(parseメソッドを持っていさえすればよい)。
with(parser) { parser.def({ expr: Seq(Ref("add"), End()), add: Seq(Ref("mul"), Repeat(Any(Token("+"), Token("-")), Ref("mul"))), mul: Seq(Ref("pow"), Repeat(Any(Token("*"), Token("/")), Ref("pow"))), pow: Seq(Ref("fact"), Repeat(Token("^"), Ref("fact"))), fact: Seq(Label("sign", Maybe(Any(Token("+"), Token("-")))), Any(Token("num"), Seq(Token("("), Ref("add"), Token(")")))), }); }
ちなみに、defに文字列を渡した時も最終的にobjectに変換するのですが、その変換処理自体にもParse.Parserを使っています。
アクション
callbackメソッドで、値を処理する関数を登録します。登録した関数には、正規表現のマッチオブジェクト的なナニモノカが渡され、関数の返り値がその要素の値になります。
マッチオブジェクト的なものは、m[index]でindex番目の要素にアクセス、m.g.nameでnameの要素にアクセスできます。
Repeatにマッチすると配列、Tokenにマッチするとトークンの値と、要素の型はマチマチです。
parser.def({ expr: "add %end", add: "mul (($+ | $-) mul)*", mul: "pow (($* | $/) pow)*", pow: "fact ($^ fact)*", fact: "($+ | $-)?:sign ( $num | $( add $))", }); parser.callback({ expr: function(m) { return m[0]; }, add:function(m) { return m[1].inject(m[0], function(acc, v){ if(v[0] == "-") { return acc - v[1]; } else { return acc + v[1]; } }); }, mul: function(m) { return m[1].inject(m[0], function(acc, v){ if(v[0] == "/") { return acc / v[1]; } else { return acc * v[1]; } }); }, pow: function(m) { return m[1].inject(m[0], function(acc, v){ return Math.pow(acc, v[1]); }); }, fact: function(m){ var v = m.g.num || m.g.add; return (m.g.sign == "-")? -v : v; }, });
長い上に、構文木を処理するのと大した違いが無い気もしますが、個人的な分かりやすさ優先です。