Static Analysis of Recursive Data Structures

• Main Authors: Arvind And Lewis, D. K. Arvind, T. A. Lewis
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: Springer-Verlag 1998
• Subjects: The Pointers
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.489; http://www.dcs.ed.ac.uk/~tl/lcpc97/doc.ps

. The static analysis of imperative languages is made difficult by the unrestricted pointer structures which makes their analysis imprecise. A static analysis approach is proposed for a class of graph structures, where the regularity is described by the programmer via a Markov algorithm. The method is illustrated with an example. 1 Motivation The static analysis of programs involving arrays with a view towards their automatic parallelisation has been studied in [2]. In contrast, the static analysis of pointer-based data structures is relatively more complicated. These structures can be viewed as a graph of values, with no restrictions placed on which values the pointers point to. In practice, they may often resemble trees or lists, but there is no requirement for them to conform to these structures. Consequently, any analysis cannot make such assumptions, unless the properties of the structures can be derived during the analysis of the code. The approach adopted here is for the p.