CLR Parsing Compiler Design

CLR Parsing

CLR parsing refers to the canonical lookahead. We will use the canonical collection of LR(1) items for the construction of the CLR(1) parsing table. Generally, CLR(1) parsing has more number of states as compared to SLR(1) parsing. In the CLR(1), the reduced node will be placed only in the lookahead symbols.

The step involves in CLR(1) parsing is given below.

• Write CFG for the given input symbol
• Check if the grammar is ambiguous or not.
• Add an augmented grammar.
• Create a canonical collection of LR(1) items.
• Draw DFA
• Construct a CLR(1) parsing table.

LR(1) item is the collection of LR(0) item and lookahead. The lookahead symbol is used to determine the place of the final item. For every augmented grammar, the lookahead will be $.

Example

Grammar

E => BB

B => cB / d

Add augment production and insert '.' symbol at the beginning of every production in G.  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 begins with "B" in the 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 production beginning with B into the 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 the production beginning with B into the 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, $

Go to on (I6, c) = Closure (B => c•B, $) = (same as I6)

Go to on (I6, d) = Closure (B => d•, $) = (same as I7)

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

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

I9 = Go to on (I6 B) = Closure (B => cB. , $)

Drawing DFA

Production to be numbered as follows:

E =>BB   (1)

B => cB    (2)

B => d       (3)

States	Action	Go To
	c                                d                                $	E                                B
I0	S3                              S4	2
I1
I2	S6                               S7	5
I3	S3                                 S4	8
I4	r3                                  r3
I5	r1
I6	S6                                 S7	9
I7	r3
I8	r2                                 r2
I9	r2

The shift move and Goto move in CLR(1) parsing are the same as LR(0) and SLR(1). The only difference is the reduced node. 

• I4 state have contains the final item which drives (B ? d•, c/d), so action {I4, c} = r3, action {I4, d} = r3.
• I5 state have the final item which drives (E ? BB•, $), so action {I5, $} = r1.
• I7 state have the final item which drives (B ? d•,$), so action {I7, $} = r3.
• I8 state have the final item which drives (B ? cB•, a/b), so action {I8, c} = r2, action {I8, d} = r2.
• I9 state have the final item which drives (B ? cB•, $), so action {I9, $} = r2.