Construction of LALR(1) Items

LALR(1) Items Construction:

Consider the following LR(1) items for the augmented grammar

S’ →S    S →CC   C → cC | d

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., $

As per the algorithm, in the given LR(1) items we have the following set of items with the same core

• I3 and I6
• I4 and I7
• I8 and I9

Now, after merging the above mentioned sets we get,

I36:

C → c.C, c/d/$

C → .cC, c/d/$

C → d., c/d/$

I47:

C → d., c/d/$

I89:

C → cC., c/d/$

While merging

• Keep core as it is and
• Merge the second components

Now the LALR(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, $

I36: C → c.C, c/d/$ C → .cC, c/d/$ C → d., c/d/$ I47: C → d., c/d/$ I5: S → CC., $ I89: C → cC., c/d/$

DFA from LALR(1) Items:

The goto function of the LALR(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 above Example from its items is as shown in the image

   LALR(1) Parsing Table:

 

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.