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

[2018-09] 新規作成. [2019-11] Bison 3.4 で更新. [2023-01] Bison 3.8.

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

各スケルトンでコードを生成させるサンプル: cpp-examples/bison at main · netsphere-labs/cpp-examples · GitHub

スケルトン

Bison 3.8 のスケルトンは, D言語, 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.
Bison 3.8 で新たに glr2.cc スケルトンが導入された。%skeleton "glr2.cc" で利用できる。

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

	言語	push parser	table	pure (reentrant)	宣言
yacc.c	Plain C	✓ 可能	LALR(1)	%define api.pure full
lalr1.cc	C++	× No	LALR(1)	常に
lalr1.d	D	✓ Bison 3.8は可能.	LALR(1)	常に
lalr1.java	Java	✓ Bison 3.0	LALR(1)	常に
glr.c	Plain C	× No	Generalized LR (GLR)	true / false	%glr-parser
glr.cc	C++	× No	Generalized LR (GLR)	常に	%glr-parser %language "c++"

yacc.c / lalr1.cc: %language "c++" 宣言 (またはコマンドラインオプション --language c++) でスケルトン lalr1.cc を選択する。bison に与える入力ファイルの拡張子で出力ソースコードの拡張子が変わるが、それとスケルトン選択とは別。入力ファイルを .yy にすると出力が .cc になるが、言語指定しなければ, スケルトンは yacc.c のまま。

GLR の場合も, %language で plain C / C++ を選ぶ。glr2.cc スケルトンは %skeleton で指名するしかない。ファイルの拡張子がスケルトン選択に影響しないのも同様。

Java 版は Bison 3.0 より push parser が可能。2020-05-03 ChangeLog より。

選び方

結論: push parser が必要な時は yacc.c. C++ なら, GLR にしたいときは glr.cc (または glr2.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 にするだけでは不十分。%language か, コマンドラインで -L c++ オプションを与えなければならない.

C++ parser

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

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

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