Re: Non-LR(k) Languages

    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 <rda@lemma-one.com>
> To: compilers@iecc.com
> 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.

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