LALR(1) Lookahead calculation

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

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