（基础数学专业论文）上下文无关文法的并行识别过程分析与算法的改进.pdf

摘要随着计算机硬件性能和软件设计水平的提高，人们越来越关注软件执行的效率问题，多处理机环境和并行处理已成为软件理论的重要研究内容上下文无关文法并行语法分析是当前计算机理论科学研究的热点，该领域的研究对并行处理机的推广应用具有重要意义，它有力推动着并行编译的识别技术与串行程序并行化的发展本文主要内容包括两部分：第一部分详细讨论了上下文无关文法理论上的一些新发展以及在并行编译中的应用重点介绍两种特殊文法：l l ( 1 ) 文法和乔姆斯基范式的并行处理基础和判定转换的并行算法在编译技术中经常需要判断给定的文法g是否为l l ( 1 ) 文法，对f i r s t 和f o l l o w 集合的求解是很重要的一个步骤本文介绍了一种利用关系矩阵计算f i r s t 和f o l l o w 集合的并行处理方法，对提高并行编译处理效率有一定的理论和现实意义对于非乔姆斯基范式，我们主要针对文法中存在一个规则的右式是两个以上的非终结符相互连接和既有非终结符，又有终结符这两种情况进行讨论重点介绍了非乔姆斯基范式转换成乔姆斯基范式的并行处理方法以及并行转换算法第二部分对上下文无关文法的几种并行识别过程进行分析和比较，并介绍了一些相应的并行算法，对已有算法中的不足进行适当修改，这几种并行语法分析的区别主要在于处理器的存储方式不同，目的都是提高语法分析的效率主要包括：一维线性阵列上的并行语法分析和二维金字塔结构上的并行语法分析以及相应的并行算法并且把这些并行语法分析方法应用于实际例题关键词：识别上下文无关文法语法分析项目乔姆斯基范式a b s t r a c tw i t ht h ed e v e l o p m e n to fc o m p u t e rh a r d w a r ea n ds o f t w a r ed e s i g n i n gm e t h o d s m o r ea n dm o r ea t t e n t i o nh a sb e e np a i dt op a r a l l e lh a n m i n gt e c h n i q u e i “st h em o s ti m p o r t a n tp a r to fc o m p u t e rt h e o r i e s p a r a l l e lc o n t e x t f r e ep a r s i n gi sap o p u l a rr e s e a r c hc e n t e ro fc o m p u t e rs c i e n c e ，t h i sr e s e a r c hi so fg r e a ti m p o r t a n c et ot h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n d 印p l i c a t i o n so fp a r 豇l e lc o m p u t e rs y s t e m i ti ss t r o n g l yb o o s t i n gp r o d u c t i o no fp a t a l l e lc o m p i l i n gf e c o g n i t i o na n dp a t a h e l i z a t i o no fs e r i a lp r o g r a m 8 i nt h i sp a p e r ，t h em a i ns t u d i e si n c l u d i n gt 、v op a r t s ：i nt h ef i r s tp a r t ，s o m ed e v e l o p m e n to fc o n t e x t f r e eg r a m m a r s ，a n da p p l i c a t i o n si np a r a l l e lc o m p i l i n gi se x h a u s t e d t w os p e c i a lg r a m m a r sa r ei n t r o d u c e d ：l l ( 1 ) g r a m m a r sa n dc o m k e yn o r m a lf o r m b e s i d e s ，s o m ea c c o r d i n ga l g o r i t h m s i nf a c tw eo f t e nc o n f r o n tt od e c i d ew h e t h e r8g i v e ng r 锄m a ri sl l ( 1 ) ，a n dt h e nt h em o s t mi m p o r t a n ts t e pi st oc o m p u t ef i r s ta n df o l l o w s ow ei n t r o d u c ean e wm e t h o dt oc o m p u t et h e m t 0c h o m k e y ，c o n s i d i n ga tt h er i 曲t s i d eo fap r o d u c t i o no fg i v e ng r a m m a r ，i ft h e r ea r em o r et h a nt w on o n _ t e r m i n a l so rb o t hn o n t e r m i n a l sa n dt e 珈a i n a l st o g e t h e r ，t h em a i np u r p o s ei st oi n t r o d u c et h ew a yt oc o n v e r ti ti n t oac h o m s k yn o r m a lf o r mi np a r a l k l ，a n da l g o r i t h m s i nt h es e c o n dp a r t ，s o m en e wr e s u l t so fp a r “l e la l g o r i t h m so nc o n 七e x t f r e er e c o g n i t i o na n dp a r s i n ga r ed e s c r i b e d ，a n dm a k es o m er e p a i rt os o m eo ft h e s ea l g o r i t h m s i n c l u d j l l gp a r a n e la l g o r i t h m so no n e d i m e n s i o na n dt 、v o d i m e n s i o n ，a n da p p l i e dt op r a t i s e k e yw o r d s ：r e c o g n i t i o n ，c o n t e x t f r e eg r 锄m a r ，p a r s i n g ，i t e m s ，c h o m s k yn o r m 出f o r m第一章绪论本章中，我们的主要目的就是通过对并行汁算机和并行算法的简单介绍，使读者明确并行语法分析的重要意义和研究价值，深化对并行语法分析理论的理解1 1 引言计算机的诞生是人类社会发展史上一个重要的里程碑，利用计算机能够显著地提高人们的工作效率和生活质量，因此计算机得到了迅速普及，广泛应用于各行各业在一些重要的实际应用中，都要求迅速而准确地进行计算和处理，这就需要从各个方面设法提高计算机的性能和运算速度雨如何提高和怎样提高就成了计算机科学理论中一个重要的研究课题，近十几年来，在全球信息化大潮的推动下，随着电子技术的快速发展，我国的计算机产业发展迅猛计算机元件的运算速度也有了惊人的提高，现在已经接近电子传输的物理极限，没有很大提高的可能要提高计算机的运行速度，仅靠加快计算机元件的运算速度是不可能的，就只有从计算机的内部入手，对其内部结构进行改造，把计算机传统的串行结构改造成并行结构，从而开始了对并行计算和并行语法分析的研究( 可参考文献 1 ) 并行计算是2 1 世纪科学与工程计算的主旋律，在自然科学中大量前沿学科问题的解决，都已由实验为主向以计算为主转化并行计算就是在并行计算机或分布式计算机等高性能计算系统上所做的超级计算，其物质基础是高性能并行机在并行计算机上进行并行计算，可以更好的发挥并行计簧的效率，也可以提高计算机的性能( 可参考文献 2 ) 1 2 并行计算机、并行算法与并行语法分析基础普通的一台计算机一般只有一个处理器，即使是最快的处理器也不能满足实际运算的需要为了进一步提高性能，就需要更多的处理器，这类有多个处理器的计算机就际为并行计算机并行计算机是使用多台计搏机协同工作的一种高性能计算机系统第一章绪论从上个世纪9 0 年代以来，并行计算机一直是世界各国计算机领域的主要研究课题利用商陛能并行计算机，可以解决许多领域中一般计算机和一些仅靠理论和实验方法无法解决的问题，对于一些涉及计算公式复杂、计算量大、时效性强、人工根本无法完成的问题，用一般计算机也许需要数月甚至几年、几十年的时间，必须采用高性能并行计算机才能处理( 可参考文献f 3 】) 高性能并行计算机是现代科学技术研究，工程技术开发和大规模数据处理的关键技术，是促进社会进步、国防安全、经济与科技发展的重要工具它代表着一个国家计算机研制水平的高低，也是解决大型计算问题的唯一有效途径，体现着一个国家的综合实力随着大规模集成电路技术的不断进步，高性能并行机得到了迅速地发展，如何使高性能并行机系统充分深入地在国民经济，科技和社会应用发展中发挥作用实为当务之急，已引起人们普通关注为使高性能计算机运算成本合理而有效，采用并行处理技术，进行并行计算，已经成为世界各国科技竞争的战略制高点高性能计算机的峰值性能与其实际应用水平差距很大并行计算是提升运算效率、缩小这一差距的重要理论基础经过多年的发展，我国在并行算法的研究上也取得了显著成绩，并行计算的应用已在天气预报、石油勘探、航空航天、生命科学、材料工程、理论研究与应用普及中均取得了很大发展参考文献【4 ) 环境科学、核能利用、生物工程等领域的是这些领域不可缺少的高端计算工具( 可并行语法分析与识别是当前理论计算机科学研究的热点，该领域的研究对计算机学科发展和并行计算机、处理机的推广应用有着重要意义，是推动并行编译的识别与并行计算机运行速度的发展的理论依据并行语法分析是并行编译过程的一个逻辑阶段主要的任务是在词法分析的基础上将单词序列组合成各类语法短语，如程序、语句、表达式等等语法分析程序可以判断源程序在结构上是否正确，源程序的结构由文法来描述对并行语法分析的研究已经成为现代计算科学的主攻方向之一1 3 发展现状和前景上世纪7 0 年代末，我国第一台巨型计算机银河i 的研制工作在国防科技大学启动经过数十年努力，先后研制出了曙光系列并行机，如曙光1 号、曙光l ( 】0 0 和曙光删) ( ) 分别属于s a i p 和、i p p 系列并行机j ! j 午9 月，由国家并行计算机工程技2第一章绪论3术研究中心牵头研制成功的神威计算机系统投入运行神威的峰值速度为每秒3 8 4 0亿次浮点运算，其主要技术指标和性能均达到国际先进水平( 可参考文献【5 ) 这些应用技术的理论基础是并行计算和并行语法分析，这一系列并行机取得了显著的效益，为我国经济建设和科学研究发挥了重要的作用，将并行算法和语法分析的研究向前推进了一大步它标志着我国成为继美国、日本之后，世界上第三个具备研制高性能计算机能力的国家，从而打破了西方某些国家在这一领域对我国的限制目前，对并行算法和语法分析的研究是计算机理论科学的热门，对国民经济的发展起着重要的推动作用，是解决并行计算机效率的理论基础，并行算法计算性能和语法分析复杂度是高端、高性能、大规模并行计算领域非常重要的研究内容研究重点大部分在并行算法改造与语法分析并行实现技术两方面，以提高计算速度和降低算法复杂度为主要目标( 可参考文献【6 ) 并行算法和语法分析的研究是当代计算机科学发展的需要，是进一步提高并行机应用范围的需要随着网格技术的发展和应用软件的进一步丰富，可以预见不远的将来会出现高性能计算的时代由此高性能计算的战略意义和产业前景更加重要，作为其理论基础的并行算法和语法分析自然成为研究的中心环节，是所要研究的核心问题1 4 结构与安排本论文分共有五个章节介绍第一章是绪论，简单介绍并行计算机、并行算法与并行语法分析理论的基本概念、联系和熏要意义，以及发展现状和未来前景第二章主要介绍并行算法的应用背景，包括并行算法的定义、分类、性质、描述和设计方法及过程技术等第三章主要介绍用于语法分析的设计算法分析，包括文法、上下文无关文法的基础概念，以及上下文无关文法的一些新的发展，包括l l ( 1 ) 文法判定的并行算法和一般文法到乔姆斯基范式转换的并行算法第四章主要对几种并行语法分析算法的进行比较包括并行语法分析的基本理论、线性阵列上的并行语法分析算法的分析与改进、金字塔结构上的并行语法分析算法、对几种算法的分析与比较和这些算法在实际并行语法分析中的应用第二章并行算法应用背景f l = i 并行计算机求解问题时，必须把问题分解成能够并行求解的子问题，而后这些子问题的结果需要进行高效的重新组合得到主问题的最后结果，把每个非常大的问题分成千问题很不容易的，这是因为子问题之间可能存在数据相关性由于数据相关性，处理器之间必须相互通信。需要考虑的重要因素还有通信时间，为了达到效率较高的并行处理方法。对并行算法进行详细而系统地研究是很重要的在这一章里，我们主要介绍并行算法的一些相关理论，包括并行算法的定义、性质、描述和分类等的一些基本知识，为后面内容的学习提供理论依据2 1 并行算法的定义及分类2 1 1 并行算法的定义定义2 1 1 算法是对解题方法的精确描述，是求解问题的方法和步骤它是一组有穷的规则，它们规定了解决某特定类型问题的一系列运算定义2 1 2 并行算法是用多台计算机联合求解问题的方法和步骤，是一些可同时执行的诸进程的集合，这些进程之间互相作用和协调动作，从而达到对给定问题的求解并行算法，就是指在各种并行计算机上求解问题和处理数据的算法本质是把多任务映射到多处理机中执行，或将现实的多维问题映射到具有特定拓扑结构的多处理机上求解( 可参考文献 7 限研究并行算法的主要目的是提高计算速度并行算法是并行计算机的理论基础并行计算机性能是否能够充分发挥，都依赖于对并行算法的研究；并行算法的研究又和并行计算机的结构关系密切并行算法是挖掘高性能并行计算机效率的关键技术之一，是并行计算技术最熏要的理沧基础通俗地说，它是使用多台计尊机联合解决一个问题的算法它对推动高性能并行计算机的应用起着至关重要的作用现在，并行算法之所以受到极大的重视，是为_ 提高计算速度【单机受物理速度限制尢法满足) 、提高计贸精度( 加密、计算网格等j 以及满足实时计算需萼( 数值天限制无法满足) 、提高计赞：精度( 加密、计算网格等) 以及满足实时计算需耍( 数值天4 一第二章并行算法应用背景气预报等)2 1 2 并行算法的分类并行算法可以从不同角度加以分类( 可参考文献 8 】) ：1 按照基本运算对象的不同可分为以下两类：( 1 ) 数值并行算法：主要是为数值计算方法而设计的并行算法，例如：矩阵运算、多项式求解、解线性方程组等( 2 ) 非数值并行算法：是指为基于关系运算的一类并行算法，例如：神经网络算法、遗传算法、演化算法、格子气算法、符号计算、排序、选择、分类、搜索和匿论等非数值计算而设计的并行算法2 按照并行进程间执行顺序关系的不同可分为以下三类：( 1 ) 同步并行算法：是指某些进程必须等待其它进程的一种并行算法，要求所有的进程必须在一个给定的时刻同步例如：向量算法、s i m d 算法、m i m d 并行机上进程间需要相互等待通信结果的算法等；( 2 ) 异步并行算法：是指诸进程的执行相对独立，不需要相互等待的一类并行算法进程间的通信一般是通过动态地读，取( 修改) 共享存储器的全局变量如通常运行在m i m ds m 机模型上的并行算法；( 3 ) 独立并行算法：是指进程间执行是完全独立的，计算的整个过程不需要任何通信，例如气象预报应用中通常需要同时计算多个模型，以保证预报的实时性3 按照各处理器承担的计算任务粒度的不同，可分为以下三类；( 1 ) 细粒度并行算法：通常是指基于向量和循环级并行的算法；( 2 ) 中粒度并行算法：通常是指基于较大的循环级并行，并且并行的好处足以弥补并行带来的额外开销的算法；( 3 ) 大粒度并行算法：通常是指基于子任务级并行的算法，例如：基于区域分解的并行算法，它们是当前并行算法设计的主流任务粒度的划分依赖于所使用的并行计算系统的计算和通信的比值第二章并行算法应用背景2 2 并行算法的性质并行算法的性质，主要包括并行算法的复杂性和对并行算法性能的评定等2 2 1 并行算法的复杂性度量并行算法的复杂度的渐进表示：对算法进行分析时，经常使用上界，下界和紧致界等一些概念( 可参考文献【8 】) ，现在把这些定义描述如下：定义2 2 1 令f ( n ) 和g ( n ) 是定义在自然数集合n 上的两个函数，如果存在两个正常数c 和n o ，使得对于所有n n o ，均有f ( n ) c g ( n ) ，则称g ( n ) 是f ( n ) 的一个上界记作：f ( n ) = o ( g ( n ) ) 定义2 2 2f ( n ) 和g ( n ) 的定义如上，如果存在两个正常数c 和n 。，使得对于所有n n o ，均有f ( n ) g ( n ) ，则称g ( n ) 是f ( n ) 的一个下界记作：f ( n ) = q ( g ( n ) ) 定义2 2 3f ( n ) 和g ( n ) 的定义如上，如果存在两个正常数c 1 ，c 2 和n o ，使得对于所有n n o ，均有c ，g ( n ) f ( n ) c 2 9 ( n ) ，则称g ( n ) 是“n ) 的一个紧致界记作：f ( n ) = o( g ( n ) ) 定义2 2 4 在分析某些输入时，使得算法的时间、空间复杂度出现最坏情况下的算法复杂度，称之为最坏情况下的复杂度定义2 2 5 如果求解一个问题并行算法的成本，在数量级上等于最坏情况下串行求解此问题所需要的执行步数。则称此并行算法是成本最优的2 2 2 并行算法的性能评价在分析并行算法时，经常要分析的几个指标有( 可参考文献【8 卜 1o ) ：( 1 ) 运行时间t ( n ) ：就是算法运行在给定模型上求解问题所需要的时间，它是输入n 的函数，通常包含计算时间和通信时闻，分别用计算时间步和选路时间步作单位( 2 ) 处理器数p ( n ) ：它就是求锯绘定问题所用鲍处理器数目，通常取p ( n ) = m 七o i l 是常见的( 3 ) 并行算法的成本c ( n ) ：它是定义为并行算法的运行时间t ( n ) 与其所需要的处理器数目p ( n ) 的乘积，即c ( n ) = t ( n ) 。p ( n ) ，( 4 ) 加速比( s p e e d u p ) 加速比定义为串行时间与并行时间的比，并行算法在用n第二章并行算法应用背景个处理器解决问题时的加速度定义为s ，( n ) = t 。( n ) b ( n ) 其中：t 。( n ) 是求解一个问题的最快的串行算法在最坏情况下的实际执行的时间t ，( n ) 是求解同一问题的并行算法在最坏情况下的运行时间，即：使用p 台处理机时算法实际执行时间加速比是一种度量并行算法的量值，它是评价算法的并行性对运行时间改进的程度用于比较一个算法在单处理机上的执行时间与在p 台处理机上的执行时间，加速比最大不超过处理机个数，但是并行算法在单处理机上并非是一种好的算法因此，加速比可以修改为：s ，( n ) = t 。，( n ) t ，( n ) 其中：t 。，( n ) 是求解问题的最快的串行算法在最坏情况下的运行时间，b ( z ) 同上( 5 ) 效率：效率是和加速比关系密切的性能尺度，它是加速比s ，( n ) 和处理器个数p ( 1 1 ) 的比，并行算法的效率定义为：耳( n ) - s ，( n ) p ( n ) ，它反映了并行系统中的处理器的利用情况，并且o b ( n ) 1 ( 6 ) 并行算法的可扩放性：并行算法的可扩放性，是在确定的应用背景下，算法( 或程序) 的性能是否随问题规模和处理器数目的增加而按比例提高它是评价并行算法的重要性能指标之一如果系统的性能随着系统规模( 问题规模和机器规模) 的增加而增加，那么该并行算法是可扩放的可扩放性度量标准包括：等效率、等速度和平均延迟等度量标准2 3 并行算法的描述在描述算法时，可以用自然语言进行物理描述，也可以使用某种程序设计语言进行形式化描述语言的选用应避免二义性，力图直观易懂描述并行算法时，算法的表达与在串行情形下的算法的表达大体相同，所有描述串行算法的语句及过程调用均可使用，需要增加的只是表达并行性的几种所谓的并行语句( 可参考文献 1 l 】 1 3 】) ，为了表达并行性而引人了并行语句有：当从第i 步到第j 步的语句要并行执行时，可以用如下形式的并行语句来表达d os t e p i t o j ，i 1 1p f l l a l l p ls t e p i ：；s t e di + l ：7第二章并行算法应用背景s t e p j ：当所有的处理器要并行执行同一组操作时，可以用如下的几种形式的并行语句之一来表达：f b re a c hp r o c e s s o ri ，i np a r a l l e ld ob e g i n；e n d ：或者：f o ra l l ip a r a l l e l l yd ob e g i ne n d ：当要求编号为i 到j 的处理器并行执行同一组操作时，可以用如下形式的并行语句来表达f b rk ：= it oji 1 1p a r a l l e ld ob e g i ne n d ：其中，当算法的若干步要并行执行时，”i np a r 甜i e l ”常常简写为”p a r - d o ”，为了简洁，在意义明确的前提下，一些变量可以省去其类型说明而直接引用，例如：f b ri = 1t onp a r d ( )e n df o r当n 个处理器同时执行相同的操作时，可以使用f o r d o 语句描述之f b ra 1 1p jw 1 1 ( r eo i kd oe n d f o r第二章并行算法应用背景术2 4 并行算法的设计本节主要介绍并行算法设计的一些理论，包括并行算法的设计方法和基本设计技2 4 1 并行算法的设计方法并行算法的设计方法是利用并行处理机系统求解一个给定的问题，需要根据系统的类型和特征设计并行算法任何并行算法的设计都是给予某一特定的并行计算模型，而并行计算模型是从各种具体的并行机中抽象出来的，它能在一定程度上反映出具体并行机的属性，又可以使算法研究不再局限于某一种具体的并行机上( 可参考文献【8 】、 1 4 、【1 5 】) ，设计并行算法通常有三种方法：( 1 ) 串行算法的直接并行化，即；检测和开发现有的串行算法中固有的并行性而直接将其并行化；( 2 ) 从问题本身的特征出发，从头开始设计一个新的并行算法；( 3 ) 修改已有的并行算法，使其可求解另一类相似问题但是，我们需要说明的是：并非任何串行算法都可以产生好的并行算法，对一类具有内在顺序性的串行算法，难于直接并行化如果在算法的执行步中，每一步都要用到上一步的计算结果，那么，这样的串行算法是无法并行执行的，一个不好的串行算法有可能产生好的并行算法；修改已有的并行算法依赖于特定的一类问题；设计全新的并行算法，技术上不成熟，又有些技巧2 4 2 并行算法的基本设计技术并行算法的基本设计技术( 可参考文献 1 4 卜 1 6 ) ，包括有：1 划分设计技术划分原理( p a r t i t i o n i n gp “n c i p i e ) ，又叫做分组原理，使用该原理求解问题时，可以分个步骤：( 1 ) 将给定的问题分成p 个独立的几乎等尺度的子问题；( 2 ) 用p 台处理器并行求解诸子问题2 分治设计技术分治( d i v j d ea n r lc o n q u e r ) 策略是一种问题求解的方法学，其思想是将原问题分第二章并行算法应用背景解为若干个特征相同的子问题分而治之，并且可以反复使用该技术直至很容易求解诸子问题，子问题的类型和原问题的类型是相同的它和划分策略的相同点是都是将原问题分解成可并行求解的子问题，但是分治的侧重点是予问题的归并上，而划分的侧重点是在划分上，使得子问题的解容易组合成原问题的解3 平衡树设计技术平衡树方法是将输入元素作为叶节点，构造一棵平衡树，然后，自叶向根往返遍历这种方法对数据的播送、压缩、抽取和前缀计算很有效果4 倍增设计技术( d o u b l i n gt e ( 、h n i g u e )也称做指针跳跃( p o i n t e rj u m p i n g ) ，这种方法特别适合处理以链表或有向有根树之类表示的数据结构，广泛应用于图论和链表算法中5 流水线设计技术流水线设计技术是一种重要的并行技术，其基本思想是将一个计算任务分成一系列子问题，使得第一个问题完成后，后面的子任务可以立即开始，并且以相同的速率进行计算6 加速级联技术加速级联技术是为了获得快速最优的算法，将一个最优但相对不快的算法和一个非常快的但不是最优的算法级联( 也称为串接，c a s c a d i n g ) 起来，形成一个加速级联算法7 破对称技术破对称( s y m m e t r yb r e a k i n g ) ，就是打破某些问题的对称性1 0 第三章用于语法分析的设计算法分析在本章，我们介绍一些传统上下文无关文法相关的理论，以及上下文无关文法理论的一些新发展和并行编译中应用主要内容包括对l l ( 1 ) 文法判定的并行算法和对乔姆斯基范式进行转换的并行算法3 1 语言和文法高级程序语言是用来描述算法和计算机实现这双重目的的，对于高级程序设计语言及其编译程序而言，语言的语法定义非常重要文法是描述语言的语法结构的形式规则( 即语法规则) 这些规则必须是准确的，易于理解的，并且，应当有相当强的描述能力，足以描述各种不同的结构有这种规则所形成的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序克林( k l e e n e ) 在1 9 5 1 1 9 5 6 年间，从识别的角度研究语言，给出了语言的另一种描述，他在研究神经细胞的过程中，建立了自动机，他用这种自动机来识别语言，对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言这个语言由该自动机所能识别的所有句子组成文法的概念是语言学家们在研究自然语言的理解时完成形式化的，对一种自然语言，如果能找到一个形式文法，贝4 对这个语言的自动理解是非常有用的为统一起见，我们把n 可以是p 表示成i p ，使用该规则，可以得到一系列的句子文法的概念是语言学家们在研究自然语言的理解时完成形式化的，对一种自然语言，如果能找到一个形式文法，则对这个语言的自动理解是非常有用的为统一起见，我们把。可以是p 表示成。一芦，使用该规则可以得到一系列的句子语言学家乔姆斯基( a v r 锄n o a n lc h o m s k y ) 最初从产生语言的角度研究语言，通过抽象他把语言形式地定义为一个字母表中的字母组成的串的集合：对任何语言l有一个字母表、使得l + ，对一类语言，可以在字母表上按照一定的顺序，根据语言的语法结构特点，定义一个文法( g r m m n a r ) ，该文法产生的所有句子组成的集合就是该文法产生的语言用文法作为相应语言的描述，不仅可以描述出语言的结构特点，而且还可以产生这个语言的所有句子1 9 5 9 年，乔姆斯基通过深入地研究，他第三章用于语法分析的设计算法分析把自己的研究成果和克林的研究成果结合起来，确定了文法和自动机分别从生成和识别的角度去表达语言，证明了文法与自动机的等价性，提出了一种用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言，形式语言形式语言建立后，很快就在计算机科学与技术领域得到了广泛地应用，在对计算机科学与技术学科人才的计算思维的培养中占有极其重要的地位，深刻地影响了计算机科学的发展( 可参考文献 1 7 1 ) 乔姆斯基根据产生语言的文法的特征，把文法分成四种类型：即o 型、1 型、2型和3 型o 型强于1 型，1 型强于2 型，2 型强于3 型，这几类文法的差别在于对产生式臆加不同的限制定义3 1 1o 型文法g 定义为一个五元组，即g = v ，v r ，p ，s ，其中：v 是非空有限集，它表示文法的所有非终结符组成的集合，其元素用大写字母a 、b 、c 、( 可以带下标，也可以不带下标，以下同) 表示；v t 是非空有限集，它表示文法的所有终结符组成的集合，其元素用小写字母a 、b 、c 、- 表示；是非空有限集，表示文法的所有符号组成的集合( 有限) ，即= v _ u v r ，1 v 1 表示文法中的非终结符的总个数，i v 引表示文法中的终结符的总个数，并且有v n v r= 由，= v u v 丁表示文法中所有符号的总个数，v t 表示终结符组成的串的集合( 包括空串由) ，集合e + = ( v u v j ) 4 表示由非终结符和终结符连接组成的串的集合，其元素用希腊字母d 、芦、，y 、表示；s 表示文法的开始符号，且s v ：p 表示产生式的有限集合，每个产生式是形如q p 的推导规则( o ，p + ) ，。中至少含有一个非终结符，n 称为产生式的左部，卢称为产生式的右部，且不允许出现形如n o 的产生式；文法的开始符号s 至少要在某个产生式的左部出现一次，3 2 传统的上下文无关文法定义3 2 1 一个( ) 型文法g = ( n ，p s ) 称之为上下文无关文法( c o n t e x t f r e eg r a m m a r 简记为c f g ) ，如果对它施加了如下的限制：文法g 的任何产生式都是形如a 一的推导规则，在这里a v 、n p 1 2第三章用于语法分析的设计算法分析1 3 一在计算机科学中，上下文无关文法是应用最广泛的一种形式语言，是语法分析中经常考虑的一种文法上下文无关文法( c f g ) 是这样的一种文法：它所定义的语法范畴( 或语法单位) 是完全独立于这种范畴可能出现的环境其特点是在对非终结符进行替换时不需要联系上下文，并且可以替换成空串它的能力足够用来描述现今大多数的程序设计语言的语法结构上下文无关文法取名为上下文无关的原因，就是因为字符v 总可以被字串w 自由替换，而无需考虑字符v 出现的上下文一个形式语言是上下文无关的，如果它是由上下文无关文法生成的上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有的程序设计语言都是通过上下文无关文法来定义的上下文无关文法足够简单，使得我们可以构造有效的分析算法来检验一个给定字符串是否是由某个上下文无关文法产生的例如：文法g ：s _ a s ebb b b ecc c c e1d就是一个上下文无关文法本文提到的文法，如果未加说明郝是指上下文无关文法3 3 两种特殊的上下文无关文法在上下文无关文法中，有两种特殊的文法，即：l l ( 1 ) 文法和乔姆斯基范式，下面。我们分别介绍这两种文法3 3 1l l ( 1 ) 文法本节主要介绍l l ( i ) 文法及对其进行判定的并行处理方法和并行算法3 3 1 1 预备知识l l ( 1 ) 文法可以对输入的字符串进行有效的无回溯自上而下的语法分析定义3 3 1 1 如果一个上下文无关文法g ，满足以下三个条件：第三章用于语法分析的设计算法分析( 1 ) 文法不含左递归；( 2 ) 对于文法中每一个非终结符a ，它的各个产生式的侯选首符集两两不相交，即：若a - l i n 2 1 - - io 。，则f i r s t ( q 。) n f i r s t ( o ，) = 中；( 3 ) 对于文法中每一个非终结符a ，如果它存在某个侯选首符集包含8 ，则f i r s t ( a ) n f o l l 0 w ( a ) = 中；那么称该文法g 为l l ( 1 ) 文法由该定义，可得判定一个上下文无关文法g 是否为l l ( 1 ) 文法有三个步骤：( 1 ) 消除左递归；( 2 ) 计算每个产生式的侯选首符集和每个非终结符a 的f i r s t ( a ) 和f o l l o w ( a )( 3 ) 判断文法是否为l l ( 1 ) 文法消除左递归的方法是：如果关于a 的所有产生式是：a ，a l i a q 2 - i a 。l p l l p 2 p 。其中；对任意i ，1 曼i n ，有。e ，并且觑都不以a 开头那么消除a 的左递归就是把产生式改写为：a - p l a 。| 臼2 ai i 风a 。a 7 ，0 1 a l q 2 a i i q 。a 7 i 由f i r s t 和f o l l 0 w 集合的定义，可得：f i r s t ( a ) = ai a j + a 一，a v t f o l l o w ( a ) = a1 s = 4 a a - ，a v 丁)其中：a v 很容易看出，事实上，f i r s t ( a ) 是非终结符a 能够推导出的所有符号串中处于串首的终结符号组成的集合f o l l 0 w ( a ) 是文法开始符号s 的推导式中紧跟在非终结符a 后面的所有终结符组成的集合在参考文献 1 7 】中，采用建立文法的预测分析表的方法，根据分析表是否含多重入口来判断文法是否为l l ( 1 ) 文法在编译技术中，对给定的文法g ，判断它是否为l l ( 1 ) 文法，需要先进行l l ( 1 ) 条件判定和构造l l ( 1 ) 分析表，其中，对f i r s t 和f o l l o w 集合的求解是很重要的一个步骤而这两个集合的求解过程可采用集合算法和矩阵算法等方法关于矩阵乘的并行算法已有较多研究成果对f i r s t 和f o l l o w 集合采用矩阵算法除占用较大空间外，在f i r s t 和f o l l o w 交集运算等方面也存在劣势般说来，终结符和非1 4第三章用于语法分析的设计算法分析1 5 一终结符的数值较大，因此，按照分而治之的思想可以考虑计算f i r s t 和f ( ) l l o w集合的并行处理方法，对提高并行编译处理效率有一定的理论和现实意义我们知道上下文无关文法的每个产生式是形如a o 的推导规则( a v n ，q+ ) ，所以在产生式的右边，可能出现s ，s 。s ，或者s 。岛等各种情况( s 。，s ，v n u v r ) 为能快速而准确的并行计算出f i r s t 和f o l l o w 集合，顺利进行文法判定，我们进行如下的约定：在上下文无关文法g 中，设文法g 的开始符号为s ，用m ，n 分别表示集合v 和集合v 了_ 中的元素个数，记作：m = iv _ i ，n = i v 丁l ，且字母表= v u v 了、西=v n v 丁定义3 3 1 2 设s k v ，s ；，s ，v u v t ( k = 1 ，2 ，一，m ；i j = l ，2 ，一，m + n )( 1 ) 若存在产生式：s k s 。，则称s k s t a r t - s ，；( 2 ) 若存在产生式：s 一s 。s ，则称相对于s ，有s 。r i g h t s ，定义3 3 1 3 设s k v ，s 。，s ，v _ u v t ( k = l ，2 ，一，m ：i ，j = 1 、2 ，- ，m + n )( 1 ) 若存在推导式：s k = 争+ s 。，则称s k f i r s t s ，；( 2 ) 若存在推导式；s 号t s 。s ，则称& f o l l o w s ，规定：( 1 ) 若s _ e 、则s k f i r s t ；( 2 ) 若s 一s 。则s 。f o l l o w # 由定义3 3 1 2 和定义3 3 1 3 可得如下定理：定理3 3 1 1 设s t v n ，s j v 7 ，( i = 1 ，2 ，m ；j 一1 ，2 ，n ) ；( 1 ) 若s 。s t a r t s 。则s 。f i r s t s j( 2 ) 相对于s ，若有s 。r i g h t 髟，则s f f o l l 0 w s j证明( 1 ) s 。s t a r t s j ，由定义3 3 1 ，2 ( 1 ) 可得，存在产生式：s 。一s j ，故存在推导式：s ，= 岛，由定义33 1 3 ( 1 ) 可得：s t f i r s t s j( 2 ) 相对于s ，s 。r i g h t - s ，由定义3 31 2 ( 2 ) ，可得存在产生式：s s t s j ( s j v _ ) ，故存在推导式：s s s j ，由定义33 1 3 ( 2 ) 可得：s ，f o l l ( ) w s j 定理3 3 1 2 设s ，s ，v n ；s7 v r ( k ，i ，= 1 ，2 ，肌；卢l ，2 ，n ) ；( 1 ) 若s s r a r t s ，s ，s t a r t s f ，则s f i r s t s ，第三章用于语法分析的设计算法分析( 2 ) 若s r i g h t s t ，s l s t a r t s j ，贝0s k f ( ) l l 0 w s j证明( 1 ) 由s s t a r t s 。由定义3 3 1 2 ( 1 ) ，可得存在产生式s 一s 。，又由s 。s t a r t s ，；由定义3 3 1 ，2 ( 1 ) ，可得存在产生式s t s j ，故存在推导式：s 号s 。= s ，由定义3 3 1 3 ( 1 ) ，可得s - f i r s t s ，( 2 ) 由s 女r i g h t s e ，由定义3 3 1 2 ( 2 ) ，可得存在产生式：s 。一s s ( s 。v ) 由s 。s t a r t - 岛，由定义3 31 2 ( 1 ) ，可得存在产生式：s 。一岛，故存在推导式；s 。j s s 。号s 岛，由定义3 3 1 3 ( 2 ) ，可得s k f o l l o w s ，定理3 3 1 3 设s k ，s 。v ，s ，v t ；( k ，i = l ，2 ，m ；j - 1 ，2 ，n )( 1 ) 在同一产生式中，若同时有s - s t a r t s t ，s 。r i g h t s f ，且在文法g 中有s 。f i r s t e ，贝0s k f i r s t s ，；( 2 ) 在同一产生式中，若同时有s r i g h t s 。，s 。r i g h t s f ，且在文法g 中有s t f i r s t - 6 ，贝0s k f o l l o w s ，证明( 1 ) 在同一产生式中，有s 女s t a r t s 。s - r i g h t s ，由定义3 3 1 2 ( 1 ) ，( 2 )可得存在产生式s 一s 。s ，又由s 。- f i r s t ，由定义3 3 13 ( 1 ) 可得可得存在产生式：s 。一e ，故存在推导式；s 女令s 。岛jes ，号s ，由定义3 3 1 3 ( 2 )可得s k f i r s t s ；( 2 ) 在同一产生式中，有s k r i g h t s t ，s t r i g h t s ，、由定义3 3 1 2 ( 2 ) 可得存在产生式：s 。一s 女s t ，s 。v ，又s ，f i r s t ，由定义3 31 3 ( 1 ) 可得存在产生式：s ；一，故存在推导式：s 。号s s 。s ，辛s 8s ，寺s 舯，由定义3 3 1 3 ( 2 ) 可得s f o l l o w s f 综合定理3 3 1 1 ，定理3 3 12 ，定理3 ，3 ，1 3 可得：( 1 ) a - f i r s t a ，即a f i r s t ( a ) 有以下几种可能的情形：( 1 1 ) a s t a r t a ；( 1 2 ) a s t a r t - s 1 ，s 1 s t a r t s 2 ，s t s t a r t f l ( i _ 1 ，2 ，n 1 + n ) ：( 1 3 ) 在同一产生式中，有a s r a r t s 。，s 。r i g h t a ，且在文法g 中有s 。f i r s t ( 2 ) a f o l l o w a ，即a f o l l o w ( a ) 有以下几种可能的情形：( 2 1 ) a r i g h ta ；( 22 ) a r i g h t s 1 ，s 1 s t a r t s 2 ，- ，s s t a r t a ( i = l ，2 ，1 1 1 + 1 1 ) ：1 6 一第三章用于语法分析的设计算法分析1 7 一( 2 3 ) 在同一产生式中，有a r i g h t s t ，s ，r i g h t a ，且在文法g 中有s 。f i r s t ，在上下文无关文法g 中，我们用m 。，m r ，m ，m f 分别表示s t a r t ，r i g h t ，f i r s t ，f o l l o w 的关系矩阵由文法g 的产生式可得关系矩阵m 。和m r ，则m ，和m r 都是mx ( m + n ) 阶矩阵，关系矩阵m 。中的元素为：ils s 丁a r 丁岛io否则s t r l g h t s j否则利用m 。，m r ，m ，m f 并行计算f i r s t ( a ) 和f o l l 0 w ( a ) 集合的算法可见参考文献 1 8 和 1 9 】，下面我们考虑符号串u 的f i r s t 集合：f i r s t ) = tuj + t ，t v t ) ，即：f i r s t ) 是符号串u 能够推导出的所有符号串中处于串首的终结符号组成的集合( 包括) 不妨设u = a 1 8 2 a 。，那么