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;
    },
});

長い上に、構文木を処理するのと大した違いが無い気もしますが、個人的な分かりやすさ優先です。

サンプル

参考

他のjavascriptパーサジェネレータ