并行语法分析是并行编译技术、并行系统程序设计等研究领域的关键技术。是目前计算机科学研究领域中倍受关注的热点之一。这一问题的研究涉及自动机理论、并行计算模型、并行存储结构、算法复杂度、并行算法设计、数据结构、多处理机任务分配、优化技术等。这些关键技术问题的研究和关键算法的设计策略对完善并行编译技术、扩大其应用范围、增强其通用和实用性都有着重要的理论和实践意义。本文主要对基于改进的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集合求解的并行处理方法,并对这类集合的并行算法设计思想和它的实现策略做了详细论述。由于文法中终结符和非终结符个数很多,因此这种并行处理方法对并行编译和提高效率有其理论和现实意义;对并行环境下非确定有限自动机和确定有限自动机之间等价性转换、有限自动机模型最小化等问题进行研究,提出并详细分析了非确定有限自动机到确定有限自动机的并行转换方法及算法和基于可区分状态表结构的并行最小化算法,并以实例描述了并行转化的过程和并行最小化算法的并行处理过程,并验证其算法的可行性和与理论分析值的一致性。本课题的后续工作包括:期望从系统角度和理论高度上研究和讨论并行语法分析的设计和操作规范;文中对所设计或改进的算法从逻辑和理论上做了验证或推导,下一步考虑这些算法实现中的技术问题。