ここ数日caper( http://qiita.com/jonigata/items/2a4e3b642afd20970eb2 )に試作GLRアルゴリズムのJavaScriptジェネレータを実装しておりまして、なんとかなったようなので実装の解説をしてみたいと思います。
GLRとは
私もあまりよく知らないので、こちらをどうぞ。
英語版の方が詳しく書かれていますね。
LR法の流れで文脈自由文法(CFG)を扱う方法として、単純にパーサを並列で動かす方法がある(後で説明します)のですが、これに名前が無いようなので、この文書ではLRパーサを並列に動かすアルゴリズム全般およびそれで受理できる文法クラスを「GLR」と呼び、並列パーサのデータ構造を改良した手法をTomita法と呼びます。この文書で「GLR」と言ったら多分それはTomita法を含んでいます。
テーブル作成
LR法は、パースに先立ってテーブルを作っておいて、受け入れるトークンから表引きして遷移先状態を見つけていくアルゴリズムですが、GLRでもそれは変わりません。ですので、今回のお試し実装は、caperのLALRテーブル作成をほぼそのまま使い、GLR用のジェネレータだけ作る形で行いました。
通常のLALRパーサと違う点は、競合時のアクションを複数持てることです。通常、LALRパーサでは、shift/reduceコンフリクトやreduce/reduceコンフリクト時には優先度の高いものだけを実行します。一方GLRは、すべて（擬似）並列で処理します。ですので、すべてのアクションをテーブルに記録しておくことが必要です。
今回、その部分だけが異なるテーブル生成ルーチンを別に作成するのがいやだったので、逆に「常にすべてのアクションを優先度付きセットに記録しておき、GLRではすべてを、LALRでは先頭だけを使う」ことにしました。
単純なGLRパーサ
GLR文法を受理するためのもっとも簡単な方法は、コンフリクトが発生するような局面に到達したらパーサ(スタック)をクローンして、以降の入力は存在しているすべてのパーサに同時に入力するようにすることです。実際にそのような方法で実装しているパーサもいくつかあるようです。受理した文法がLALR文法に毛が生えた程度の機械言語文法であれば、ある局面では曖昧でもしばらくすれば本道以外はエラーになることが多いので、さほど問題ないようです。
ですが、曖昧な局面に遭遇するたびにパーサ（スタック）がクローンされるため、「大筋は一緒でも細かいところが曖昧な文法」に適用すると、ローカルな曖昧さのためにクローンされたパーサが最後まで生存してしまい、どんどん遅くなっていきます。おそらく、ねずみ算式で増加していくのでしょう。そういったわけで、この単純な方法でたとえばスキャナーレスパーサ（lexをシームレスに統合したパーサ）を実装するのは、現実的でないようです。
Tomita法
Tomita法では、上記の問題を解決するため、以下の3つを特徴として備えています。
分岐
パーサが曖昧な局面に遭遇してクローンするとき、スタックをまるごとコピーしないで分岐するようにします。lispなど関数型言語の覚えがある方は、関数型言語での片方向リストの実装(consセルのようなもの)を想像してください。スタックをconsセルで形成すれば、途中から別の方向に進むこともできるというわけです。
統合
曖昧な局面でクローンされたパーサ（スタック）を放置すると指数関数的に速度が低下していくので、Tomita法ではReduce/Shiftするごとにいちいち各パーサの状態を調べて、同じ状態になっているパーサを統合します。
パースフォレスト
GLR文法ではひとつの入力を複数に解釈できる可能性があるため、受理後の構文木も部分的に重複する可能性が十分にあります。爆発を防ぐために、共通部分木を持つ複数の木を所有する構造になっています。関数型言語のpersistent treeのようなものを想像してください。
とりあえず
前提知識編はここまで。ストックしてくださる方がいらっしゃれば、続き(コーディング編)も書いてみようと思います。いなくても自分が忘れないために書くかもしれませんが。
今回勉強のために生成したGLRアニメータが http://jonigata.github.io/caper/glr/glrdemo.html にあります。次回はこれをつかって説明しようと思いますので、興味のある方は触ってみてください。左上の「Next」ボタンを押せばパースが進行します。メイン画面はドラッグでパン、ホイールでズームが可能です。赤いのがスタック的なもの、青いのがAST的なものです。