Re: ambiguity of grammar and LR(k)

Henning Makholm <henning@makholm.net>
29 Oct 1999 02:32:16 -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)
[3 later articles]
| List of all articles for this month |

From: Henning Makholm <henning@makholm.net>
Newsgroups: comp.theory,comp.compilers
Date: 29 Oct 1999 02:32:16 -0400
Organization: UNI-C
Distribution: inet
References: 99-10-130
Keywords: parse, LR(1)

Linlist Leo <linlist@fudan.edu> writes:


> But it can be written in an umambiguous way. I devised the following
> grammar(maybe incorrect).
> S -> M | U
> M -> iEtMeM | a
> U -> iEtS


The standard solution from the Dragon Book is identical to yours,
except it also contains the production


      U -> iEtMeU


which allows strings such as


    if E then if E then a else a else if E then a


to be parsed.


> What I cannot figure out is whether there is any language that is not
> inherently ambiguous but cannot be LR(k) for any k.


> [Sure. Construct one along these lines:


> S -> aX | bY
> a -> A | aA;
> b -> A | bA;


The problem here is the particular grammar you give- not the language
itself. The language described by your grammar does have a LR(0)
grammar:


    S -> TX | TY
    T -> A | TA


(which is not surprising as the original grammar is left regular hence
the language it defines is regular).


--
Henning Makholm


Post a followup to this message

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