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

"Michael Sperber [Mr. Preprocessor]" <sperber@informatik.uni-tuebingen.de>
9 Dec 1995 19:59:10 -0500

          From comp.compilers

Related articles
[16 earlier articles]
Re: LL(1) vs LALR(1) parsers pardo@cs.washington.edu (1995-11-29)
Re: LL(1) vs LALR(1) parsers CSPT@giraffe.ru.ac.za (Pat Terry) (1995-11-30)
Re: LL(1) vs LALR(1) parsers gvcormac@plg.uwaterloo.ca (Gord Cormack) (1995-12-01)
Re: LL(1) vs LALR(1) parsers bridges@cs.arizona.edu (1995-12-01)
Re: LL(1) vs LALR(1) parsers mparks@oz.net (1995-12-09)
Re: LL(1) vs LALR(1) parsers maatwerk@euronet.nl (1995-12-09)
Re: LL(1) vs LALR(1) parsers sperber@informatik.uni-tuebingen.de (Michael Sperber [Mr. Preprocessor]) (1995-12-09)
Re: LL(1) vs LALR(1) parsers mparks@oz.net (1995-12-12)
Re: LL(1) vs LALR(1) parsers solution@gate.net (1995-12-16)
Re: LL(1) vs LALR(1) parsers sb@metis.no (1995-12-17)
Re: LL(1) vs LALR(1) parsers scooter@mccabe.com (Scott Stanchfield) (1995-12-18)
Re: LL(1) vs LALR(1) parsers G.A.Tijssen@eco.RUG.NL (Gert A. Tijssen) (1995-12-19)
| List of all articles for this month |

From: "Michael Sperber [Mr. Preprocessor]" <sperber@informatik.uni-tuebingen.de>
Newsgroups: comp.compilers
Date: 9 Dec 1995 19:59:10 -0500
Organization: Compilers Central
References: 95-11-138 95-11-242 95-12-022
Keywords: LALR, LL(1), bibliography

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


Post a followup to this message

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