6 May 2003 01:02:23 -0400

Related articles |
---|

Kannapinn in a Nutshell joachim_d@gmx.de (Joachim Durchholz) (2003-04-20) |

Re: Kannapinn in a Nutshell cdc@maxnet.co.nz (Carl Cerecke) (2003-04-27) |

Re: Kannapinn in a Nutshell joachim_d@gmx.de (Joachim Durchholz) (2003-04-27) |

Re: Kannapinn in a Nutshell soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-06) |

Re: Kannapinn in a Nutshell cfc@world.std.com (Chris F Clark) (2003-05-06) |

Re: Kannapinn in a Nutshell cdc@maxnet.co.nz (Carl Cerecke) (2003-05-13) |

Re: Kannapinn in a Nutshell soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-14) |

Re: Kannapinn in a Nutshell soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-16) |

Re: Kannapinn in a Nutshell joachim.durchholz@web.de (Joachim Durchholz) (2003-06-20) |

From: | =?Windows-1252?Q?S=F6nke_Kannapinn?= <soenke.kannapinn@wincor-nixdorf.com> |

Newsgroups: | comp.compilers |

Date: | 6 May 2003 01:02:23 -0400 |

Organization: | Siemens Business Services |

References: | 03-04-075 |

Keywords: | parse |

Posted-Date: | 06 May 2003 01:02:23 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.