|Re: Looking for Unambiguous Non-LR(k) Grammar email@example.com (Ziemowit Laski) (1998-11-06)|
|Re: Looking for Unambiguous Non-LR(k) Grammar firstname.lastname@example.org (Chris F Clark) (1998-11-07)|
|From:||Ziemowit Laski <email@example.com>|
|Date:||6 Nov 1998 16:29:48 -0500|
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.
Return to the
Search the comp.compilers archives again.