JavaScript で構文解析2007年09月12日 14時46分

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 パーサの動作を確認できるサンプルもごらんください。

参考文書

Mozilla 24 行動記録2007年09月25日 19時21分

さる 9 月 15 ~ 16 日に Mozilla 24 へ行ってきました。大体の様子は他のブログなどで知れ渡っているかと思いますが、とりあえず私の行動記録を少々。

  • 9 月 15 日 4:30 電車内で参加賞を印刷し忘れたことに気づき焦るも、Twitter にて os0x さんyoshiori さんに携帯での確認方法を教えてもらい一安心。
  • 5:05 東京駅着。
  • 6:55 仮眠と時間つぶしをかねて山手線を 1 周半、池袋駅着。
  • 7:30 バーガーキングにて朝食。ブレックファストメニューのクロワッサンウィッチ・ハムを頼むも、通常メニューも頼めるということを後から知り、ワッパーにしておけばよかったかと少し後悔。
  • 8:40 上野駅着。鶯谷から歩いてこようかとも思ったが、時間と土地勘のなさ、そして暑さにより断念。
  • 9:10 不忍池、めがねの碑、正岡子規記念球場を巡る。
  • 9:20 国立科学博物館へ。シアター 360 に圧倒される。
  • 11:20 科博より撤退。お昼を食べてから会場入りのつもりだったがその時間がなくなる。
  • 11:55 ベルサール九段に到着。入り口にて Kuruma さんSaito さんと一緒に。
  • 12:00 DocFest M24 開始、と思いきや設営などの関係で開始は 12:30 からとのこと。
  • 13:00 DocFest M24 開始。実はこれが OmegaT の使い初め。
  • 14:30 対訳ユーザー辞書仕様 UTX に関するプレゼンテーションおよびディスカッション。1 時間の予定が話題も広がり最終的に 2 時間近くに。
    • シリアライズ形式として XML を採用。
    • 訳語の分野を明確化することにより、文脈に合った訳が可能に。
    • 作成者・作成日時といったメタ情報を付加して、管理・共有しやすく。
  • お昼のお弁当が余ったとかで分けてもらう。
  • 18:30 出張 Shibuya.js 24 に参加。開始直前にホール入りし、終了直後に DocFest へ戻ったため、特に誰とも交流することなし。もったいないことをした。
  • 20:30 DocFest 会場に戻るとカツサンドが山のように積まれていた。
  • Taken さんMDC 支援プロジェクト翻訳文書新規作成支援ボットの存在を教えてもらう。
  • Shimono さんに、title-override をつけるのは breadcrumbs を正しく表示させるためのおまじないでもあると教えてもらう。
  • 新規翻訳文書には英語版へのリンクさえつけておけば、後はボットが英語版を含む他言語版のページに言語間リンクをつけてくれると教えてもらう。
  • 16 日 0:30 事務局にて仮眠。
  • 3:00 ビンゴに参加。リーチは一番乗りだったものの、結局ビンゴならず。
  • トイレで小飼弾さんに合うも、挨拶だけで終わってしまった。
  • 6:00 賞味期限切れの弁当を食べませんかとお誘いがかかるものの、代表理事じきじきにストップがかかったとかで食べられず。
  • 7:00 朝の弁当が到着したとのことでいただく。
  • 9:00 事務局にて仮眠。
  • 10:30 DocFest 成果発表。Core JavaScript 1.5 ReferenceStatements の項をすべて訳せるかと思っていたが、結局 3 分の 2 程度しか訳せず。
  • 11:30 ベルサール九段から退出。お土産に Firefox カステラ、カロリーメイトポテト味、余った駄菓子類をいただく。カツサンドの最後の一包みももらったので駅弁代わりの昼食とした。

食料は豊富でしたが、夜のお弁当を食べ逃したのが心残りです。翻訳も Twitter やら何やらで脱線していなければもっと進められたかも。

それにしても翻訳支援ソフトというものは、一度使い出すともう手放せませんね。E4X 邦訳なんて、よくテキストエディタだけで訳せたものだと今になって思います。