Talk About Network



Register and Login
Nick
Password
Register create new account Sign up is FREE and you can post replies, new topics, bookmark posts and more!
Recover lost password


Programming > Compilers > computation of ...
Latest [ Topics | Posts ] Archive Post A New Topic Post a Reply
<< Topic < Post Post 1 of 2 Topic 2358 of 2427
Post > Topic >>

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

by Carlo Salinari <carlo.salinari@[EMAIL PROTECTED] > Mar 10, 2008 at 04:57 PM

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




 2 Posts in Topic:
computation of the canonical collection of sets of LR(0) items
Carlo Salinari <carlo.  2008-03-10 16:57:46 
Re: computation of the canonical collection of sets of LR(0) ite
Scott Burson <FSet.SLB  2008-03-15 11:36:36 

Post A Reply:
  Go here to Signup

AddThis Feed Button


About - Advertising - Contact - Frequently Asked Questions - Privacy Policy - Terms of Use - Signup

Contact
tan12V112 Thu May 22 12:26:32 CDT 2008.