Re: parsing, was .NET Compiler for Interactive Fiction

Joachim Durchholz <joachim_d@gmx.de>
20 Apr 2003 17:15:08 -0400

          From comp.compilers

Related articles
[3 earlier articles]
Re: .NET Compiler for Interactive Fiction david.cornelson@iflibrary.com (David A. Cornelson) (2003-03-14)
Re: .NET Compiler for Interactive Fiction tbandrow@unitedsoftworks.com (2003-03-16)
Re: .NET Compiler for Interactive Fiction JeffKenton@attbi.com (Jeff Kenton) (2003-04-05)
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: Joachim Durchholz <joachim_d@gmx.de>
Newsgroups: comp.compilers
Date: 20 Apr 2003 17:15:08 -0400
Organization: Compilers Central
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
Keywords: parse
Posted-Date: 20 Apr 2003 17:15:08 EDT

Ralph P. Boland wrote:
> Joachim Durchholz wrote:
>>
>>Well, Kannapinn's recent work is still a noticeable improvement in LR
>>parsing, so there *is* progress in this area. But I agree that things
>>have come to a near-standstill, problems are either solved or
>>known/assumed to be unsolvable. Research has moved on to other topics.
>
> 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 .


The thesis covers two areas: 1. A variant of LALR parsing that creates a
minimal set of states; this is achieved by encoding slightly different
information in each state; 2. how to adapt the parser to allow regular
expressions on the right side of productions, including a proof that the
parser accepts the expected language.


His ideas about state generation seem to be applicable to all forms of
LR parsing, so they might also benefit your work.


The downside: it's in German. No English translation is available on the
Web, at least none that Google knows about :-(


> My algorithm is clearly much more powerful than LR parsing and (I
> claim) more powerful than the various extensions to LR parsing in the
> literature.
  > [...]
  > (Kannapinn's excepted since I am unfamiliar with it as
> far as I know


Kannapinn's algorithm lies between LR(k) and LALR(k), for any given k.


  > and GLR excepted which can handle all CFGs but doesn't
> build a full parser in advance)


AFAIK Tomita-style parsers use a table-driven approach.


> Doubters may at least verify that I am a postdoc in the school of
> computer science at the univerity of Waterloo, Canada. This doesn't
> prove my claim of course, but it supports that I make it seriously.


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


Anyway, the proof of the pudding is in the eating, so I'm looking
forward to your implementation ;-)
(Look at Chris Clark's post to look up traps to avoid and things nice to
have.)


Regards,
Jo
--
Currently looking for a new job.


Post a followup to this message

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