Re: Reduce/reduce conflicts on A -> e (empty) productions

Chuck Batson asks an insightful question about what to do (in a parser
generator) with the following grammar's reduce-reduce conflict:


1) S -> 'Q' foo 'R'
2) foo -> empty1 empty2
3) empty1 ->
4) empty2 ->


Acording to Ullman in "Deterministic Parsing of Ambiguous Grammars"
the way to resolve this is to reduce the rule that is lexically first
in the grammar (or lexically last, as long as one is consistent). This
allows writing grammars that use reduce-reduce conflict resolution to
handle special cases. That's what most yacc-alike's do.


However, this is one place that LL parser generators do a better job
than LALR ones. The LL solution is to note that empty1 and empty2 are
nullable non-terminals, and thus foo is also nullable. Once, noting
that, if one has sees a Q then an R in the input, one knows that the
null version of foo (and the two empties) is desired.


It is possible (and not all that difficult) to make this process
rigorous and there are variants of the SLR, LALR, and related
generation algorithms that take this property into account. I call
such variants SLLR, LALLR (etc.). The hierarchy being the LLR
grammars (as opposed to the LL or LR ones). It is fairly easy to
show that the variants have the property that they parse all LL
grammars (for any fixed k) as well as their LR variants. I know I
should write this up sometime, but other things are more pressing.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.