Graph grammars and global program data flow analysis

Abstract

Program structure is defined in terms of a simple graph grammar, the "semi-structured flow graph grammar," which admits many of the control structure extensions suggested for "structured programming." The grammar defines a set of graph reductions which are shown to have the "Finite Church-Rosser (FCR)" property; i.e., when applied in any order to a graph, the limit (when no further reductions are possible) is unique. In particular, if a given graph is generated by the grammar, repeated application of the reductions will result in a single node regardless of the order in which they are applied. This property gives rise to an algorithm that parses a given program flow graph in time linear in the size of the graph. The resulting parse is used in a global data flow analysis algorithm which requires a number of bit-vector steps which is also linear in the size of the given graph.