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

Algorithm 3.10 Computing the LR(1) Collection
Input: a context-free grammar G = (N;T;S;P)
Output: the canonical LR(1) collection of states c = fs 0 ;s 1 ;:::;s n g
Dene an augmented grammar G 0 , which is G with the added non-terminal S 0 and added
production rule S 0 ::= S, where S is G's start symbol. The following steps apply to G 0 .
Enumerate the production rules beginning at 0 for the newly added production.
c fs 0 g where s 0 = closure(f[S 0 ::= S, # ]g)
repeat
for each s in c, and for each symbol X 2 T [N do
if goto(s;X) 6= ; and goto(s;X) 2 c then
add goto(s;X) to c.
end if
end for
until no new states are added to c
Example. We can now resume computing the LR(1) canonical collection for the simple
expression grammar, beginning from state s 1 :
goto(s 1 , + ) = s 6
= f[E ::= E + T, +/# ],
[T ::= T * F, +/*/# ],
[T ::= F, +/*/# ],
[F ::= ( E ) , +/*/#] ,
[F ::= id , +/*/# ]g
There are no more moves from s 1 . Similarly, from s 2 ,
goto(s 2 , * ) = s 7
= f[T ::= T * F, +/*/# ],
[F ::= ( E ) , +/*/# ],
[F ::= id , +/*/# ]g
Notice that the closure of f[T ::= T * F, +/*/# ]g carries along the same lookaheads
because no symbol follows the F in the right-hand side. There are no gotos from s 3 , but
several from s 4 .
goto(s 4 , E) = s 8
= f[F ::= ( E ) , +/*/# ],
[E ::= E + T, +/ )]g
goto(s 4 , T) = s 9
= f[E ::= T , +/ )],
[T ::= T * F, +/*/ )]g
goto(s 4 , F) = s 10
= f[T ::= F , +/*/ )]g