Re: Looking for Unambiguous Non-LR(k) Grammar

Sorry for not replying earlier -- some rather nasty administrative
matters got in the way... :(


John R Levine wrote:


> > Can anyone think of a context-free grammar that is unambiguous, and yet
> > not part of LR(k)?
>
> Sure. Let C be an LR(k) C grammar, and P be an LR(k) Pascal grammar (or
> any other two languages you want):
>
> program:: C "C"
> | P "Pascal"
>
> It's not hard to construct grammars that are unambiguous but can't be
> resolved with any fixed lookahead.


Why isn't this grammar in LR(k)? If C is LR(k) and P is LR(k), then
program is LR(k) too, unless FIRST(C) and FIRST(P) are not disjoint,
in which case program is LR(k + n) for some finite n.


I think a context-free grammar that is unambiguous but not LR(k) would
be one where I would absolutely need to apply a derivation that is NOT
rightmost at some point in a derivation of a sentence. But why would
I have such a restriction? If I did, it seems I would no longer be
dealing with a context-free grammar.


Thank you,


Zem Laski

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