Re: Can shift/reduce problems be eliminated?

> [ ...
  > Reduce/reduce conflicts mean your grammar is
> ambiguous and two rules match the same input.
  > ...
> -John]


To be a bit nitpicky, a reduce/reduce conflict doesn't necessarily
indicate an ambiguity. The only thing you can be sure about (without
looking at the grammar) is that it is not LALR(1) (for yacc/bison).


For example, the bison grammar:


S: A 'a' 'b' | B 'a' 'c' ;
A: 'z' ;
B: 'z' ;


is definitely not ambiguous, but it needs two symbols of lookahead
to determine whether A -> z or B -> z should be reduced after seeing
a 'z'. Bison reports a reduce/reduce error.


The state with the problem looks like:


state 1


          A -> 'z' . (rule 3)
          B -> 'z' . (rule 4)


          'a' reduce using rule 3 (A)
          'a' [reduce using rule 4 (B)]
          $default reduce using rule 3 (A)


It should be clear that, if bison were LR(2), then this state would
have no conflict and look like:


state 1


          A -> 'z' . (rule 3)
          B -> 'z' . (rule 4)


          'a' 'b' reduce using rule 3 (A)
          'a' 'c' reduce using rule 4 (B)
          $default reduce using rule 3 (A)


The solution in this simple case is, of course, is to rewrite the
grammar. But sometimes it can be quite difficult to rewrite correctly.


<grumble>
I'm currently finishing off a parser for a rather large language with
many such tricky cases. The current version of my grammar "contains 147
shift/reduce conflicts and 232 reduce/reduce conflicts.", according
to bison, in a generated parser of over 2000 states. Beware of languages
designed by comittee!
</grumble>


Cheers,
Carl

Return to the comp.compilers page.
Search the comp.compilers archives again.