bison conflicts shift/reduce

Question

I am a novice to bison\ yacc and I'm trying to write a pascal-like syntactic analyzer and I'm getting

analizorSintactic.y: conflicts: 1 shift/reduce 
analizorSintactic.y:65.13-23: warning: rule useless in parser due to conflicts: decllist: declaration

I'm getting the warning on the following grammar rules

program : PROGRAM IDENTIFIER SEMICOLON content; 
content : VAR decllist SEMICOLON cmpdstmt DOT ;

decllist :  declaration | declaration SEMICOLON decllist ;
declaration : IDENTIFIER COLON type 
        | IDENTIFIER COMMA declaration;

How can I fix this conflict? Thank You!

akim akim · Accepted Answer · 2013-12-02T08:15:58

First of all, please post something with is self-sufficient. It's not too hard: turn into token the nonterminals that you don't need in your grammar fragment. In your case:

%%
program : "PROGRAM" "IDENTIFIER" "SEMICOLON" content; 
content : "VAR" decllist "SEMICOLON" "cmpdstmt" "DOT" ;

decllist :  declaration | declaration "SEMICOLON" decllist ;
declaration : "IDENTIFIER" "COLON" "type" 
        | "IDENTIFIER" "COMMA" declaration;

Then, feed this to bison --report=all and read the generated *.output file, which contains:

State 10

    3 decllist: declaration .  ["SEMICOLON"]
    4         | declaration . "SEMICOLON" decllist

    "SEMICOLON"  shift, and go to state 14

    "SEMICOLON"  [reduce using rule 3 (decllist)]

In other words Bison does not know how to read a declaration followed by a ;. This is because there a "single" declaration (rule 3) can be followed by a ; because of the rule of content. This conflict cannot be solved by precedence/associativity, because on some occasion the shift is right (if there is a decllist after the ;), on others the reduce is right (because there is a cmpdstmt after the ;). You have to rewrite your grammar to help the parser generator "see farther in the rules".

For instance you can send the ; from the content rule, to the decllist rule:

%%
program : "PROGRAM" "IDENTIFIER" "SEMICOLON" content; 
content : "VAR" decllist "cmpdstmt" "DOT" ;

decllist : declaration "SEMICOLON"
         | declaration "SEMICOLON" decllist ;
declaration : "IDENTIFIER" "COLON" "type" 
        | "IDENTIFIER" "COMMA" declaration;

That should do it.

bison conflicts shift/reduce

1 Answers