一种基于边的上下文相关图文法形式化框架

摘要

形式语言理论对计算机科学的发展起了重大的作用，作为对传统字符文法扩展的图文法的形式化研究，其重要意义是不言而喻的。图文法研究中最主要的几个问题包括：嵌入问题的解决、文法类型的划分、成员问题的判定和语法分析计算复杂性的降低。过去几十年中已经有一些图文法形式化方法及图文法应用方面的成果问世，但它们大多是基于上下文无关图文法的。而随着图文法研究的不断深入，人们发现上下文相关图文法具有更广阔的应用前景。目前已经有一些上下文相关图文法被提出，但它们或者是过于繁琐，既不直观又不简便，不方便使用；或者是计算复杂性太高，不实用。 本文首先对图文法发展及其现状进行了简要介绍，并重点讨论了图文法研究中的几个主要问题。在此基础上，针对现有上下文相关图文法的一些不足，围绕解决图文法中关键问题——嵌入问题提出了一个基于边的上下文相关图文法形式化框架，并对由此定义的文法的一些性质及相应的归约算法进行了讨论。接着，对所提出的图文法与已有的文法进行了比较。然后，给出了一个该文法的应用实例：利用它来描述设计模式的演化。最后，对全文进行了总结并展望了今后值得进一步研究的一些问题和方向。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2研究现状

1.3论文内容

1.4论文组织

第二章图文法形式化方法

2.1图文法的相关定义

2.2图文法研究的关键问题

2.3现有图文法解决关键问题的一些途径

2.4一个简单的图文法实例

2.5本章小结

第三章基于边的上下文相关图文法EGG

3.1基本定义

3.2基于边的上下文相关图文法的定义和性质

3.3基于边的上下文相关图文法的归约

3.4本章小结

第四章EGG与已有文法的比较

4.1与典型上下文相关图文法的比较

4.1.1产生式结构的比较

4.1.2解决嵌入问题方法的比较

4.1.3保证文法可判定性的方法的比较

4.1.4归约算法复杂度的比较

4.1.5其它方面的比较

4.2与其它类似图文法的比较

4.3本章小结

第五章EGG在设计模式中的应用

5.1设计模式及其演化

5.1.1设计模式的定义及描述

5.1.2设计模式的演化

5.1.3一种对设计模式进行演化的方法

5.2 EGG在设计模式演化方法中的应用

5.2.1使用EGG文法判定设计模式的一些说明

5.2.2描述几种模式的EGG产生式

5.2.3一个利用EGG产生式进行推导的实例

5.3本章小结

第六章总结与展望

6.1总结

6.2展望

参考文献

致谢

攻读硕上期间的研究成果