(2018.9) 新規作成.
(2019.11) Bison 3.4 で更新.
Bison は, いくつかの添付 skeleton かあるいは独自のものをベースに、それを書き換えることで構文解析器を生成する。その選び方。
Bison 3.0 のスケルトンは, Java を措いておくと, 次のいずれか。これが、困ったことに, 意外と挙動と機能性が違う。できることが直交していない.
yacc.c
lalr1.cc
glr.c
glr.cc
全体を表に整理すると、次になる。
言語 | push parser | table | pure (reentrant) | 宣言 | |
---|---|---|---|---|---|
yacc.c | C | ✓可能 | LALR(1) | %define api.pure full
| |
lalr1.cc | C++ | × | LALR(1) | 常に | |
lalr1.d | D | × | LALR(1) | 常に | |
lalr1.java | Java | ✓可能 | LALR(1) | 常に | |
glr.c | C | × | Generalized LR (GLR) | true / false | %glr-parser
|
glr.cc | C++ | × | Generalized LR (GLR) | 常に | %glr-parser
|
yacc.c
/ lalr1.cc
: %language
宣言で言語を指定した場合は、それが優先される。書かなかった場合は、bison に与えるファイルの拡張子でプログラミング言語が選ばれる.
GLR の場合, %language
は無視される. %skeleton
で指定できる。省略した場合は、拡張子 .yy なら C++ になる。
Java 版は Bison 3.0 より push parser が可能。2020-05-03 ChangeLog より。
結論: 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衝突の解決法
(Bison 3.4) C++版は常に pure になる。Plain C版は, デフォルトでは non-pure だが, glr.c
スケルトンは pure (再入可能) parser にできない。%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 が生成される.