Re: ambiguity of grammar and LR(k)

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

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