| 1 |
Consider the following (somewhat peculiar) grammar: |
| 2 |
verbinclude(demos/peculiar) |
| 3 |
|
| 4 |
Even though operator precedence and association rules are used the grammar |
| 5 |
still displays a shift/reduce conflict. One of the grammar's states consists |
| 6 |
of the following two items: |
| 7 |
verb( |
| 8 |
0: expr -> term . |
| 9 |
1: term -> term . '*' factor |
| 10 |
) |
| 11 |
and b() reduces to item 0, dropping item 1 rather than shifting a tt('*') and |
| 12 |
proceeding with item 0. |
| 13 |
|
| 14 |
When considering states where shift/reduce conflicts are encountered the |
| 15 |
`shiftable' items of these states shift when encountering terminal tokens that |
| 16 |
are also in the follow sets of the reducible items of these states. In the |
| 17 |
above example item 1 shifts when tt('*') is encountered, but tt('*') is also |
| 18 |
an element of the set of look-ahead tokens of item 0. B() must now decide what |
| 19 |
to do. In cases we've seen earlier b() could make the decision because the |
| 20 |
reducible item itself had a well known precedence. The precedence of a |
| 21 |
reducible item is defined as the precedence of the rule's LHS. Item |
| 22 |
0 in the above example is an item of the rule tt(expr -> term). |
| 23 |
|
| 24 |
The precedence of a production rule is defined as follows: |
| 25 |
itemization( |
| 26 |
it() If tt(%prec) is used then the precedence of the production rule is |
| 27 |
equal to the precedence of the terminal that is specified with the tt(%prec) |
| 28 |
directive; |
| 29 |
it() If tt(%prec) is not used then the production rule's precedence is |
| 30 |
equal to the precedence of the first terminal token that is used in the |
| 31 |
production rule; |
| 32 |
it() In all other cases the production rule's precedence is set to the |
| 33 |
maximum possible precedence. |
| 34 |
) |
| 35 |
|
| 36 |
Since tt(expr -> term) does not contain a terminal token and does not use |
| 37 |
tt(%prec), its precedence is the maximum possible precedence. Consequently in |
| 38 |
the above state the shift/reduce conflict is solved by em(reducing) rather |
| 39 |
than shifting. |
| 40 |
|
| 41 |
Some final remark as to why the above grammar is peculiar. It is peculiar as |
| 42 |
it combines precedence and association specifying directives with auxiliary |
| 43 |
nonterminals that may be useful conceptually (or when implementing an |
| 44 |
expression parser `by hand') but which are not required when defining grammars |
| 45 |
for b(). The following grammar does not use tt(term) and tt(factor) but |
| 46 |
recognizes the same grammar as the above `peculiar' grammar without reporting |
| 47 |
any shift/reduce conflict: |
| 48 |
verbinclude(demos/notpeculiar) |
| 49 |
|