Reduce\/Reduce
Previous: <Parser States=>ParserStat> * Next: <Mystery Conflicts=>MysteryCon> * Up: <Algorithm=>Algorithm>

#Wrap on
{fH3}Reduce\/Reduce Conflicts{f}

A reduce\/reduce conflict occurs if there are two or more rules that apply
to the same sequence of input.  This usually indicates a serious error
in the grammar.

For example, here is an erroneous attempt to define a sequence
of zero or more {fCode}word{f} groupings.

#Wrap off
#fCode
sequence: \/\* empty \*\/
                \{ printf ("empty sequence\\n"); \}
        | maybeword
        | sequence word
                \{ printf ("added word %s\\n", $2); \}
        ;

maybeword: \/\* empty \*\/
                \{ printf ("empty maybeword\\n"); \}
        | word
                \{ printf ("single word %s\\n", $1); \}
        ;
#f
#Wrap on

The error is an ambiguity: there is more than one way to parse a single
{fCode}word{f} into a {fCode}sequence{f}.  It could be reduced to a
{fCode}maybeword{f} and then into a {fCode}sequence{f} via the second rule.
Alternatively, nothing-at-all could be reduced into a {fCode}sequence{f}
via the first rule, and this could be combined with the {fCode}word{f}
using the third rule for {fCode}sequence{f}.

There is also more than one way to reduce nothing-at-all into a
{fCode}sequence{f}.  This can be done directly via the first rule,
or indirectly via {fCode}maybeword{f} and then the second rule.

You might think that this is a distinction without a difference, because it
does not change whether any particular input is valid or not.  But it does
affect which actions are run.  One parsing order runs the second rule's
action; the other runs the first rule's action and the third rule's action.
In this example, the output of the program changes.

Bison resolves a reduce\/reduce conflict by choosing to use the rule that
appears first in the grammar, but it is very risky to rely on this.  Every
reduce\/reduce conflict must be studied and usually eliminated.  Here is the
proper way to define {fCode}sequence{f}:

#Wrap off
#fCode
sequence: \/\* empty \*\/
                \{ printf ("empty sequence\\n"); \}
        | sequence word
                \{ printf ("added word %s\\n", $2); \}
        ;
#f
#Wrap on

Here is another common error that yields a reduce\/reduce conflict:

#Wrap off
#fCode
sequence: \/\* empty \*\/
        | sequence words
        | sequence redirects
        ;

words:    \/\* empty \*\/
        | words word
        ;

redirects:\/\* empty \*\/
        | redirects redirect
        ;
#f
#Wrap on

The intention here is to define a sequence which can contain either
{fCode}word{f} or {fCode}redirect{f} groupings.  The individual definitions of
{fCode}sequence{f}, {fCode}words{f} and {fCode}redirects{f} are error-free, but the
three together make a subtle ambiguity: even an empty input can be parsed
in infinitely many ways!

Consider: nothing-at-all could be a {fCode}words{f}.  Or it could be two
{fCode}words{f} in a row, or three, or any number.  It could equally well be a
{fCode}redirects{f}, or two, or any number.  Or it could be a {fCode}words{f}
followed by three {fCode}redirects{f} and another {fCode}words{f}.  And so on.

Here are two ways to correct these rules.  First, to make it a single level
of sequence:

#Wrap off
#fCode
sequence: \/\* empty \*\/
        | sequence word
        | sequence redirect
        ;
#f
#Wrap on

Second, to prevent either a {fCode}words{f} or a {fCode}redirects{f}
from being empty:

#Wrap off
#fCode
sequence: \/\* empty \*\/
        | sequence words
        | sequence redirects
        ;

words:    word
        | words word
        ;

redirects:redirect
        | redirects redirect
        ;
#f
#Wrap on

