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 ;

Answer 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 ;

Answer 2

maybe you should try a yacc -v <filename>, it generates an output of the details.

I tested here, and your grammar description fails in the classic "dangling else" problem.

Take a look at this Wikipedia article.

Answer 3

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.

Answer 4

First, get a state machine output from yacc. A state which can be either shifted or reduced represents a shift/reduce conflict. Find one, and then solve the conflict by rewriting the grammar.

Answer 5

This article gives an alternative solution to the one posted by ardsrk.