Re: LR Grammars not in LALR(1) or LR(1)

> [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
> equivalent").


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


Regards,
Sönke

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