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

摘要：

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

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

所属期刊栏目：39

分类号：TP391(计算技术、计算机技术)

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

在线出版日期：2013-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：272-277,293