Re: bison bug.

[Akim Demaille]

>>>>> "Hans" == Hans Aberg <address@hidden> writes:

Hans> At 07:57 -0800 2001/12/21, James Harris wrote:
>> The attached archive has a gammer "foo.y" that will breaks bison.
>> 
>> The error is reported by assertion "found" failed: file "lalr.c",
>> line 484

Hans> One thing one should note is that already for regular
Hans> expressions, the NFA
-> DFA translation sometimes produces exponential results. See, for
Hans> example, Aho et al., "Compilers...", sec. 3.7, where it is said
Hans> that (a|b)*a(a|b)^(n-1) requires a DFA of at least 2^n states.

This is a well known result, but it fortunately does not apply to
Bison.  First of all, the concept of NFA and DFA does not apply
exactly the same way (one needs to stretch the concept of NFA quite a
lot to consider an LR(0) automaton is one), and most importantly, the
nature of a real world grammar makes it near impossible to fall into
the exponential case.

Hans> The reported bug causes overflow in the NFSM -> DFSM
Hans> translation, and it is probably possible to do the same thing
Hans> here (I do not know if the DFSM of the grammar above also
Hans> requires 2^n states). It would mean that relatively small
Hans> grammars can always overflow the number of states.

I'm sure someone can come up with one such grammar, indeed.  But Bison
is dedicated to real world problems.

Hans> So the question is then also whether this grammar you have is
Hans> important in the regular Bison use. It may happen that you
Hans> should concentrate on a NFSM parser, instead of a DFSM one.

Which means, in other words, don't use Bison.  Bison is dedicated to
producing O(n) parsers, hence without backtracking.  It addresses
LALR(1) grammar as well as one can do.  If you grammar does not lie
into LALR(1), don't use bison.