Re: Shift/reduce conflict in Yacc C grammar

Apologies for error #2 of last monday.


Dmitri&Nina Bronnikov <Bronikov@inreach.com>'s posting is correct.
The problem is not in the language. It is in the grammar. Any
grammar which does not distinguish statements with if-then's allowed
from statements where all if-then's must have else's will have the
problem. To correct the grammar, you simply re-introduce the
distinction (or apply precedence declarations), which I will not
attempt given my tendency to make mistakes.


A similar problem exists in the following example (excuse me if I have
the recursion or precedence reversed, I don't normally write grammars
this way). The idea of this grammar is that only variables can be
tested to see if they are initialized, but any kind of expression can
be zero. This produces a shift/reduce conflict. (I'm not sure what
the equivalent problem is in LL, although I know this grammar is not
LL(1), since upon seing a VAR you don't know whether to descend into a
expr or not.)


test: init_test | zero_test;
init_test: VAR not INIT;
zero_test: expr not ZERO;
expr: term PLUS expr | term;
term: factor TIMES term | factor;
factor: VAR | CONST;
not: NOT | ;


To correct the problem (getting rid of the shift/reduce conflict and
making the grammar LL(1) at the same time), you need to split the
productions. The corrected version looks like:


test: init_test | zero_test;
init_test: VAR not INIT;
zero_test: VAR not ZERO | non_var_expr not ZERO;
non_var_expr: term PLUS expr | non_var_term;
expr: term PLUS expr | term;
non_var_term: factor TIMES term | non_var_factor;
term: factor TIMES term | factor;
non_var_factor: CONST;
factor: VAR | CONST;
not: NOT | ;


Notice how the problem propagates through a whole series of rules,
creating numerous non_var_ copies of each rule. Also note that the
change to the zero_test rule is required for the grammar to parse
correctly, while the splitting of the expr rules into nov_var_ copies
is simply to remove the shift/reduce conflict. (By the way, if you
split grammars like this be careful, I made three mistakes while
slitting this simple grammar--of course, I do seem error prone this
week.)


This is one case when precedence tricks can help. Correct the
zero_test rule (so that the conflict is between alternatives of the
zero_test rule and not between the zero_test rule and the init_test
rule), but use precedence to fix shift/reduce conflicts within the
zero_test rule. A rule-of-thumb for distinguishing the cases, is that
if the shift reduce conflict involves two alternatives of the same
rule (as in the next grammar where the two alternatives of zero_test
cause the shift/reduce conflict) , it is probably okay to solve by
selecting the shift. However, if the shift/reduce conflict selects
between different rules (as in between init_test and zero_test) then
the grammar should be rewritten to resolve the conflict.


Similarly to being careful when splitting rules, use caution when
applying precedence declarations. One technique is to get the grammar
working without precedence declarations leaving only shift/reduce
conflicts where the correct solution is always to shift and then to
add the appropriate precedence declarations checking that exactly the
same tables are generated.


right NOT; // prefer shift over reduce


test: init_test | zero_test;
init_test: VAR not INIT;
zero_test: VAR not ZERO | expr not ZERO;
expr: term PLUS expr | term;
term: factor TIMES term | factor;
factor: VAR %prec NOT // hack to avoid conflict message
            | CONST;
not: NOT | ;


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
--

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