LALR(1) Parsing Table

In this class, We discuss LALR(1) Parsing Table.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of CLR(1) table construction. Click Here.

We use the same example from LR(1) items construction class.

The productions are given numbers.

1) S – CC

2) C – cC

3) C – d

The below diagram shows the state diagram of LR(1) items and CLR(1) parse table.

We have ten states in LR(1) items construction.

In an LALR(1) parse table, we combine similar states.

How do we combine the states?

Take a look at the LR(1) state diagram.

The states I8 and I9 have the same productions. But different lookahead symbols.

We combine the states I8 and I9 and reduce action on lookahead symbols in both the states.

Similarly, we have I4 and I7 states.

We combine the states I4 and I7.

Similarly, we combine the states I3 and I6.

On the state I3, with the input symbol ‘c,’ we move to I3. On the state I6, we move to I6.

The states I3 and I6 are combined, So we write SHIFT action S36.

The number of states in the LALR parse table is <= number of states in CLR(1)