Re: parsing, was .NET Compiler for Interactive Fiction

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.

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