Bison shift/reduce error

Question

I have an error in bison which I do not know how to fix.

I get 1 shift/reduce errors when trying to compile my grammar:

START: type_specifier MAIN LBR_R RBR_R LBR_C program RBR_C

program: statement ; 

type_specifier: INT | DOUBLE | VOID;


var_declaration: type_specifier var_declist SECOLON;

var_declist: var_declist COMMA var_intialise | var_intialise;

var_intialise: var_ID | var_ID EQL simple_expression; 



assign : var_ID EQL simple_expression SECOLON; 


statement: expression_stmt | local_declaration | selection_stmt | iteration_stmt| return_stmt | break_stmt; 

local_declaration: var_declaration | assign; 

expression_stmt: expression SECOLON | SECOLON;

selection_stmt: IF LBR_R simple_expression RBR_R LBR_C statement RBR_C;

iteration_stmt: WHILE LBR_R simple_expression RBR_R LBR_C statement RBR_C;

return_stmt: RETURN SECOLON | RETURN expression SECOLON; 

break_stmt: BREAK SECOLON; 




expression: var_ID EQL expression | var_ID INCR_EQL expression | var_ID DECR_EQL expression | var_ID INCR | var_ID DECR | simple_expression; 

simple_expression: simple_expression OR and_expression | and_expression; 

and_expression: and_expression AND unary_rel_expression | unary_rel_expression; 

unary_rel_expression: NOT rel_expression | rel_expression; 

rel_expression: sum_expression relop sum_expression | sum_expression;

relop: LSS_EQL | LSS | GR | GR_EQL | EQUIV | NOT EQL;

sum_expression: sum_expression sumop term | term; 

sumop: ADD | SUB;

term: term mulop unary_expression | unary_expression; 

mulop: MULT | DIV | RMDR; 

unary_expression: factor; 

factor: immutable | var_ID; 

var_ID: ID;

immutable: LBR_R expression RBR_R | call | constant; 

call: ID LBR_R args RBR_R; 

args:  | arg_list; 

arg_list: arg_list COMMA expression | expression; 
constant: INT | CHAR | STRING;

I get 1 shift/reduce at

State 102 conflicts: 1 shift/reduce

The specific states are :

state 102

   11 assign: var_ID EQL simple_expression . SECOLON
   32 expression: simple_expression .  [SECOLON]
   33 simple_expression: simple_expression . OR and_expression

    OR       shift, and go to state 63
    SECOLON  shift, and go to state 111

    SECOLON  [reduce using rule 32 (expression)]

Could someone please explain how to fix this error, I know it has something to do with precedence.

rici rici · Accepted Answer · 2015-03-22T00:12:03

This has nothing to do with precedence.

Here's the relevant subset of your grammar:

statement: expression_stmt | local_declaration
expression_stmt: expression ';'
expression: var_ID EQL expression | simple_expression
local_declaration: assign
assign: var_ID EQL simple_expression ';'

That's clearly ambiguous; var = <simple_expression> ; could either be an expression_stmt or a local_declaration. This sort of ambiguity would normally result in a reduce/reduce conflict, but in this case you get a shift/reduce conflict because of the way you handle semicolons. In any event, the solution is to remove the ambiguity.

Bison shift/reduce error

1 Answers