Non-LR(k)Languages

I've been looking for an example of a language that can be defined by a
context free grammar (ideally a non-ambiguous one), but not by any LR(k)
grammar. I can't find any example in the literature to hand or on the net.
The nearest I've got from the literature is the non-LR(k) grammar:


        C = B, C, `c` | `c`;
        B = | `b`;


which defines the language of strings b^mc^n with 0<= m < n.


But this language can be described by the LR(1) grammar:


        C = C, `c` | E, `c`;
        E = `b`, E, `c` | ;


My best guess so far is:


        C = A, `b`, C, `c` | B, C, `c` | `c`;
        B = | `b`;
        A = | `a`;


which defines the language of strings a^kb^mc^n with either 0 <= k < m < n
or 0 = k = m < n.


I can't think of an LR(k) grammar for this language, but, of course, that
may just be lack of ingenuity on my part.How do you go about trying to that
there isn't an LR(k) grammar for a language? If this isn't an example of a
non-LR(k) language, can anyone point me towards an example that is?


Rob Arthan (rda@lemma-one.com)

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