Bison Yacc resolve shift reduce conflict

Question

How can I change this to remove the shiftt/reduce conflict?

var_part
    :                                           
    |   VAR var_declaration SEMIC var_part_multi
    ;

var_part_multi
    :   var_declaration SEMIC var_part_multi    
    |                                           
    ;

var_declaration
    :   ID id_list COLON ID                     
    ;

id_list
    :   COMMA ID id_list                        
    |                                           
    ;

I have two conflicts and the y.output gives me this:

State 19 conflicts: 1 shift/reduce
State 59 conflicts: 1 shift/reduce

state 19

    4 var_part: VAR var_declaration SEMIC . var_part_multi
    5 var_part_multi: . var_declaration SEMIC var_part_multi
    6               
    7 var_declaration: . ID id_list COLON ID

    ID  shift, and go to state 12

    ID        [reduce using rule 6 (var_part_multi)]
    $default  reduce using rule 6 (var_part_multi)

    var_part_multi   go to state 33
    var_declaration  go to state 34

state 59

    5 var_part_multi: . var_declaration SEMIC var_part_multi
    5               | var_declaration SEMIC . var_part_multi
    6               | .  [ID, BEGIN, DOT, IF, FUNCTION, REPEAT, SEMIC, VAL, WHILE, WRITELN]
    7 var_declaration: . ID id_list COLON ID

    ID  shift, and go to state 12

    ID        [reduce using rule 6 (var_part_multi)]
    $default  reduce using rule 6 (var_part_multi)

    var_part_multi   go to state 95
    var_declaration  go to state 34

I know the problem is with the ID, it has two possible routes but I've been trying for the last hour changing the rules, adding precedences and whatnot and wasn't able to remove the conflict. Can you guys help?

Answer 1

You haven't pasted enough of your grammar to answer the question, but it is almost certainly related to the fact that var_part_multi can be empty.

The question is what is the context of the use of var_part; specifically, how it is possible for var_part to be followed by something which starts with ID.

In that case, since var_part_multi can be empty, the parser will have to choose between starting a non-empty var_part_multi using the ID, or reducing an empty var_part_multi (and then reducing a var_part), which will allow the ID to start the non-terminal which can follow var_part.

By the way, in your paste of the y.output file, the third line under State 19 (the one which starts with the number 6) has been truncated. It should resemble the third line under State 59.

If you can't figure out by examining your grammar how ID could follow var_part, it might help to trace the state machine backwards from one of the two conflicted states.

Answer 2

I've tried more than one independent yacc implementation and all of them agree that the grammar you've posted is conflict-free. For example:

$ cat so.y
%token VAR ID COLON SEMIC COMMA

%%

var_part
    :                                           
    |   VAR var_declaration SEMIC var_part_multi
    ;

var_part_multi
    :   var_declaration SEMIC var_part_multi    
    |                                           
    ;

var_declaration
    :   ID id_list COLON ID                     
    ;

id_list
    :   COMMA ID id_list                        
    |                                           
    ;
$ cat y.output
state 0 //

    0 $accept: . var_part
    1 var_part: .  [$end]

    $end  reduce using rule 1 (var_part)
    VAR   shift, and goto state 2

    var_part  goto state 1

state 1 // [$end]

    0 $accept: var_part .  [$end]

    $end  accept

state 2 // VAR

    2 var_part: VAR . var_declaration SEMIC var_part_multi

    ID  shift, and goto state 4

    var_declaration  goto state 3

state 3 // VAR ID COLON ID [SEMIC]

    2 var_part: VAR var_declaration . SEMIC var_part_multi

    SEMIC  shift, and goto state 11

state 4 // VAR ID

    5 var_declaration: ID . id_list COLON ID
    7 id_list: .  [COLON]

    COLON  reduce using rule 7 (id_list)
    COMMA  shift, and goto state 6

    id_list  goto state 5

state 5 // VAR ID [COLON]

    5 var_declaration: ID id_list . COLON ID

    COLON  shift, and goto state 9

state 6 // VAR ID COMMA

    6 id_list: COMMA . ID id_list

    ID  shift, and goto state 7

state 7 // VAR ID COMMA ID

    6 id_list: COMMA ID . id_list
    7 id_list: .  [COLON]

    COLON  reduce using rule 7 (id_list)
    COMMA  shift, and goto state 6

    id_list  goto state 8

state 8 // VAR ID COMMA ID [COLON]

    6 id_list: COMMA ID id_list .  [COLON]

    COLON  reduce using rule 6 (id_list)

state 9 // VAR ID COLON

    5 var_declaration: ID id_list COLON . ID

    ID  shift, and goto state 10

state 10 // VAR ID COLON ID

    5 var_declaration: ID id_list COLON ID .  [SEMIC]

    SEMIC  reduce using rule 5 (var_declaration)

state 11 // VAR ID COLON ID SEMIC

    2 var_part: VAR var_declaration SEMIC . var_part_multi
    4 var_part_multi: .  [$end]

    $end  reduce using rule 4 (var_part_multi)
    ID    shift, and goto state 4

    var_declaration  goto state 13
    var_part_multi   goto state 12

state 12 // VAR ID COLON ID SEMIC [$end]

    2 var_part: VAR var_declaration SEMIC var_part_multi .  [$end]

    $end  reduce using rule 2 (var_part)

state 13 // VAR ID COLON ID SEMIC ID COLON ID [SEMIC]

    3 var_part_multi: var_declaration . SEMIC var_part_multi

    SEMIC  shift, and goto state 14

state 14 // VAR ID COLON ID SEMIC ID COLON ID SEMIC

    3 var_part_multi: var_declaration SEMIC . var_part_multi
    4 var_part_multi: .  [$end]

    $end  reduce using rule 4 (var_part_multi)
    ID    shift, and goto state 4

    var_declaration  goto state 13
    var_part_multi   goto state 15

state 15 // VAR ID COLON ID SEMIC ID COLON ID SEMIC [$end]

    3 var_part_multi: var_declaration SEMIC var_part_multi .  [$end]

    $end  reduce using rule 3 (var_part_multi)

$