Introduction of CLR Parsers

CLR Parsers

CLR Parsers table entries are filled by using an algorithm that uses LR(1) items constructed for the given grammar
For constructing the LR(1) items for a given grammar the method is similar to LR(0) item construction with only few changes in the closure and goto functions after constructing the augmented grammar
Closure:
setOfItems CLOURE(I)   {
                                                repeat
                                                for(each item[A α.Bβ, a] in I)
                                                for(each production B → γ in G’)
                                                for(each terminal b in FIRST(βa))
                                                                add[B → .γ, b] to set I;
                                                until no more items are added to I;
                                                }
Example:
Consider the augmented grammar S’ → S    S → CC    C → cC | d. Now the closure of the item [S’ → .S, $] includes
                                S’ → .S, $
                                S → .CC, $
                                C → .Cc, c/d
                                C → .d, c/d
Explanation:
\[To\text{ }proceed,\text{ }compare\text{ }your\text{ }item\text{ }with\text{ }\left[ A\text{ }\to \text{ }\alpha .B\beta ,\text{ }a \right].\text{ }Initially\text{ }A\text{ }=\text{ }S,\text{ }a\text{ }=\text{ }\varepsilon ,\text{ }B\text{ }=\text{ }S,\text{ }\beta \text{ }=\text{ }\varepsilon \text{ }and\text{ }a\text{ }=\text{ }\$.~\] 
\[Now\text{ }compute\text{ }FIRST\left( \beta a \right)\text{ }=\text{ }FIRST\left( \text{ }\$\text{}\right)\text{}=\left\{\text{}\$\text{}\right\}\] 
\[Now\text{ }add\text{ }all\text{ }productions\text{ }of\text{ }the\text{ }form\text{ }B\text{ }\to \text{ }.\text{ }Y,\text{ }\$\text{}to\text{}the\text{}set.\text{}So,\text{}S\text{}\to\text{}CC,\text{}\$\text{}is\text{}added\] 
\[Now\text{ }comparing\text{ }S\text{ }\to \text{ }.CC,\text{ }\$\text{}with\text{}\left[A\text{}\to\text{}\alpha.B\beta,\text{}a\right].A\text{}=\text{}S,\text{}a\text{}=\text{}\varepsilon,\text{}B\text{}=\text{}C,\text{}\beta\text{}=\text{}C\text{}and\text{}a\text{}=\text{}\$.~\]
\[Now\text{ }compute\text{ }FIRST\left( \beta a \right)\text{ }=\text{ }FIRST\left( C\$\right)\text{}=\text{}\left\{\text{}c,\text{}d\right\}\] 
So C → .cC, c/d and C → .c, c/d are added. No further productions can be added (as B matches no variable)

Goto:
SetOfItems GOTO(I, X) {
                                                Initialize J to be the empty set;
                                                                for(each item [A α.Xβ, a] in I)
                                                                                add item item [A αX.β, a] to set J;
                                                return CLOSURE(J);
                                                }
Example:
Let the set of items I contains
                                S’ → .S, $   S → .CC, $  C → .Cc, c/d   C → .d, c/d
Then goto(I, S) includes moving over S and taking its closure. This results in only one item set S’ → S., $
Similarly goto(I, C) includes moving over C and taking its closure
                                S → .CC, $   C → .Cc, $  C → .c, $

LR(1) Items Constructions:
The following algorithm is used to generate LR(1) items:
Void items(G’)  {
                                                initialize C to CLOSURE({[S’ .S, $]});
                                                repeat
                                                for(each set of items I in C)
                                                for(each grammar symbol X)
                                                if(GOTO(I, X) is not empty and not in C)
                                                                add GOTO(I, X) to C;
                                                until no new sets of items are added to C;
                                }

LR(1) Items Construction:
Example 1:
For the augmented grammar S’ → S  S → CC  C → cC | d the sets of LR(1) items are
I0:
S’ → .S, $
S → .Cc, $
C → .cC, c/d
C → .d, c/d

I1:
S’ → .S, $

I2:
S → C.C, $
C → .cC, $
C → .d, $

I3:
C → c.C, c/d
C → .cC, c/d
C → .d, c/d
I4:
C → d., c/d

I5:
S → CC., $

I6:
C → c.C, $
C → .cC, $
C → .d, $

I7:
C → d., $

I8:
C → cC., c/d

I9:
C → cC., $

DFA from LR(1) Items:
The Goto function for the LR(1) collection of set of items defines a DFA that recognizes the viable prefixes of the grammar. Each set of item becomes a state in the DFA. The DFA for the example 1 from it’s items is as shown in the image.
Introduction of CLR Parsers, how to construct clr parsing table, how to construct dfa from clr parser,what is clr parser, difference between lr(0) and LR(10), r16 jntuh compiler design syllabus pdf,r16 jntuh compiler design lecture notes pdf unitwise,jntuh r16 compiler design notes,jntuh 3-1 compiler design notes, estudies4you,



Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment