Re: ambiguity of grammar and LR(k)

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

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