対象読者など
前回の続きです。LR構文解析の基本的な方法が分かっている方が想定読者です。そこから知りたい方は、ドラゴンブックを読むか、Wikipedia、前々回紹介したytqwertyさんの記事などを御覧ください。
申し訳ありませんが、この文書を読んでもGLRを実装できるようにはたぶんなりません。が、概略と注意点を大まかにつかむ程度はできるのではないかな、と思います。
お手本
実装にあたって、「Efficient Parsing for Natural Language」をお手本とします。本文書で「教科書」と言ったらこの本のことだと思ってください。
私の履歴を見ると、どうも20000円だして買ったようです。たっか！ 研究者でもないのにちょっと頭おかしい感じがしますね。でもお陰でなんとか実装できたようなので、後悔はしていません。
この本は、
- 1章 イントロ
- 2章 アルゴリズムのインフォーマルな説明
- 3章 実例
- 4章 アルゴリズムのフォーマルな説明
- 5章以降 他のアルゴリズムとの比較、証明、パフォーマンスなど
といった構成になっていて、さらにおまけとして証明やコード！がついています。
コードといっても、MACLISPのコードで、ちょっと読む気が起きなかったので私は読みませんでした。
本を買う気のある方は、これをschemeあたりに逐語訳してから読むなどすれば、少し楽ができるかもしれません。
アルゴリズムのフォーマルな説明も、私の知性が足りなかったのでほとんど読んでいません。ほぼ2章と3章だけ読んで実装しました。したがって、どこか間違っているかもしれません。間違いを見つけたら是非教えて下さい。
GLRは、この本のタイトル通り、自然言語の構文解析のために考案されたアルゴリズムのようですね。ですが、特性的には機械言語の方が向いている気がします。この文書を読んでいただければなんとなく納得していただける、かもしれません。
3章の実例ではスタックの詳細のトレースが図示されていて非常にありがたい（というか私から見るとこの本の価値の7割くらいは3章、2割くらいが2章といった感じ）ですが、パースフォレストの内容が一部あきらかに間違っているっぽいので注意してください。例えばp30以降のnode12は6ではなく8が正しく、p36以降のnode26も[S(15 20)]の間違いだと思います。
実装難易度
考え方自体はかなりstraightforwardな感じで、LALRテーブル作成よりははるかに楽でした。正味2～3日でできたのではないかという気がします（間にコーディングはしてないけど頭では考えてる時間が挟まってますが）。データ構造がとても関数型チックなので、関数型言語の覚えがない方は先に勉強をしておくと捗ると思います。
テーブル
テーブルはLR系だったらなんでもいいと教科書にも書いてありましたので、私はcaperのLALRテーブルを利用しました。
前回書いたように、GLRではコンフリクトが起きる場合すべて並列に扱いますので、アクションテーブルは順序つきセットとして、すべての可能性を保持するようにちょっとだけ改造しました。その結果コードはある意味簡潔になりました。
データ構造
データ構造については前回も書きましたが、軽くおさらいしておきます。
GLRのスタックは、前回はlispのconsセルで構成されたリストのようなもの、と書きましたが、それは正確ではなくて、実際は「合流」があるためDAGになります。教科書ではGraph Structured Stack(GSS)と呼ばれています。
受理済みデータは「パースフォレスト」と呼ばれるデータ構造に置かれます。パースツリーと違ってrootが一つではないので「フォレスト」です。前回述べたように、関数型言語のpersistent treeのようなデータ構造を想像してください。たとえばOCamlのMapを使ってみると、「insertした後insert後のtreeが帰ってくるけど、insert前のtreeも依然として使える」ことに気づくと思いますが、あれです。
これらのデータ構造に関しては、前回お見せしたシミュレータをいじってみていただければ、だいたいのノリはわかると思います。
前回の記事を書いてから気づいたことですが、GLRのデータ構造はgitのデータ構造ととてもよく似ています。gitをご存知の方は、gitを想像しながらシミュレータをいじってみれば理解しやすいかもしれません。
用語
グラフ構造が2種類出てきて紛らわしいこともあり、教科書ではGSSのノードを「Vertex」、パースフォレストのノードを「Node」と読んでいますので、本文書およびcaperの出力でもそれに習います。前述のシミュレータで言うと、赤がVertex、青がNodeです。
ターゲット言語
前述のように、GLRパーサのデータ構造はとても関数型チックです。
caperは基本的にはC++をターゲット言語とする処理系で、他の言語用のジェネレータは「できるからやった」くらいのものなのですが、GLRの駆動エンジンを実装するにあたってC++はどう考えても不向きです（GCがないときつい）。またデバッグ出力などを必要とする時に、データ構造が1次元のテキスト向きでないので、ビジュアル化したい（そうしないと私の知性ではおそらく理解できない）といった希望もありました。そういったわけで、GCと関数型言語的な機能があり、ウェブブラウザとの親和性も高いJavascriptをターゲット言語としました。
全体構造
複数のパーサが同時に動くところを想像していたので、パーサの上位概念を作ってそれをParserと呼び、今までParserと呼んでいたものをSliceと呼んでみることにしました。
分岐
まず、一番簡単そうな分岐からはじめました。caper(LALR)の出力するスタックは、動的メモリ割り当てなしの配列でロールバックに対応しようとしたりしているため、微妙にややこしい実装になっています。ですので、一旦全部削除してlispっぽい構造に書き直しました。すると、スタック操作を独立させる必要が感じられないほどシンプルになったので、スタックという概念を削除しました。SliceはVertexへのポインタを「head」として一つだけ持つ構造になりました。
スタックがそういった構造になっていると分岐は実際楽で、Sliceがコンフリクトに遭遇したらParserにそれを伝えると、ParserがSliceをcloneする、といった処理で難なく実装できました。
これができれば後は難しいことないだろう、と思っていたら、そうでもなかった……
合流
合流自体は単純な処理（同じ状態にいるSliceを統一するだけ)なのですが、2つほど実装上面倒な点がありました。
reduce
LRパーサは、reduceするとき、文法規則の右側に登場するシンボルの数の分だけスタックをpopして、代わりに左側のnonterminalをpushするような動きをするのですが、合流後のスタックをpopする(合流したVertexを削除する)ということは、すなわちその操作によって合流前のheadが複数露出する可能性があるということなのです。シミュレータでいじってみればなんとなくわかると思います。実装するまでこれに気づいていなくて、結構面倒な目にあいました。
教科書ではどうやってるのか形式的定義とかサンプルコード読んでないのでよくわからないんですが、反射的に「再帰っすよね」と思ったので再帰で書きました。動いてるっぽいです。
合流判定
当初、こんな感じのコードを書いていました。1ポスト＝1サイクルと考えてください。
- 生きているSliceをすべて「reduce集合」に入れ、空の「次のreduce集合」と空の「shift集合」を用意する
- 「reduce集合」に入っているすべてのSliceに対し、
1. そのSliceにトークンをpost
2. 表引きの結果がshiftだったらSliceのクローンをshift集合に入れる
3. 表引きの結果がreduceだったらSliceのクローンを「次のreduce集合」に入れる - 「次のreduce集合」が空でなければ、「reduce集合」にして2へ
- 「shift集合」を全部処理(トークンをshift)
- 「shift集合」を統合
- 「shift集合」を「生きてるSlice」にする
- 1サイクル終了
が、どうもサンプルの結果が合わないので調べたところ、各サイクルは以下のようなアルゴリズムで書くべきだということがわかりました。
- 生きているSliceをすべて「reduce集合」に入れ、空の「shift集合」を用意する
- 「reduce集合」に入っている各Sliceから一つ取り出し、
1. そのSliceにトークンをpost
2. 表引きの結果がshiftだったらSliceのクローンをshift集合に入れる
3. 表引きの結果がreduceだったらSliceのクローンを「reduce集合」に入れる- b, cは同時に行われる可能性もある。
- cはreduce/reduceコンフリクトで複数回行われる可能性もある
- reduceによるpopで前述のようにheadが複数生じた場合も複数回行われる可能性がある
d. 「reduce集合」を統合
e. 「reduce集合」が空になるまで2を繰り返す
- 「shift集合」を統合
- 「shift集合」を全部処理(トークンをshift)
- 「shift集合」を統合
- 「shift集合」を「生きてるSlice」にする
- 1サイクル終了
つまり、何か1個reduceするたびに統合処理が入るということです。統合処理は基本的にO($n^2$)(nは生存パーサ数)なので、これだけ頻繁に行う必要があると重そうだなあという印象です。それでも、とにかくSliceの数は最小限に減らさないと危険なのでしょう。あるいは常に最小であることを保証する必要があるのかもしれませんが、私の知性だとちょっとわかりません。興味のある方は教科書の証明のところを読んでみてください。
ただ、O($n^2$)とはいえ、LALRに毛が生えた程度の文法の場合、だいたいnが1なのでGLRは大体は高速、ということのようです。O(nlogn)程度にする方法もあるでしょうが、nが大体1なのであれば係数負けしそうです。自然言語だったらそれでもO(nlogn)程度にしたほうがいいのかな？ ちょっと測ってみないとわからないですね。
ひょっとしたら、Hacker's delight的なうまい方法がある、かもしれません。
パースフォレスト
パースフォレストについては、OCamlのSetのようなデータ構造がわかっていればだいたいそれと同じなので、直球で書くだけです。Vertex一つが基本的にはNode一つへのポインタを持っています。OCamlのSetなどと一つ違うのは、Vertexを統合した場合にはNodeが複数の値を持つことがある点です。
書き直し
以上で大体動くようにはなりましたが、ここまで書いた時点でSliceという概念とVertexという概念が独立して存在している意義を見失ったので、統合してSliceという概念を削除し、書き直しました。パーサ＝スタック(トップ)です。「現在生きているパーサ」は「parser.heads」になりました。型はVertexです。
ソース
こちらに、caperのGLR/js出力を載せておきました。ご興味のある方はどうぞ。state_*, gotof_*のあたりは機械的に展開されたテーブルですので、読み飛ばして大丈夫です。統合の処理はいまのところちょっと冗長です。
GLRの問題
さて、GLRには、実用にあたって、実装難易度と速度以外にも幾つか問題点があります。いったいそれはなんでしょうか？ ちょっと長くなりすぎましたので、また次回としたいと思います。