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

(2018.9) 新規作成.

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.

選び方

push parser

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

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

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

%define api.push-pull both 宣言.

GLR parser

次は, GLR法が必要か.

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

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

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

glr.c スケルトンは pure (再入可能) parser にできない。%define api.pure full がエラーになってしまう。スケルトンのなかを見たところ, フラグでの指定はできず, plain C なら non-pure, C++版なら pure になるようだ。

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

C++ parser

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

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

まとめ

表にした。

push parser table pure (reentrant) language
yacc.c LALR(1) plain C
lalr1.cc × LALR(1) C++
glr.c × GLR × plain C
glr.cc × GLR C++

push parser なら yacc.c. あとは GLR なら glr.cc, そうでないなら lalr1.cc.