This paper concerns a method for approximating the possible "shapes" that heap-allocated structures in a program can take on. We present a new approach to finding solutions to shape-analysis problems that involves formulating them as generalized graph-reachability problems. The reachability problem that arises is not an ordinary reachability problem (e.g., transitive closure), but one in which a path is considered to connect two vertices only if the concatenation of the labels on the edges of the path is a word in a certain context-free language. This graph-reachability approach allows us to give polynomial bounds on the running time of an algorithm for shape analysis. It also permits us to obtain a demand algorithm for shape analysis. (In a demand algorithm, the goal is to determine shape information selectively --- i.e., for particular variables at particular points in the program, rather than for every variable at every point in the program.)

(Click here to access the paper: PostScript, PDF.)