Scribd
Upload
317 views

What Is clr1?: Various Steps Involved in The CLR (1) Parsing

CLR1 refers to canonical LR(1) parsing, which uses the canonical collection of LR(0) items to construct the CLR(1) parsing table. CLR(1) parsing typically has more states than SLR(1) parsing. The reduced node is placed only in the lookahead symbols. The key steps to CLR(1) parsing involve writing a context-free grammar, checking for ambiguity, adding augmenting productions, creating the canonical LR(0) item collection, drawing a DFA, and constructing the CLR(1) parsing table.

Uploaded by

Sadia Sumi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
317 views

What Is clr1?: Various Steps Involved in The CLR (1) Parsing

CLR1 refers to canonical LR(1) parsing, which uses the canonical collection of LR(0) items to construct the CLR(1) parsing table. CLR(1) parsing typically has more states than SLR(1) parsing. The reduced node is placed only in the lookahead symbols. The key steps to CLR(1) parsing involve writing a context-free grammar, checking for ambiguity, adding augmenting productions, creating the canonical LR(0) item collection, drawing a DFA, and constructing the CLR(1) parsing table.

Uploaded by

Sadia Sumi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

CLR1

What is clr1?
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.

Table construction ideas of clr1:

Various steps involved in the CLR (1) Parsing:

o For the given input string write a context free grammar


o Check the ambiguity of the grammar
o Add Augment production in the given grammar
o Create Canonical collection of LR (0) items
o Draw a data flow diagram (DFA)
o Construct a CLR (1) parsing table
o

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
Grammar Add the lookahead also.

E’ => .E, $
E => .BB,$
B => .cB, 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

-----------------------------------draw dfa-------------------
Production to be numbered as follows:

E’ => E
E => BB (1)
B => cB(2) /d (3)

Canonical parsing table-

State Action Go-to

c d $ E B
I0 S3 S4 1 2

I1 accept
I2 S6 S7 5

I3 S3 S4 8
I4 r3 r3

I5 r1
I6 S6 S7 9

I7 r3
I8 r2 r2
I9 r2

You might also like