%0 Journal Article
%T Research on Parsing Algorithm of EGG Graph Grammar<br>EGG图文法语法分析算法的研究
%A ZHU Yun
%A ZENG Xiao-qin
%A ZHU Ning
%A <br>朱云
%A 曾晓勤
%A 朱宁
%J 计算机科学
%D 2012
%I 
%X 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.
%K Graph grammar
%K Parsing
%K Subgraph matching
%K Subgraph substitution
%K Derivation
%K Reduction<br>图文法
%K 语法分析
%K 子图匹配
%K 子图替换
%K 推导
%K 归约
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=A97816070393C0265C2B5BFDAF2249E8&yid=99E9153A83D4CB11&vid=7C3A4C1EE6A45749&iid=F3090AE9B60B7ED1&sid=4E6F5C60B72D9B1C&eid=CAA7BAE04CB631A1&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=0