【作者】 孙玉强；

【导师】 刘三阳；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2008， 博士

【摘要】 并行语法分析是并行编译技术、并行系统程序设计等研究领域的关键技术。是目前计算机科学研究领域中倍受关注的热点之一。这一问题的研究涉及自动机理论、并行计算模型、并行存储结构、算法复杂度、并行算法设计、数据结构、多处理机任务分配、优化技术等。这些关键技术问题的研究和关键算法的设计策略对完善并行编译技术、扩大其应用范围、增强其通用和实用性都有着重要的理论和实践意义。本文主要对基于改进的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】 Parallel parsing is key technology in the research fields of parallel compiler technology and programming of parallel system, and is one of the hot spots in computer science field currently. The study involved in automata theory, parallel computing model, parallel storage structure, algorithm complexity, parallel algorithm design, data structure, multi-task processor and optimize technology. These key technology research and key algorithm design strategy have great theoretical and practical significance of improving parallel compiler technology, expanding the scope of application and enhancing the practicality.The thesis makes research on Word—Lattice parsing method based on improved CYK algorithm, parallel parsing context-free grammar in linear array connecting state, improved increment parallel LL parsing algorithm, method of context-free grammar parallel recognition and parallel parsing on PRAM model, Parallel conversion method and algorithm from NFA to DFA and parallel algorithm of minimization based on distinguishable state table. As follows:Parallel parsing technology is classified and summarized systemically in the thesis. Word—Lattice parsing method based on improved CYK algorithm is proposed, which improves on CYK algorithm according time sequence span attribute after Word—Lattice distortion, makes parsing without changing structure and data of CYK table. Instance feasibility of producing useless in passing item of the form [i , j , B?η·] in parallel parsing table memory structure in circle structure and design idea of parallel parsing context-free grammar in linear array connecting state after analyzing carefully the reason to reduce this kind of useless is illustrated, and storage evolvement progress of linear array connection state is described in detail by examples. Method of context-free grammar parallel recognition and parallel parsing on PRAM model, pyramid structure, are parsed, mended and supplemented, in order to make it apply to Chomsky Normal Form. An improved increment parallel LL parsing algorithm is improved after analysis of increment parsing algorithm and parsing tree of indexed LL and discussing the parallel of using grammar parsing, calculating of d space function and node separating. A kind of parallel processing method to compute the FIRST and FOLLOW sets under multi-process environment is proposed, which discuss this kind of sets’parallel design idea and implement method. The parallel process method has great significance both in theory and practice for so many terminators and non-terminators in grammar. Parallel conversion method and algorithm from NFA to DFA and parallel algorithm of minimization based on distinguishable state table are proposed after study in perfect conversion between NFA and DFA under parallel environment and DFA model minimization, and parallel conversion process together with parallel process of parallel minimization algorithm are described with examples, in order to prove feasibility of algorithm and consistency of the value of theory parsing.The follow research of the subject include: study and discuss the design and operation norms of parallel parsing from the view of system theory, verify and derive the design and improved algorithm on papers. The next is to consider the technique of algorithm realization.更多还原