6 Nov 1998 16:29:48 -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: | 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.