8 Sep 2002 22:31:53 -0400

Related articles |
---|

LR Grammars not in LALR(1) or LR(1) tbandrow@unitedsoftworks.com (tj bandrowsky) (2002-09-03) |

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

Re: LR Grammars not in LALR(1) or LR(1) idbaxter@semdesigns.com (Ira Baxter) (2002-09-08) |

Re: LR Grammars not in LALR(1) or LR(1) tbandrow@unitedsoftworks.com (tj bandrowsky) (2002-09-12) |

Re: LR Grammars not in LALR(1) or LR(1) tbandrow@unitedsoftworks.com (tj bandrowsky) (2002-09-12) |

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

Re: LR Grammars not in LALR(1) or LR(1) soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2002-09-14) |

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

[14 later articles] |

From: | "Hans Aberg" <haberg@matematik.su.se> |

Newsgroups: | comp.compilers |

Date: | 8 Sep 2002 22:31:53 -0400 |

Organization: | Mathematics |

References: | 02-09-014 |

Keywords: | parse |

Posted-Date: | 08 Sep 2002 22:31:53 EDT |

"tj bandrowsky" <tbandrow@unitedsoftworks.com> wrote:

*>Are there examples of grammars that are GLR but not LR(1) or LALR(1)?*

I do not know the definition of GLR, but I have an old book by Robin

Hunter, "Compilers...", which says on page 103 that LR(k) grammars are

LR(1) grammars, and even LR(0) if each sentence is given an

end-marker, citing a paper by Hopcroft and Ullman, "Introduction to

Automata Theory, Languages and Computation" 1979.

It also says, p. 105, that for each fixed k, it is decidable whether a

grammar is LR(k), but undecidable for a given grammar if there is a k such

that it is LR(k).

These grammar rewritings are just syntactic in the sense that if one

attaches semantics to the language, the rewriting may screw that up, at

least from the practical point of view. Therefore these theoretically

possible grammar rewritings have not been of much practical use.

Hans Aberg * Anti-spam: remove "remove." from email address.

* Email: Hans Aberg <remove.haberg@member.ams.org>

* Home Page: <http://www.matematik.su.se/~haberg/>

* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.