Mon, 10 Mar 2008 16:57:46 -0700 (PDT)

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

From: | Carlo Salinari <carlo.salinari@gmail.com> |

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 )

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.