|Reduce/reduce conflicts on A -> e (empty) productions email@example.com (Chuck Batson) (2004-06-06)|
|Re: Reduce/reduce conflicts on A -> e (empty) productions firstname.lastname@example.org (Chuck Batson) (2004-06-09)|
|Re: Reduce/reduce conflicts on A -> e (empty) productions cfc@shell01.TheWorld.com (Chris F Clark) (2004-06-09)|
|Re: Reduce/reduce conflicts on A -> e (empty) productions email@example.com (Hans Aberg) (2004-06-15)|
|From:||Hans Aberg <firstname.lastname@example.org>|
|Date:||15 Jun 2004 01:01:06 -0400|
|Posted-Date:||15 Jun 2004 01:01:06 EDT|
, "Chuck Batson" <email@example.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
>(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
Return to the
Search the comp.compilers archives again.