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

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

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

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

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

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

goto(s 16 ,T) =s 19
goto(s 16 ,F) =s 10
goto(s 16 , ( ) =s 11
goto(s 16 , id ) =s 12

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

goto(s 6 ,T) =s 13
goto(s 6 ,F) =s 3
goto(s 6 , ( ) =s 4
goto(s 6 , id ) =s 5

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

goto(s 17 ,F) =s 20
goto(s 17 , ( ) =s 11
goto(s 17 , id ) =s 12

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

goto(s 7 ,F) =s 14
goto(s 7 , ( ) =s 4
goto(s 7 , id )

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

goto(s 18 , ) ) =s 21
goto(s 18 , + ) =s 16

=s 5

goto(s 19 , * ) =s 17

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

goto(s 8 , ) ) =s 15
goto(s 8 , + ) =s 16

s 19 = f[E::=E + T, +/) ],
[T ::=T * F, +/*/) ]g

goto(s 9 , * )

s 9 = f[E::=T, +/ )],
[T ::=T * F, +/*/ )]g

=s 17 s 20 = f[T ::=T * F, +/*/) ]g

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

Merging the states and re-computing the gotos gives us the LALR(1) canonical collection
illustrated in the table below.

s 0 = s 6:16 =

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:9
goto(s 0 ,F) =s 3:10
goto(s 0 , ( ) =s 4:11
goto(s 0 , id ) =s 5:12

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

goto(s 6:16 ,T) =s 13:19
goto(s 6:16 ,F) =s 3:10
goto(s 6:16 , ( ) =s 4:11
goto(s 6:16 , id ) =s 5:12

s 1 = s 7:17 =

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

goto(s 1 , + ) =s 6:16 f[T ::=T * F, +/*/)/# ],
[F ::= ( E ) , +/*/)/# ],
[F ::= id , +/*/)/# ]g

goto(s 7:17 ,F) =s 14:20

goto(s 7:17 , ( ) =s 4:11

goto(s 7:17 , id ) =s 5:12