(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
できた。