A class of linearly parsable graph grammars |
| |
Authors: | Reinhold Franck |
| |
Affiliation: | (1) SOFTLAB GmbH, Arabellastr. 13, D-8000 München 81, Germany (Fed. Rep.) |
| |
Abstract: | Summary Specializing an existing graph grammar model we look in detail at node context-free graph grammars. With a slight generalization the parse trees for context-free Chomsky grammars can be used to describe derivations of these graph grammars.As shown already in former works the precedence graph grammars are defined as a subclass of context-free graph grammars by certain algebraic restrictions on the form of the rules. Then we can prove that every precedence grammar is unambiguous and additionally the reduction process in such a grammar read as replacement system is finite.The most important aim in defining the predence relations was a simple parsing method. This is realized because it is shown that the syntactic analysis for precedence graph grammars can be done in a time which linearly depends on the size of the input graph.The whole method has been implemented and a documentation is available. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|