前回に引き続きbisonネタ。
bisonで構文解析器を作っていて、文法が複雑になってくると急に表れて、開発者を地獄に突き落とすのがコンフリクトです。結局どこがどうコンフリクトしてるのかよくわからなくて放置してたり。(私だけ?)Palan開発当初は何がどうなっているのかさっぱりわからず、しばらく見なかったことしてました。ここでは私がやっている対処方法を紹介します。

コンフリクトとは

コンフリクトとは「文法があいまい(2種類上の解釈ができる)で定義された文法どおり正しく解析できない」とbisonが教えてくれる警告です。種類としては「shift/reduce conflict」/ 「reduce/reduce conflict」がありますが、正直あまり詳しくないので説明は省きます。shift/reduce conflictは大丈夫な場合がありますが、やはりなぜかが分かっていないと放置は危険と思います。また文法があいまいでなくても出る場合があります。bisonは通常トークン1文の先読みしかできないからです。2つ以上のトークンを先読みしないと確定できない文法はコンフリクトと判断されてしまいます。

コンフリクトの例

例として以下の様な謎言語を設計してみます。何できるかさっぱりですが、とりあえず複数の戻り値を返せそうです。また戻り値の宣言では型だけでなく名前を付けたり省略することもできる様です。

int y,z;
calc(y+z, 3);
int a, float calc(int x, float y)
{
   x-1; y+1;
}

これが読めそうな構文解析器を勢いで書いてみましょう。いかにもコンフリクトしそうですが意図は明確と思います。

前提としては字句解析yylexは数字がきたらINT、アルファベットがきたらID、それ以外の記号がきたらその文字を返すとします。

conflict.yy

%skeleton "lalr1.cc"
%require "3.0.4"
%defines

%code
{
int yylex();
}

%token INT
%token ID

%start module

%%
module: /* empty */
    | module function_definition
    | module statement
    ;

function_definition: return_values ID '(' parameters ')' block
    ;

return_values: return_value
    | return_values ',' return_value
    ;
return_value: type_def ID
    | type_def
    ;

parameters: parameter
    | parameters ',' parameter
    ;
parameter: type_def ID 
    ;

block: '{' statements '}'
    ;

statements: statement
    | statements statement
    ;

statement: declarations ';'
    | expression ';'
    | func_call
    | block
    ;

declarations: declaration
    | declarations ',' declaration 
    ;
declaration: type_def ID
    ;

func_call: ID '(' arguments ')'
    ;
arguments: expression
    | arguments ',' expression
    ;
expression:
    | expression '+' expression
    | expression '-' expression
    | term
    ;

term: INT
    | ID
    ;

type_def: ID
%%

さてbisonで構文解析器を生成するためにコマンド叩いてみましょう。

$ bison conflict.yy
conflict.yy: warning: 6 shift/reduce conflicts [-Wconflicts-sr]
conflict.yy: warning: 1 reduce/reduce conflicts [-Wconflicts-rr]

はい、出ましたconflicts。コンフリクトさせようとしたからそりゃ出るのですが、思ったのとちょっと違う。。う、これを調べて直すのか。。。私の心が折れそうです。

コンフリクトを分析して解決する

うーん、大変そうなので、次回にまわそう(汗)。
問題解決の手がかりは下記のコマンドです。

$ bison conflict.yy  -r all --report-file=conflict.log

次回へ続く。