Re: LALR(1) Lookahead calculation

> State splitting is not a way of computing LALR(1) lookahead sets.


However, David's algorithm can also be used to determine lookahead
sets from an LR(0) machine (either LALR ones or LR ones). It does
that in the process of determining where to split the states. You
don't have to split the states to use his look-back method for
computing lookaheads.


Importantly, this is the key to the previous question, the LR(0)
machine contains all the information needed to compute the lookahead
sets. In fact, the incrementally compiled LR(0) machine has almost
enough information--and when it doesn't all you need to do is fill out
a few more states--the ones which have the lookaheads for the parent
productions, which is where the machine will go if one reduces.


> State splitting is very hard.


I also disagree with this. There is one simple algorithm which always
works (although it can make a slightly larger than required machine).
Once, you have determine a state to split off, generate a new set of
LR(0) tables based upon that state (without merging with any previous
tables). The LR(0) tables capture that state as if it were a
sub-grammar to itself. Thus, you effectively generate separate sets
of LR(0) tables for each place where the LR engine would not have
merged them in the first place, which is what the extra information in
the canonical LR items is designed to do (that is keep one from
merging items that have conflicting lookahead).


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : cfc@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
--

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