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)

StatesActionGo To
 c                                d                                $E                                B
I0S3                              S4                                  2
I1  
I2S6                               S7                                   5
I3S3                                 S4                                   8
I4r3                                  r3 
I5                                                                    r1 
I6S6                                 S7                                    9
I7                                                                     r3 
I8r2                                 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.

Pin It on Pinterest

Share This