31 Oct 1999 01:18:21 -0400

Related articles |
---|

[2 earlier articles] |

Re: ambiguity of grammar and LR(k) hanskamp@introweb.nl (Hans Kamp) (1999-10-29) |

Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-29) |

Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-29) |

Re: ambiguity of grammar and LR(k) mtimmerm@microstar.nospam-remove.com (Matt Timmermans) (1999-10-29) |

Re: ambiguity of grammar and LR(k) nhartzell@macalester.edu (Nathan Hartzell) (1999-10-29) |

Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31) |

Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31) |

Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-31) |

Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-31) |

Re: ambiguity of grammar and LR(k) uranus!ikastan@uunet.uu.net (1999-10-31) |

Re: ambiguity of grammar and LR(k) linlist@fudan.edu (Linlist Leo) (1999-10-31) |

Re: ambiguity of grammar and LR(k) sol!ikastan@agate-ether.berkeley.edu (1999-11-02) |

From: | Xavier Nicollin <Xavier.Nicollin@imag.fr> |

Newsgroups: | comp.theory,comp.compilers |

Date: | 31 Oct 1999 01:18:21 -0400 |

Organization: | Institut IMAG, Grenoble (http://www.imag.fr) |

Distribution: | inet |

References: | 99-10-130 99-10-167 |

Keywords: | parse, LR(1) |

Matt Timmermans wrote:

*>*

*> >What I cannot figure out is whether there is any language that is not*

*> >inherently ambiguous but cannot be LR(k) for any k. I'd appreciate if*

*> >anyone can give me some hints.*

*>*

*> Lots of them. Here's an easy one:*

*>*

*> S -> A C a | B C b*

*> A -> x*

*> B -> x*

*> C -> c | C c*

The grammar is not LR(k) for any k, but the *language* is LR(0), since

is is generated by the grammar

S -> x C a | x C b

C -> c | C c

However, I wonder if there exists an LR(k) grammar for the following

languages:

L1 = {a^i b^j, 0 <= j < i}

L2 = {a^i b^j, 0 <= i < j} U {a^i b^j, 0 <= j < i}

--

Xavier Nicollin

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.