Biblio

Context-sensitive graph grammars have been rigorous formalisms for specifying visual programming languages, as they possess sufficient expressive powers and intuitive forms. Efficient parsing mechanisms are essential to these formalisms. However, the existent parsing algorithms are either inefficient or confined to a minority of graph grammars. This paper introduces the notion of partial precedence, defines the partial precedence graph of a graph grammar and theoretically unveils the existence of a valid parsing path conforming to the topological orderings of the partial precedence graph. Then, it provides algorithms for computing the partial precedence graph and presents an approach to improving general parsing algorithms with the graph based on the drawn conclusion. It is shown that the approach can considerably improve the efficiency of general parsing algorithms.