Research on Parsing Algorithm of EGG Graph Grammar
EGG图文法语法分析算法的研究

EGG is an edgcbased context sensitive graph grammar formalism, in which the parsing (reduction operation)algorithm is a very important part. On the basis of a brief introduction of EGG, this paper presented the design of a parsing algorithm, which includes subgraph matching algorithm, subgraph substitution algorithm, and their computational complexity analyses. In order to show how to apply EGG to define graph languages and especially parse graphs with the designed algorithms, the paper taking program flow diagram as an example, presented its formal definition of producdons and its parsing procedures for a given flow diagram. As the future research directions, the possible ways to reduce the complexity of the algorithms were also discussed.