Re: LL(1) vs LALR(1) parsers

  Patrick Bridges <bridges@cs.arizona.edu> writes:


> Note that Penello's LR parser did not actually include *actions* or
> error recovery... Someone I know actually implemented Penello's scheme
> inside of Bison, and this sped up the generated parser on a cut-down C
> (used in a local compiler class) grammar from 300% to 600% (on
> pre-tokenized input). On the other hand, the generated parsers were
> enormous since Penello's scheme encodes most of the parsing tables in
> instruction state.


Look in:


@INPROCEEDINGS{SperberThiemann1995,
                CROSSREF = {PEPM1995},
                AUTHOR = {Michael Sperber and Peter Thiemann},
                TITLE = {The Essence of {LR} Parsing},
                PAGES = {146-155},
                YEAR = 1995
}


The paper shows how to get Pennello's scheme by actually using a
partial evaluator. As it turns out, implementing actions and pretty
much every error recovery scheme under the sun is trivial; we've
recently implemented this, too. The parsers, even though written in
Scheme, and without any fine-tuning, perform about as fast as
Bison/byacc.


Also, since good generated code for the parser is in effect a sparse
encoding of the LR state table, I'm surprised that you should get
enormous parsers. It's certainly not inherent in the approach.


--
Cheers =8-} Chipsy
--

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