Ambiguity involving two parse stacks reducing on the same rule

[Derek M Jones]

All,

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.
                        

derek

--
Derek M Jones                                     tel: +44 (0) 1252 520 667
Knowledge Software Ltd                         mailto:address@hidden
Applications Standards Conformance Testing   http://www.knosof.co.uk