Bison grammar (1 reduce/reduce 1 shift/reduce )

Question

Updated ... i know, my grammar is ambiguous but how can I rewrite this grammar to eliminate this ambiguity? ..................

I have a grammar just like this:

Bison file

%left equal nEqual
%left gre less greOrEqual lessOrEqual
%left plus sub
%left DIV mult exp mod
%left not
%left leftB rightB
%%


S :
var "=" A ";"  
;


A:
 Aexp   
|Rexp   
;

Aexp :
Num                                     
| leftB Aexp  rightB               
| Aexp  plus    Aexp            
| Aexp  sub     Aexp            
| Aexp  DIV     Aexp            
| Aexp  mult    Aexp            
;


Rexp :
Aexp                            
| Rexp  gre Rexp                
| Rexp  less Rexp               
| Rexp  greOrEqual  Rexp                
| Rexp  lessOrEqual Rexp            
| Rexp  equal Rexp              
| Rexp  nEqual Rexp             
;

I get 1 shift/reduce and 1 reduce/reduce conflicts doing this, how can I change the grammar to eliminate Conflicts ?

I removed the Flex tag; as this has nothing to do w/ the Adobe/Apache UI Framework. I added the lex and gnu-flex tags because this is related to the lexical analyzer. — JeffryHouser
It would make it easier for us if you showed the actual input to Bison, and not something that is almost, but not quite, what you have in your input file. The grammar above gives errors for missing tokens, and if you add those tokens, you get seven shift/reduce conflicts, not one. — Thomas Padron-McCarthy
I removed the lex and gnu-flex tags again, because this is about parsing and grammars, not lexical analysis. — Thomas Padron-McCarthy

Thomas Padron-McCarthy Thomas Padron-McCarthy · Accepted Answer · 2012-12-28T18:16:30

Your grammar is ambiguous. An A can be an Aexp or an Rexp. But an Rexp can also be an Aexp. This leads to a reduce/reduce conflict.

Let's say you give your parser this token sequence as input:

var = Num ;

The start symbol S expands to var = A ;

The non-terminal A has to match the token Num. But should that be an A that expands to and Aexp which then expands to Num, or should it be an A that expands to and Rexp, which then expands to Aexp, which then expands to Num?

Bison grammar (1 reduce/reduce 1 shift/reduce )

1 Answers