Debian Codegraph @

documentation/manual/algorithm/lookaheads.yo

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