Incremental Graph Parsing
Carolyn L. McCreary, Susan S. Roth · 1994
A Program Dependence Graph is a useful representation of the dependencies within a code module, with the nodes representing code segments and the edges showing dependency constraints. Through this representation, inherent parallelism in the program structure can be exploited by various heuristics. This paper presents an incremental graph decomposition algorithm which parses the graph into a structure called a Parse Tree that aids in the analysis. The algorithm presented executes in O(n²) time.