Skip to main content

A Bottom-Up Analysis Toolkit

John Gallagher, A Bottom-Up Analysis Toolkit. CSTR-95-016, Department of Computer Science, University of Bristol. July 1995. PDF, 200 Kbytes.


Bottom-up analysis has an elegant semantic basis, straightforward implementation, and flexible application. Several recent studies indicate good prospects for flexible and efficient analysis systems based on bottom-up core semantics. In addition, goal-directed or top-down analyses can be simulated through the use of query-answer transformations, of which the so-called ``magic set" method is one. These transformations can also serve to increase precision with respect to bottom-up analysis. A toolkit of bottom-up analysis tools and query-answer transformations has been built up, based on a number of experiments over three years. These tools and aspects of their implementation will be described. Efficient algorithms for bottom-up analysis are at the heart of the toolkit. A systematic method for implementing analyses using the tools is then set out. The method is based on (i) abstract compilation of a program into a ``domain program", (ii) computation of (an approximation to) the model of the domain program, and (iii) use of various query-answer transformations to simulate goal-directed analysis and improve precision. Stages (ii) and (iii) can also be used directly on the original program in some applications. If the domain program has a finite model, then a precise model can be computed in step (ii). If the model is infinite or very large, methods of approximation including regular approximation and others can be used. The question of precision and complexity of bottom-up and goal-directed analysis will also be discussed.

Bibtex entry.

Publication Admin