Re: ambiguity of grammar and LR(k)

uranus!ikastan@uunet.uu.net (Ilias Kastanas)
31 Oct 1999 01:25:45 -0400

          From comp.compilers

Related articles
[5 earlier articles]
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: uranus!ikastan@uunet.uu.net (Ilias Kastanas)
Newsgroups: comp.theory,comp.compilers
Date: 31 Oct 1999 01:25:45 -0400
Organization: CSUnet
Distribution: inet
References: 99-10-130 99-10-158
Keywords: parse, LR(1)

Xavier Nicollin <Xavier.Nicollin@imag.fr> wrote:
@Linlist Leo wrote:
@>
@> It is well-known the following grammar is ambiguous so that it is
@> not LR(k) for any k.
@> S -> iEtSeS | iEtS | a
@> ('a' is not important, maybe just some assigning statement)
@>
@> But it can be written in an umambiguous way. I devised the following
@> grammar(maybe incorrect).
@> S -> M | U
@> M -> iEtMeM | a
@> U -> iEtS
@>
@> I guess it LR(1). Any correction will be welcomed.
@
@It is incorrect: you cannot derive
@ iEtaeiEta
@The rules for U should be:
@ U -> iEtS | iEtMeU
@The grammar is then LR(1) (it is even SLR(1)).
@
@> 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.






Yes, L = palindromes over {0,1}. The obvious grammar for L is
unambiguous; but L isn't LR(k) for any k, because L is not a deter-
ministic CFL.




@Sorry, no hint there. BTW, do there exist language inherently ambiguous?




{0^m 1^n 2^n} U {0^m 1^m 2^n}






Ilias


Post a followup to this message

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