Re: C++ symbol table (Paul Dietz)
Tue, 23 Feb 1993 18:31:17 GMT

          From comp.compilers

Related articles
C++ symbol table (Joydip Dass) (1993-02-19)
Re: C++ symbol table (1993-02-19)
Re: C++ symbol table chased@rbbb.Eng.Sun.COM (1993-02-19)
Re: C++ symbol table (1993-02-21)
Re: C++ symbol table (1993-02-23)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Paul Dietz)
Keywords: C++, parse
Organization: University of Rochester
References: 93-02-101 93-02-114
Date: Tue, 23 Feb 1993 18:31:17 GMT

chased@rbbb.Eng.Sun.COM (David Chase) writes:
> I don't have a complete answer, but I do have a suggestion. There was a
> nifty trick proposed by Paul Dietz in STOC '81, and it has been used with
> some success by several people that I know (in fact, it has been
> rediscovered with some success by several people, and we (= me, Wegman,
> Zadeck) used it in a different context to get good time bounds for a sort
> of incremental SSA. ...

The problem I was solving can be abstracted as follows. Let T be a tree
whose nodes are labelled with names drawn from some set N. Initially, the
tree consists of a single node with the null label. The tree is updated
by the operation AddLeaf(x,n), which creates a new leaf y with parent x
and label n, returning a pointer to y. The query FindAncestor(x,n) finds
the deepest ancestor of x with label n (possibly x itself), or null if no
such ancestor exists.

This gets solved as follows. We store the nodes of the tree in a list, in
preorder. Each label occuring in the tree decomposes the tree into
connected subgraphs on which the FindAncestor queries for that label
return the same answer. These subgraphs induce a decomposition on the
preorder list. One can easily show that if a particular label occurs k
times, it induces a partition of the preorder list into at most 2k+1
sublists. We can represent this decomposition by storing the first
element of each of the sublists in a binary search tree, where the
comparison operation is "does this node occur before this node in the

It turns out one can implement insertions, deletions and these order
queries in a list in constant time per operation (the STOC 81 paper was
foolishly off by log* n; Tarjan and also Tsakalidis pointed out a trick to
get linear amortized time, and Dietz and Sleator (STOC 87) showed how to
do it in constant single operation time; we also gave a simpler amortized
constant time algorithm, using an idea related to one obtained by
Leiserson). This lets one do operations on the trees in O(log k) time,
where k is the number of times the label appears in the tree.

I later shows (WADS 89) how to do all these operations in O(loglogn)
amortized time per operation (on a RAM). This algorithm is completely
impractical, however.

Related to all this is work on so-called "fully persistent data
structures"; see Driscoll, Sarnak, Sleator and Tarjan (JCSS 89), as well
as algorithms for maintaining sorted arrays with density > some positive
constant in O(log^2 n) time per insertion.

(Dave: I'd love to see some references to people using this stuff.)

Paul F. Dietz

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.