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;
}
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 (I0) along a path labelled γ. For example, I7 contains the items valid for viable prefix E + T*
