computation of the canonical collection of sets of LR(0) items

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

Return to the comp.compilers page.
Search the comp.compilers archives again.