動機

そもそもは独自言語を作るのが目的だったので、いろいろなパーサジェネレータを試してみたのですが、以下のような感じで満足できるものがありませんでした。

bison・byacc
→設計の古さが目立つ。他のコードの邪魔になる。ライセンスも微妙。
D parser
→最近まで使ってたけど、データの与え方に問題がある。VCで動かすのも大変そうだった
Elkhound
→忘れたけど使いづらかった(サンプル不足で意味がわからなかったんだったかな？)
spirit
→デバッグつらすぎで絶望、涙が出そう
他のもの
→あとはだいたいyaccと同様

現代プログラミングで培われた再利用性を導入すれば、もっといろいろなところでパーサジェネレータを使えるはずなのに、どうも既存のパーサジェネレータは古い設計(yaccの呪縛)から抜け出ていない感があって使いづらいことが多い、ということで車輪の再発明に踏み切りました。そんなわけで、私が思いつく限り、かつ可能な限り、不便な点はすべて取り除いたつもりです。

基本的にドラゴンブック(一部"Modern Compiler Implementation in Ml")のアルゴリズムを素直に実装しただけです。学問的な新しさとかには期待しないでください。

ソースファイルの簡単な説明

grammar.hpp
--- 動的文法定義用インターフェイスクラス群
lr.hpp
--- 動的LR系解析エンジンの共通部
fastlalr.hpp
--- 動的LALR(1)解析エンジン grammar.hppの文法からテーブル・パーサを作成する
↑この3つのファイルが動的パーサエンジン

caper_ast.hpp
--- caper入力文法ファイル(.cpg)の抽象構文木の定義
caper.cpp
--- 本体
caper_cpg.cpp
make_cpg_parser
--- caper入力文法ファイル(.cpg)パーサの作成ルーチン
<動的パーサエンジンの例>
collect_informations
--- ASTからの宣言・型定義の収集
caper_tgt.cpp
make_target_parser
--- 入力文法からターゲット構文解析テーブルを作るルーチン
caper_generate_cpp.cpp
--- c++ジェネレータ
caper_generate_js.cpp
--- JavaScriptジェネレータ

例外安全について

caperの出力するパーサ自身は、一切例外を発生させません。

しかしながら、テンプレートパラメータの「Value」と「SemanticAction」については配慮が必要です。

SemanticActionに関しては、安全かつ効率的にもほとんど変わらない実装を行うことができました。従って、SemanticAction内では自由に例外を発生させてかまいません。SemanticActionが例外によって中断された場合、そのSemanticActionを起動したpost呼び出しも中断され、パーサの内部状態(スタック)もpost呼び出し直前まで巻き戻されます。いわゆる「強い保証」です。

一方、Valueの処理を含むスタックの扱いに関しては、「強い保証」を実現するには、今のところスタックをまるまるバックアップしておくような負荷の高い実装方法しか思いついていません。そのため現状では対処を行っていません。

実際の使用でこれが問題になるのは、テンプレートパラメータ"Value"が

ときです。これらを行わないようにすれば特に問題ありません。たとえば、Valueがintやただのポインタであれば問題ありません。

Valueが上記のメンバ関数で例外を発生させた場合、パーサの状態は不定になり、後続のpostの結果は不定になります(アクセス例外になるかもしれません)。不定になった場合、resetすることで回復できますが、当然パーサの状態は初期状態に戻ります。パーサの状態が不定になってもリソースリークなどは発生しないので、破棄は安全に行うことができます。不定のまま破棄しても構いません。

時間がかかってもパーサの状態を保存しておきたい場合は、コピーコンストラクタを使ってもう一つパーサインスタンスを作っておいてください。上記の「スタックのコピーは高負荷」は一般的な最悪条件を念頭に述べているものであり、LALRパーサのスタックは(文法とデータによりますが)実用上は言うほど深くはならないと思います。

そのほか、caperがスタックにstd::vectorを使う場合、std::vectorがメモリ割り当て等で例外を発生させる可能性がありますが、この場合、パーサは、SemanticAction時の例外と同様に適切に扱います。オプションでSTLを使わないこともでき、その場合例外は発生しませんが、代わりにスタックの大きさに制限が加わります。

まあ、いまのところ、「気を使って作ったつもりだけどまだバグはあるかも」くらいの感じです。