前回までの内容はこちらです。
caperの紹介
GLRパーサの実装(背景編)
GLRパーサの実装(コーディング編)
今回は、GLRを実用する上での問題点について考えていきたいと思います。
GLRの実用上の問題点
GLRは決定的でない
私が考える、GLRパーサジェネレータを実用化する上での一番の問題は、「真実はいつもひとつ」じゃないことです。前々回ご紹介したシミュレータをいじっていただければわかると思いますが、文法的には正しくても複数の解釈が可能なのです。
LALRパーサであれば、deterministicであるため、エラー以外でセマンティックアクションの結果が捨てられることはありません。そのため、例えばセマンティックアクションの中でASTノードが生成された場合、エラーに遭遇しなければそのノードはまず確実に使われます。
ところが、GLRは、今まで解説してきたように、曖昧な局面ではパーサを複製しますので、仮に最終的にはひとつの解釈に収まるような文法であっても、そこに至るまでに本筋でないパーサがセマンティックアクションを起動してしまうことがあります。その結果、全体としてはパースに失敗していないのに、セマンティックアクションの結果が無用のものとして捨てられるといったことが頻繁に発生し得ます。
また、GLRでは、単純に、ひとつの文章について合法的に複数の解釈が可能になるという問題も挙げられます。どれが望む解釈なのかをユーザに選択させる方法が必要になってくるでしょう。
GLRパーサのデータ構造は単純でない
前回示したように、GLRパーサのデータ構造は通常のLRパーサほど単純ではありません。もしGCのない言語で実装しようとすると、ヒープを利用してshared_ptr的なものを使うか、あるいは自前でアロケータを作るようなことをするしかないと思います。またGCが存在する環境で動かすとしても、ある程度ヒープを食い散らかすような動作にせざるを得ないでしょう。応用はその分狭まることになるかと思います。
また、GCのない環境では、上記の「全体としてはエラーが起きていないのにセマンティックアクションの結果が捨てられることがある」問題にも、ユーザが対応しなければいけません。つまり、ユーザがGCのようなものを用意しなければならないことになります。C++であれば、現実的にはshared_ptrを使うしかないのではないでしょうか？
私の考える「便利なGLR」
そういったようなことを踏まえると、やはりGLRの真価は、「スキャナーレスでASTまで生成してくれる」ような「こまけえことはいいんだよ型オールインワンフロントエンドジェネレータ」でこそ発揮されると思っています。caperでかなりの部分を汎用的にしたのとは真逆の方向性です。ジェネレータも、C++では現実的にはshared_ptr以外考えにくいのでそうと決めつけるし、C++以外のジェネレータではもちろん容赦なくGCを使う感じです。
急にDSLが欲しくなった時にものすごく気軽に作れる道具、というのが想定しているユースケースです。
といったわけで、これから作るGLRパーサはcaperとしては独立したコマンドにしようかと思っています。レポジトリは面倒なので一緒にしようかと思っていますが。もしご興味のあるかたがいらっしゃったら、ぜひjonigata@twitterをフォローしていただけると励みになります。