Abstract: 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.

Key words: Graph grammar,Parsing,Subgraph matching,Subgraph substitution,Derivation,Reduction