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

## Carlo Salinari <carlo.salinari@gmail.com>Mon, 10 Mar 2008 16:57:46 -0700 (PDT)

From comp.compilers

Related articles
computation of the canonical collection of sets of LR(0) items carlo.salinari@gmail.com (Carlo Salinari) (2008-03-10)
Re: computation of the canonical collection of sets of LR(0) items FSet.SLB@gmail.com (Scott Burson) (2008-03-15)
| List of all articles for this month |

 From: Carlo Salinari Newsgroups: comp.compilers Date: Mon, 10 Mar 2008 16:57:46 -0700 (PDT) Organization: Compilers Central Keywords: LR(1), question Posted-Date: 13 Mar 2008 17:53:18 EDT

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 )
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 )
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

Post a followup to this message