Re: LALR(1) Lookahead calculation

Chris F Clark <cfc@world.std.com>
22 Sep 1998 01:12:08 -0400

          From comp.compilers

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)
| List of all articles for this month |

From: Chris F Clark <cfc@world.std.com>
Newsgroups: comp.compilers
Date: 22 Sep 1998 01:12:08 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 98-09-069
Keywords: LR(1), parse

> Right now the generator is LR(0) . . . adapting it to calculate the
> lookahead tokens required for LALR(1) . . . is there a more simplistic
> alternative to these algorithms?


Yes, find David Spector's paper on "state splitting". It's in SIGPLAN
Notices from ~1986. However, here's the kernel of the idea for your
use. Simply generate the LR(0) machine. Then, when you come to a
state where you might need to reduce, look back along the path that
got you there and if the lookahead from the parent production forces a
reduce, then reduce (or deal with the conflict if it results from
desiring a reduce there). Do this calculation for each rule that has
a reduction in the state.


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)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
--


Post a followup to this message

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