Re: Grammar LR(1) but not LALR(1)

Jean-Marc Bourguet <jm@bourguet.org>
8 Nov 2003 01:37:59 -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: 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.