Re: Ambiguity involving two parse stacks reducing on the same rule

[Frank Heckenbach]

Derek M Jones wrote:

> I had misunderstood how %merge worked and was trying to
> solve a problem by using %dprec and grammar rewrites.
> Frank Heckenbach came up with the following grammar which
> highlights the issue very well (I had assumed that %merge would
> only be applicable when two different grammar rules were involved).
> 
> You might like to consider the following text (or something like it)
> for inclusion in the Bison manual (credit to Frank for such a
> minimalist grammar).
> 
> ---------------------
> It is possible for a grammar to contain an ambiguity that
> is only recognised as such when two glr parse stacks attempt
> to reduce through the same rule.  For instance, given the
> grammar:
> 
> %%
> v: e
>  | e e
> 
> e: 'a'
>  | 'a' 'a'
> 
> the input "aaa" could be parsed as either
> 
>    e -> 'a' 'a'
>    e -> 'a'
>    v -> e e
> 
> or as
>    
>    e -> 'a'
>    e -> 'a' 'a'
>    v -> e e
> 
> Adding a %merge to the second production involving
> v removes the parse stack resolution ambiguity (or at least
> passes it off to a user supplied function).  This ambiguity
> cannot be resolved using %dprec because at the point
> it occurs only one rule is under consideration by both
> parse stacks.

Actually there are two issues. The example above is a case that
`%dprec' can't handle. As I can't easily use `%merge' in my grammar
because of the semantic actions, my question was if there was a way
to get `%dprec' to work in such a case without having to rearrange
the grammar. This question still stands, and perhaps someone here
has an idea ...?

The other example I provided (attached) demonstrates a case how
`%merge' can be used, possibly even if the final reduction in on the
same rule (where `%dprec' doesn't work, as above). This particular
conflict is about parentheses vs. type cast and unary `+' in C. Feel
free to inlcude it in the manual if you regard it useful. (I have
made a copyright assignment for bison already.)

Frank

-- 
Frank Heckenbach, address@hidden
http://fjf.gnu.de/
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)

ambiguity.y
Description: Binary data