14 Mar 2003 11:05:10 -0500

Related articles |
---|

Non-LR(k)Languages rda@lemma-one.com (Rob Arthan) (2003-03-09) |

Re: Non-LR(k) Languages andrei@comp.nus.edu.sg (Andrei Stefan) (2003-03-14) |

Re: Non-LR(k) Languages torbenm@diku.dk (2003-03-14) |

From: | "Andrei Stefan" <andrei@comp.nus.edu.sg> |

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 <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.*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.