Pair grammars, graph languages and string-to-graph translations

摘要

Translation between string and graph representations of programs and data may be formally defined by means of pair grammars. A pair grammar is composed of a pair of grammars whose rules and nonterminals are paired. The pair grammar defines a correspondence between elements of the languages defined by the two grammars. This correspondence may be viewed as a definition of the translation of the elements of one language into the elements of the other. Of particular interest is the case in which the first language is a set of strings and the second is a set of directed graphs with labeled arcs and nodes.Preliminary to the definition of pair grammars, a class of graph grammars are defined which are a generalization of ordinary context-free grammars. A graph grammar defines a language composed of a set of directed graphs. Pair grammars are constructed from pairs of graph grammars. Each unambiguous pair grammar defines a reversible function mapping one graph language onto another. Special cases of interest include string-to-graph, graph-to-string, and string-to-string mappings. In the general case a pair grammar defines a transformation on a set of graphs.Two extensions to the elementary pair grammars allow representation of hierarchies of graphs and constructs such as labels and go to statements. Examples are given of the translation of a major subset of Algol into flowchart graphs and the translation of Lisp S-expressions into list structure graphs with structured atoms.