Canonical Collection of LR(0) Items

This collection is computed by using the following algorithm:

                void item(G’)     {

                                C = CLOSURE({[S’ → .S]});

                                repeat

                                                for(each set of items I and 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 on a round;

                }

DFA from canonical collection of LR(0) Items 

The Goto function of the canonical collection of a 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 its items is:

What is the use of DFA?

• We can make use of the DFA in construction of parsing table because it recognizes the viable prefixes of the grammar.

Viable Prefix

• These are the prefixes of the right sentential forms that do not contain any symbols to the right of the handle
• It is also called because it is always possible to add terminal symbols to the end of a viable prefix to obtain a right sentential form

Valid Item: An item A → β1.β2  is viable for some prefix αβ1 if there is a derivation \[S\underset{rm}{\overset{*}{\mathop{\Rightarrow }}}\,\text{ }\alpha Aw\text{ }\underset{rm}{\overset{*}{\mathop{\Rightarrow }}}\,\alpha \beta 1\beta 2w\] 

• The valid item says to parser whether it has to shift or reduce

For example, if A→β1.β2 is valid αβ1 and with αβ1 on the stack with β2 ≠ εcalls for shift and with β2 = ε calls for reduction by A → β1

• In general, there may be more than one item valid for one viable prefix. In such case, the conflicts are resolved by looking at the next input symbol.
• In the DFA, the valid items for a viable prefix γ is exactly the set of items reached from the initial state (I₀) along a path labelled γ. For example, I₇ contains the items valid for viable prefix E + T* 

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.