[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 Heckenbach, address@hidden
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)

Attachment: ambiguity.y
Description: Binary data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]