31 Oct 2003 23:05:01 -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: | 31 Oct 2003 23:05:01 -0500 |

Organization: | Compilers Central |

Keywords: | parse, LALR, question |

Posted-Date: | 31 Oct 2003 23:05:01 EST |

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

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)

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?

Thanks,

--

Jean-Marc

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.