Grammar LR(1) but not LALR(1)

Jean-Marc Bourguet <jm@bourguet.org>
31 Oct 2003 23:05:01 -0500

          From comp.compilers

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)
| List of all articles for this month |

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.