Re: ambiguity of grammar and LR(k)

"Matt Timmermans" <mtimmerm@microstar.nospam-remove.com> writes:
> Linlist Leo wrote in message 99-10-130...


> >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.


> Lots of them. Here's an easy one:


Like the earlier example we've seen, this is example of a *grammar*
that is unambigous yet not LR(k) for any k.


However, note that Linlist asks for *languages*, not *grammars*.
The language described by your grammar certainly *can* be LR(k)
simply by describing it with another grammar than the one you give.


Indeed the language in question:


    { xc^nb | n > 0 } U { xc^na | n > 0 }


is regular, so it trivially has a LR(0) grammar.


--
Henning Makholm

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