Re: ambiguity of grammar and LR(k)

Xavier Nicollin <Xavier.Nicollin@imag.fr>
29 Oct 1999 02:31:00 -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)
[4 later articles]
| List of all articles for this month |

From: Xavier Nicollin <Xavier.Nicollin@imag.fr>
Newsgroups: comp.theory,comp.compilers
Date: 29 Oct 1999 02:31:00 -0400
Organization: Institut IMAG, Grenoble (http://www.imag.fr)
Distribution: inet
References: 99-10-130
Keywords: parse, LR(1)

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.


Sorry, no hint there. BTW, do there exist language inherently ambiguous?
--
| 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.