Re: Shift/reduce conflict in Yacc C grammar

Chris Clark USG wrote:
> Or to specifically answer the question, there cannot be a grammar
> without a shift-reduce conflict (it is present in the language,
> i.e. you must know whether you have a lookahead of ELSE to decide
> whether to shift to the if-then-else alternative or reduce the if-then
> alternative), but as I will show below that does not prevent adding
> action code to the grammar.


Language C does not have if-then-else problem, quoted BNF definition
does. Language spec, both usually and in case of C, disambiguates
this so that 'else' is attached to nearest 'if'.


Problem is easy to resolve by splitting balanced (all 'if's have
'else's in 'then' parts) and unbalanced if statements. I've not seen
anybody using this in practice until recently - you can see one at
(mind yourself it's rather long html)


http://java.sun.com/docs/books/jls/html/19.doc.html#52994


It does not solve the action problem, but this one has little to do
with shift/reduce conflict: parser does not know yet if it's parsing
balanced or unbalanced if at this moment. If the same action is to be
performed in the middle of balanced/unbalanced productions - factor
out common part and code actions in the middle of new production.
[That splitting is a standard technique, but it's in the folklore, not
written up in a lot of places. -John]




--

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