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.

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

	言語	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 が必要かどうか。

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

もし push parser が必要なら, yacc.c 一択になる。C++ parser も GLR [C/C++] も, 実装できないことはないはずだが、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 にできない。 (Bison 3.4) C++版は常に pure になる。Plain C版は, デフォルトでは non-pure だが, %define api.pure true で pure になる。

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

C++ parser

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

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

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