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

Algorithm 3.12 Constructing the LALR(1) Parsing Tables for a Context-Free Grammar
Input: a context-free grammar G = (N;T;S;P)
Output: the LALR(1) tables Action and Goto

1. Compute the LR(1) canonical collection c = fs 0 ;s 1 ;:::;s n g

2. Merge those states whose item cores are identical. The items in the merged state
are a union of the items from the states being merged. This produces an LALR(1)
canonical collection of states

3. The goto function for each new merged state is the union of the goto for the indi-
vidual merged states

4. The entries in the Action and Goto tables are constructed from the LALR(1) states
in the same way as for the LR(1) parser in Algorithm 3.11

If all entries in the Action table are unique, then the grammar G is said to be LALR(1).

Example. Reconsider our grammar for simple expressions from (3.31), and (again) re-
peated here as (3.42).

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

(3.42)

Step 1 of Algorithm 3.12 has us compute the LR(1) canonical collection that was shown
in a table above, and is repeated here.

s 0 = f[E 0 ::= E, # ],
[E::= E + T, +/# ],
[E::= T, +/# ],
[T ::= T * F, +/*/# ],
[T ::= F, +/*/# ],
[F ::= ( E ) , +/*/# ],
[F ::= id , +/*/# ]g

goto(s 0 ,E) =s 1
goto(s 0 ,T) =s 2
goto(s 0 ,F) =s 3
goto(s 0 , ( ) =s 4
goto(s 0 , id ) =s 5

s 11 = f[F ::= ( E ) , +/*/ )],
[E::= E + T, +/ )],
[E::= T, +/ )],
[T ::= T * F, +/*/ )],
[T ::= F, +/*/ )],
[F ::= ( E ) , +/*/ )],
[F ::= id , +/*/ )]g

goto(s 11 ,E) =s 18
goto(s 11 ,T) =s 9
goto(s 11 ,F) =s 10
goto(s 11 , ( ) =s 11
goto(s 11 , id ) =s 12

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

goto(s 1 , + ) =s 6 s 12 = f[F ::= id , +/*/ )]g

goto(s 2 , * ) =s 7 s 13 = f[E::=E + T, +/# ],
[T ::=T * F, +/*/# ]g

goto(s 13 , * ) =s 7

s 2 = f[E::=T, +/# ],
[T ::=T * F, +/*/# ]g

s 3 = f[T ::=F, +/*/# ]g s 14 = f[T ::=T * F, +/*/# ]g