Grammar LR(1) but not LALR(1)

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

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