| 1 |
In the previous section a grammar was discussed whose fifth state contained |
| 2 |
two items: one resulting in a shift-action, the other resulting in a |
| 3 |
reduce-action. This state contained these two items: |
| 4 |
itemization( |
| 5 |
it() item 0: tt(expr -> expr '+' expr .) |
| 6 |
it() item 1: tt(expr -> expr . '+' expr) |
| 7 |
) |
| 8 |
Although this state in theory defines two different actions, in practice |
| 9 |
only one is used. This is a direct consequence of the tt(%left '+') |
| 10 |
specification, which is explained in this and the next section. |
| 11 |
|
| 12 |
When analyzing a grammar all states that can be reached from the augmented |
| 13 |
start rule are determined. In the current grammar's fifth state b() must |
| 14 |
decide which action to take: should it shift on tt('+') or should it reduce |
| 15 |
according to the item `tt(expr -> expr '+' expr .)'? What choice will b() |
| 16 |
make? |
| 17 |
|
| 18 |
Here the fact that b() implements a parser for a em(Look Ahead Left to Right |
| 19 |
(1)) (LALR(1)) grammar becomes relevant. B() computes em(look-ahead sets) to |
| 20 |
determine which alternative to select when confronted with a choice. The |
| 21 |
look-ahead set can be used to favor one action over another when generating |
| 22 |
tables for the parsing function. |
| 23 |
|
| 24 |
Sometimes the look-ahead sets allow b() simply to remove one action from the |
| 25 |
set of possible actions. When b() is called to process the example grammar |
| 26 |
while specifying the tt(--construction) option state five em(only) shows the |
| 27 |
reduction and em(not) the shifting action, as b() has removed that latter |
| 28 |
action from the action set. In state five the choice is between shifting a |
| 29 |
tt('+') token on the stack, or reducing the stack according to the rule |
| 30 |
verb( |
| 31 |
expr -> expr '+' expr |
| 32 |
) |
| 33 |
Here, as we will shortly see, the tt('+') is em(also) an element of the |
| 34 |
em(look-ahead set) of the reducible item, creating a conflict: what to do |
| 35 |
on tt('+')? |
| 36 |
|
| 37 |
In this case the grammar designer has provided b() with a way out: the |
| 38 |
tt(%left) directive tells b() to favor a reduction over a shift, and so it |
| 39 |
removed tt(expr -> expr . '+' expr) from its set of actions in state five. |