Debian Codegraph @

documentation/manual/algorithm/conflicts.yo

raw
1 Suppose we are parsing a language which has tt(if) and tt(if-else)
2 statements, with a pair of rules like this:
3 verb(
4 if_stmt:
5 IF '(' expr ')' stmt
6 |
7 IF '(' expr ')' stmt ELSE stmt
8 ;
9 )
10 Here we assume that tt(IF) and tt(ELSE) are terminal symbols for specific
11 keywords, and that tt(expr) and tt(stmnt) are defined nonterminals.
12
13 When the tt(ELSE) token is read and becomes the look-ahead token, the contents
14 of the stack (assuming the input is valid) are just right for em(reduction) by
15 the first rule. But it is also legitimate to em(shift) the tt(ELSE), because
16 that would lead to eventual reduction by the second rule.
17
18 This situation, where either a shift or a reduction would be valid, is called
19 a tt(shift/reduce) conflict. B() is designed to resolve these conflicts
20 by em(implementing) a shift, unless otherwise directed by operator precedence
21 declarations. To see the reason for this, let's contrast it with the other
22 alternative.
23
24 Since the parser prefers to shift the tt(ELSE), the result is to attach the
25 em(else-clause) to the innermost if-statement, making these two inputs
26 equivalent:
27 verb(
28 if (x) if (y) then win(); else lose();
29
30 if (x)
31 {
32 if (y) then win(); else lose();
33 }
34 )
35 But if the parser would perform a em(reduction) whenever possible rather
36 than a em(shift), the result would be to attach the em(else-clause) to the
37 outermost if-statement, making these two inputs equivalent:
38 verb(
39 if (x) if (y) then win(); else lose();
40
41 if (x)
42 {
43 if (y) win();
44 }
45 else
46 lose();
47 )
48 The conflict exists because the grammar as written is em(ambiguous):
49 em(either) parsing of the simple nested if-statement is legitimate. The
50 established convention is that these ambiguities are resolved by attaching the
51 else-clause to the innermost if-statement; this is what b() accomplishes
52 by implementing a shift rather than a reduce. This
53 particular ambiguity was first encountered in the specifications of Algol 60
54 and is called the em(dangling else) ambiguity.
55
56 To avoid warnings from b() about predictable, legitimate shift/reduce
57 conflicts, use the tt(%expect n) directive. There will be no warning as long
58 as the number of shift/reduce conflicts is exactly tt(n). See section
59 ref(EXPECT).
60
61 The definition of tt(if_stmt) above is solely to blame for the conflict, but
62 the plain tt(stmnt) rule, consisting of two recursive alternatives will of
63 course never be able to match actual input, since there's no way for the
64 grammar to eventually derive a sentence this way. Adding one non-recursive
65 alternative is enough to convert the grammar into one that em(does) derive
66 sentences. Here is a complete b() input file that actually shows the
67 conflict:
68 verbinclude(demos/dangling)
69
70 Looking again at the dangling else problem note that there are multiple ways
71 to handle tt(stmnt) productions. Depending on the particular input that is
72 provided it could
73 either be reduced to a tt(stmt) or the parser could continue to consume input
74 by processing an tt(ELSE) token, eventually resulting in the recognition of
75 tt(IF '(' VAR ')' stmt ELSE stmt) as a tt(stmt).
76
77 There is little we can do but resorting to tt(%expect) to handle the dangling
78 else problem. The default handling is what most people intuitively expect and
79 so in this case using tt(%expect 1) is an easy way to prevent b() from
80 reporting a shift/reduce conflict. But shift/reduce conflicts are most often
81 solved by specifying disambiguating rules specifying priorities or
82 associations, usually in the context of arithmetic expressions, as discussed
83 in the next sections.
84
85 However, shift-reduce conflicts can also be observed in grammars where a state
86 contains items that could be reduced to a certain nonterminal and items in
87 which a shift is possible in an item of a production rule of a completely
88 different nonterminal. Here is an example of such a grammar:
89 verbinclude(demos/peculiar)
90 Why these grammars show shift reduce conflicts and how these are solved is
91 discussed in the next section.