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

Author

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

Chuck Batson

2004-06-07, 3:57 am

Hello,

I am writing an LALR(1) parser-generator for my own amusement using
the "Efficient Construction of LALR Parsing Table" techniques from the
dragon book. I have a question regarding reductions by productions
with an empty RHS. To quote from the dragon book:

"Reduction by A -> e is called for on input a if and only if there is
a kernel item [B -> u.Cv, b] such that C => As for some s, and a is in
FIRST(svb)."

(Note, "e" means the empty string and "=>" means right-most derives in
zero or more steps.) Take the following grammar:

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

According to the dragon book's definition, kernel item [S -> 'Q' . foo
'R', b] results in a reduce/reduce conflict on input 'R', since a
reduction by both productions 3 and 4 are called for as foo => empty1,
foo => empty2 (again "=>" implies zero or more steps), and 'R' is in
FIRST(svb) for both cases. How should this conflict be resolved?
Intuitively we want to reduce by production 3 in this case. Generally
speaking, we could say we prefer to reduce by the A -> e for which C
derives As for some s without the use of empty productions. This little
detail wasn't mentioned, and I'm curious how others have dealt with
this.

Thank you,

Chuck

Chuck Batson

2004-06-09, 3:57 am

> 1) S -> 'Q' foo 'R'
> 2) foo -> empty1 empty2
> 3) empty1 ->
> 4) empty2 ->
>
> According to the dragon book's definition, kernel item [S -> 'Q' . foo
> 'R', b] results in a reduce/reduce conflict on input 'R', since a
> reduction by both productions 3 and 4 are called for as foo => empty1,
> foo => empty2 (again "=>" implies zero or more steps), and 'R' is in
> FIRST(svb) for both cases. How should this conflict be resolved?

I believe I have found my flaw. While it's true foo derives empty2 (in
zero or more steps), it is NOT true that foo *right-most* derives
empty2.

Thanks! :-)

Chuck

Chris F Clark

2004-06-09, 3:57 am

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)
------------------------------------------------------------------------------

Hans Aberg

2004-06-25, 7:45 pm

, "Chuck Batson" <broadcast@cbatson.com> wrote:
>I am writing an LALR(1) parser-generator for my own amusement using
>the "Efficient Construction of LALR Parsing Table" techniques from the
>dragon book. I have a question regarding reductions by productions
>with an empty RHS. To quote from the dragon book:
>
>"Reduction by A -> e is called for on input a if and only if there is
>a kernel item [B -> u.Cv, b] such that C => As for some s, and a is in
>FIRST(svb)."
>
>(Note, "e" means the empty string and "=>" means right-most derives in
>zero or more steps.) Take the following grammar:
>
>1) S -> 'Q' foo 'R'
>2) foo -> empty1 empty2
>3) empty1 ->
>4) empty2 ->
>
>According to the dragon book's definition, kernel item [S -> 'Q' . foo
>'R', b] results in a reduce/reduce conflict on input 'R', since a
>reduction by both productions 3 and 4 are called for as foo => empty1,
>foo => empty2 (again "=>" implies zero or more steps), and 'R' is in
>FIRST(svb) for both cases. How should this conflict be resolved?

Reduce/reduce and shift/reduce conflicts are merely reported, but according
to the POSIX standard for Yacc style parser-generators, one also provides a
parser where each conflict is resolved by choosing the rule first mentioned
in the input. I.e., strictly speaking the grammar failed, but on the same
time, one provides a working parser.

Shift/reduce conflicts can sometimes be resolved by the use of precedence.
One can also resolve conflicts by the use of a GLR parser. Bison
<http://gnu.org> has a GLR parser.

If you, instead of making your own LALR(1) parser, would want to write a
LR(1) module for Bison, I feel sure the computing community would be
appreciative.

Hans Aberg

Sponsored Links