Bottom-Up Parsing - Crafting a Compiler - page 215

Item Prop To Initial Pass 1

1 13 $

2 5,8 $

3 11 $

4 6 $

5 12 b $

6 18 $

7 19 c

8 9,10,17 $

9 16 $

10 $

11 15 $

12 b $

13 14 $

14 $

15 $

16 $

17 $

18 20 $

19 c

20 $

Figure 6.30: Iterations for LALR(1) follow sets.

ItemFollow set at Item 2 is forwarded to Item 5 by a propagation edge placed
by Marker 29 . Finally, the lookahead present at Item 2 must make its way
to Item 17 where it can be consulted when the reduction S ABis applied.

Thus, propagation edges are placed by Marker 27 between Items 2 and 8 and
between Items 8 and 17.
Constructing the propagation graph is only half of the process we need to
compute lookahead sets. Once LALR(1) construction has established the prop-
agation graph and has initialized the ItemFollow sets, as shown in Figure 6.29,
the propagation graph can be evaluated. E

→

in Figure 6.28
evaluates the graph by iteratively propagating lookahead information along
the graph's edges until no new information appears.
In Figure 6.30 we trace the progress of this algorithm on our example. The
“Initial” column shows the lookahead sets established byMarker 28 . The loop
at Marker 30 unions lookahead sets as determined by the propagation graph's
edges. For the example we have considered thus far, the loop at Marker 30
converges after a single pass. As written, the algorithm requires a second pass
to detect that no lookahead sets change after the first pass. We do not show

val I tem P rop G raph