Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken. (German) Zbl 0587.68076

Fachbereich für Mathematik und Informatik der Universität Passau. 242 S. (1985).
In this thesis precedence parsers for graphs are described. First an appropriate class of context-free graph grammars and precedence relations are introduced. The membership problem for this class is PSAPCE-complete, for confluent graph grammars with disjoint precedence relations and uniquely invertible productions decidable in \(O(n^ 2)\) time, n being the number of nodes of the input graph. Members of this class are called precedence graph grammars, for short PGG’s. Several properties of PGG’s, e.g. unambiguity up to symmetry, are shown. PGG’s are decidable. But it is not decidable, whether there exist an equivalent PGG for a given graph grammar. Precedence graph languages are described in a graph theoretic and in an information theoretic manner. Precedence relations are described without reference to special embedding relations and thus can be used for all context-free graph grammars. Rutishauser’s bracket mountains are generalized to graphs. Legal bracketings of graphs can be recognized efficiently.
The graph parsers are given by simple abstract models supporting correctness proofs. Three graph parsers differing by their error handling are compared. Time resources are restricted by \(O(n^ 2)\), \(O(n^ 3)\) respectively.
The implementation with adjacency lists is given for an abstract computing device. By stepwise refinement Pascal-programs are derived, which have been implemented on a real computer. PGG’s are applied to series-parallel-networks, Petri-nets, well-structured flowgraphs and data structures. A control flow model for PROLOG-programs is derived. Several interesting graph classes are compactly described by PGG’s, including graph theoretically characterizable graph classes.


68N20 Theory of compilers and interpreters
68Q45 Formal languages and automata
68R10 Graph theory (including graph drawing) in computer science