Re: DR Grammars

[Hans Aberg]

At 07:12 +1000 2001/07/04, Tim Josling wrote:
>I got a copy of the paper on DR grammars (Fortes) yesterday.

Is this an electronic copy? -- I have not yet been able to get hold of the
electronic copy that Carlos Borges has.

> His
>idea is to reuse some of the concepts of precendence grammers to
>make parse tables smaller.

Do you know if DR will take any LR(1) grammar?

>The basic idea of DR is that you start with the lookahead and
>walk down the stack until you have certainly about what to do.
>The parse tables tell you when to stop looking for the next
>action. Fortes claims that typically you only have to go 0,1,2,3
>levels into the stack so in practice the parser is fast. And the
>main benefit is that the tables are much smaller.
>
>However it is not just a different way of generating the bison
>tables - the parse code will have to be different. Error handling
>workks somewhat differently (you may find errors later than with
>LR(1)).

But the parsing is still fully deterministic, right?

>At this stage I tend to think that the best solution for the
>table size in LR(1) is just to put the entries into a hash table.
>This will be slower but should often be fast enough. Eg if you
>look at GCC the parse time is negligible as a percentage.

I think it is would be great to have both, if they are implemented as Bison
options and it is easy to switch between them. Then one can try them out in
actual cases to see if there is any performance benefits of the one over
the other.

The standard LR(1) algorithm could be implemented with table compression of
various degrees, so that one can accept larger tables if speed is crucial.

  Hans Aberg