[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Ambiguity involving two parse stacks reducing on the same rule
From: |
Frank Heckenbach |
Subject: |
Re: Ambiguity involving two parse stacks reducing on the same rule |
Date: |
Thu, 10 Mar 2005 13:30:36 +0100 |
User-agent: |
semail 20050101 |
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