Debian Codegraph @

documentation/manual/algorithm/reduce.yo

raw
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 )