[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: bison bug.

From: Hans Aberg
Subject: Re: bison bug.
Date: Sat, 29 Dec 2001 18:51:53 +0100

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
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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]