18 Sep 1998 23:06:33 -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: | chrish@3drealms.com (Chris Hargrove) |

Newsgroups: | comp.compilers |

Date: | 18 Sep 1998 23:06:33 -0400 |

Organization: | Concentric Internet Services |

Keywords: | parse, LALR |

I've been mucking around with making a C++ parser generation library

for the hell of it (so I could calculate parser state machines on the

fly based on string-passed rules rather than stick with pre-generated

output from an external tool). I've decided to limit it to LALR(1)

since it seems to allow enough grammar complexity.

Right now the generator is LR(0), and to that end it works like a

champ. But I've run into problems adapting it to calculate the

lookahead tokens required for LALR(1). I've referred to both [Aho]

and [Holub] and while both have several routines for lookahead

determination, they all seem to depend on either organizing the

generator's kernel item closure routine for LR(1) (including the

calculation of first sets during that operation), or doing many passes

over the kernel items to determine spontaneous and propogated

lookaheads. All these algorithms seem to come from the point of view

of a generator that must output precomputed action/goto tables which

are entirely deterministic from that point on.

Since I'm coming from a different standpoint (calculating the

generators on demand as node-driven state machines which will remain

in memory while the generator is used), is there a more simplistic

alternative to these algorithms? Worst case scenario I'll go ahead

and mimic the pregenerated case and use the algorithm in [Aho], but I

wanted to know if recent literature addressed any newer methods

tailored to this scenario (i.e. all information accessible to the

parser generator is accessible to the parser itself). It's not a

common case, so my search so far has been to little avail.

Any ideas would be appreciated,

--

Chris Hargrove

Programmer, 3DRealms Entertainment

chrish@3drealms.com

http://www.3drealms.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.