Re: ambiguity of grammar and LR(k)

Henning Makholm <henning@makholm.net>
31 Oct 1999 01:24:29 -0400

          From comp.compilers

Related articles
[4 earlier articles]
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: Henning Makholm <henning@makholm.net>
Newsgroups: comp.theory,comp.compilers
Date: 31 Oct 1999 01:24:29 -0400
Organization: UNI-C
Distribution: inet
References: 99-10-130 99-10-167
Keywords: parse, theory

"Matt Timmermans" <mtimmerm@microstar.nospam-remove.com> writes:
> Linlist Leo wrote in message 99-10-130...


> >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:


Like the earlier example we've seen, this is example of a *grammar*
that is unambigous yet not LR(k) for any k.


However, note that Linlist asks for *languages*, not *grammars*.
The language described by your grammar certainly *can* be LR(k)
simply by describing it with another grammar than the one you give.


Indeed the language in question:


    { xc^nb | n > 0 } U { xc^na | n > 0 }


is regular, so it trivially has a LR(0) grammar.


--
Henning Makholm


Post a followup to this message

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