Re: parsing, was .NET Compiler for Interactive Fiction

"Ralph P. Boland" <rpboland@math.uwaterloo.ca>
27 Apr 2003 02:03:36 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.