[Top][All Lists]

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

Re: Bison development

From: Hans Aberg
Subject: Re: Bison development
Date: Thu, 17 Jan 2002 18:15:22 +0100

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

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

reply via email to

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