Re: C++ symbol table

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
list?"


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
dietz@cs.rochester.edu
--

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