（应用数学专业论文）并行语法分析中几类算法的设计与研究.pdf

摘要 并行语法分析是并行编译技术、并行系统程序设计等研究领域的关键技术。 是目前计算机科学研究领域中倍受关注的热点之一。这一问题的研究涉及自动机 理论、并行计算模型、并行存储结构、算法复杂度、并行算法设计、数据结构、 多处理机任务分配、优化技术等。这些关键技术问题的研究和关键算法的设计策 略对完善并行编译技术、扩大其应用范围、增强其通用和实用性都有着重要的理 论和实践意义。 本文主要对基于改进的c y k 算法的字一格语法分析方法、线性阵列 l a ( l i n e a ra r r a y ) 连接状态中上下文无关文法( c f g ) 的并行语法分析算法、扩增式 l l 语法分析算法的并行化、p r a m 模型上的上下文无关文法的并行识别和并行 语法分析方法、并行环境下非确定有限自动机和确定有限自动机之间等价性转换、 有限自动机模型最小化等问题进行研究。具体内容如下： 对并行语法分析技术做了较系统的分类和综述；提出一种基于改进的c y k 算法的字一格语法分析方法：将字一格的c y k 初始化表与c y k 算法对常规句子 的语法分析相比较，以字一格变形后的时间序列跨度为属性改进c y k 算法，在 字一格的c y k 初始化表结构基础上做语法分析而不需改动c y k 表结构或数据； 指出环型结构网络连接状态中，并行语法分析项目表的存储结构中形如【i ，j ，b - - ) r l 的项目的传递可能产生冗余的情况，对其产生的原因做了仔细分析；提出线 性阵列l a ( l i n e a ra r r a y ) 连接状态中上下文无关文法( c f g ) 的并行语法分析算法的 设计思想，减少这种传递中的冗余，并以实例详细描述了线性阵列连接结构中分 析信息的存储演变过程；对p r a m 模型上的上下文无关文法的并行识别和并行语 法分析方法一金字塔结构进行分析、修改和补充，使其适用于非c h o m s k y 范式； 在对扩增式语法分析算法和线索化l l 语法分析树进行分析的基础上，对其中的 语法分析树的重用、d 距离函数的计算和结点分离等关键问题的并行性做了详细 讨论，给出一个改进的并行化扩增式l l 语法分析算法；提出一种多处理机环境 中f i r s t 和f o l l o w 集合求解的并行处理方法，并对这类集合的并行算法设计 思想和它的实现策略做了详细论述。由于文法中终结符和非终结符个数很多，因 此这种并行处理方法对并行编译和提高效率有其理论和现实意义；对并行环境下 非确定有限自动机和确定有限自动机之间等价性转换、有限自动机模型最小化等 问题进行研究，提出并详细分析了非确定有限自动机到确定有限自动机的并行转 换方法及算法和基于可区分状态表结构的并行最小化算法，并以实例描述了并行 转化的过程和并行最小化算法的并行处理过程，并验证其算法的可行性和与理论 分析值的一致性。 本课题的后续工作包括：期望从系统角度和理论高度上研究和讨论并行语法 分析的设计和操作规范；文中对所设计或改进的算法从逻辑和理论上做了验证或 推导，下一步考虑这些算法实现中的技术问题。 关键词：语法分析算法并行处理 上下文无关文法 a b s t r a c t p a r a l l e lp a r s i n gi sk e yt e c h n o l o g yi nt h er e s e a r c hf i e l d so fp a r a l l e lc o m p i l e r t e c h n o l o g ya n dp r o g r a m m i n go fp a r a l l e ls y s t e m ，a n di so n eo ft h eh o ts p o t si n c o m p u t e rs c i e n c ef i e l dc u r r e n t l y t h es t u d y i n v o l v e di na u t o m a t at h e o r y ，p a r a l l e l c o m p u t i n gm o d e l ，p a r a l l e ls t o r a g es t r u c t u r e ，a l g o r i t h mc o m p l e x i t y ，p a r a l l e la l g o r i t h m d e s i g n ，d a t as t r u c t u r e ，m u l t i t a s kp r o c e s s o ra n do p t i m i z et e c h n o l o g y t h e s ek e y t e c h n o l o g yr e s e a r c ha n dk e ya l g o r i t h md e s i g ns t r a t e g yh a v eg r e a tt h e o r e t i c a la n d p r a c t i c a ls i g n i f i c a n c eo fi m p r o v i n gp a r a l l e lc o m p i l e rt e c h n o l o g y ，e x p a n d i n gt h es c o p e o f a p p l i c a t i o na n de n h a n c i n gt h ep r a c t i c a l i t y t h et h e s i sm a k e sr e s e a r c ho nw o r d - - l a t t i c ep a r s i n gm e t h o db a s e do ni m p r o v e d c y k a l g o r i t h m ，p a r a l l e lp a r s i n gc o n t e x t - f r e eg r a m m a ri nl i n e a ra r r a yc o n n e c t i n gs t a t e ， i m p r o v e di n c r e m e n tp a r a l l e ll lp a r s i n ga l g o r i t h m ，m e t h o do fc o n t e x t f r e eg r a m m a r p a r a l l e lr e c o g n i t i o na n dp a r a l l e lp a r s i n go np r a mm o d e l ，p a r a l l e lc o n v e r s i o nm e t h o d a n da l g o r i t h mf r o mn f at od f aa n dp a r a l l e la l g o r i t h mo fm i n i m i z a t i o nb a s e do n d i s t i n g u i s h a b l es t a t et a b l e a sf o l l o w s ： p a r a l l e lp a r s i n gt e c h n o l o g yi sc l a s s i f i e da n ds u m m a r i z e ds y s t e m i c a l l yi nt h e t h e s i s w o r d - - l a t t i c ep a r s i n gm e t h o db a s e do ni m p r o v e dc y k a l g o r i t h mi sp r o p o s e d ， w h i c hi m p r o v e so nc y ka l g o r i t h ma c c o r d i n gt i m e s e q u e n c es p a na t t r i b u t ea f t e r w o r d - - l a u i c ed i s t o r t i o n ，m a k e sp a r s i n gw i t h o u tc h a n g i n gs t r u c t u r ea n dd a t ao fc y k t a b l e i n s t a n c ef e a s i b i l i t yo f p r o d u c i n gu s e l e s si np a s s i n gi t e mo f t h ef o r m 【i ，j ，b 专t 1 】 i np a r a l l e lp a r s i n gt a b l em e m o r ys t r u c t u r ei nc i r c l es t r u c t u r ea n dd e s i g ni d e ao f p a r a l l e l p a r s i n gc o n t e x t f r e eg r a m m a ri nl i n e a ra r r a yc o n n e c t i n gs t a t ea f t e ra n a l y z i n gc a r e f u l l y t h er e a s o nt or e d u c et h i sk i n do fu s e l e s si si l l u s t r a t e d ，a n ds t o r a g ee v o l v e m e n tp r o g r e s s o fl i n e a ra r r a yc o n n e c t i o ns t a t ei sd e s c r i b e di nd e t a i l b ye x a m p l e s m e t h o do f c o n t e x t f r e eg r a m m a rp a r a l l e l r e c o g n i t i o na n dp a r a l l e lp a r s i n g o np r a mm o d e l ， p y r a m i ds t r u c t u r e ，a r ep a r s e d ，m e n d e da n ds u p p l e m e n t e d ，i no r d e rt om a k ei ta p p l yt o c h o m s k yn o r m a lf o r m a ni m p r o v e di n c r e m e n tp a r a l l e ll lp a r s i n ga l g o r i t h mi s i m p r o v e da f t e ra n a l y s i so fi n c r e m e n tp a r s i n ga l g o r i t h ma n dp a r s i n gt r e eo fi n d e x e dl l a n dd i s c u s s i n gt h ep a r a l l e lo fu s i n gg r a m m a rp a r s i n g ，c a l c u l a t i n go fds p a c ef u n c t i o n a n dn o d es e p a r a t i n g ak i n do fp a r a l l e lp r o c e s s i n gm e t h o dt oc o m p u t et h ef i r s ta n d f o l l o ws e t su n d e rm u l t i p r o c e s se n v i r o n m e n ti sp r o p o s e d ，w h i c hd i s c u s st h i sk i n d o fs e t s p a r a l l e ld e s i g ni d e aa n di m p l e m e n tm e t h o d t h ep a r a l l e lp r o c e s sm e t h o dh a s g r e a ts i g n i f i c a n c e b o t hi nt h e o r ya n d p r a c t i c e f o rs o m a n yt e r m i n a t o r sa n d n o n - t e r m i n a t o r si ng r a m m a r p a r a l l e lc o n v e r s i o nm e t h o da n da l g o r i t h mf r o mn f at o d f aa n dp a r a l l e la l g o r i t h mo fm i n i m i z a t i o nb a s e do nd i s t i n g u i s h a b l es t a t et a b l ea r e p r o p o s e da f t e rs t u d yi np e r f e c tc o n v e r s i o nb e t w e e nn f a a n dd f au n d e rp a r a l l e l e n v i r o n m e n ta n dd f am o d e lm i n i m i z a t i o n ，a n dp a r a l l e lc o n v e r s i o np r o c e s st o g e t h e r w i t hp a r a l l e lp r o c e s so fp a r a l l e lm i n i m i z a t i o na l g o r i t h ma r ed e s c r i b e dw i t he x a m p l e s ， i no r d e rt op r o v ef e a s i b i l i t yo fa l g o r i t h ma n dc o n s i s t e n c yo ft h ev a l u eo ft h e o r y p a r s i n g t h ef o l l o wr e s e a r c ho ft h es u b j e c ti n c l u d e ：s t u d ya n dd i s c u s st h ed e s i g na n d o p e r a t i o nn o r m so fp a r a l l e lp a r s i n gf r o mt h ev i e wo fs y s t e mt h e o r y , v e r i f ya n dd e r i v e t h ed e s i g na n di m p r o v e da l g o r i t h mo np a p e r s t h en e x ti st oc o n s i d e rt h et e c h n i q u eo f a l g o r i t h mr e a l i z a t i o n k e y w o r d ：p a r s i n ga l g o r i t h m p a r a l l e lp r o c e s s i n gc o n t e x t - f r e eg r a m m a r 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科 技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同j 基 对本研究所做的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 弭翟、殇 日期2 0 0 8 9 2 2 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科 技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以 公稚论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存 论文。( 保密的论文在解密后遵守此规定) 本人签名： 导师签名： 掣b 舡 i 二| 期2 q q 墨：皇：2 2 纂牵绪论 第一章绪论 计算机技术的发展已成力当今各高新技术和基础科学研究领域取得受大突破 的基石。特别是高性能计算技术的研究使得这些领域能对所研究的对象进行数值 模拟和动态显示，获得在实验或先前计算的条件下很难得到甚至不能得到的结果。 高性能计算的研究与发展为诸如：基因信息学、航空航天、石油勘探和开发、大 范围天气预报、核爆模拟和经济模型等离薪技术的研究开创了美好前景。 计算机性能价格比的提高主要源自两个方面：器件技术的进步和体系结构的 创新。一方面，计算机系统的制造者通过使用具有更高速度和集成度的器件，来 提高整个系统的运算速度和存储容量；另一方面，体系结构设计者则致力于发掘 系统内的并行性，通过使多个操作并行执彳亍丽达到缩短程序总的执行时闻的目的。 由于硬 牛的元器件、集成度、工艺和体系结构的发展迅速几乎到了极限，因此， 并行处理技术当然成为现代高性能计算机的关键技术【l ，2 j 。各个发达国家都无不把 研究开发超高性能的并行计算机系统列为重要战略目标，例如美国的a c s i 计划、 h p c 现代化计划以及p e t a f l o p sc o m p u t i n g 计划。为此他们投入了大量的人力、物 力和财力，不惜代价地为在高新科技领域这一关键技术上领先一步丽奋斗，竞争 尤为激烈。在信息技术高度发达、国际竞争目益激烈的今天，高性能计算机的发 展水平融成为一个国家囡力强弱的重要标志。 本文研究的并行语法分析技术是高性能计算、并行处理技术中的重要课题。 王。l 并行化编译与并行语言编译 为实现高性能并行计算，并行系统通常采用两种过程实现模式( 或者说在并 行系统上实现并行计算有两个途径) ： ( 1 ) 程序设计人员编写串行的应用程序，由编译器将其转换为并行鼹标代码执 行。 ( 2 ) 按照某种并行语法规范编写的并行程序，由并行语言编译器将并行程序转 化为并行的目标代码执行。 前者称为并行化编译，后者称为并行语言编译。它们的关系模型如图1 1 所 示。 下面对这两种编译方法及特点进行简要描述。 1 1 1 并行化编译 根据转化尽标的不同，并行纯编译器诞以分为两种类型：源到源的警动并 行化系统。它能够对输入的串行源程穿进行分析，生成带有并行提示说明的并行 源程序。这种自动并行化系统通常作为高级语言编译器的一个并行化辅助工具出 现。自动并行化编译器。它可以将个串行程序转化为能够并行执行的目标代 2并行语法分析中几类算法的设计与研究 码在目标机上执行( 见图1 1 ) 。 自动并行编译为充分发挥并行计算环境不断增强的计算能力提供了一条重要 的途径它有以下优点【3 j ： ( 1 ) 在缺乏被普遍接受的并行程序设计语言的情况下，自动并行化工具能有效地解 决代码的可重用和可移植问题； ( 2 ) 解决了用一种语言难以显式地表达从指令层到任务层各个层次的并行性，并进 行基于体系结构的优化问题； ( 3 ) 自动并行化工具为大量存在于应用领域的，并经过长时间的设计、使用和测试 的成熟大型串行应用程序的并行化提供了唯一可行的选择。 典型的并行化系统有1 4 j j ： ( 1 ) i l l i n o i s 大学的g u p t a 和b a n e r j e e 等开发的p a r a f r a s e 2 系统是一个源到源的程 序并行化辅助工具。它不仅能把f o r t r a n 7 7 程序转换为包含外在通信的s p m d 节点程序，还可以处理用c 和p a s c a l 编写的源程序。p a r a f r a s e 有1 0 0 多个程 序转化软件模块。给定一个串行程序，p a r a f r a s e 通过一张传递表( p a s sl i s t ) 表 示转换的特定次序。不同的程序使用不同的传递表，因而经过转换的次序也不 同。 ( 2 ) r i c e 大学的k e nk e n n e d y 等研制的源到源的并行化辅助工具p f c ( p a r a l l e l f o r t r a nc o n v e r t e r ) 。能够对程序结构分析和数据相关性进行分析，使用循环变 换、相关消除变换等多种程序变换技术。分类相关性测试的方法可以指明循环 向量化的可能性。 ( 3 ) s t a n f o r d 大学开发的自动化系统s u i f 。系统集成了多项并行化分析技术，包 含数组和标量的私有化和归约化识别、数组下标的符号分析、过程间分析技术。 第一章绪论 许多计算机公司还研制了商品化的并行化编译系统，如k u c k & a s s o c i a t e s 公司研制的k a p 、i b m 公司研制的p t 凡蝌等。 国内也对并行化编译技术进行了大量研究，实现了几个并行化编译系统。主 要有： ( 1 ) 南京大学研制了面向j a 、，a 语言的自动并行化系统j a p s l 6 j 。该系统能够自动进 行任务划分，分析j a v a 程序中任务并行性，自动插入通信原语，将任务分配到 不同的处理结点上。其基本过程为：对用户程序的执行任务进行划分，生成层 次任务图h t g ；对各任务估计执行时间；进行数据相关性分析，构造层次任 务相关图h t d g ；估计通信产生的开销；对h t d g 按照并行性进行合成和分 层处理，形成分层任务图l t g ；向每个任务插入通信原语和其他必要成分，使 之成为可独立编译和运行的单位；将任务分配到不同的处理机结点上。 ( 2 ) 西北工业大学研制的针对流体力学计算( c f d ：c o m p u t a t i o n a lf l u i dd y n a m i c s ) 的并行化系统n p u p 2 l r 【7 8 】。它接受一个用f o r t r a n 7 7 编写的c f d 源程序，将其转 换为包含并行编译指导命令的等价并行源程序。系统由两部分构成：与硬件平台 和软件环境无关的相关性分析和与实际机器环境的程序重构部分。系统运行于并 行虚拟机( p a r a l l e lv i r t u a lm a c h i n e ) 和n o w 上。 ( 3 ) 中科院计算所为曙光系列并行机开发的面向分布存储f o r t r a n 程序的源到源的 自动并行编译器a u t o p a r 。a u t o p a r 主要实现循环级的并行，根据程序分析能够识 别并行循环、执行数据划分、产生并行的f o r t r a n 源代码1 9 l 。 ( 4 ) 复旦大学研制的自动并行化系统( a f t - a u t o m a t i cf o r t r a nt r a n s f o r m e r ) 1 1 】。该系 统主要采用数组私有化( a r r a yp r i v a t i z a t i o n ) 、相关性测试、并行变换、过程间分析、 存储优化等技术产生高效的并行程序。 1 1 2 并行语言编译研究 理想的并行程序设计方法是串行程序自动并行化。尽管并行化编译的研究与 开发已有2 0 多年的历史，实现了一些并行化系统。但这些并行化系统仍然限于对 简单的数据相关性的分析和特定的程序结构( 如循环迭代等) 实现并行化，对于复杂 的程序自动并行化效果并不十分明显。因此使用并行语言进行并行程序设计是当 前实现并行计算的主要途径。 并行程序设计语言是描述和设计并行程序的工具，一个并行程序设计语言应 当具有如下的两个特征： ( 1 ) 灵活性。即这种语言能够使程序员在应用程序中描述所需的各种并行性。 ( 2 ) 高效性。即这种语言可以在各种并行计算系统上高效地实现。 并行语言按照生成的方式可以分为两类： ( 1 ) 语言扩充型。这类语言的特点是在原有串行语言的基础上增加并行成分使并行 性得到有效发挥。普遍使用的并行语言绝大多数都属于这种类型，如h p f t l 2 j 、 f o r t r a nd 【1 3 j 、d p c i l 4 j 、h p c + + 等。 ( 2 ) 新语言方案【1 5 】。设计出全新的语言来支持并行处理。近年来已设计出的并行语 4 并行语法分析中几类算法的设计与研究 言有c o n c u r r e n tp a s c a l ，m o d u l a 2 ，o c c a m ，a d a ，v a l ，c s p ，s i s a l 等。按照 并行执行的特征，并行语言主要分为两大类：数据并行语言和任务并行语言。也有 学者提出了将任务并行和数据并行集成的并行语割1 6 1 引。 由于应用问题的复杂性，程序分析极为复杂，为了保证程序变换的正确性， 有时只能采用保守的处理方法，因此纯粹的自动并行化技术在解决实际应用问题 时显现了局限性。特别是对于具有分布式内存的并行处理系统，自动并行化的功 能很不理想，这主要体现在以下几个方面： 1 ) 由于程序分析信息难以十分精确，对程序中蕴涵的并行性不能完全发掘； 2 ) 数据局部性分析难以十分精确，数据局部性分析与计算的分割是相互影响、相 互制约的，是影响并行化后的软件性能的关键因素； 3 ) 同步和通讯的优化。同步和通讯对保证并行软件执行的正确性是重要的，但在 并行软件中如何恰当地加入同步和通讯操作，以及实现通讯与计算的覆盖对提 高并行软件的性能也很重要。 1 1 3 并行化编译与并行语言编译的比较 根据并行化编译与并行语言编译的特征，我们从语言规范、程序设计、编译 实现等几方面对这两种典型的并行计算实现方法进行比较，结果如表1 1 所示。 表1 1 并行化编译与并行语言编译的比较 类别并行化编译 并行语言编译( h p f 为例) 语言特征标准串行语言。带有并行结构语句和数据分 布提示的并行语言。 编译器构造需完成串行程序的自动并行化工作及只需完成并行程序的编译工 数据分布的实现。构造复杂，难于实现。作，将计算数据按程序中的指 定进行分布。实现较前者简 单。 生成并行目标只能针对特定的结构语句及较为简单根据程序中的并行结构生成 代码的效率的数据引用程序生成的并行执行的目高效率并行执行的目标代码。 标代码，并行化程度受限制。 对程序设计人只要能够使用串行语言编写串行程序。必须掌握并行语言的程序设 员的要求 计方法及使用数据分布提示 的方法。对程序设计人员要求 较高。 对原有串行程无需修改直接编译使用。改造成并行程序，增加数据分 序的使用布提示后使用。 第一章绪论 通过比较我们可以看出：并行化编译作为理想的并行程序设计方式，实现起 来较为困难，而典型的并行语言( 如h p f ) 编译虽然有较高的并行执行效率，但对 程序设计人员有较高的要求，程序员编写程序时必须改变传统的串行程序设计鼹 念，熟悉并行语句、结构程序设计的特点和方法，给出计算数据的数据分布。这 种方法程序设计人员难以掌握。如果数据分布提示与并行代码不一致时，反倒会 影响并行执行效率。因此，设计人员在设计像l sm p p 数据并行c 这样的语言规 范时，考虑在语言中包含并行语句结构，不包含数据分布提示，将数据分布功能 完全留给编译器实现。从两一方面程序舆有较高的并行执行效率，另一方面程序 设计人员也能够较快地掌握该数据并行语言。 1 2 并行语法分析在并行编译的地位和研究现状 综上分析，在各类并行编译处理的方法中，主要考虑的是将用户程序源代码 的功能并行处理。用户程序的目标代码或按任务或按功能或按时间等各种并行策 略分配给各处理机( 如图1 1 ) 。其实，真正意义上的并行编译还面临一个问题， 即系统程序( 恧非震户程序) 本身的并行处理阀题。 在图1 1 中，扁椭圆中所包含部分( 如自动并行编译器、半自动自动并行化 程序、并行语言编译器等) 的系统程序的并行处理更是本文的关注对象。而其中 的语法分析成分也是并行编译的主要内容。为了充分利用多机的并行环境，提高 编译速度，把语法分析甚至词法分析任务并行处理。 1 2 1 文法研究 由于语法分析依赖于所规定的文法，换句话说，文法的特性决定语法分析和 并行语法分析的方法和效率，因此，胰9 0 年代至今，各种文法和特性文法的研究 是并彳亍编译技术的重要研究分支。该分支主要研究这些文法的特点和特性，以及 适用于语法分析范畴的不同环境、不同类别和不同的应用。例如：范围串联语法 类作为很多工作的语法基础，特别是在自然语言处理中。这些语法功能强大，因 为它们严格包含适度的上下文相关体系，还保持它们的语句能在多项式时闻内被 分橱。它们的语法分析器的输出结果可以被看作是经典上下文无关共享树形结构 的多项式形式的结构。这种体系允许模块化的形式，可以设计一个可重用的语法 元件库 1 9 1 。而优先逻辑文法可以看作是定语从句文法( d c g s ) 和定语从句转换文法 ( d c t g s ) ( d e f i n i t e c l a u s et r a n s l a t i o ng r a m m a r s ) 的扩展。正如d c g s 和d c t g s 可以 直接转换为逻辑程序，p l g s 也可以转换为优先逻辑程序( p l p s ) 2 翻。提出的薪的文 法类或做了深入研究的文法还有h e i k og o e m a n 提出的在线性时间内压缩输入字 符串的l r 方法。这种方法依赖于l r 自动机，扩展了子串语法分析器。再次重 新语法分析时，可加快速度【2 1 1 。a l e x a n d e ro k h o t i n 提出在规则公式化体系上附加 6 并行语法分析中几类算法的设计与研究 一套外在交叉操作，对这种连接文法的识别和处理算法没有增加其时间复杂度 2 2 1 。而k a r l m i c h a e ls c h n e i d e r 用两个同态代数转换方法描述列表式语法分析， 语法分析问题被描述成关于同态的输入字符串的逆镜像的计算等等。这些改进或 扩展的文法定义和算法为并行的语法分析的设计提供了新的思路和方法。 1 2 2 并行语法分析研究现状 关于文法识别过程和并行处理问题的研究也有较大进展，s t e f a n oc r 等将文 法分解成确定的子文法，语法分析模型分解成独立子模型。文法模块化有利于消 除复杂性，便于维护和模块重用1 2 引。j a m e sf p o w e r 提出一种映射，在文法中描述 软件标准化【2 4 1 。在大型文法的构建时采用软件工程的方法评价程序设计语言的标 准也可以由文法表示，使得该表述的语言是标准化的。a d e e l a b b a s 等对面向对象 的并行处理的两种方法p v m ( 并行虚拟机) 和m p i ( 信息传输接口) 进行了比较， p v m 和m p i 工具使并行程序设计可以移植，引入了s c o o p ( 大规模面向对象的程 序设计) 方法，该方法支持并行应用的设计和执行【2 5 1 。 w a r r e nx l i 提出扩增式文法概念：扩增式语法分析广泛应用于基于语言的编 辑和扩增式编译解释环境。在这种环境中，对修改得到的输入字符串进行重新语 法分析是经常执行的操作，它的执行效率在很大程度上影响在这种背景下的并行 语法分析是否成功。他介绍了一种方法，在语法分析树和l l 语法分析表中的一 个附加远距离输入( a na d d i t i o n a ld i s t a n c e ) 之间的线程化的连接，以支持最小化 的l l ( 1 ) 重新语法分析，这些改进有利于产生高效的扩增式l l 语法分析器f 2 6 】。 在参考文献【2 7 j 中，按传统的语法分析规则，描述了对一般上下文无关语言的并行 识别和语法分析的并行算法。文献 2 8 j 对上下文无关语言的特殊集括号语言，给出 了一个用n l o g n 个处理器和o ( 1 0 9 n ) 时间的识别和语法分析优化的并行算法。对于 任意的上下文无关文法在线性环形拓扑结构中的并行语法分析算法，在文酬2 9 】中 有较深入地讨论，并且给出了在多处理机环境下并行语法分析的项目传递过程中 单向环形拓扑结构的优势和分析算法。在参考文献【3 0 】中，介绍了p r a m 模型上的 一种并行语法分析方法，对给出的文法有较高的要求，只可以对c h o m s k y 规范形 式文法进行语法分析，即对传统的产生式右部候选式为一个终结符或者为两个连 接的非终结符有效。 c c i r e s s a n 和e s a n c h e z 等提出将字一格语法分析用于语音句子识别的方法， 并用硬件实现基于f p g a 的语法分析协处理裂3 1 j 。j c c h a p p e l i e r 等提供处理上下 文无关文法的c y k 算法为作者提高了对字一格语法分析处理的新思路【3 2 】。 r y t t e rw 与陈国良等描述了正则表达式到非确定自动机的最优并行转换 1 3 3 , , 3 4 】。典型数据结构的并行处理算法的研究为并行语法分析技术提供了非常有用 的设计平台，因为语法分析的许多数据结构和算法本身就是典型结构。 第章绪论 7 1 3 本文的主要工作与贡献以及结构安排 本文 乍者从事大学“编译原理”课教学近2 0 年，对编译原理中的语法分析技 术尤感兴趣。2 0 0 2 年攻读博士学位以来对并行语法分孝斤技术进行了较为深入的研 究。本文的贡献主要是： 1 对并行语法分析技术做了较系统的分类和综述。凼于没有一本论述并行语 法分析的专著，作者搜集了散落在各类图终杂志的有关论文，进行分析和归纳， 著指出并行语法分辑技术在并行编译中所处的地位和所起的作用。 2 分析讨论了c y k 算法在字一格语法分析中的应用和它们的存储结构、字一 格语法分析过程、形式的转换等问题。提出了一种基于改进的c y k 算法的字一 格语法分析方法，这种方法将字一格的c y k 初始化表与c y k 算法对常规句子的 语法分誊厅做了深入比较，以字格变形薏的时间序歹l 跨度为属性改进了c 算 法，可以在字一格变形屠的c y k 表初始化基础上通过软件继续进行语法分析两 不需改动c y k 表结构或数据。以一个实例说明算法的可用性以及运行过程和结 果，与理论分析结果相一致。 3 。提出线性阵列l a ( l i n e a ra r r a y ) 连接状态中上下文无关文法( c f g ) 的并行语 法分析算法的设计恶想，指出对形如羹，j ，b 专砖豫皇项瓣传递时环形拓扑结构的 冗余，并以实例详细描述了线性阵列连接结构中分析信息的存储演变过程。 4 对p r a m 模型上的上下文无关文法的并行识别和并行语法分析方法一金字 塔结构进行分析、修改和补充，使其对非c h o m s k y 规范形式也能识别和分析。 5 。对并行化环境下扩增式语法分析算法和线索化l l 语法分析树进行改进，给 出一个改进的并行化扩增式l l 语法分析算法，并用一个实例进行详细分析。 6 提出一种多处理机环境中f i r s t 和f o l l o w 集合求解的并行处理方法， 并对这类集合的并行算法设计思想和它的实现策略做了详细讨论。由于文法中终 结符和非终结符个数很多，因此，这种并行处理方法对并行编译和提高效率有其 理论和现实意义。 7 。对并行环境下非确定有限自动机和确定有限自动机之间等价性转换、有限 自动机模型最小化等问题进行研究，提出并详细分析了非确定有限自动机到确定 有限自动机的并行转换方法及算法和基于可区分状态表结构的并行最小化算法， 并以实例描述了并行转化的过程和并行最小优算法的并行处理过程，并验证其算 法的可行性。 本文基分十章。第一章为概论，介绍并行化编译与并行语言编译的基础和区 别，分析了并行语法分析技术在并行编译的地位，描述了并行语法分析技术当前 研究现状；第二章介绍并行语法分析基础理论，主要包括在后面章节所麸用的定 义、定理和推理。而各章所独用的基本定义和定理等将在各章中拦述；第三章重 点描述了一种经过改进的c y k 算法用于字一格语法分析的原理和方法；第四章 介绍基于线性阵列网络的并行语法分析算法设计；第五章介绍一种基于p r a m 模 型的c f g s 并行识别与语法分析的扩充算法；第六章介绍基于扩增式l l 文法的 8并行语法分析中几类算法的设计与研究 并行语法分析算法的设计思想和算法设计：第七章描述f i r s t 和f o l l o w 集合 的并行算法；第八章介绍n f a 到d f a 的并行转换以及d f a 的最小化并行算法； 第九章描述了一种特定文法的并行处理过程以及有关并行遍历算法；第十章为结 束语，指出本课题研究中存在的问题、未来发展和作者的后续工作。 第二章并行滔法分橱基礁与定义 9 第二章并行语法分析基础与定义 本章攒述了并行语法分橱的基础( 或称底层概念) ，包括并行计算机模型和著 行存储模型，并行系统软件，并行编译等等。并行语法分析的工作是基于这些基 础之上的。对它们的理解有助于对本文后续内容的理解。本章的定义可以说是后 面各章的公共定义。 2 。l 并行硬件基础：并行计算机模型与并行存储模型 并行计算机是使用多台计算机协同工作的一种高性能计算机系统。囱2 0 世纪 7 0 年代初到现在，出现了各种不同类型的并行计算机。当代主流的并行诗舞机是可 扩展的并行计算机，其结构模型有六类 2 , 3 5 l ，包括： 1 单指令流多数据流机s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) ； 2 共享存储的对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) ； 3 并行向量处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r ) ； 4 。对称分布存储的大规模并行机m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) ； 5 分布共享存储多处理机d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) ； 6 t 作站机群c o w ( c l u s t e ro fw o r k s t a t i o n ) 。 s i m d 计算机多为专用( 见图2 1 ) ，其余的5 耪均属于多指令流多数据流 m i m d ( m u l t i p l e i n s t r u c t i o nm u l t i p l e - d a t a ) 计算机。五种m i m d 并行枫的结构模型 示于图2 2 。 图中c u 控制部件；p i 卜一处理部件；m m 主存模块；s m 共享主存； 控制流；l s 指令流；d s 数据流 图2 1 单指令流多数据流s i m d l o 并行语法分析中几类算法的设计与研究 s m 图2 。2 多指令流多数据流鹾l 涵 定义2 1 并行处理机( 又叫s i m d 计算机) ：它是单一控制部件控制下的多 个处理单元构成的阵列，也即：由多个p u 按照一定方式互连，在同一个c u 控 割下，对各自的数据完成丽一条指令规定的操作。 从c u 看，指令是宰行执季于的，从p u 看，数据是并行处理的。 并行处理机也称为阵列处理机。按照佛林分类法，它属于s i m d 计算机( 见图 2 1 ) 。 这类并行处理机的应用领域主要用于高速向量或矩阵运算中。 这种s i m d 枫又可分为分毒存储器并行处理机和共攀存储器并行处理机。 目前的大部分并行处理机是基于分布式存储器模型的系统。它有如下特点： 1 1 比较容易构成m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) ，几十万个p e 。 n 必须依靠并行算法来提高p e 的利用率。因此，应用领域很有限。 n c u 是控割部件，执行标量指令，并把向量指令广播到各个p e 中。在c u 中通常有一个较大容量的存储器。 n l o p 是输入输出处理机，或称为主机。在i o p 上安装操作系统，它除了负担 输入输出工作外，还负责程序的编辑、编译和调试等工作。 n 数据在局部存储器中的分布是一个很关键的问题。 建标量指令与向量指令可以并发执行 定义2 。2 并行处理机的操作模型可用五元组来表示： m 一( n ，c ，i ，m ，r ) ， 其中： n 为p e 个数，如i l l i a c l v 有6 4 个p e 。 c 为由控翩部件c u 直接执行的指令集，包括标量指令和程序控制指令。 l 为所有p e 并行执行的指令集，包括算术运算、逻辑运算、数据寻径、屏 蔽以及其它由每个活动的p e 对它的数据所执行的局部操作。 第二章并行语法分析基础与定义 m 为屏蔽操作集，每种屏蔽将p e 划分为允许操作和禁止操作两个子集。 r 是数据寻径集，说明互连网络中p e 间通信所需要的各种设置模式。 2 2 并行系统软件：并行操作系统和并行编译系统 并行系统软件一方面指挥、协调并行计算机运行，另一方面为用户提供并行 计算机的使用界面。因此并行系统软件对充分发挥并行计算机的高性能，对有效 地，方便地使用并行计算机都具有关键作用。并行系统软件主要包括并行操作系 统和并行编译系统