7 Nov 1998 01:29:14 -0500

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

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 7 Nov 1998 01:29:14 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | <Pine.BSI.3.91.981030111345.22214J-100000@ivan.iecc.com> 98-11-044 |

Keywords: | parse |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.