Tue, 23 Feb 1993 18:31:17 GMT

Related articles |
---|

C++ symbol table jdass@cssc-melb.tansu.com.au (Joydip Dass) (1993-02-19) |

Re: C++ symbol table preston@dawn.cs.rice.edu (1993-02-19) |

Re: C++ symbol table chased@rbbb.Eng.Sun.COM (1993-02-19) |

Re: C++ symbol table tony@cs.colorado.edu (1993-02-21) |

Re: C++ symbol table dietz@cs.rochester.edu (1993-02-23) |

Newsgroups: | comp.compilers |

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

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.