关联文法语法分析的并行处理研究

摘要

上下文无关文法是应用最广泛的一种形式语言,现今大多数程序设计语言的语法结构都是用上下文无关文法来描述的。但上下文无关文法描述问题的能力是不充分的,不能很好的处理自然语言。因此,作为上下文无关文法的改进或扩充,人们定义了一些特定文法,用于处理不同环境的语法分析。加拿大的Okhotin引入的关联文法属于这一类。关联文法是上下文无关文法的扩展,它是在上下文无关文法的基础上对文法产生式规则加入集合的交运算形成的。关联文法仍然保留了上下文无关文法一些重要特性,但比上下文无关文法具有更强的生成能力,能够更好的描述语言的语法结构,更好的描述自然语言。对于关联文法和上下文无关文法的语法分析和识别算法通常有LR(k)和LL(k)算法等。 本文对关联文法进行了比较系统的分析与研究,重点讨论了并行处理环境中的并行语法分析问题。由于传统的CKY并行算法和Earley并行算法只能处理上下文无关文法的语法分析,针对这种情况,本文对关联文法中的交运算进行特殊处理,在CYK算法和Earley算法中分别引入了f(RE)函数和finished(R)的集合,并在此基础上设计了关联文法在并行环境下的语法分析和识别算法,通过实例详细描述了这两种算法并行处理的过程,验证算法的可行性和正确性。本文中关联文法语法推导树采用压缩树的形式,与普通推导树相比,它所占用的存储空间较少。压缩推导树不仅可以共享终结符叶子,也可以共享具有相同后继终结符的子树。根据这个特点,推导出相同终结符的子树可以同时被构造,文中也提出了并行构造关联文法压缩推导树的算法并详细描述了算法的执行过程。本文算法的设计、分析方法与分析处理过程对其它特定文法的并行语法分析和设计有较高的参考价值。多处理机并行处理的方法大大提高了算法的执行效率,具有重要的理论和实践意义。

目录

文摘

英文文摘

声明

第一章绪论

1.1关联文法语法分析的研究现状

1.2关联文法语法分析并行处理的研究意义

1.3论文的结构与安排

第二章并行语法分析的理论基础

2.1编译的基本原理

2.2并行体系结构和并行编译理论

2.2.1并行体系结构

2.2.2并行编译理论

2.3并行编译的发展趋势

第三章上下文无关文法及语法分析的并行处理

3.1语言和文法

3.2上下文无关文法语法分析与识别的理论研究

3.3上下文无关文法语法分析并行处理的研究现状

第四章关联文法及语法分析的并行处理

4.1关联文法

4.2关联文法语法分析并行处理的相关定义

4.3基于CYK算法的关联文法语法分析的并行处理

4.3.1算法描述

4.3.2实例及其分析

4.4 基于Earley算法的关联文法语法分析的并行处理

4.4.1算法描述

4.4.2实例及其分析

4.5本章小节

第五章关联文法压缩推导树构造方法的并行处理

5.1关联文法的一般推导树和压缩压缩树

5.2关联文法压缩推导树构造方法的并行处理

5.2.1算法描述

5.2.2实例及其分析

5.3本章小节

第六章结束语

参考文献

致谢

攻读硕士学位期间的科研成果