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

Ziemowit Laski <>
6 Nov 1998 16:29:48 -0500

          From comp.compilers

Related articles
Re: Looking for Unambiguous Non-LR(k) Grammar (Ziemowit Laski) (1998-11-06)
Re: Looking for Unambiguous Non-LR(k) Grammar (Chris F Clark) (1998-11-07)
| List of all articles for this month |

From: Ziemowit Laski <>
Newsgroups: comp.compilers
Date: 6 Nov 1998 16:29:48 -0500
Organization: Compilers Central
References: <>
Keywords: parse, theory

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

Post a followup to this message

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