Bison: スケルトンの選択 [Bison 3.4対応]

(2018.9) 新規作成.

(2019.11) Bison 3.4 で更新.

Bison は, いくつかの添付 skeleton かあるいは独自のものをベースに、それを書き換えることで構文解析器を生成する。その選び方。

スケルトン

Bison 3.0 のスケルトンは, Java を措いておくと, 次のいずれか。これが、困ったことに, 意外と挙動と機能性が違う。できることが直交していない.

yacc.c: It used to be named bison.simple: it corresponds to C Yacc compatible LALR(1) parsers.
lalr1.cc: Produces a C++ parser class.
glr.c: A Generalized LR C parser based on Bison's LALR(1) tables.
glr.cc: A Generalized LR C++ parser. Actually a C++ wrapper around glr.c.

全体を表に整理すると、次になる。

yacc.c / lalr1.cc: %language 宣言で言語を指定した場合は、それが優先される。書かなかった場合は、bison に与えるファイルの拡張子でプログラミング言語が選ばれる.

GLR の場合, %language は無視される. %skeleton で指定できる。省略した場合は、拡張子 .yy なら C++ になる。

結論: push parser が必要な時は yacc.c. C++ なら, GLR にしたいときは glr.cc, そうでないなら lalr1.cc.

まず, push parser が必要かどうか。

push parser は、最後まで入力を読みきるのではなく, 一つ読み進めるごとにパーサから return するもの。ストリームパーサを作るときは, push parser にしたい。

もし push parser が必要なら, yacc.c 一択になる。C++ parser も GLR [C/C++] も, 実装できないことはないはずだが、Bison 3.0 では用意されていない。

%define api.push-pull both 宣言.

次は, GLR法が必要か.

.y ファイル内で %glr-parser を指定すると, Generalized LR (GLR) 法になる。

GLR法は, いくらでも必要なだけ分岐を保留し, 最終的に解決できる限り、あらゆる曖昧ではない文法を処理できる。LR(1) だと先読みが一つだけのためエラーになってしまうような reduce/reduce衝突も, 問題にならない。でも遅い。

別ページで実際に GLR法を試してみる; Bison: reduce/reduce衝突の解決法

~~glr.c スケルトンは pure (再入可能) parser にできない。~~ (Bison 3.4) C++版は常に pure になる。Plain C版は, デフォルトでは non-pure だが, %define api.pure true で pure になる。

GLR で C++ 版を選ぶには, ファイルの拡張子を .yy にするだけでは不十分。コマンドラインで -L c++ オプションを与えなければならない.

最後は, C++ parser にするかどうか.

Bison 3.0 がリリースされたのは 2013年7月. もうずいぶん経っている。新しく作るなら, C++ parser でいいように思う。

lalr1.cc であれ glr.cc であれ, 'parser' class が生成される.