[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Mysterious Reduce/Reduce Conflicts
From: |
Hans Aberg |
Subject: |
Re: Mysterious Reduce/Reduce Conflicts |
Date: |
Fri, 9 Aug 2002 01:01:13 +0200 |
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