Scribd
Upload
59 views6 pages

CLR 1 Parsing - Javatpoint

CLR (1) parsing utilizes canonical collections of LR (1) items to create a parsing table that generates more states than SLR (1) parsing. The process involves writing context-free grammar, checking for ambiguity, adding augment production, and constructing the CLR (1) parsing table through various states. An LR (1) item consists of LR (0) items combined with a lookahead symbol, which is essential for determining production placement.

Uploaded by

Madan Tiwari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
59 views6 pages

CLR 1 Parsing - Javatpoint

CLR (1) parsing utilizes canonical collections of LR (1) items to create a parsing table that generates more states than SLR (1) parsing. The process involves writing context-free grammar, checking for ambiguity, adding augment production, and constructing the CLR (1) parsing table through various states. An LR (1) item consists of LR (0) items combined with a lookahead symbol, which is essential for determining production placement.

Uploaded by

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

ADVERTISEMENT

CLR (1) Parsing


CLR refers to canonical lookahead. CLR parsing use the canonical collection of LR (1) items to build the
CLR (1) parsing table. CLR (1) parsing table produces the more number of states as compare to the SLR
(1) parsing.

In the CLR (1), we place the reduce node only in the lookahead symbols.

Various steps involved in the CLR (1) Parsing:

ADVERTISEMENT ADVERTISEMENT

For the given input string write a context free grammar

Check the ambiguity of the grammar

Add Augment production in the given grammar

Create Canonical collection of LR (0) items

Draw a data flow diagram (DFA)

Construct a CLR (1) parsing table

LR (1) item
ADVERTISEMENT

LR (1) item is a collection of LR (0) items and a look ahead symbol.

LR (1) item = LR (0) item + look ahead

The look ahead is used to determine that where we place the final item.

The look ahead always add $ symbol for the argument production.

Example

CLR ( 1 ) Grammar

S → AA
A → aA
A→b

Add Augment Production, insert '•' symbol at the first position for every production in G and also add
the lookahead.
ADVERTISEMENT ADVERTISEMENT
S` → •S, $
S → •AA, $
A → •aA, a/b
A → •b, a/b

I0 State:

Add Augment production to the I0 State and Compute the Closure

I0 = Closure (S` → •S)

Add all productions starting with S in to I0 State because "." is followed by the non-terminal. So, the I0
State becomes

I0 = S` → •S, $
S → •AA, $

Add all productions starting with A in modified I0 State because "." is followed by the non-terminal. So,
the I0 State becomes.

I0= S` → •S, $
S → •AA, $
A → •aA, a/b
A → •b, a/b
I1= Go to (I0, S) = closure (S` → S•, $) = S` → S•, $
I2= Go to (I0, A) = closure ( S → A•A, $ )

Add all productions starting with A in I2 State because "." is followed by the non-terminal. So, the I2
State becomes

I2= S → A•A, $
A → •aA, $
A → •b, $

I3= Go to (I0, a) = Closure ( A → a•A, a/b )

Add all productions starting with A in I3 State because "." is followed by the non-terminal. So, the I3
State becomes

I3= A → a•A, a/b


A → •aA, a/b
A → •b, a/b
Go to (I3, a) = Closure (A → a•A, a/b) = (same as I3)
Go to (I3, b) = Closure (A → b•, a/b) = (same as I4)

I4= Go to (I0, b) = closure ( A → b•, a/b) = A → b•, a/b


I5= Go to (I2, A) = Closure (S → AA•, $) =S → AA•, $
I6= Go to (I2, a) = Closure (A → a•A, $)

Add all productions starting with A in I6 State because "." is followed by the non-terminal. So, the I6
State becomes

I6 = A → a•A, $
A → •aA, $
A → •b, $

Go to (I6, a) = Closure (A → a•A, $) = (same as I6)


Go to (I6, b) = Closure (A → b•, $) = (same as I7)

I7= Go to (I2, b) = Closure (A → b•, $) = A → b•, $


I8= Go to (I3, A) = Closure (A → aA•, a/b) = A → aA•, a/b
I9= Go to (I6, A) = Closure (A → aA•, $) = A → aA•, $
Drawing DFA:

CLR (1) Parsing table:

Productions are numbered as follows:

S → AA ... (1)
A → aA ....(2)
A → b ... (3)

You might also like