| 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. |