Re: parsing, was .NET Compiler for Interactive Fiction

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

Return to the comp.compilers page.
Search the comp.compilers archives again.