Rob Arthan <>
9 Mar 2003 17:17:52 -0500

          From comp.compilers

Related articles
Non-LR(k)Languages (Rob Arthan) (2003-03-09)
Re: Non-LR(k) Languages (Andrei Stefan) (2003-03-14)
Re: Non-LR(k) Languages (2003-03-14)
| List of all articles for this month |

From: Rob Arthan <>
Newsgroups: comp.compilers
Date: 9 Mar 2003 17:17:52 -0500
Organization: Lemma 1 Ltd.
Keywords: parse, theory, question
Posted-Date: 09 Mar 2003 17:17:52 EST

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 (

Post a followup to this message

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