Re: bison bug.

[Hans Aberg]

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

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

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

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

  Hans Aberg