18 Oct 2002 23:29:22 -0400

Related articles |
---|

[12 earlier articles] |

Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-09-29) |

Re: LR Grammars not in LALR(1) or LR(1) haberg@matematik.su.se (Hans Aberg) (2002-09-29) |

Re: LR Grammars not in LALR(1) or LR(1) joachim_d@gmx.de (Joachim Durchholz) (2002-09-29) |

Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (Clint Olsen) (2002-10-13) |

Re: LR Grammars not in LALR(1) or LR(1) cfc@shell01.TheWorld.com (Chris F Clark) (2002-10-13) |

Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-10-13) |

Re: LR Grammars not in LALR(1) or LR(1) ska1@snafu.de (Sönke Kannapinn) (2002-10-18) |

Re: LR Grammars not in LALR(1) or LR(1) joachim_d@gmx.de (Joachim Durchholz) (2002-10-20) |

Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (Clint Olsen) (2002-10-24) |

Re: LR Grammars not in LALR(1) or LR(1) ska1@snafu.de (Sönke Kannapinn) (2002-10-25) |

From: | "Sönke Kannapinn" <ska1@snafu.de> |

Newsgroups: | comp.compilers |

Date: | 18 Oct 2002 23:29:22 -0400 |

Organization: | [Posted via] Inter.net Germany GmbH |

References: | 02-09-014 02-09-029 02-09-068 02-09-092 02-09-097 02-09-126 02-09-130 02-09-143 02-10-015 |

Keywords: | parse |

Posted-Date: | 18 Oct 2002 23:29:22 EDT |

Chris F Clark writes:

*> 1) Any deterministic context-free language (DCFL) (that is a language*

*> that has at least one deterministic context free grammar (DCFG))*

*> has an LR(1) grammar.*

*>*

*> ...*

*>*

*> 3) Not every DCFL has an LALR(1) grammar.*

*>*

*> ...*

*>*

*> From what I understand of the theory, I believe points 2 & 3 are*

*> potential killers. Essentially I think they point to the existence of*

*> pathological grammars that are ambiguous but which have a*

*> deterministic (unambiguous) parse and for which it is not possible to*

*> algorithmically find the corresponding LALR grammar (if there even is*

*> one).*

Just a minor correction concerning 3):

For k >= 0, any cfg G can be transformed into a structurally equivalent

cfg which is SLR(k) if and only if G is LR(k).

Therefore, for any fixed k >= 0, the families of LR(k) languages,

LALR(k) languages, and SLR(k) languages are all equal.

See Theorem 6.70 in chapter 6.6 of

Seppo Sippu and Eljas Soisalon-Soininen:

Parsing Theory. Vol.II: LR(k) and LL(k) Parsing

EATCS Monographs on Theoretical Computer Science

Springer-Verlag, 1990

which also contains a detailed proof (using the concept of a cfg

T_k(G) that right-to-right covers a cfg G).

Put another way, every DCFL has an LR(1), an LALR(1) and even an SLR(1)

grammar.

Regards,

Soenke.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.