yacc Shift/Reduce conflicts

Question

For the following grammar i have encountered SR errors.

This is my Grammar

program : CLASS Program '{' field_decl '}'
        ;    
field_decl : type field_part ';'
           | field_part field_fact
           | meth_decl
           |
           ;    
field_fact : ',' field_decl
           | field_part
           ;    
field_part  : IDENTIFIER field_part2
            ;    
field_part2 :
            | '[' int_literal ']' field_decl
            ;    
meth_decl   : type meth_decl1
            | VOID meth_decl1
            ;    
meth_decl1  : IDENTIFIER '(' meth_part ')' block 
            ;    
meth_part   : type meth_part1
            |
            ;    
meth_part1  : IDENTIFIER meth_part2
            ;                
meth_part2  :
            | ',' meth_part
            ;    
block       : '{' block_list '}'
            ;    
type        : INT
            | BOOLEAN
            ;    
block_list  : var_decl
            |
            ;    
var_decl    : type ids ';'
            | statement
            ;    
ids         : IDENTIFIER ids_part
            ;    
ids_part    :
            | ',' ids
            ;    
statement   : location ASSIGNMENT_OPERATOR expr ';'
            | method_call ';'
            | IF '(' expr ')' block ELSE block 
            | IF '(' expr ')' block
            | FOR IDENTIFIER '=' expr ',' expr block
            | RETURN expr ';'
            | RETURN ';'
            | BREAK ';'
            | CONTINUE ';'
            | block
            ;    
location    : IDENTIFIER loc_part
            ;               
loc_part    : 
            | '[' expr ']'
            ;    
method_call : IDENTIFIER '(' ')'
            | IDENTIFIER '(' expr_block ')'
            | CALLOUT '(' STRING_LITERAL ')'
            | CALLOUT '(' STRING_LITERAL ',' callout_arg_block ')'
            ;    
callout_arg_block : callout_arg
                  | callout_arg ',' callout_arg_block
                  ;    
callout_arg : expr
            | STRING_LITERAL
            ;    
expr        : location
            | method_call
            | literal
            | expr bin_op expr
            | MINUS expr
            | '!' expr
            | '(' expr ')'
            ;    
expr_block  : expr expr_fact
            ;    
expr_fact   : 
            |  ',' expr_block
            ;
bin_op      : ARITHEMATIC_OPERATOR
            | EQUALS_OPERATOR
            | RELATIONAL_OPERATOR
            | CONDITIONAL_OPERATOR
            ;
literal     : int_literal
            | bool_literal
            ;
int_literal : DIGIT
            | HEXADECIMAL_VALUE
            ;
bool_literal    : TRUE
                | FALSE
                ;

and the output bison shows is

State 19 conflicts: 1 shift/reduce

State 33 conflicts: 1 shift/reduce

State 87 conflicts: 4 shift/reduce

State 107 conflicts: 4 shift/reduce

how can i rewrite the grammar so as to remove these conflicts

rici rici · Accepted Answer · 2014-11-04T17:12:19

I didn't actually compile the grammar to check, so the following may not be exhaustive.

Basically, you have both of the classic shift/reduce conflicts:

Your expression grammar is ambiguous:
```
expr: expr bin_op expr
```
The grammar does not allow the parser to decide which bin_op has precedence in any given expression, so it would allow (for example) 3 + 4 * 5 to be parsed as either expr(3 + 4) bin_op(*) expr(5) or as expr(3) bin_op(+) expr(4 * 5). The usual solution to this problem is to use precedence declarations, but those are not compatible with clumping all binary operators into a single production.

See Yacc/Bison, minimize amount by grouping math ops and read the bison manual section on precedence.
Your if statements are ambiguous. For example, in
```
if ( <expr> ) if ( <expr> ) <block> else <block>
```
the grammar does not specify to which if the else applies.

In this specific case, the default bison rule (which is to favour shift over reduce) will do the right thing (by associating the else with the innermost if), but it will still report a shift/reduce conflict.

See the bison manual for an example (in the previously-linked section) or look at Removing shift/reduce conflict on optional else block and Reforming the grammar to remove shift reduce conflict in if-then-else

yacc Shift/Reduce conflicts

1 Answers