EGG图文法语法分析算法的研究  

Research on Parsing Algorithm of EGG Graph Grammar

作　　者：朱云[1] 曾晓勤[1] 朱宁[1] 

机构地区：[1]河海大学计算机与信息学院,南京211100

出　　处：《计算机科学》2012年第10期272-277,293,共7页Computer Science

基　　金：国家自然基金(61170089)资助

摘　　要：EGG是一种基于边的上下文相关图文法形式化框架,其语法分析(归约操作)算法是该文法重要的组成部分。在简要介绍EGG的基础上,给出了EGG语法分析算法的设计,其中包括子图匹配算法、子图替换算法和算法计算复杂性的分析。为了展示如何用EGG来定义图语言,特别是如何用所设计的归约算法来分析图,文中以程序流程图为例,给出了相关的EGG形式定义以及对一个具体流程图的归约过程,并探讨了可能降低分析算法复杂性的一些途径。EGG is an edge-based 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 productions 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.

关 键 词：图文法 语法分析 子图匹配 子图替换 推导 归约 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]