|Grammar LR(1) but not LALR(1) email@example.com (Jean-Marc Bourguet) (2003-10-31)|
|Re: Grammar LR(1) but not LALR(1) firstname.lastname@example.org (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) email@example.com (ANDREI Stefan) (2003-11-08)|
|Re: Grammar LR(1) but not LALR(1) firstname.lastname@example.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 <email@example.com>|
|Date:||8 Nov 2003 01:37:59 -0500|
|Posted-Date:||08 Nov 2003 01:37:59 EST|
Jean-Marc Bourguet <firstname.lastname@example.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)
> 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.
Return to the
Search the comp.compilers archives again.