|Parsing techniques firstname.lastname@example.org (1993-05-04)|
|Re: Parsing techniques email@example.com (1993-05-07)|
|Re: Parsing techniques firstname.lastname@example.org (1993-05-08)|
|Parsing techniques email@example.com (Kent Rollins) (1996-11-26)|
|Re: Parsing techniques firstname.lastname@example.org (Scott Stanchfield) (1996-12-01)|
|Re: Parsing techniques email@example.com (1996-12-01)|
|Re: Parsing techniques firstname.lastname@example.org (1996-12-01)|
|Re: Parsing techniques email@example.com (1996-12-01)|
|Re: Parsing techniques firstname.lastname@example.org (1996-12-03)|
|Re: Parsing techniques email@example.com (Ron House) (1996-12-07)|
|Re: Parsing techniques firstname.lastname@example.org (1996-12-09)|
|[3 later articles]|
|From:||Scott Stanchfield <email@example.com>|
|Date:||1 Dec 1996 22:51:58 -0500|
|Keywords:||parse, LL(1), LALR|
I can't get too much into this, but...
Most of the literature says "use LALR(1) vs LL(1)" for two main reasons
that I can think of.
1) performance of table-driven (most LALR implementations) is
usually better than recursive-descent (most LL implementations)
2) LALR(1) is stronger than LL(1) (it can handle more grammars)
Now to attack these...
1) depending on the implementation and on how carefully the parser
is written, the performance difference is very small, especially
in light of today's processor speeds. It mattered a great deal
when LALR was born, because processors were nowhere near as fast
as today, but it's not as big a deal now. (Note that I'm still
saying that LALR is usually a slightly faster performer...)
2) Today we have predicated LL(k) grammars, which are (methinks) at
least as strong as LALR(1). (One example of this is ANTLR, PCCTS'
parser generator.) In practice, most grammars will only need one
or two tokens of lookahead. There are evil languages, such as
C++, that need "infinite lookahead" in spots to determine whether
something is a type or not, or a decl vs expr. These can be
implemented by either hacking with a tightly-coupled scanner/parser
or by using predicated grammars that can check semantics and
simply "try it to see if it works" when selecting which alternative
3) Debugging recursive-desecent is much easier (IMHO) than a table-
driven parser. (Maintenance, ya know.)
4) If you have the right parser-generator, error recovery can
be pretty simple (as in ANTLR, using "parser exception handling.")
That's my (limited) input for now...
Kent Rollins wrote:
> [what's the relative merits of LALR vs. LL, especially for C++ ?]
Santa Cruz, CA
Return to the
Search the comp.compilers archives again.