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.

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.