Re: ambiguity of grammar and LR(k)

Xavier Nicollin <Xavier.Nicollin@imag.fr>
31 Oct 1999 01:18:21 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.