22 Sep 1998 01:12:08 -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: | 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.