(2018.9) 新規作成.
reduce/reduce衝突のある文法の解決方法について。reduce/reduce衝突が起こったときに, じゃあどうやって解消するのか書いてある Webページが全然なかった。
reduce (還元) は, 構文規則の右側にマッチしたときに、左辺に置き換えること。ある入力テキストが与えられたときに, 同時に複数の規則で還元が起こりうる場合が、reduce/reduce衝突になる。
こういう入力テキストを受け付ける構文を考える。レンジと enum という二つの構文.
type subrange = lo .. hi; type enum = (a, b, c);
次の例は、レンジの下限、上限に式を取れる。それがもとで、構文規則の衝突がある。
/* glr.tab.h を生成 */
%defines
%error-verbose
/* GLR parser
#define YYSKELETON_NAME "glr.c"
*/
%glr-parser
%token TK_TYPE DOTDOT
%token ID
%left '+' '-'
%{
#include "glr.tab.hh" // YYSTYPE が定義される
extern int yylex( YYSTYPE* yylval_param );
%}
%%
type_decl : TK_TYPE ID '=' type ';'
;
type : '(' id_list ')' { printf("id_list\n"); }
| expr DOTDOT expr { printf("dotdot\n"); }
;
id_list :
ID
| id_list ',' ID
;
expr:
'(' expr ')'
| expr '+' expr
| expr '-' expr
| ID
;
bison に -v オプションを与え, state report (.output ファイル) を生成する。ここで衝突している.
State 10
4 id_list: ID .
9 expr: ID .
'+' reduce using rule 9 (expr)
'-' reduce using rule 9 (expr)
')' reduce using rule 4 (id_list)
')' [reduce using rule 9 (expr)]
$default reduce using rule 4 (id_list)
ふむふむ. 次の入力例で a の直後にカーソルがあるときに ')' が来る, どちらのルールで還元するか, で衝突している.
type t = (a);
LR(1) では, 先読みが一つだけなので, 本当は曖昧ではないにも関わらず, うまく判定できない. bison コマンドは、不味いことに, reduce/reduce衝突を警告で済ましてしまい、エラーにしない。実際には常にデフォルトルール (最初のルール) で還元されてしまうのに。
しかしながら, GLR 法を使うと, いくらでも判断を保留するため, 解決できる。やってみよう.
/* YY_NO_UNPUT が定義され, yyunput() がコメントアウトされる. */
%option nounput
/* ファイル一つで終了 */
%option noyywrap
%{
#include "glr.tab.hh"
%}
%%
[a-zA-Z][a-zA-Z0-9]* {
if (!strcmp(yytext, "type"))
return yy::parser::token::TK_TYPE;
else
return yy::parser::token::ID;
}
".." return yy::parser::token::DOTDOT;
[ \t\r\n]+ { }
. return yytext[0];
%%
サポート関数.
最後, Makefile.
TARGETS = glr glr.jpg lr1 CC = gcc CFLAGS = -Wall -x c++ all: $(TARGETS) # GLR parser YACC_OUTPUT = glr.tab.cc glr.tab.hh glr.dot glr.output glr: glr.tab.o lex.yy.o support.o $(CC) $^ -o $@ -lstdc++ glr.tab.o: glr.tab.cc glr.tab.hh # 拡張子を .yy にするだけでは, glr.tab.cc/hh は生成されるが, スケルトンは # glr.c のまま. YYPURE 0 # -L c++ を与えると, glr.cc になって, YYPURE 1 になる. $(YACC_OUTPUT): glr.yy bison -W -L c++ -v --graph $< glr.jpg: glr.dot dot -Tjpg $< > $@ ## LR(1) parser LR1_OUTPUT = lr1.tab.c lr1.tab.h lr1: lr1.tab.o lex.yy.o support.o $(CC) $^ -o $@ lr1.tab.o: lr1.tab.c lr1.tab.h $(LR1_OUTPUT): lr1.y bison -W $< ## support support.o: support.cc glr.tab.hh lex.yy.o: lex.yy.c glr.tab.hh lex.yy.c: lex.l glr.tab.hh flex --bison-bridge $< clean: rm -f $(TARGETS) $(YACC_OUTPUT) $(LR1_OUTPUT) lex.yy.c *.o *~
できあがった glr コマンドに入力テキストを与える.
$ ./glr type t = (a) .. b; dotdot $ ./glr type t = (a); id_list
きちんと判定できている。
Bison: スケルトンの選択 で見たように, glr.cc は機能が不足している。遅い、必要リソースが見通しにくい。無限の対価。
LR(1) で何とかする方法も見ておく。
reduce/reduce衝突が起こる文法は、人間が見ても難しいことが多い。文法を変えてもいいなら、変えるのがもっともいい。上の例だと, 例えばキーワード enum を導入する、とか。
Python のように, ID が一つだけのときは "," を後ろに書かないといけない、とするのでもいい。
レンジの方は式なので、識別子はあらかじめ宣言されたものに限る。enum のほうは逆に、宣言されたものであってはならない。したがい、lexer のほうで、宣言済みかどうかでトークンを分ける。この手法もよく使われる。
構文を書き換える。例えば, shift/reduceにすればshiftが選ばれることを利用して, 構文規則を展開してみる。
/* lr1.tab.h を生成 */
%defines
%error-verbose
%token TK_TYPE DOTDOT
%token ID
%left '+' '-'
%{
#include "lr1.tab.hh"
extern int yylex( yy::parser::semantic_type* yylval_param );
%}
%%
/*
type subrange = lo .. hi;
type enum = (a, b, c);
*/
type_decl : TK_TYPE ID '=' type ';'
;
type : '(' id_list ')' { printf("id_list\n"); }
| '(' ID ')' { printf("id_list: single\n"); }
| '(' ID ')' DOTDOT expr { printf("dotdot: single\n"); }
| expr DOTDOT expr { printf("dotdot\n"); }
;
id_list :
ID ',' ID
| id_list ',' ID
;
expr:
'(' expr ')'
| expr '+' expr
| expr '-' expr
| ID
;
適当にコンパイルして、試してみる.
$ ./lr1 type t = (a) .. b; dotdot: single $ ./lr1 type t = (a); id_list: single $ ./lr1 type t = (a + b) .. c; dotdot $ ./lr1 type t = (a, b, c); id_list
できた。