Re: Performance impact of "redundant" rules

[Hans Aberg]

On 15 Mar 2006, at 01:24, Sylvain Schmitz wrote:

> > So, as for LR(1), I guess for typical grammars there will be a  
> > blow- up a couple of times of the number of states.  If there is a  
> > problem with exponential blowups, one might perhaps try the same  
> > approach, make a grammar to non-deterministic automata  
> > translation, with a runtime component computing the final  
> > deterministic push-down automaton states at need, caching them.
>
> I have never seen this kind of implementations either.  I can see  
> one reason for that: when we construct the deterministic handle  
> finding automaton, we also get information on whether the LR parser  
> is deterministic or not, and on where the conflicts are.
>
>   One could perhaps use a LR(1) testing algorithm, which is  
> supposed to be much less costly than the complete parser  
> generation, to check whether the determinization will work or not--- 
> I don't know enough about these tests to tell whether they also  
> give you where the conflicts occur---

This would anyhow be a later stage, after a traditional LR(1)  
implementation has been put into Bison as an option for awhile. I  
just mention the possibility, as it opens up for interesting hybrids,  
perhaps in connection with GLR, which uses a different method for  
handling non-deterministic parsing.

> and do the NFA to DFA translation on parsing time like you suggest.

It is dangerous to use the wording "NFA" and DFA" here, as it is push- 
down automatons using a stack.

>   A second reason is simply that, for purely parsing purposes--- 
> that is, ignoring the advantages you already mentioned, like  
> correct prefix + lookahead---, we do not need the full-blown LR(1)  
> automaton; its compressed form works just fine; even the weaker LALR 
> (1) parser is good enough in most cases.  The space constrains  
> experienced in the days where LR parsing was invented did not leave  
> much choice on the matter.
>
> > As for Bison, I think it should at some point in the future have a  
> > LR(1)
> > feature, so that one at least can experiment with it.
>
> Indeed, you now have the choice.

This is the one major reason for putting it in: these days even  
personal computers do not have space problems having it. So starting  
to use it, will give inputs of its usability.

  Hans Aberg