8 Nov 2003 01:37:59 -0500

Related articles |
---|

Grammar LR(1) but not LALR(1) jm@bourguet.org (Jean-Marc Bourguet) (2003-10-31) |

Re: Grammar LR(1) but not LALR(1) oliver@zeigermann.de (Oliver Zeigermann) (2003-11-02) |

Re: Grammar LR(1) but not LALR(1) cfc@shell01.TheWorld.com (Chris F Clark) (2003-11-02) |

Re: Grammar LR(1) but not LALR(1) stefan@infoiasi.ro (ANDREI Stefan) (2003-11-08) |

Re: Grammar LR(1) but not LALR(1) jm@bourguet.org (Jean-Marc Bourguet) (2003-11-08) |

Re: Grammar LR(1) but not LALR(1) RLake@oxfam.org.uk (2003-11-11) |

From: | Jean-Marc Bourguet <jm@bourguet.org> |

Newsgroups: | comp.compilers |

Date: | 8 Nov 2003 01:37:59 -0500 |

Organization: | Compilers Central |

References: | 03-10-139 |

Keywords: | parse, LALR |

Posted-Date: | 08 Nov 2003 01:37:59 EST |

Jean-Marc Bourguet <jm@bourguet.org> writes:

Thanks to all who answered.

*> It is well known that there are grammars which are LR(1) but not*

*> LALR(1). For exemple:*

*>*

*> S -> aEa | bEb | aFb | bFa*

*> E -> e*

*> F -> e*

*>*

*> It is possible to transform this grammar to make it LALR(1) by*

*> duplicating productions. For exemple:*

*>*

*> S -> a E a | b E' a | a F b | b F' a*

There was a typo here, it should be:

S -> a E a | b E' b | a F b | b F' a

*> E -> e*

*> E' -> e*

*> F -> e*

*> F' -> e*

*>*

*> As a matter of fact, only one duplication is needed to make the*

*> grammar LALR(1).*

*>*

*> I'm convinced that such a transformation (contructing an LALR(1)*

*> grammar by duplicating productions) is possible for every LR(1)*

It's more duplicating non-terminals than duplicating productions, BTW.

*> grammars, such duplication preventing the merge of the states LR(1)*

*> automaton.*

*>*

*> A collegue is not convinced and try to come up -- without success*

*> until now -- with a language which would have a LR(1) grammar but no*

*> LALR(1) one.*

*>*

*> Could someone point me to a counter example for my claim or a proof of*

*> its correctness?*

In a private mail, someone pointed me to

[DR69] DeRemer, F.L.: Practical translators for LR(k) languages. Ph.D.

Thesis, MIT, Cambridge, 1969

[DRP82] DeRemer, F.L., Pennello, T.: Efficient Computation of LALR(1)

Look-Ahead Set. TOPLAS, vol. 4, no. 4, october 1982

and stated that if the process was fully applied, the resulting

LALR(1) CFG would have the same number of states than the

corresponding LR(1) CFG but the parsing tables would be bigger because

of the new symbols needing reduction information. And we'll still get

the additional reduction that LALR(1) does before detecting an error.

Yours,

--

Jean-Marc

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.