25 Oct 2002 00:15:36 -0400

Related articles |
---|

[15 earlier articles] |

Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (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) ska1@snafu.de (Sönke Kannapinn) (2002-10-18) |

Re: LR Grammars not in LALR(1) or LR(1) joachim_d@gmx.de (Joachim Durchholz) (2002-10-20) |

Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (Clint Olsen) (2002-10-24) |

Re: LR Grammars not in LALR(1) or LR(1) ska1@snafu.de (Sönke Kannapinn) (2002-10-25) |

From: | "Sönke Kannapinn" <ska1@snafu.de> |

Newsgroups: | comp.compilers |

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 |

Keywords: | LALR |

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*

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.