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

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

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