| 1 |
A em(reduce/reduce conflict) occurs if there are two or more rules that apply |
| 2 |
to the same sequence of input. This usually indicates a serious error in the |
| 3 |
grammar. |
| 4 |
|
| 5 |
For example, here is an erroneous attempt to define a sequence of zero or more |
| 6 |
words: |
| 7 |
verbinsert(-as4 demos/rr1) |
| 8 |
The error is an ambiguity: there is more than one way to parse a single |
| 9 |
word into a sequence. It could be reduced to a maybeword and then into a |
| 10 |
sequence via the second rule. Alternatively, nothing-at-all could be reduced |
| 11 |
into a sequence via the first rule, and this could be combined with the word |
| 12 |
using the third rule for sequence. |
| 13 |
|
| 14 |
There is also more than one way to reduce nothing-at-all into a sequence. This |
| 15 |
can be done directly via the first rule, or indirectly via maybeword and then |
| 16 |
the second rule. |
| 17 |
|
| 18 |
You might think that this is a distinction without a difference, because it |
| 19 |
does not change whether any particular input is valid or not. But it does |
| 20 |
affect which actions are run. One parsing order runs the second rule's action; |
| 21 |
the other runs the first rule's action and the third rule's action. In this |
| 22 |
example, the output of the program changes. |
| 23 |
|
| 24 |
B() resolves a reduce/reduce conflict by choosing to use the rule that appears |
| 25 |
first in the grammar, but it is very risky to rely on this. Every |
| 26 |
reduce/reduce conflict must be studied and usually eliminated. Here is the |
| 27 |
proper way to define sequence: |
| 28 |
verb( |
| 29 |
sequence: |
| 30 |
// empty |
| 31 |
{ printf ("empty sequence\n"); } |
| 32 |
| sequence word |
| 33 |
{ printf ("added word %s\n", $2); } |
| 34 |
; |
| 35 |
) |
| 36 |
|
| 37 |
Here is another common error that yields a reduce/reduce conflict: |
| 38 |
verb( |
| 39 |
sequence: |
| 40 |
// empty |
| 41 |
| sequence words |
| 42 |
| sequence redirects |
| 43 |
; |
| 44 |
|
| 45 |
words: |
| 46 |
// empty |
| 47 |
| words word |
| 48 |
; |
| 49 |
|
| 50 |
redirects: |
| 51 |
// empty |
| 52 |
| redirects redirect |
| 53 |
; |
| 54 |
) |
| 55 |
|
| 56 |
The intention here is to define a sequence containing either tt(word) or |
| 57 |
tt(redirect) nonterminals. The individual definitions of sequence, words and |
| 58 |
redirects are error-free, but the three together make a subtle ambiguity: even |
| 59 |
an empty input can be parsed in infinitely many ways! |
| 60 |
|
| 61 |
Consider: nothing-at-all could be a words. Or it could be two words in a row, |
| 62 |
or three, or any number. It could equally well be a redirects, or two, or any |
| 63 |
number. Or it could be a words followed by three redirects and another |
| 64 |
words. And so on. |
| 65 |
|
| 66 |
Here are two ways to correct these rules. First, to make it a single level of |
| 67 |
sequence: |
| 68 |
verb( |
| 69 |
sequence: |
| 70 |
// empty |
| 71 |
| sequence word |
| 72 |
| sequence redirect |
| 73 |
; |
| 74 |
) |
| 75 |
|
| 76 |
Second, to prevent either a words or a redirects from being empty: |
| 77 |
verb( |
| 78 |
sequence: |
| 79 |
// empty |
| 80 |
| sequence words |
| 81 |
| sequence redirects |
| 82 |
; |
| 83 |
|
| 84 |
words: |
| 85 |
word |
| 86 |
| words word |
| 87 |
; |
| 88 |
|
| 89 |
redirects: |
| 90 |
redirect |
| 91 |
| redirects redirect |
| 92 |
; |
| 93 |
) |