14 Sep 2002 16:18:05 -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) |

Re: LR Grammars not in LALR(1) or LR(1) thp@cs.ucr.edu (2002-09-20) |

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

Re: LR Grammars not in LALR(1) or LR(1) thp@cs.ucr.edu (2002-09-25) |

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

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

[8 later articles] |

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

Newsgroups: | comp.compilers |

Date: | 14 Sep 2002 16:18:05 -0400 |

Organization: | Mathematics |

References: | 02-09-014 02-09-029 02-09-068 02-09-092 |

Keywords: | LR(1), parse |

Posted-Date: | 14 Sep 2002 16:18:05 EDT |

"=?Windows-1252?Q?S=F6nke_Kannapinn?=" <soenke.kannapinn@wincor-nixdorf.com> wrote:

*>"Hans Aberg" wrote:*

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

*>That's wrong! (Hope it's not wrong in that book!)*

*>It mixes up the concepts of 'language' and 'grammar'.*

*>The class of LR(k) languages (!) is identical to the class of*

*>LR(1) languages (!), for k >= 1.*

*>But not every LR(k) grammar is also an LR(1) grammar.*

Sorry, I was sloppy in the use of the terminology. It should (of course) be:

but I have an old book by Robin Hunter, "Compilers...", which says

on page 103 that LR(k) languages are LR(1) languages, 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.

A language L is called LR(k) if there exists a grammar G which is

LR(k) which generates the language L, i.e. L = L(G). This is a

non-constructive set theoretic definition, which causes problems when

one takes a language L and want by an algorithm to determine whether

it is LR(k) for some k: There is no such algorithm.

It is also a problem when trying to rewrite a language from LR(k) to

LR(1) because the rewriting may not be useful with respect to the

semantics. Then that shows up in error recovery problems.

This is why GLR compilers may be suitable when studying error recovery

problem in LR(k) grammars, despite the existence of such _language_

rewriting theorems.

This reminds me that Susan L. Graham <graham@cs.berkeley.edu> who works

with error recovery in GLR parsers recently sent me a paper by Tim A.

Wagner and herself, "Incremental Analysis of Real Programming Languages".

-- Perhaps this can give some inputs to the original poster.

Also, the Bison manual <http://gnu.org>, sec. 5.7, "Mysterious

Reduce/Reduce Conflicts" has an example of a grammar which is not LALR(1).

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.