Re: Kannapinn in a Nutshell

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.

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