Re: Mysterious Reduce/Reduce Conflicts

[Hans Aberg]

At 14:03 -0700 2002/08/08, Reza Roboubi wrote:
>I have trouble understanding this part of the bison manual on
>"Mysterious Reduce/Reduce Conflicts:"
>return_spec:
>             type
>        |    name ':' type
>        /* This rule is never used.  */
>        |    ID BOGUS
>        ;
>
>the manual explains:
>
>" This corrects the problem because it introduces the possibility of an
>additional active rule in the context after the ID at the beginning of
>return_spec. This rule is not active in the corresponding context in a
>param_spec, so the two contexts receive distinct parser states. "
>
>My confusion is this:
>
>If bison only needs some non-active visual queue to know that it must
>generate different parser states for the two contexts, why does bison
>not simply take into account the fact that the two rules have different
>names?  Why is this not enough to distinguish their associated contexts?

Bison is only applying LALR(1) straight off, so I think you have to work
through that algorithm in order to understand your question. (See for
example the Aho, Sethi & Ullman book.)

LALR(1) is merging LR(1) states, but cannot handle all LR(1) grammars. The
grammar chosen is LR(1) but not LALR(1), but in this case a way is found to
tell that states should not be merged.

It is a good question how general this technique is, but perhaps the
example given is just a lucky case. It is also a good question why one,
when designing LALR(1), did not do it so that if the states cannot be
merged, they are replaced by a chunk of LR(1) states. I do not know that,
but perhaps when working through those two algorithms, one can see it.

-- Perhaps somebody else has a better answer.

  Hans Aberg