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

Zem Laski wrote (quoting others):
> > > 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"
> 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.


Actually, the "program" grammar may or may not be LR(k) depending on
the two grammars being merged. The question comes down to whether
there is some text that is both legal to the C and P parts of the
grammar that needs reduction and where only infinite lookahead will
determine which of the two reductions to apply.


An example of that is:


C: C1 C2
C1: "x"
C2: C2 "y" | "y"
P: P1 P2
P1: "x"
P2: P2 "y" | "y"


This problem grammar is not LR(k) for any finite k, since you can have
k y's after the x and before the C or Pascal which tells whether to
reduce the x to a C1 or a P1. The grammar is not ambiguous because
any complete sentence has only one parse (and it belongs to the simple
classes of RR(1) and RL(1), the right-to-left versions of LL and LR).


> 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.


I believe the problem grammar at some point has a non-rightmost
derivation (the derivation step which expands C1|P1 depending on what
the last token is).


The only requirement for a grammar to be context free is that it have
only one non-terminal on the LHS.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : cfc@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres

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