Date of Award


Document Type

Honors Thesis


Computer Science

First Advisor

Tim Wahls




In this paper we present two novel abstract syntax tree (AST) indexing algorithms that solve the get-descendants-by-type problem in near constant time. This work has been implemented in the U.S. Department of Energy's ROSE compiler framework with plans to be officially integrated as an optimization library called "NodeFinder". ROSE is an open source software analysis platform and source-to-source compiler suited for large-scale C/C++, UPC, Java, Python, Fortran, OpenCL, CUDA, and OpenMP applications that has been actively developed at Lawrence Livermore National Laboratory for the last sixteen years. The get-descendants-by-type problem is the problem of efficiently answering queries of the form “given an arbitrary AST node and an arbitrary node type , return all descendants of that are of type ". Our algorithms are generic in that they can also be applied to any tree that has a meaningful notion of node "type", so we also explore some potential applications in the fields of file systems and databases.