Re: Bison development

[Hans Aberg]

At 16:06 +0100 2002/01/17, Hans Aberg wrote:
>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.

I think that if this algorithm is used, then one only has a series of
unions, and the quickest way to do that is to merely append the set
members, and then remove duplicates by a heap sort type of algorithm
afterwards.

In the case of Bison though, I think that you have bit vectors with the
bits telling set membership, so that the C bit-or can be used. This is
probably faster, but I think the complexities are the same (probably O(n
log n), n = #terminals + #nonterminals, for the whole algorithm).

  Hans Aberg