Bison/Yacc reduce reduce conflict for a specific grammar example

Question

I have a parser project for my compilers class. I could not resolve a reduce/reduce conflict for one of the rules.

The graphical representation of this grammar rule is available at this link (sorry I cannot post the image here, due to stackoverflow policies):

Graphical representation of the "type" grammar rule

Where all the ovals are terminal symbols.

Since this rule looks a little complicated, I tried to break it down into smaller pieces. Here is my attempt to construct the grammar:

type    :   id_or_int   brackets_or_end
        ;
id_or_int   :   IDnum
        |   INTnum
        ;
brackets_or_end :   brackets    remainingpartboe
        |
        ;
brackets    :   LBRACnum    RBRACnum    brackets
        |
        ;
remainingpartboe:   DOTnum      type
        |
        ;

Note that terminals are the words ending with the suffix num, e.g. DOTnum. Rest are nonterminals.

Bison is reporting the following conflict

mj-parser.y: conflicts: 1 reduce/reduce
mj-parser.y:122.18: warning: rule useless in parser due to conflicts: 
brackets_or_end: /* empty */

Note that bison error above is referring to the second alternative production of the brackets_or_end rule.

Please help in resolving this conflict by suggesting another way to write the grammar. By the way, I have looked at the verbose output of Bison, but it wasn't of much help.

Thanks -sas

Notice that you have two nonterminals that can be empty in the same production tree. So an empty string can reduce to either brackets or brackets_or_end. This won't work. — Bob Dalgleish
You're absolutely right Bob. Thanks for the hint: brackets should not have an epsilon-reduction. This will remove the reduce-reduce conflict. — user3416142

Brian Tompsett - 汤莱恩 Brian Tompsett - 汤莱恩 · Accepted Answer · 2015-02-07T17:46:34

(Question answered in the comments. Converted to a community wiki answer. See Question with no answers, but issue solved in the comments (or extended in chat) )

@BobDalgleish wrote:

Notice that you have two nonterminals that can be empty in the same production tree. So an empty string can reduce to either brackets or brackets_or_end. This won't work.

The OP wrote:

You're absolutely right Bob. Thanks for the hint: brackets should not have an epsilon-reduction. This will remove the reduce-reduce conflict.

Bison/Yacc reduce reduce conflict for a specific grammar example

1 Answers