Re: ambiguity of grammar and LR(k)

Xavier Nicollin <Xavier.Nicollin@imag.fr>
31 Oct 1999 01:17:52 -0400

          From comp.compilers
Related articles
ambiguity of grammar and LR(k) linlist@fudan.edu (Linlist Leo) (1999-10-27)
Re: ambiguity of grammar and LR(k) hanskamp@introweb.nl (Hans Kamp) (1999-10-28)
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)
| List of all articles for this month |
From: Xavier Nicollin <Xavier.Nicollin@imag.fr>
Newsgroups: comp.theory,comp.compilers
Date: 31 Oct 1999 01:17:52 -0400
Organization: Institut IMAG, Grenoble (http://www.imag.fr)
Distribution: inet
References: 99-10-130 99-10-158
Keywords: parse, theory

Before anyone does it, I answer my own question:


Xavier Nicollin wrote:
> Do there exist language inherently ambiguous?


BTW, by "lnguage" I meant "context-free languages"


The answer is yes. For instance:


L = {a^i b^i c^j , i >= 0, j >= 0} U {a^j b^i c^i, i >= 0, j >= 0}


It is a CFL, but ther is no way to define it by an unambiguous grammar.
--
| Xavier NICOLLIN (mailto:Xavier.Nicollin@imag.fr), INPG (ENSIMAG)
| VERIMAG - Centre Equation - 2, ave. de Vignate - 38610 Gieres - France
| Tel : (33 | 0) 476 63 48 46 -- Fax : (33 | 0) 476 63 48 50

Post a followup to this message

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