Re: reduce/reduce conflict

On 01 Feb 2004, you wrote in comp.compilers:
> I'm currently writing a grammar for a C/Pascal-like language using
> btyacc (bactracking yacc). The grammar is free from conflicts except
> for 1 shift/reduce conflict. When I tried using inherited attributes I
> got 1 reduce/reduce conflict. Is there any way I can get rid of it
> without having to rewrite the grammar ?
> [No. -John]


The moderator is right -- you'll need to modify the grammar in some
way, but it may just require a trivial tweak.


Inherited attributes tend to introduce conflicts only when you have
have conflicting uses of a non-terminal with different attribute
values. If the inherited attribute was the same (or not present)
there'd be no conflict. It may be the case that the conflicteing
attribute values are the same, but btyacc isn't recognizing them as
such (due to minor differences in punctuation). If you look at the
y.output file produced by the -v option, you can see which state the
conflict is in, and from the items of that state, can determine which
values are in conflict (the conflict will likely be between two $$X
rules, which come from the inherited attributes.)


Note, however, that one of the points of btyacc is that a grammar can
work just fine even with conflicts in btyacc -- the generated parser
will parse both ways through the conflict and will prune off parses
that generate YYERROR, until it finds one that does a YYVALID. Its
just a bit slower. There is a potential for an exponential explosion
of possible parses (which will likely make the generated parser seem
to hang as it tries to go through all of them), but that can be
avoided by ensuring that YYVALID is called frquently enough.


-chris

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