并行语法分析中几类算法的设计与研究

论文摘要

并行语法分析是并行编译技术、并行系统程序设计等研究领域的关键技术。是目前计算机科学研究领域中倍受关注的热点之一。这一问题的研究涉及自动机理论、并行计算模型、并行存储结构、算法复杂度、并行算法设计、数据结构、多处理机任务分配、优化技术等。这些关键技术问题的研究和关键算法的设计策略对完善并行编译技术、扩大其应用范围、增强其通用和实用性都有着重要的理论和实践意义。本文主要对基于改进的CYK算法的字—格语法分析方法、线性阵列LA(Linear Array)连接状态中上下文无关文法(CFG)的并行语法分析算法、扩增式LL语法分析算法的并行化、PRAM模型上的上下文无关文法的并行识别和并行语法分析方法、并行环境下非确定有限自动机和确定有限自动机之间等价性转换、有限自动机模型最小化等问题进行研究。具体内容如下:对并行语法分析技术做了较系统的分类和综述;提出一种基于改进的CYK算法的字—格语法分析方法:将字—格的CYK初始化表与CYK算法对常规句子的语法分析相比较,以字—格变形后的时间序列跨度为属性改进CYK算法,在字—格的CYK初始化表结构基础上做语法分析而不需改动CYK表结构或数据;指出环型结构网络连接状态中,并行语法分析项目表的存储结构中形如[i , j , B?η·]的项目的传递可能产生冗余的情况,对其产生的原因做了仔细分析;提出线性阵列LA(Linear Array)连接状态中上下文无关文法(CFG)的并行语法分析算法的设计思想,减少这种传递中的冗余,并以实例详细描述了线性阵列连接结构中分析信息的存储演变过程;对PRAM模型上的上下文无关文法的并行识别和并行语法分析方法—金字塔结构进行分析、修改和补充,使其适用于非Chomsky范式;在对扩增式语法分析算法和线索化LL语法分析树进行分析的基础上,对其中的语法分析树的重用、d距离函数的计算和结点分离等关键问题的并行性做了详细讨论,给出一个改进的并行化扩增式LL语法分析算法;提出一种多处理机环境中FIRST和FOLLOW集合求解的并行处理方法,并对这类集合的并行算法设计思想和它的实现策略做了详细论述。由于文法中终结符和非终结符个数很多,因此这种并行处理方法对并行编译和提高效率有其理论和现实意义;对并行环境下非确定有限自动机和确定有限自动机之间等价性转换、有限自动机模型最小化等问题进行研究,提出并详细分析了非确定有限自动机到确定有限自动机的并行转换方法及算法和基于可区分状态表结构的并行最小化算法,并以实例描述了并行转化的过程和并行最小化算法的并行处理过程,并验证其算法的可行性和与理论分析值的一致性。本课题的后续工作包括:期望从系统角度和理论高度上研究和讨论并行语法分析的设计和操作规范;文中对所设计或改进的算法从逻辑和理论上做了验证或推导,下一步考虑这些算法实现中的技术问题。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 并行化编译与并行语言编译
• 1.1.1 并行化编译
• 1.1.2 并行语言编译研究
• 1.1.3 并行化编译与并行语言编译的比较
• 1.2 并行语法分析在并行编译的地位和研究现状
• 1.2.1 文法研究
• 1.2.2 并行语法分析研究现状
• 1.3 本文的主要工作与贡献以及结构安排
• 第二章 并行语法分析基础与定义
• 2.1 并行硬件基础：并行计算机模型与并行存储模型
• 2.2 并行系统软件：并行操作系统和并行编译系统
• 2.3 相关自动机与文法描述
• 第三章 一种基于改进的CYK算法的字—格语法分析方法
• 3.1 本章引论
• 3.2 CYK算法描述与定义
• 3.2.1 CYK算法描述
• 3.2.2 CYK算法定义
• 3.2.3 实例与过程分析
• 3.3 基于CYK算法的字—格语法分析
• 3.3.1 字—格变形
• 3.3.2 字—格的CYK表初始化
• 3.4 改进的字—格语法分析方法
• 3.4.1 改进算法的设计思想
• 3.4.2 改进的字—格语法分析方法
• 3.5 实例分析与结果分析
• 3.5.1 方法一实例分析
• 3.5.2 方法二实例分析
• 第四章 基于线性阵列网络的并行语法分析算法设计
• 4.1 相关定义
• 4.2 问题描述
• 4.3 LL（i）结构描述与定理
• 4.4 LA上并行语法分析算法设计
• 4.4.1 算法描述与说明
• 4.4.2 算法设计
• 4.4.3 构造过程分析
• 第五章 基于PRAM模型的CFGs并行识别与语法分析扩充算法
• 5.1 问题描述
• 5.2 算法思想
• 5.3 并行算法的设计和改进
• 5.3.1 Chomsky规范形式文法并行识别算法
• 5.3.2 算法的改进与扩充
• 第六章 基于扩增式LL文法的并行语法分析
• 6.1 相关定义
• 6.2 扩增式LL语法分析
• 6.2.1 语法分析树的线索化
• 6.2.2 语法分析树的重用
• 6.2.3 扩增式LL语法分析表的构造
• 6.2.4 扩增式LL语法分析算法
• 6.3 改进的扩增式LL文法并行语法分析
• 6.3.1 并行处理的思考
• 6.3.2 并行环境中算法改进
• 6.3.3 扩增式LL并行语法分析实例—表达式分析
• 第七章 FIRST与FOLLOW集合的并行算法设计
• 7.1 理论基础
• 7.2 FIRST与FOLLOW集合并行算法设计
• 7.2.1 计算Mf关系矩阵并行算法
• 7.2.2 计算MF关系矩阵并行算法
• 7.2.3 算法性能分析
• 7.3 并行技术过程分析
• 7.3.1 并行计算过程
• 7.3.2 非算符文法计算过程
• 7.3.3 ε文法计算过程
• 第八章 NFA到DFA的并行转换
• 8.1 相关定义
• 8.2 并行确定化算法设计
• 8.3 并行转换实例分析
• 8.4 基于可区分状态表结构的并行处理
• 8.4.1 可区分状态表构造
• 8.4.2 基于可区分状态表结构的DFA最小化算法
• 8.4.3 实例分析
• 第九章 其它特定文法的并行语法分析和相关并行算法
• 9.1 相关概念与定义
• 9.2 扩充GHR语法分析算法的并行处理及过程
• 9.2.1 扩充GHR语法分析算法的并行处理
• 9.2.2 连接文法的并行处理过程分析
• 9.3 基于PRAM模型的二叉树A序列并行算法
• 9.3.1 先序遍历并行算法
• 9.3.2 A序列的并行算法
• 9.3.3 算法实例分析
• 第十章 结束语
• 感悟与致谢
• 参考文献
• 读博期间取得的科研成果