Re: Non-LR(k) Languages

"Andrei Stefan" <>
14 Mar 2003 11:05:10 -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: "Andrei Stefan" <>
Newsgroups: comp.compilers
Date: 14 Mar 2003 11:05:10 -0500
Organization: Compilers Central
References: 03-03-015
Keywords: parse, LR(1)
Posted-Date: 14 Mar 2003 11:05:10 EST

    Dear Rob Arthan,

Looking in:

    Knuth, D.E.: On the translation of languages from left to right.
    Information Control. No. 8, pp. 607-639 (1965)

there is a result which states that:
    "There exist RL(0) languages which cannot be LR(k), for any
    k >= 0".
To prove that, let us consider the CFG given by:
    S -> A c | B
    A -> a A b b | a b b
    B -> a B b | a b
Obviously, G is RL(0) because mirror(G) is LR(0). The language
L(G) ={a^n b^{2n}c, a^n b^n | n >= 1} is not a deterministic
context-free language. In the same paper (Knu65), it was proven
that a language is deterministic CFL iff it can be generated by a
LR(k) grammar. So, there is no equivalent LR(k) grammar to G.
(end of the constructive proof)

    Is it O.K. for you? By the way, the last grammar proposed
by you, namely:
    C = A, `b`, C, `c` | B, C, `c` | `c`;
    B = | `b`;
    A = | `a`;
has a different language. This is:
    L=((lambda+a)b+(lambda+b))^n c^{n+1}.
Moreover, the one proposed by you, namely
    {a^k b^m c^n | 0 <= k < m < n or 0 = k = m < n}
is not a context-free language!!
    Best wishes,
  Stefan Andrei

> ---------- Forwarded message ----------
> Date: 9 Mar 2003 17:17:52 -0500
> From: Rob Arthan <>
> To:
> Subject: [Compilers] 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.

Post a followup to this message

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