26 Sep 1998 01:07:51 -0400

Related articles |
---|

LALR(1) Lookahead calculation chrish@3drealms.com (1998-09-18) |

Re: LALR(1) Lookahead calculation cfc@world.std.com (Chris F Clark) (1998-09-22) |

Re: LALR(1) Lookahead calculation sperber@informatik.uni-tuebingen.de (1998-09-22) |

Re: LALR(1) Lookahead calculation corbett@lupa.Eng.Sun.COM (1998-09-24) |

Re: LALR(1) Lookahead calculation dick@cs.vu.nl (1998-09-26) |

Re: LALR(1) Lookahead calculation cfc@world.std.com (Chris F Clark) (1998-09-26) |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 26 Sep 1998 01:07:51 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 98-09-069 98-09-088 98-09-122 |

Keywords: | parse, LALR |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.