An algorithm for parsing a graph grammar
Carolyn L. McCreary · 1987
A dependency graph is an acyclic, directed graph with the transitive property. A graph-grammar describes the process of building a dependency graph from a simpler dependency graph. A derivation step replaces a mother node with a daughter dependency graph and connects each node of the daughter graph to nodes adjacent to the mother node. The algorithm described in this paper, takes an arbitrary dependency graph and shows the derivation steps used by the graph-grammar to derive the graph, i.e. the algorithm parses the graph. With a worst-case time complexity of O(n$\sp 3$), the algorithm describes each factor as primitive, linear, or independent and thus describes the graph's structure. The algorithm generates the factors in a bottom-up manner that facilitates the construction of the parse tree. The significance of this paper is that it describes a graph-grammar for which there exists a good parsing algorithm. Just as regular string grammars and context-free string grammars have little practical importance, the general theory of graph-grammars has had little practical application. LR string grammars, on the other hand have proven useful in the development of programming languages simply because they are parsable. As a result of an algorithm such as the one described in this paper, dependency graphs may prove to be the workhorse of graph-grammars. Another significance of the algorithm is that it is the first application of a very powerful set representation called a semi-independent boolean algebra, a construct discovered by A. Ehrenfeucht and G. Rosenberg. Ehrenfeucht and Rosenberg proved that a for a set of size n, a family of subsets with certain properties can be represented by a tree with n leaves. This represents a tremendous data reduction capability considering that there are potentially 2$\sp{\rm n}$ sets in the family. It turns out that the factors of the parse tree for the dependency graph have the properties of a semi-independent boolean algebra.