27 Apr 2003 02:03:36 -0400

Related articles |
---|

[6 earlier articles] |

Re: .NET Compiler for Interactive Fiction joachim_d@gmx.de (Joachim Durchholz) (2003-04-13) |

Re: parsing, was .NET Compiler for Interactive Fiction rpboland@math.uwaterloo.ca (Ralph P. Boland) (2003-04-15) |

Re: parsing, was .NET Compiler for Interactive Fiction cfc@TheWorld.com (Chris F Clark) (2003-04-15) |

Re: parsing, was .NET Compiler for Interactive Fiction joachim_d@gmx.de (Joachim Durchholz) (2003-04-20) |

Re: parsing, was .NET Compiler for Interactive Fiction bobduff@shell01.TheWorld.com (Robert A Duff) (2003-04-20) |

Re: parsing, was .NET Compiler for Interactive Fiction bobduff@shell01.TheWorld.com (Robert A Duff) (2003-04-27) |

Re: parsing, was .NET Compiler for Interactive Fiction rpboland@math.uwaterloo.ca (Ralph P. Boland) (2003-04-27) |

Re: parsing, was .NET Compiler for Interactive Fiction zivca@netvision.net.il (2003-04-27) |

Re: parsing, was .NET Compiler for Interactive Fiction joachim_d@gmx.de (Joachim Durchholz) (2003-04-27) |

From: | "Ralph P. Boland" <rpboland@math.uwaterloo.ca> |

Newsgroups: | comp.compilers |

Date: | 27 Apr 2003 02:03:36 -0400 |

Organization: | University of Waterloo |

References: | 03-02-125 03-02-147 03-03-043 03-03-061 03-03-103 03-04-006 03-04-028 03-04-046 03-04-064 |

Keywords: | parse |

Posted-Date: | 27 Apr 2003 02:03:36 EDT |

*>>DO YOU HAVE A REFERENCE TO KANNIPINN'S WORK?*

*>>I WOULD LIKE TO HAVE IT.*

*>*

*>*

*> I downloaded his thesis from the Internet; it's currently available at*

*> http://edocs.tu-berlin.de/diss/2001/kannapinn_soenke.htm .*

Thanks for the link. I think though in retrospect that I have heard

of his thesis before. I have asked him if he would be translating his

thesis into English or publishing any papers. Unfortunately is answer

is not soon. He works in industry now and get papers published is not

a high priority. :-( There is important material in his thesis that I

need to know but I can't count to one in German.

*> No problem.*

*> I'd just hope that you'll find the time to prove that your algorithm is*

*> more general than LR(k) parsing, either for k=1 or for any k.*

*> Also, saying that "number of states is larger but not catastrophically*

*> so" is handwaving. I'd want some more concrete estimates, such as "at*

*> most double the number of LR states for all LR grammars". Or "at most*

*> 35% more states than in the equivalent Tomita parser". (Less states*

*> would be preferrable, of course.)*

The algorithm builds an LR parser if the grammar is LR(1) so the same

number of states are required. Only if the grammar is not LR(1) are

"more states needed" to resolve the conflicts. The number of

additional states needed could explode exponentially (as it can for

LR(1) parsing) but I claim that in practice this won't happen for

practical grammars just like it doesn't for LR(1) parsers. However it

will take an implementation and a fair bit of examples to establish

this.

*> Anyway, the proof of the pudding is in the eating, so I'm looking*

*> forward to your implementation ;-)*

Unfortunately things like a job have to come first.

Thanks for the info.

Ralph

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.