Re: Kannapinn in a Nutshell

Hello.


> I found Kannapinn's thesis extremely well-written and easily
> understandable. I have never done any serious parsing theory beyond
> the Dragon book (and the Johnstone/??? paper on Tomita-style parsing),
> and I found even the theoretic parts of the thesis readable. It was
> even easy to trace which pieces of theory were relevant for which
> piece of practical advice, something that's often woefully absent in
> theoretic papers (if they dwell on practice at all).


Thank you for the compliments and for trying to present a "nutshell
version" of my thesis. While gives an impression of what readers will
find in the paper, I'm not completely happy with your selection of the
most important points regarding your sections 1--4 because you left
out results that I find even more important than the ones you
presented.


Especially, the thesis proves that, for a given grammar, there exists
a lattice structure of infinitely many LR(k) parsers which all "behave
like" the well known Knuth-style canonical LR(k) parser. In the
English abstract of my thesis (which I encourage comp.compilers
participants with a "parsing affinity" to read; see the link below) I
call all these parsers "general LR(k) parsers". (Note that Tomita's
GLR parsers are a completely different sort or generalization.) The
"minimal LR(k) parser" in this lattice can effectively be computed by
applying a minimization algorithm from automata theory. The canonical
LR(k) parser and the (what you called) CLR(k) parser are merely
special cases having important special properties that can be (and for
the canonical case: are) used to simplify the implementation of the
parser's actions. Notably, the amount of information available in the
stacked parser states differs as follows:


* _all_ general LR(k) parsers (if deterministic) have enough
    information available at their states such that the stacked
    states and grammar symbols "touched" by the parser actions
    always allow to determine which (shift or reduce) action is to
    be applied. (Reduce actions "touch" _all_ topmost stack states
    and grammar symbols that correspond to the handle plus the
    k-lookahead; shift actions "touch" only the topmost state plus
    the k-lookahead.)
* _canonical_ LR(k) parsers, as a special case, know what action
    to perform from inspecting merely the topmost stack state,
    which makes implementation easy. (In other words, the formal
    canonical LR(k) parser - as opposed to it's usual
    implementation - contains a lot of redundant information in
    its states.)
* CLR(k) parsers know, from looking at the topmost stack state,
    _whether_ a shift, or a reduce action is applicable, but still
    have to inspect more stack context to find out _which_ reduce
    action is to be applied.


I would like to point the reader's attention to the didactical worth
of the LR-related results in the thesis: It clearly distills what
parts of the classical Knuth-style item set construction is actually
needed in order to contruct formally correct LR parsers, and which
parts are serving implementation purposes.


I have more comments on your "nutshell version", but do not have more
time to elaborate.


In a recent post to comp.compilers ("Re: parsing, was: .NET compiler
for interactive fiction"), Ralph P. Boland wrote w.r.t. my thesis:


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


I hope to get first work for a journal publication of my thesis
done this summer, results concerning "general LR(k) parsers"
being the first on the agenda. But this is work I'm not payed
for. I encourage those of you who can't wait and don't speak
German to look into the thesis anyway:
* it has an English abstract,
* its formal style is very close to the style of Sippu/Soisalon-
    Soininen's two-volume "Parsing Theory" book, which is in
    English and should be available at your home university's
    library. (If it's not, complain loudly! This is today's
    Aho/Ullman!)
* it contains a series of diagrams that, together with the
    examples from the text, should still be useful for readers who
    know Sippu/Soisalon-Soininen's book, especially because the
    main example I used to illustrate the theoretic results is
    exactly the one used in Sippu/Soisalon-Soininen's chapter on
    LR parsing.
* you can improve your German ;-)


> 6. LR parsing for extended CFGs (ECFG)
> [...]
> Ironically, a detail in this part
> of the thesis seems to be in error... the difference being that the
> error is inconsequential for the statements made in the thesis ;-)


Joachim, can you point me to what you believe to be erroneous? (Post
it to comp.compilers if you feel that others should profit.)


Regards,
Sönke


--
Dr. Sönke Kannapinn
String.concat[ "soenke", ".", "kannapinn", "@", "wincor-nixdorf", ".", "com" ]

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