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

Ziemowit Laski <laski@ics.uci.edu>
6 Nov 1998 16:29:48 -0500

          From comp.compilers

Related articles
Re: Looking for Unambiguous Non-LR(k) Grammar laski@ics.uci.edu (Ziemowit Laski) (1998-11-06)
Re: Looking for Unambiguous Non-LR(k) Grammar cfc@world.std.com (Chris F Clark) (1998-11-07)
| List of all articles for this month |

From: Ziemowit Laski <laski@ics.uci.edu>
Newsgroups: comp.compilers
Date: 6 Nov 1998 16:29:48 -0500
Organization: Compilers Central
References: <Pine.BSI.3.91.981030111345.22214J-100000@ivan.iecc.com>
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.