Debian Codegraph @

documentation/manual/algorithm/mysterious.yo

raw
1 Sometimes reduce/reduce conflicts occur that are puzzling at first sight. Here
2 is an example:
3 verb(
4 %token ID
5
6 %%
7 def:
8 param_spec return_spec ','
9 ;
10
11 param_spec:
12 type
13 |
14 name_list ':' type
15 ;
16
17 return_spec:
18 type
19 |
20 name ':' type
21 ;
22
23 type:
24 ID
25 ;
26
27 name:
28 ID
29 ;
30
31 name_list:
32 name
33 |
34 name ',' name_list
35 ;
36 )
37 It would seem that this grammar can be parsed with only a single
38 look-ahead token: when a param_spec is being read, an tt(ID) is a tt(name) if
39 a comma or colon follows, or a tt(type) if another tt(ID) follows. In other
40 words, this grammar is LR(1).
41
42 However, b(), like most parser generators, cannot actually handle all LR(1)
43 grammars. In this grammar two contexts, one after an tt(ID) at the beginning
44 of a tt(param_spec) and another one at the beginning of a tt(return_spec), are
45 similar enough for b() to assume that they are identical. They appear similar
46 because the same set of rules would be active--the rule for reducing to a name
47 and that for reducing to a type. B() is unable to determine at that stage of
48 processing that the rules would require different look-ahead tokens in the two
49 contexts, so it makes a single parser state for them both. Combining the two
50 contexts causes a conflict later. In parser terminology, this occurrence means
51 that the grammar is not LALR(1).
52
53 In general, it is better to fix deficiencies than to document them. But this
54 particular deficiency is intrinsically hard to fix; parser generators that can
55 handle LR(1) grammars are hard to write and tend to produce parsers that are
56 very large. In practice, b() is more useful the way it's currently operating.
57
58 When the problem arises, you can often fix it by identifying the two parser
59 states that are being confused, and adding something to make them look
60 distinct. In the above example, adding one rule to tt(return_spec) as follows
61 makes the problem go away:
62 verb(
63 %token BOGUS
64 ...
65 %%
66 ...
67 return_spec:
68 type
69 |
70 name ':' type
71 |
72 ID BOGUS // This rule is never used.
73 ;
74 )
75 This corrects the problem because it introduces the possibility of an
76 additional active rule in the context after the tt(ID) at the beginning of
77 tt(return_spec). This rule is not active in the corresponding context in a
78 tt(param_spec), so the two contexts receive distinct parser states. As long as
79 the token tt(BOGUS) is never generated by the parser's member function
80 tt(lex()), the added rule cannot alter the way actual input is parsed.
81
82 In this particular example, there is another way to solve the problem: rewrite
83 the rule for tt(return_spec) to use tt(ID) directly instead of via name. This
84 also causes the two confusing contexts to have different sets of active rules,
85 because the one for tt(return_spec) activates the altered rule for
86 tt(return_spec) rather than the one for name.
87 verb(
88 param_spec:
89 type
90 |
91 name_list ':' type
92 ;
93
94 return_spec:
95 type
96 |
97 ID ':' type
98 ;
99 )
100
101
102