Bottom-Up Parsing - Crafting a Compiler - page 213

procedure C ompute L ookahead ()

call B uild I tem P rop G raph ()

call E val I tem P rop G raph ()

end
procedure B

uild I tem P rop G raph ()

foreach s ∈ States do
foreach item ∈ state do

v ← Graph . AddVertex(( s , item ))
ItemFollow ( v )

24

←∅

foreach p ∈ P roductions F or (Start ) do

ItemFollow (( StartState , Start →• RHS( p ))) ←{ $ }

25

foreach s ∈ States do

foreach A γ∈ s do

v ← Graph . FindVertex(( s ,A→α•Bγ))

→α• B

26

call Graph . AddEdge( v ,( Table [ s ][ B ],A→αB•γ))
foreach ( w ←

27

( s , B →•δ )) ∈ Graph . Vertices do

ItemFollow ( w ) ← ItemFollow ( w ) ∪ First( γ )

28

if A )

then call Graph . AddEdge( v , w )

ll D erive E mpty ( γ

29

end
procedure E val I tem P rop G raph ()

repeat
changed ←

30

false
foreach ( v , w )

∈ Graph . Edges do
old ← ItemFollow ( w )
ItemFollow ( w ) ← ItemFollow ( w ) ∪ ItemFollow ( v )

if ItemFollow ( w ) old

then changed ← true

until not changed
end

Figure 6.28: LALR(1) version of C ompute L ookahead .