Re: Kannapinn in a Nutshell

Carl Cerecke <cdc@maxnet.co.nz>
27 Apr 2003 02:02:37 -0400

          From comp.compilers

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)
[1 later articles]
| List of all articles for this month |

From: Carl Cerecke <cdc@maxnet.co.nz>
Newsgroups: comp.compilers
Date: 27 Apr 2003 02:02:37 -0400
Organization: TelstraClear
References: 03-04-075
Keywords: parse
Posted-Date: 27 Apr 2003 02:02:37 EDT

Joachim Durchholz wrote:
> Hi all,
>
> Since Sönke Kannapinn's parsing algorithm has caused some echo, here
> are the results of his doctoral thesis, in a nutshell.


Thanks! My German is not good enough to read a thesis.




> 3. CLR parsers are practical.
> They can be implemented with reasonable effort.
> Shifts work just as with normal LR parsers.
> On a reduction, the parser cannot simply read off the grammar rule from
> the state that it is in, so it will have to scan the stack downwards and
> see which grammar rule fits. (Since carrying out the actual reduction
> involved popping the same stack symbols that are being scanned, the
> overhead compared to classical LR parsing should be negligible.)


Surely reductions needn't be anymore complicated than normal. If I
understand it, the partial items (a delightfully obvious idea, but
only in retrospect) used in CLR are only used for the construction of
the parsing automata. The actual LR parsing algorithm is the same as
for LR/SLR/LALR and doesn't need the items (partial or full) that are
in each state. For a state that has a reduction, that reduction is
known. No scanning backwards down their stack is necessary. In fact,
I'm pretty sure that if the reduction wasn't known explicitly, and had
to be worked out from the stack, then conflicts would arise where more
than one reduction would match the information on the stack.


Cheers,
Carl.


Post a followup to this message

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