Bison: reduce/reduce衝突の解決法 [Bison 3.0対応]

(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 parser

しかしながら, 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];

%%

サポート関数.

C++
[RAW]
  1. #include <stdio.h>
  2. #include "glr.tab.hh"
  3. void yy::parser::error(const std::string& msg)
  4. {
  5. printf("%s\n", msg.c_str());
  6. }
  7. extern void yyrestart( FILE* input_file );
  8. int main()
  9. {
  10. //const char* text = "type t = (a) .. b;";
  11. yyrestart(stdin);
  12. yy::parser my_parser;
  13. // 成功時 0
  14. int r = my_parser.parse();
  15. return r;
  16. }

最後, 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

きちんと判定できている。

LR(1)で対応

Bison: スケルトンの選択 で見たように, glr.cc は機能が不足している。遅い、必要リソースが見通しにくい。無限の対価。

LR(1) で何とかする方法も見ておく。

  1. 構文を変える。

    reduce/reduce衝突が起こる文法は、人間が見ても難しいことが多い。文法を変えてもいいなら、変えるのがもっともいい。上の例だと, 例えばキーワード enum を導入する、とか。

    Python のように, ID が一つだけのときは "," を後ろに書かないといけない、とするのでもいい。

  2. 字句解析を工夫

    レンジの方は式なので、識別子はあらかじめ宣言されたものに限る。enum のほうは逆に、宣言されたものであってはならない。したがい、lexer のほうで、宣言済みかどうかでトークンを分ける。この手法もよく使われる。

  3. 最後、構文規則で頑張る。

構文を書き換える。例えば, 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

できた。