Re: ambiguity of grammar and LR(k)

Matt Timmermans wrote:
>
> >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:
>
> S -> A C a | B C b
> A -> x
> B -> x
> C -> c | C c


The grammar is not LR(k) for any k, but the *language* is LR(0), since
is is generated by the grammar


S -> x C a | x C b
C -> c | C c


However, I wonder if there exists an LR(k) grammar for the following
languages:


L1 = {a^i b^j, 0 <= j < i}


L2 = {a^i b^j, 0 <= i < j} U {a^i b^j, 0 <= j < i}


--
Xavier Nicollin

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