Parsing - Introduction to Compiler Construction in a Java World - page 100

0. E 0 ::= E
1. E ::= E + T
2. E ::= T
3. T ::= T * F
4. T ::= F
5. F ::= ( E )
6. F ::= id

We then start constructing item sets from this augmented grammar. The first set, rep-
resenting the initial state in our DFA, will contain the LR(1) item:

f[E 0 ::= E, # ]g

(3.34)

which says that parsing an E 0 means parsing an E from the input, after which point the
next (and last) remaining unscanned token should be the terminator # . But at this point,
we have not yet parsed the E; the in front of it indicates that it is still ahead of us.
Now that we must parse an E at this point means that we might be parsing either an
E + T (by rule 1 of 3.33) or a T (by rule 2). So the initial set would also contain

[E ::= E + T, # ]
[E ::= T, # ]

(3.35)

In fact, the initial set will contain additional items implied by (3.34). We call the initial
set (3.34) the kernel. From the kernel, we can then compute the closure, that is, all items
implied by the kernel. Algorithm 3.8 computes the closure for any set of items.

Algorithm 3.8 Computing the Closure of a Set of Items
Input: a set of items, s
Output: closure(s)
add s to closure(s)
repeat
if closure(s) contains an item of the form

[Y ::= X , a ]

add the item

[X ::= , b ]

for every rule X ::= in P and for every token b in rst( a ).
until no new items may be added

Example. To compute the closure of our kernel (3.34), that is, closure(f[E 0 ::= E, # ]g),
by step 1 is initially

f[E 0 ::= E, # ]g

(3.36)

We then invoke step 2. Because the comes before the E, and because we have the rule
E ::= E + T and E ::= T, we add [E ::= E + T, # ] and [E ::= T, # ] to get

f[E 0 ::= E, # ],
[E ::= E + T, # ],
[E ::= T, # ]g

(3.37)