Re: ambiguity of grammar and LR(k)

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

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