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

, "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

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