How to find shift/reduce conflict in this yacc file?

Question

When I try to use yacc on the following file I get the error conflicts: 1 shift/reduce How can I find and fix the conflict?

/* C-Minus BNF Grammar */

%token ELSE
%token IF
%token INT
%token RETURN
%token VOID
%token WHILE

%token ID
%token NUM

%token LTE
%token GTE
%token EQUAL
%token NOTEQUAL
%%

program : declaration_list ;

declaration_list : declaration_list declaration | declaration ;

declaration : var_declaration | fun_declaration ;

var_declaration : type_specifier ID ';'
                | type_specifier ID '[' NUM ']' ';' ;

type_specifier : INT | VOID ;

fun_declaration : type_specifier ID '(' params ')' compound_stmt ;

params : param_list | VOID ;

param_list : param_list ',' param
           | param ;

param : type_specifier ID | type_specifier ID '[' ']' ;

compound_stmt : '{' local_declarations statement_list '}' ;

local_declarations : local_declarations var_declaration
                   | /* empty */ ;

statement_list : statement_list statement
               | /* empty */ ;

statement : expression_stmt
          | compound_stmt
          | selection_stmt
          | iteration_stmt
          | return_stmt ;

expression_stmt : expression ';'
                | ';' ;

selection_stmt : IF '(' expression ')' statement
               | IF '(' expression ')' statement ELSE statement ;

iteration_stmt : WHILE '(' expression ')' statement ;

return_stmt : RETURN ';' | RETURN expression ';' ;

expression : var '=' expression | simple_expression ;

var : ID | ID '[' expression ']' ;

simple_expression : additive_expression relop additive_expression
                  | additive_expression ;

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ;

additive_expression : additive_expression addop term | term ;

addop : '+' | '-' ;

term : term mulop factor | factor ;

mulop : '*' | '/' ;

factor : '(' expression ')' | var | call | NUM ;

call : ID '(' args ')' ;

args : arg_list | /* empty */ ;

arg_list : arg_list ',' expression | expression ;

Solution 1

As mientefuego pointed out you grammar has the classic "dangling else" problem. You could beat the problem by assigning precedence to the rules that causes conflict.

The rule causing conflict is:

selection_stmt : IF '(' expression ')' statement
               | IF '(' expression ')' statement ELSE statement ;

First start by making ELSE and LOWER_THAN_ELSE ( a pseudo-token ) non associative:

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE

This gives ELSE more precedence over LOWER_THAN_ELSE simply because LOWER_THAN_ELSE is declared first.

Then in the conflicting rule you have to assign a precedence to either the shift or reduce action:

selection_stmt : IF '(' expression ')' statement    %prec LOWER_THAN_ELSE ;
               | IF '(' expression ')' statement ELSE statement ;

Here, higher precedence is given to shifting. I have incorporated the above mentioned corrections and listed the complete grammar below:

/* C-Minus BNF Grammar */

%token ELSE
%token IF
%token INT
%token RETURN
%token VOID
%token WHILE

%token ID
%token NUM

%token LTE
%token GTE
%token EQUAL
%token NOTEQUAL

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE
%%

program : declaration_list ;

declaration_list : declaration_list declaration | declaration ;

declaration : var_declaration | fun_declaration ;

var_declaration : type_specifier ID ';'
                | type_specifier ID '[' NUM ']' ';' ;

type_specifier : INT | VOID ;

fun_declaration : type_specifier ID '(' params ')' compound_stmt ;

params : param_list | VOID ;

param_list : param_list ',' param
           | param ;

param : type_specifier ID | type_specifier ID '[' ']' ;

compound_stmt : '{' local_declarations statement_list '}' ;

local_declarations : local_declarations var_declaration
                   | /* empty */ ;

statement_list : statement_list statement
               | /* empty */ ;

statement : expression_stmt
          | compound_stmt
          | selection_stmt
          | iteration_stmt
          | return_stmt ;

expression_stmt : expression ';'
                | ';' ;

selection_stmt : IF '(' expression ')' statement    %prec LOWER_THAN_ELSE ;
               | IF '(' expression ')' statement ELSE statement ;

iteration_stmt : WHILE '(' expression ')' statement ;

return_stmt : RETURN ';' | RETURN expression ';' ;

expression : var '=' expression | simple_expression ;

var : ID | ID '[' expression ']' ;

simple_expression : additive_expression relop additive_expression
                  | additive_expression ;

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ;

additive_expression : additive_expression addop term | term ;

addop : '+' | '-' ;

term : term mulop factor | factor ;

mulop : '*' | '/' ;

factor : '(' expression ')' | var | call | NUM ;

call : ID '(' args ')' ;

args : arg_list | /* empty */ ;

arg_list : arg_list ',' expression | expression ;

Solution 2

Ahem, the correct answer to this problem is usually: do nothing.

Shift/reduce conflicts are expected with ambiguous grammars. They are not errors, they are conflicts.

The conflict will be resolved by preferring shift over reduce, which just happens to solve the canonical dangling else problem.

And bison even has an %expect n statement so that you don't get a S/R conflict warning when there are exactly n conflicts.

Comments

[new_perl]

Why should I make ELSE and LOWER_THAN_ELSE ( a pseudo-token ) non associative in the first place??

[ardsrk]

Oh. I had overlooked it. It does not seem necessary as ELSE and LOWER_THAN_ELSE don't have the same precedence.

[user764754]

%nonassoc is necessary. Using only %token won't tell bison anything about the precedence.

[Ron Burk]

%expect is a most horrible invention. It's like telling your QC department "we expect 5 bugs, so ship it if the number of bugs is exactly 5". No distinction between the bug that is a misspelled error message and the bug that formats your hard drive. :-)

[DigitalRoss]

But ... but ... s/r conflicts are not bugs. It's true that marking specific conflicts would be preferable but the conflicts aren't exactly in the rules as such, they are in the generated state machine. So we kludge it with %expect. Welcome to the real world.

[DigitalRoss]

And all of this produces the exact same result as the original yacc. It might be useful to point out that the original conflict is expected and was correctly resolved by the yacc default of preferring the shift.

[Tomato]

Thanks, I've corrected the link to the a proper one!