The dragon book gives this algorithm to compute the canonical
collection of sets of LR(0) items for an augmented grammar G' (page
246 in the 2nd edition):
void items(G') {
C = 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 on a round;
}
which, if I understand correctly, from the first state on (where a
state is a set of items), incrementally finds all the possible
transitions and relative next-states, appending the latter to the
state collection, until all possible transitions have been examined.
what I don't understand is the second "for" clause: why do we have to
iterate over each symbol in the grammar?
don't we already know that the only symbol for which a transition is
possible are those on the rigth of a dot?
I mean, given the item set:
T -> T*.F
F -> .(E)
F -> .id
we know that the only valid transitions are on F, ( and id. Why should
one check for all the other symbols in the grammar?
Couldn't the algorithm be rewritten like this:
void items(G') {
C = CLOSURE({[S' -> .S]});
repeat
for ( each set of items I in C )
for ( each symbol X in the current set that is on the
right of a dot )
if ( GOTO(I, X) is not already in C )
add GOTO(I, X) to C;
until no new sets of items are added to C on a round;
}
Avoiding a (possibly large) set of unfruitful iterations?
Or I am missing something foundamental here?
Regards,
Carlo


|