Re: Bison development

[Hans Aberg]

At 10:27 +0100 2002/01/17, Akim Demaille wrote:
>Hans> So I think it is you, like the Spartans (according to
>Hans> Herodotus), that is trying to kill the messenger because you
>Hans> don't like the message. :-)
>
>Hm...  I understand what you mean here, and it might be the case
>indeed.

Of course, the Spartans realized how stupid this in view that it does not
change the reality and sought atonement from the gods, a wisdom that
admitted them to later defeating the Persians. -- If the idea is to
"defeat" the C++ issue.

>OK, if you want a project, then there is one thing we need: that
>someone find a good implementation of bit vector to implement sets.
>We need a good implementation, efficient and with a nice interface.
>There is a crucial need in Bison, but for the time being, unions,
>intersections etc. are computed but loops all over the place.  We need
>macros/routines that raise the abstraction level up to sets.

I usually use std::set (I am not myself an ABC programmer) which is using a
balanced tree implementation, and provides the best general type of
interface and time complexities. This cuts down on complexity, but on the
expense of the dynamic memory allocation time.

If your idea is to find a good set implementation using arrays, then you
need to analyze more carefully which types of operations you are going to
use. If you for example have one initial build phase, followed by a
terminal search phase, one solution might be to use two different
containers and copy over. Also, if you have a total order present, that
might be used to cut down time complexity -- it might be possible to
simulate the balanced tree approach by using binary search and heap sort
techniques and the like.

If the idea is to use this stuff in order to compute FIRST and FOLLOW, I
have studied that, but for my C++ implementation. One suggestion is to use
Tarjan's SCC (strongly connected component) algorithm, which is the most
efficient one possible (each vertex only visited once), but I do not know
if Bison is using that.

Hope this helps. -- It is not possible to be more specific with the data
you indicated.

  Hans Aberg