Bottom-Up Parsing - Crafting a Compiler - page 212

be absent, in which case , respectively. The symbol B is al-

ways present unless the grammar rule is A

α = λ or γ = λ

→λ . The lookahead computation

is specifically concerned with A →α• B γ when B is a nonterminal, because

C in Figure 6.10 adds items to state s for each of B's productions. The

symbols that can follow B depend on

losure

γ , which is either absent or present in the

γ⇒ λ item. Also, even when γ is present, it is possible that . The algorithm

in Figure 6.28 takes these cases into account as follows:

• For the item A →α• B γ ,anysymbolinFirst( γ ) can follow each closure

itemB →•δ .Thisistrueevenwhen γ is absent: in such cases, First( λ ) =

∅ .Thus,Marker 28 places symbols from First( γ )inthe ItemFollow sets

for each B in state s .

ItemFollow sets are useful only when the bookmark progresses to the
point of a reduction. B

→•δ

→•δ is only the promise of a reduction to B once

δ has been found. Thus, the lookahead symbols must accompany the

bookmark's progress across in the

appropriate state. Such migration of lookahead symbols is represented
by propagation edges.

δ so they are available for B →δ•

• Edgesmust be placed in the propagation graphwhen the symbols that are

associatedwith one item should be added to the symbols associatedwith
another item. The two situations that call for the addition of propagation
edges are as follows:

- As described above, lookahead symbols introduced by Marker 28
are useful only when the bookmark has advanced to the end of the
rule. In LR(0), the CFSMcontains an edge fromstate s to state t when
the advance of the bookmark symbol for an item in state s creates an
item in state t . For lookahead propagation in LALR,theedgesare
more specific—Marker 27 places edges in the propagation graph
between items ,notstates.
Specifically, an edge is placed from an item A →α• B γ in state s to

in state t obtained by advancing the bookmark,
if t is the CFSM state reached by processing a B in state s .
- Consider again the itemA

the item A →α B •γ

→α• B γ and the closure items introduced

γ⇒ λ

when B is a nonterminal. When ,eitherbecause γ is absent

or because the string of symbols in , then any symbol

that can follow A can also follow B.Thus,Marker 29 places a
propagation edge from the item for A to the item for B.

γ can derive λ

The edges placed by these steps are used at Marker 30 to a ect the

appropriate ItemFollow sets. The loop at Marker 30 continues until no
changes are observed in any ItemFollow set. This loop must eventually
terminate because the lookahead sets are increased only by symbols
drawn from a finite alphabet (

ff

Σ ).