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

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

Return to the comp.compilers page.
Search the comp.compilers archives again.