Bottom-Up Parsing - Crafting a Compiler - page 211

procedure T ry R ule I n S tate ( s , r )

if LHS( r ) → RHS( r ) •∈ s

then
foreach

X∈Σ do

if X∈ ItemFollow (( s , LHS( r ) → RHS( r ) • ))

then call A ssert E ntry ( s ,X, reduce r )

end

Figure 6.27: LALR(1) version of T ry R ule I n S tate .

ciency, LALR(1) is the most popular
LR table-building method. To obtain LALR(1), we redefine the following two
methods from Figure 6.14:

Due to its balance of power and e

T ry R ule In the LALR(1) version shown in Figure 6.27, a reduce action

is asserted only for those symbols that can occur after the reduction, ac-
cording to ItemFollow . Exercise 26 investigates the relationship between
an ItemFollow set and Follow as computed for SLR.

I n S tate

C ompute Figure 6.28 contains code to build and evaluate a looka-

head propagation graph .The ItemFollow (( state , item )) sets keep track of the
symbols that can follow the item when its reduction occurs (i.e., when
the bookmark is fully to the right). The details of the propagation graph
are discussed in Section 6.5.3.

L ookahead

6.5.3 LALR Propagation Graph

We have not formally named each LR(0) item, but an item occurs at most
once in any state. Thus, the pair ( s , A →α•β )su ces to identify an item

A that occurs in state s . For each valid state and item pair, Marker 24

in Figure 6.28 creates a vertex v in the LALR propagation graph .Eachitemin
an LR(0) construction is represented by a vertex in this graph. The ItemFollow
sets are initially empty, except for the augmenting item Start

→α•β

S$in the
LR(0) start-state. Edges are placed in the graph between items i and j when
the symbols that follow the reducible form of item i should be included in
the corresponding set of symbols for item j . For the purposes of lookahead
analysis, the input string can be considered to end with an arbitrary number
of $ (end-of-input) symbols. Marker 25 forces the entire program, derived
from any rule for Start, to be followed by $.
Marker 26 of the algorithm in Figure 6.28 considers items of the form

→•

A in state s . This generic item indicates that the bookmark is just

before the symbol B, with grammar symbols in

→α• B γ

α appearing before the book-

mark, and grammar symbols in γ appearing after B.Notethat α or γ could