9 Mar 2003 17:17:52 -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: | Rob Arthan <rda@lemma-one.com> |

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 (rda@lemma-one.com)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.