LALR 1 Parsing | Compiler Design

LALR (1) Parsing

The LALR parsing refers to the “lookahead LR” that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical collection of LR(1) items is used. In the LALR(1) parsing, the LR(1) items with the same productions but have different lookahead are grouped together to form a single set of items. It is generally the same as CLR(1) parsing except for the one difference that is the parsing table.

Example

Suppose we have the following grammar:

E => BB

B => cB / d

Then add augment production and insert ‘.’ symbol at the beginning of every production in the grammar G.  Next, add the lookahead also.

E’ => .E, $

E => .BB,$

B => .cB, c/d

B => .d, c/d

I0 state

Add starting production to the I0 State and Compute the Closure.

I0 = closure (E’ => .E)

Add all the production beginning with E into I0 State because “.” is at the first place of production before the non-terminal. So, the I0 State becomes:

I0 = E’ => .E, $

E => .BB, $

Add all the production beginning with “B” in modified I0 State because “.” is at the first place of production before the non-terminal. So, the I0 State becomes:

E’ => .E, $

E => .BB, $

B => .cB, c/d

B => .d, c/d

I1 = Go to on (I0 E) = closure (E’ => E., $)

I1 = E’ => E., $

I2 = Go to on (I0 B) = Closure (E => B.B, $)

Add all the productions beginning with B into I2 State because “.” is at the first place of production before the non-terminal. So, the I2 state becomes:

E => B.B, $

B => .cB, $

B => .d, $

I3 = Go to on (I0 c) = Closure (B => c.B, c/d)

Add productions beginning with B in I3.

B => c.B, c/d

B => .cB, c/d

B => .d, c/d

Goto on (I3 c) = Closure (B => c. B, c/d)                       (Same as I3)

Goto on (I3 d) = Cllosure (B => d., c/d)                            (Same as I4)

I4 = Goto on (I0 d) = Closure (B => d. , c/d) = B => d. , c/d

I5 = Goto on (I2 B) = Closure (E => BB. , $) = E => BB. , c/d

I6 = Goto on (I3 c) = Closure (B =>c.B, $)

Add all productions beginning with B into I6 State because “.” is at the first place of production before the non-terminal. So, the I6 state becomes:

B => c.B, $

B => .cB, $

B => .d, $

Goto on (I6, c) = Closure (B => c.B, $) = (same as I6)

Goto on (I6, d) = Closure (B => d., $) = (same as I7)

I7 = Goto on (I2 d) = Closure (B => d., $)

I8 = Goto on (I3 B) = Closure (B => cD., c/d)

I9 = Goto on (I6 B) = Closure (cB., $)

We can see that the LR(0) items of I3 and I6 are the same, but the only difference is their lookahead.

I3 = {B => c.B, c/d

B => .cB, c/d

B => .d, c/d

}

I6 = {B => c.B, $

B => .cB, $

B => .d, $

}

We can combine I3 and I6 as I36.

I36 = {B => c.B, c/d/$

B => .cB, c/d/$

B => .d, c/d/$

}

The I4 and I7 states are same, but the lookahead symbol is distinct in both case, so we have combined both states and named as I47.

I47 = {B => d., c/d/$}

The I8 and I9 states are same, but the lookahead symbol is distinct in both case, so we have combined both states and named as I89.

I89 = {B => Cb., c/d/$ }

Drawing DFA

LALR(1) Parsing Table

source