Bottom-Up Parsing - Crafting a Compiler - page 192

LR(0) item Progress of rule in this state

E →• plus E E Beginning of rule

E → plus • EE Processed a plus,expectanE

E → plus E • E Expect another E

E → plus E E • Handle on top-of-stack, ready to reduce

Figure 6.8: LR(0) items for production E → plus E E.

symbol denotes that there is nothing on this rule's RHS. We make this clear

when representing such rules as items. For A

λ

→λ , the only possible item is the

reducible A .

We now define a parser state as a set of LR(0) items. While each state is
formally a set, we drop the usual braces notation and simply list the the set's
elements (items). The LR(0) construction algorithm is shown in Figure 6.9.
The start state for our parser—nominally state 0—is formed at Marker 7
by including fresh items for each of the grammar's goal-symbol productions.
For our example grammar in Figure 6.2, we initialize the start state with
Start

→•

E$. The algorithm maintains WorkList —a set of states that need to
be processed by the loop at Marker 8 . Each state formed during processing
is passed through A

→•

, which determines at Marker 9 if the set of items
has already been identified as a state. If not, then a new state is constructed at
Marker 10 . The resulting state is added to WorkList at Marker 11 .Thestate's
row in the parse table is initialized at Marker 12 .
The processing of a state begins when the loop at Marker 8 extracts a state
s from the WorkList .WhenC

dd S tate

ompute G oto is called on state s , the following

steps are performed:

1. The closure of state s is computed at Marker 17 . If a nonterminal

B appears just after the bookmark symbol ( ), then in state s we can

process a B once one has been found. Transitions from state s must
include actions that can lead to discovery of a B.C

•

in Figure 6.10
returns a set that includes its supplied set of items along with fresh items
for B's rules. The addition of fresh items can trigger the addition of
still more fresh items. Because the computed answer is a set, no item
is added twice. The loop at Marker 14 continues until nothing new is
added. Thus, this loop eventually terminates.

losure

2. Marker 18 determines transitions from s . When a new state is added
during LR(0) construction, Marker 12 sets all actions for this state as
error. Transitions are defined for each grammar symbol X that appears

after the bookmark. C in Figure 6.10 defines a transition at

Marker 20 from s to a (potentially new) state that reflects the parser's

ompute G oto