摘要
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.
出处
《计算机科学》
CSCD
北大核心
2012年第10期272-277,293,共7页
Computer Science
基金
国家自然基金(61170089)资助
关键词
图文法
语法分析
子图匹配
子图替换
推导
归约
Graph grammar
Parsing
Subgraph matching
Subgraph substitution
Derivation
Reduction
