Days on the Moon

C++ の特徴のひとつである演算子オーバーロード、その粋を極めたのが Boost Lambda (無名関数) と Boost Spirit (構文解析) ではないかと思っています。JavaScript では無名関数が使えるので Lambda に関しては間に合っているとも言えますが、Spirit はそうも行きません。JavaScript 2 で演算子オーバーロードがサポートされるのならチャレンジしてみようかななどと思ってそれきりになっていました。

しかし、一部でパーサブームが起こっているというのを受け、Perl 6 Rules をつらつらと眺めているうち、正規表現のメタ文字を使えば文法定義をきれいに書けるのではと思い至りました。そこで実際に JavaScript でパーサジェネレータを作り、Spirit にあやかって Gin (ジン) と名づけてみました。

文法定義

正規表現リテラルを使うことにより、EBNF に非常に近い形で文法定義を書けます。たとえば四則演算を用いた数式パーサを作成する場合は次のようになります。

var calc = new Gin.Grammar({
  Expr: / Term ([+] Term | [-] Term)* /,
  Term: / Fctr ([*] Fctr | [/] Fctr)* /,
  Fctr: / $INT | [(] Expr [)] /
}, "Expr", Gin.SPACE);

var input = ["1 + 2 * 3", "(4 - 5) / 6", "7 * (8 - 9"];
for (var i = 0; i < input.length; i++) {
  var match = calc.parse(input[i]);
  if (match && match.full)
    print("構文木: " + match.value.toSource());
  else
    print("数式が間違っています。");
}
// 構文木: [[[1]], "+", [[2], "*", [3]]]
// 構文木: [[["(", [[[4]], "-", [[5]]], ")"], "/", [6]]]
// 数式が間違っています。

Gin.Grammar コンストラクタの引数に生成規則の集合、開始記号、スキップパーサを渡してやることで、構文解析器を生成できます。ただし、生成されるのは再帰下降パーサなので、左再帰を含んだ生成規則は扱えません。

生成規則内では丸括弧によるグループ化、縦線による選択、*、+、?、{n,m} 形式の繰り返しなどが使えるほか、角括弧、一重引用符、二重引用符で囲まれた文字列が終端記号として認識されます。Digits: / <\d+> / のように、小なり大なり記号で囲めば正規表現を使うこともできます。$ から始まるのは定義済みの終端記号で、INT のほかにも符号を含まない UINT、小数部・指数部を含む REAL、改行文字を表す EOL または NL などがあります。

解析は開始記号で指定された非終端記号の生成規則から始まり、構文解析に先立ってスキップパーサで解析される文字列 (この場合はスペース、タブ、復帰、改行の空白文字) が除去されます。スキップパーサを省略するとデフォルトで空白文字が除去されます。

実際に解析を行うには Grammar オブジェクトの parse メソッドを呼び出します。解析が成功すれば Match オブジェクト、失敗すれば null がかえります。Match オブジェクトは構文木を納める value プロパティや、文字列を最後まで読み込んだかを示す full プロパティなどを持ちます。

セマンティックアクション

入力が文法に適合しているか調べるだけならこれで十分ですが、そうでない場合はさらに構文木を処理する必要があります。後からの処理を避け、構文解析時に特定の動作を実行するためには、セマンティックアクションを付加してやります。

var calc = new Gin.Grammar({
  Expr: / Term ([+] Term:add | [-] Term:sub)* /,
  Term: / Fctr ([*] Fctr:mul | [/] Fctr:div)* /,
  Fctr: / $INT:push | [(] Expr [)] /
}, "Expr", Gin.SPACE);

var calcAction = {
  _stack: [],
  push: function (v) { this._stack.push(v); },
  pop: function () { return this._stack.pop(); },
  add: function (v) { var b = this.pop(), a = this.pop(); this.push(a + b); },
  sub: function (v) { var b = this.pop(), a = this.pop(); this.push(a - b); },
  mul: function (v) { var b = this.pop(), a = this.pop(); this.push(a * b); },
  div: function (v) { var b = this.pop(), a = this.pop(); this.push(a / b); }
};

var input = "1 + (2 - 3) * 4";
var match = calc.parse(input, calcAction);
if (match && match.full)
  print(input + " = " + calcAction.pop());

// 1 + (2 - 3) * 4 = -3

生成規則内ではコロンの後にメソッド名を続け、parse メソッドの第 2 引数にアクションをつかさどるオブジェクトを渡すことにより、適宜そのオブジェクトのメソッドが呼び出されます。この例では数値が出現するごとにそれをスタックに積み、演算子が現れれば演算結果をスタックに積み直しています。

ソースコード、サンプル

ソースファイルは gin.js (Gin 0.90) です。数式パーサ、JSON パーサの動作を確認できるサンプルもごらんください。

参考文書

• Spirit v1.6
• お手軽パーザー
• Boost Software License - Version 1.0 (日本語参考訳)