パーサジェネレータ caper
"caper" （github）は拙作のパーサジェネレータです。yaccやbisonなどと同じ場所で使うツールです。
基本的にはC++コードを生成するために作ったのですが、そのほかにもJavascript, D, Java, C#などのコードを出力することができます。
特長
大きなところでは、こんな特長があります。
- 出力コードが全部テンプレートクラスでヘッダファイル一つなので、ライブラリなどをリンクする必要がない
- 出力コードが大変ヒューマンリーダブル（手書きで書いたと強弁できるLALRパーサ、というコンセプト）
- PUSH型（パーサは常に受身で、トークンをポストするまで動かない）
そのほかの特長については、http://jonigata.github.io/caper/caper_more.html を御覧ください。
歴史など
このソフトは結構古いソフトで、初出は2006年です。なんで今頃また持ち出してきたかというと、とある人から「大きい文法で7分かかってたのを30秒にした」というプルリクエストを受け取ったためです。それをきっかけに、今まで戦略的なアルゴリズムの問題で遅いと思ってたのが、実は戦術的な問題で遅かっただけなのでは？ と疑念を抱いていろいろ見なおしてみたところ、3秒まで縮まってしまいました。さらに、すでにほとんど忘れていたソースを読みなおすことによってほぼ把握できたため、積んでいた拡張リクエスト（C++11対応、EBNF対応）を消化する気になってしまったわけです。
新仕様
EBNF
というわけで、そこのドキュメントにはまだ書いてありませんが、githubの最新バージョンでは、EBNF対応が実装してあります。対応する機能は以下のとおりです。
- '*' 0個以上のリスト
- '+' 1個以上のリスト
- '?' 0個または1個
- '/' (オリジナル仕様) a/bの形で指定すると、a(ba)*にマッチしてbを捨てる（コンマ区切りリストなどに有用）
カッコには対応していません。caperの型付けの強い仕様だと、カッコには結局セマンティックアクションを指定しなければならず、「名前を考えなくて良い」以外のメリットが見当たらなかったためです。
EBNF拡張の文法等については https://github.com/jonigata/caper/tree/master/caper/samples/grammar にある"list0" "list1" "list2" "optional"あたりを参考にしてください。これらの文法ファイルを使う側はどうすればよいかについては、https://github.com/jonigata/caper/tree/master/caper/samples/cpp この辺りを参考にしてください。
エラーリカバリ
また、簡単なエラーリカバリを実装してあります。機能は多分yaccとだいたい同じです。
%recover error;
で"error"という識別子をリカバリ指定用識別子として利用できるようになります。
文法等についてはサンプルディレクトリの「recovery0」「recovery1」を参考にしてください。
ジェネレータをリライト
その他、この機会に書きづらかったジェネレータをヒアドキュメント的な記法で一新しました。新しいジェネレータを作るのも簡単になっていると思います。
関連情報
-
こんな記事を書いてくださった方もいます。出力パーサが読みやすいので、LALRの学習にも向いているようです。（http://d.hatena.ne.jp/ytqwerty/20080304#p3）
-
また、どの程度の範囲かわかりませんが、caperから一部利用するなどしてパーサジェネレータを作られた方もいらっしゃいます。自分でも信じられませんが、アルゴリズムには問題なかったみたいですね。
各言語ジェネレータ
上記出力可能な言語のうちC++, Javascript, Dについては最近書きなおしたので新しい仕様に追従していますが、C#・Javaに関しては気に入ってくださったユーザの方からいただいたコードである上、自分で使わない言語なので今でもcaperの仕様変更や言語自体の仕様変更に追従して動く状態なのかどうか自信がありません。どなたか得意な方に書きなおして貰えると嬉しいです。ジェネレータを書く場合は、現状のまま当該言語で一度hello0.cpgなどからパーサを出力しておいて、上記3つの中から近いものを選んで置き換え、最初の出力を見ながら直すのが一番ラクなのではないかと思います。
その他の言語についてもプルリクエストは大歓迎です。