|[15 earlier articles]|
|Re: LR Grammars not in LALR(1) or LR(1) firstname.lastname@example.org (Clint Olsen) (2002-10-13)|
|Re: LR Grammars not in LALR(1) or LR(1) cfc@shell01.TheWorld.com (Chris F Clark) (2002-10-13)|
|Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-10-13)|
|Re: LR Grammars not in LALR(1) or LR(1) email@example.com (Sönke Kannapinn) (2002-10-18)|
|Re: LR Grammars not in LALR(1) or LR(1) firstname.lastname@example.org (Joachim Durchholz) (2002-10-20)|
|Re: LR Grammars not in LALR(1) or LR(1) email@example.com (Clint Olsen) (2002-10-24)|
|Re: LR Grammars not in LALR(1) or LR(1) firstname.lastname@example.org (Sönke Kannapinn) (2002-10-25)|
|From:||"Sönke Kannapinn" <email@example.com>|
|Date:||25 Oct 2002 00:15:36 -0400|
|Organization:||[Posted via] Inter.net Germany GmbH|
|References:||02-09-014 02-09-029 02-09-068 02-09-092 02-09-097 02-09-126 02-09-130 02-09-143 02-10-015 02-10-064 02-10-096|
|Posted-Date:||25 Oct 2002 00:15:36 EDT|
> [I was under the impression that LALR tables are smaller. -John]
Yes and no. Depends on what concept of "parser size" you apply.
You can ask for the "size" of an LALR(k) parser
* as a pushdown transducer - that's a formal concept of "size" -, or
* as the cumulative size of the parser tables of a parser as generated
by some parser generator; that's an implementation-oriented concept
of parser size (which is problematic in theoretical size comparisons
for several reasons).
The number of canonical LR(0) states is, of course, the main
contributing factor for both the formal and some implementation-
oriented parser size concept for LALR(k) and SLR(k) parsers. But
formally, the SLR(k) parser of a grammar has at least as many actions
than the LALR(k) parser. Consequently, a grammar's SLR(k) parser is
always greater or equal in formal size than its LALR(k) parser. But
whether the same is also true when looking at implementations is hard
to say: I cannot say whether the compression techniques applied by
your favorite parser generator is able to produce smaller output for
SLR(k) than for LALR(k). Can you?
> > Put another way, every DCFL has an LR(1), an LALR(1) and even an
> > SLR(1) grammar.
> What, then, is the advantage of LALR(1) over SLR(1)? Especially in
> the light that LALR and SLR versions of the grammar are structurally
> equivalent (assuming some useful definition of "structurally
Of course, for a *fixed* grammar, the SLR(k) parser may be ambiguous
while the LALR(k) parser isn't.
An SLR(1) grammar for a DCFL will probably have more nonterminals and
rules than an LALR(1) grammar (and even more that an LR(1) grammar)
for the same language. Still, they can both be "structurally equivalent"
to the LR(1) grammar (needs a mapping from xLR(1) grammar rules to
corresponding LR(1) grammar rules).
Return to the
Search the comp.compilers archives again.