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