（计算机软件与理论专业论文）高效扩增式ll语法分析并行化扩充.pdf

摘要 随着并行技术和并行语言的发展，处理并行语言的并行编译技术，将串行程序转换 成并行程序的自动并行编译技术正在深入研究之中。语法分析是编译系统设计最重要的 内容之一，而扩增式语法分析广泛的用于基于语言编辑器，扩增式编辑和译码环境中。 在这些环境中，最经常执行的操作是对改进输入串的重新语法分析，它的效率能极大的 影响这些环境的成功 本文描述了对应用于支持最小化l l ( 1 ) 重新语法分析的语法分析树中线性链接和l l 预测分析表中附加距离入口的简介随后，线索化语法分析树和扩增式l l 预测分析表 被用于生成一个高效的扩增式l l 语法分析。然后又具体讨论了在并行化环境下对这个 高效的扩增式语法分析的分析和改进，给出一个改进的并行化扩增式l l 语法分析算法， 并用一个实例进行详细分析。文章的最后还针对该并行算法在数学表达式分析过程中局 部树的相同变换重复替换问题进行了探讨，并给出了该并行算法在数学表达式语法分析 过程的特殊作用的相关结论。 本文通过在并行环境下对构建高效扩增式l l 语法分析的详细分析和讨论，对提高 扩增式l l 语法分析效能有其实践意义，从而也为进一步讨论在并行环境下的数学表达 式分析打下了良好的理论基础。 关键词：语法分析，l l ( i ) 文法，线索化语法分析树，扩增式语法分析，并行 a b s t r a c t b yt h ed e v e l o p m e n to f t h ep a 越l e lt e c h n i c a la n dp a r a l l e ll m i g u a g o , t h ep a r a l l e lc o m p n et e c h n o l o g yo f p r o c e 嚣i n gp a r a l l e ll a n g u a g e , t h e 锄j t o m 砒cp a r a l l e lc o m p i l et e c h n o l o g yo fc h a n g e 翻：r i a lp r o c e d u r et ot h e p a r a u e lp r o c e d u r ei st h 饵翻蛐t os t u d y t h ep a i s m gi so o ft h em o s ti m p o r t a n tc o n t e n t so ft h e c o m p i n gs | y s t e md e s i g n s , a n di n c 托m e n t a lp a r s i n gi sw i d e l yu s e di nl a n g u a g e - b e de d i t o r , i n c r e m e n t a l m l i l i n ga n di m 哪鹏d i l ge n v i r o n m e n t i nt h e s ee n v i r o n m e n t sr e - p a r s i n go f m o d i 矗e di n p u ts t r i n 笋i st h e m o s t f i e q u e n t l y p e r f o r m e d o p e r a t i o n , i t se f f i c i e n c y 啪g r e a t l y a f f e c t t h e 飘砧c e 嚣o f t h e s e e n v i r o n m e n t s 1 1 l i sp a p e rd e s c r i b e st h ed e s c r i p t i o no f at h r e a d e dl i n ki np a r s ei r e s sa n d 雒a d d i t i o n a ld i s t a n c ee n t r y 缸l lf o r e c a s tp a r s et a b l e st 0s u p p o r tm i n i m a lu l ( 1 ) r e - p a r s i n g t h r e a d i n gp a r s et r e e sa n di n c r e m e n t a ll l p a r s et a b l ea 坞t h e nu s e dt op r o d u c e 缸e f f i c i e n ti n c r e m e n t a ll lp a r s e t h e ni ts p e c i f i c a l l yd i s c u s s e dt h e a n a l y s i sa n di m p r o v e m e n tt ot h ee f f 酬v ei n c r e m e n t a lp a r s i n gi nt h ep a r a l l e le l l v i r o l l l 吣p r o d u c e da n i m p r o v e m e n tt op a r a l l e li n c r e m e n t a ll lp m i n ga l g o r i t h m , a n dc a r r i e do nt h ea n a l y s i sw i l ha nc x a m p l e t h ea r t i c l e6 u a l l ya l s od i s c u s s e dr e p e t i t i o nr e p l a c eq u e s t i o no ft h ep a r a m 在- e e s s a m el r a n s f o r m a t i o nf o r t h i sp a r a l l e la j g o r i t h mi nt h em a t h e m a t i c a le x p r e s s i o na n a l y s i sp r o c e s s , a n dh a sp r o d u c e d 缸r e l a t e d c o n c l u s i o nf o rt h es p e c i a lf u n c t i o no ft h i sp a r a l l e la l g o r i t h mi n t h em a t h e m a t i c a le x p r e s s i o np a m i n g p r o c e s s t h i sa r t i c l et h r o u g ht h el a b o ra n dd i s c u s s t o 。叫1 s t n l c 协h i g h l ye f f e c t i v ei n c r e m e n t a ll lp 啪i n gi nt h e p a r a l l e le n v i r o n m e n t , h a v ei t sp m 舐s i g r 曲c a n c et o 伽舡m f i l ee f f i c i e n c yo fi n c r e m e n t a ll lp a b i r 够 t h u si th a sl a i dag o o df o u n d a t i o ni nt h e o r yf o rf u r t h e rd i s c u s s i o no f t h em s t h e m s t i c a le x p r e s s i o n p a r s ei n p a r a l l e le n v i r o n m e n t k e yw o r d s ：p a r s i n g , l l ( 1 ) 乎锄m n a r ，t h m d i n gp a r s et r e e s ，i n c r e m e n t a lp a r s e , p a r a l l e l n 独创声明和论文使用授权说明 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河 南师范大学或其他教育机构的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢 意。 关于论文使用授权的说明 本人完全了解河南师范大学有关保留、使用学位论文的规定，即：有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权河南师范大学可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编 学位论文。( 保密的学位论文在解密后适用本授权书) 签名： 五型垫导师签名：型2 至：魏日期：塑l ：! 第一章绪论 第一章绪论 本章主要综述了有关编译原理的概念，研究背景以及发展现状，提出了本文的主要 研究内容语法分析，最后介绍了本文的组织结构。 1 1 研究背景与发展现状 1 1 1 编译技术的发展 在计算机软件科学中，编译是较早在实践上和理论上同时取得巨大发展的一个分 支。世界上第一个编译程序，早在2 0 世纪5 0 年代中期就已问世，多数早期的编译工作是 将算术公式翻译成机器代码。用现在的标准来衡量，当时的编译程序能完成的工作十分 初步，然而它们为高级语言编译系统的研究和开发奠定了基础。2 0 世纪5 0 年代中期出现 了f o r t r a n 等一批高级语言，相应的一批编译系统开发成功。随着编译技术的发展和 社会对编译程序需求的不断增长，2 0 世纪5 0 年代末有人开始研究编译程序的自动生成工 具，提出并研制编译程序的编译程序。它的功能是以任一语言的词法规则、语法规则和 语义解释出发，自动产生该语言的编译程序。目前很多自动生成工具已广泛使用，如词 法分析程序的生成系统l e x ，语法分析程序的生成系统y a c c 等。2 0 世纪6 0 年代起，不 断有人使用自展技术来构造编译程序。自展的主要特征是用被编译的语言来书写该语言 自身的编译程序。1 9 7 1 年，p a s c a l 的编译程序用自展技术生成后，其影响就越来越大。 经过近半个世纪的努力，编译理论和技术伴随着计算机技术的发展而迅速完备化和系统 化，形成了一个完整的理论体系，并且开发出了丰富的编译程序的实现语言、实现环境 和开发工具。在此基础上，设计并实现一个编译程序不再是高不可攀的事情 1 1 。 伴随并行计算机的出现，并行c 、并行c _ h 、并行f o r t r a n 或高性能f o m a n ( h p v ) 等语 言也纷纷出台，这些语言的编译系统一般都是在相应串行语言编译系统的基础上增加并 行部分，把并行语言转换成串行语言，再用串行语言编译系统编译。另外随着并行技术 和并行语言的发展，处理并行语言的并行编译技术 2 - 3 1 ，将串行程序转换成并行程序的 自动并行编译技术也正在深入研究之中。 而今计算机的发展趋向于并行化，多处理机并行处理是不可逆转的时代潮流。多处 理机的硬件集成在技术上己不存在困难，但相应的并行编译软件系统成了计算并行性发 第一章绪论 展的瓶颈，因此，开发并行编译成了当前计算机研究的一大课题。 编译实现方式的发展o ：经历了手工，机器语言，汇编，系统程序设计语言和自动 构造工具l e x 、y a c c 、g c c 的过程。 推动编译技术发展的因素：包括语言范型( 计算模式) 和计算机体系结构。 语言范型分为：命令式( i m p e r a t i v el a n g u a g e ) ，应用式( a p p l i c a t i v e ) ，基于规则的 ( r u l e - b a s e d ) ，面向对象的( o b j e c t - - o r i e n t e d ) ，并行计算( p a r a l l e lc o m p u t i n g ) 。 体系结构有：万诺曼机体系结构，并行体系结构，嵌入系统。 编译程序执行环境有：批处理，交互环境，嵌入系统环境。 并行编译技术如图l 一1 所示： 图1 - 1 并行编译技术 1 1 2 编译的概念 程序设计语言可分为低级语言和高级语言两大类，目翦普遍使用的程序设计语言是 高级语言。然而，计算机硬件只懂自己的指令系统，即它只能直接执行用相应机器语言 编写的代码程序，而不能直接执行用高级语言编写的程序。因此，要在计算机上执行除 机器语言之外的任一程序设计语言，就必须有这样一个程序，它把用高级语言编写的程 序转换成等价的机器语言程序，我们把这种程序称为编译程序( 也称作编译器) 。即编 译程序的输入对象为源程序，输出对象为目标程序。且在这个转换过程中，编译器将源 程序中出现的错误报告给用户。编译器的结构如图1 - 2 所示： 。计算机网络小组广师网络工程课件之编译原理 既；0 l h t t p ：w w , 2 g d i n e d u c a j k x w e b s t u d y b i a n y i y u a n l i f o r n p a g e i n d e x h t m ，2 0 0 6 - 8 1 2 第一章绪论 错误信息 图1 2 编译器结构 由此可见，若要按编译方式在计算机上执行用高级语言编写的程序，一般需经过两 个阶段：第一阶段称为编译阶段，其任务是由编译程序将源程序编译为目标程序，若目 标程序不是机器代码，而是汇编语言程序，则尚须将汇编程序再行汇编为机器代码程序； 第二阶段称为运行阶段，其任务是在目标计算机上执行编译阶段所得到的目标程序。在 执行目标程序时，一般还应有一些子程序配合进行工作，例如：常见的数据格式转换子 程序、标准函数计算子程序、浮点解释子程序、数组动态存储分配子程序、下标变量地 址计算子程序等等都属此类。这些子程序组成一个子程序库，称为运行系统。编译程序 与运行系统合称为编译系统 4 4 1 1 1 3 编译的阶段 编译程序的主要功能是把用高级语言编写的源程序翻译为等价的目标程序。既然编 译过程是一种语言的翻译过程，因此我们就可以将编译的工作过程与通常外文的翻译过 程进行类比抽象地看，任何一本外文资料都是由字母、标点符号( 包括空格和其它符号) 并按相应语法规范所组成的字符串。因此，任何欲进行外文翻译的人，都应具备如下能 力：也能认识外语的字母及标点符号；b 能识别出文中的各个单词；c 会查字典；d 懂得 此种外语的语法；e 具有目标语言的修饰能力至于如何进行翻译，概括地讲无非是做 两方面的工作；一是进行分析，二是进行综合。所谓分析，就是从第一行的第一个字母 开始。依次阅读原文中的各个符号，逐个识别出原文中的各个单词，然后根据语法规则 进行语法分析，即分析原文中如何由单词组成短语和句子，以及句子的种类特点等。此 外，在识别单词和进行语法分析的过程中，还要不时地查阅字典，傲语法正确性的检查， 进行相应的语义分析，并做一些必要的信息簿记工作等等。所谓综合，就是根据上述分 析所得到的信息，拟定译稿，进行修饰加工，最后写出译文。类似地，编译程序在其工 作过程中，也需做两方面的工作，即先分析源程序，然后再综合为目标程序。我们可以 将编译的工作过程分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示，编 译过程的一种典型分解如图1 - 3 所示旧： 3 第一章绪论 圉1 - 3 编译的阶段 实际上，若干阶段可以组合在一起，各阶段之间的中间表示也无需显式构造。 1 1 4 文法和语言 一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语 法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适 的程序。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系，阐明 语法的一个工具是文法。所谓文法，直观的解释是对含有无穷句子、不能列举的语言， 给出它的有穷表示的描述规则。文法的形式定义如下1 c , - 7 1 ： 文法g 定义为四元组( v _ n ，、，p ，s ) 。其中v n 为非终结符号集，、h 为终结符号集，p 为 产生式( 也称规则) 的集合，、v t 和p 都是非空有穷集。s 称作识别符号或开始符号， 它是一个非终结符，至少要在一条规则中做为左部出现，并且v n 和v t 不含有公共元素 文法g 所产生的语言定义为集合 ) ( is 辛x ，其中s 为文法识别符号，_ g x e v r + ) 乔 姆斯基把文法分成四种类型，即0 型、1 型、2 型和3 型。这几类文法的差别在于对产生式 施加不同的限制，它们的定义如下： o 型文法：设g = ( 、r n ，v t ，p ，s ) ，如果它的每个产生式”p 是这样一种结构： a e ( v n u v t ) + ，且至少含有一个非终结符，而p 眠i t ) ，则g 是一个0 型文法。 l 型文法( 上下文有关文法) ：设o - - ( v n , v v ，p ，s ) 为一文法，若p 中的每个产生式n b 4 第一章绪论 均满足i p i = i 口i ，仅仅s 川除外，则文法g 是1 型文法，也称为上下文有关文法。 2 型文法( 上下文无关文法) ：设g = ( 、，l i v t ，p ，s ) 为一文法，若p 中的每个产生式d b 均满足：n 是一非终结符，d ( v n u v t ) * ，则此文法称为2 型的或上下文无关文法。 3 型文法( i f 规文法) ：设c , - - ( v n ，v t ，p ，s ) 为文法，若p 中的每个产生式的形式都是 a _ ，a b 或a a ，其中a 和b 都是非终结符，a 是终结符，则g 是3 型文法或正规文法。其中 上下文无关文法是应用较多的，它有足够的能力描述现今程序设计语言的语法结构。 1 2 论文研究内容 1 2 1 本课题研究的目的与意义 计算机技术日益发展的今天，尽管目前单个c p u 的性能已经达到相当高的水平， 但就一些超大规模计算或一些必须实时完成的多媒体运算而言，如果不利用并行计算技 术是很难满足用户需求的。如何获得更高的速度和峰值已成为我们所追求的方向，并行 技术能够将原本串行( 线性) 处理的工作改成并行( 多维) 处理，不仅节省了使用的时 间并且减少了所用的存储空间，因而并行计算机在近2 0 年迅速发展。并行程序设计和 并行编译技术是提高实际运行速度的关键。因此，并行优化编译技术已成为当代计算机 软件的重要研究课题之一。 并行语法分析是并行优化编译技术中的主要环节和重要组成部分，主要用于并行程 序设计语言的编译器和解释器的实现，以及自然语言的理解和翻译等领域中降埘。扩增 式语法分析在基于语言编辑器，扩增式编译和解释环境中广泛使用，修改输入串的重新 语法分析是这些环境下最频繁的执行操作，它的效率能极大的影响这些环境的成功。 目前的研究主要停留在单处理器上对单独一处修改的输入串的扩增式语法分析，并 未实现在并行环境下对多处修改输入串的扩增式语法分析算法。因此，并行扩增式语法 分析急需进一步发展。 1 2 2 本文的主要工作 c , - - - ( n ，1 卫s ) 是一个无歧义上下文无关文法，n 是非终结符集合，t 是终结符集合， p 是产生式集合，s 是开始符。我们假设g 是一个$ 一扩大文法。如果不是，我们构建 $ 一扩大文法g ；吖u s ) ，t u $ ) ，p u s - s $ ) ，s ) ，这里$ 是代表输入结束的标记。 对文法g 生成的串x y l z l y 2 2 2 ，我们有s 冷x y lz i y 2 2 2 ，x 、y l 、z l 、y 2 、z 2 e t 。 第一章绪论 当串xy iz iy 2z z 变成串xy l z ly 2 z 2 时，扩增式语法分析试图进行最小量的分析步骤。在 本文中，我们首先讨论使用语法树和l l 预测分析表的扩增式语法分析过程，随后推广 到在并行环境下对串x y lz i y 2z 2 。y n z a ( z l 、z 2 z n 不为空) 变成串x y l z ly 2 ，z 2 。y n 的扩 增式语法分析，并给出一个在并行环境下的改进算法。 1 3 论文的组织结构 本文由五个章节组成： 第1 章，概要性的论述了有关编译原理的概念，研究背景以及发展现状，提出了本 文的主要研究内容语法分析，最后介绍了本文的组织结构： 第2 章，本章为了介绍构造扩增式l l 预测分析表的方法，首先引出语法分析树， l l ( 1 ) 文法和f i r s t 、f o l l o w 及s e l e c t 集合的相关概念，随后还具体讨论了构造扩增式 l l 预测分析表和语法分析树的方法； 第3 章，本章首先针对串x y z 到x y z 的扩增式语法分析过程，使用已有的扩增式语 法分析算法，给出一个实例具体分析讨论，通过在分析过程中的思考，引出扩增式语法 分析算法在并行环境下的扩充，并证明了该改进算法的正确性和有效性： 第4 章，本章首先给出关于四则混合运算表达式处理这个经典的算法问题的讨论， 引出了一个数学表达式语法分析的传统算法，继而用一个典型实例分析了数学表达式在 并行环境下的语法分析过程，随后讨论了数学表达式中局部树的相同变换的重复替换问 题，最终给出一个针对该问题的再次改进的算法； 第5 章，总结全文，并展望了并行编译的研究前景和扩增式语法分析的进一步研究 方向。 6 第二章扩增式l l 预测分析表和线索化分析树 第二章扩增式l l 预测分析表和线索化分析树 为了下面构造扩增式l l 预测分析表，我们首先引出语法分析树，l l ( 1 ) 文法和 f i r s t 、f o l l o w 及s e l e c t 集合的相关概念。 2 1 语法分析 语法分析阶段是编译过程的第二个阶段，也是编译程序的核心部分。语法分析的任 务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”。“语句”，“表 达式”等等。一般这种语法短语，也称语法单位，可表示成语法树，语法分析所依据的 是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一 个语法上正确的程序，报告错误信息，并能从错误中恢复。目前语法分析常用的方法有 自顶向下分析和自底向上分析两大类。 ( 1 ) 自项向下语法分析 自顶向下语法分析法也称面向目标的分析方法，也就是从文法的开始符号出发，企 图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出， 反之必然出错。自顶向下语法分析又可分为确定的和不确定的两种，确定的语法分析方 法是指在分析推导过程中，每一步都是确定的，即能够根据当前的输入符号( 单词符号) 唯一地确定选用哪个产生式替换相应非终结符往下推导，这就需要对文法有一定的限 制，但由于其实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目 前常用的方法之一，l l ( 1 ) 方法是确定的自顶向下语法分析的典型代表。不确定的方法 即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，其分析效率低，代价高， 因而极少使用。 ( 2 ) 自底向上语法分析 自底向上分析方法，也称移进一归约分析法，它的实现思想是对输入符号串自左向 右进行扫描，并将输入符号逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号 串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串， 这称为一步归约。重复这个过程，直到栈中只剩文法的开始符号时则为分析成功，也就 确认输入串是文法的句子，否则为出错。这种方法的难点是在分析过程中如何确定句柄， 常用的自底向上分析法有算符优先分析和u i 分析。 7 第二章扩增式l l 预测分析表和线索化分析树 2 2 语法分析树 句型分析是语法分析的核心内容，所谓句型分析就是识别一个符号串是否为某文法 的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分 析程序。对于上下文无关文法，语法树是句型结构分析的极好工具，是句型推导过程的 几何表示，它可以将所给句型的结构很直观地显示出来。语法树的定义如下： 给定文法g - - ( v s ，、，t ，p ，s ) ，对于g 的任何句型能构造与之关联的语法树( 推导树) 。 这棵树满足下列4 个条件： ( 1 ) 每个结点都有一个标记，此标记是v 的一个符号； ( 2 ) 根的标记是s ； ( 3 ) 若一结点n 至少有一个除它自己外的子孙，并且有标记a ，则a 肯定在v n 中； ( 4 ) 如果结点1 1 的直接子孙，从左到右的次序是结点n l 、玎2 、l l k ，其标记分别为a l 、 a 2 、趣，那么a a l a 2 a f _ 定是p 中的一个产生式。 例如，给定文法g 和句型如下： g = ( s a b ， 咖，c ，p ，s ) ，其中p 为： ( 1 ) s - + a a a b b ( 2 ) a - - b ( 3 ) a 一a b ( 4 ) b c ( 4 ) b - - b e 句型a b b a c b 的推导树如图2 1 所示： s 形刀蕊、 aaab b 入i a b c l b 图2 - 1a b b a c b 的语法树 从上图的语法树中，从左到右读出语法树的叶子标记，得到的就是句型a b b a c b 。语 法树表示了在推导过程中施用了哪个产生式和施用在哪个非终结符上，它并不表明施用 产生式的顺序。 3 第二章扩增式l l 预测分析表和线索化分析树 句型分析的算法可分为两大类，即自顶向下和自底向上的。所谓自项向下分析法， 是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。 自下而上的方法，则是从输入串出发，逐步进行“归约”，直至归约到文法的开始符号。 而相应的语法树的建立方式也有两种，自上向下和自底向上。自上而下方法是从文法的 开始符号开始，将它作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号 串正好是输入符号串；自底向上方法则是从输入符号串开始，以它作为语法树末端结点 符号串，自底向上地构造语法树【4 】。 2 3 自顶向下分析法构造f 麟t 、f o l l o w 及s e l e c t 集合 2 3 1 基本概念 确定的自顶向下分析方法所要解决的首要问题就是，如何根据当前的输入符号( 单 词符号) 唯一地确定选用哪个产生式替换相应非终结符往下推导。显然，如果文法满足 下列条件： ( 1 ) 每个产生式的右部都由终结符号开始； ( 2 ) 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 则在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此 分析过程是唯一的。但如果文法具有下列特点： ( 1 ) 产生式的右部不全是由终结符开始； ( 2 ) 如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始； ( 3 ) 文法中无空产生式。 此时，对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪 个产生式，则需要知道这些产生式的右部符号串可以推导出的首字符集，又称之为f i r s t 集，如果所有具有相同左部的产生式的右部符号串的f i r s t 集不相交，则仍然可以根据 当前的输入符号是属于哪个产生式右部的f i r s t 集而确定选择相应产生式进行推导。上 面两种情况文法中均未考虑空产生式，对于下面含有空产生式的文法： g ：s a a s 坩 a b a s a - - - 屹 9 第二章扩增式l l 预测分析表和线索化分析树 若输入串为w = a b d ，则试图推导出a b d 串的推导过程为： s 辛a a = a b a s ： a b s 号a b d 从这个推导过程可以看到在第二步到第三步的推导中， 即a b a s 兮a b s 时，因为当前面临输入符号为d ，而最左非终结符a 的产生式右部的开始符 号集合都不包含d ，但有因此对于d 的匹配自然认为只能依赖于可能的推导过程中a 的 后面的符号，所以这时选用a e 向下推导，而当前a 后面的符号为s ，s 产生式右部的开 始符号集包含了d ，所以可以匹配。由此可见，当某一非终结符的产生式中含有空产生 式时，它的非空产生式右部的首字符集合两两不相交，并与在推导过程中紧跟该非终结 符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。为此，定义一 个文法符号的后跟符号集合，即f o l l o w 集合。 下面给出f i r s t 集、f o l l o w 集和s e l e c t 集的定义f l l 】： f i r s t 集：设g = o ，t 、，n ，s ，p ) 是上下文无关文法，我们定义： f i r s t ( 砂= a j a 号a p ，a e v t ，a 、p g v 若a 辛。8 ，则规定ef i r s t ( a ) 。 f o l l o w 集：g - 司v * n , v t , s ，p ) 是上下文无关文法，a v n ，s 是开始符号，我们定义： f o l l o w ( a ) = v | s a a ，a v t ) 若有s 号+ 。a ，则规定# e f o l l o w ( a ) ，这里的群作为输入串的结束符，或称为句 子括号。 s e l e c t j 耗：给定上下文无关文法的产生式j a ，a e v n ，a v ，我们定义： 若n 不能推出8 ，贝i j s e l e c t ( a - - * c 0 = f i r s t ( 0 0 , 如果口能推出，贝t j s e l e c t ( a - - - , a ) = f i r s t ( a ) uf o l l o w ( a ) 。 2 3 2 算法设计 a 求f i r s t 集合 计算一个符号的f i r s t 集合，需要判别文法中每个符号是否能推出空，判别的方法 如下r 1 2 】： 首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符， 对应每一非终结符有一标志位，用以记录能否推出空。其值有三种情况“未定”、“是”、 “否”。 然后按下列步骤计算嗍： ( 1 ) 将数组x 【】中对应每一非终结符的标记置初值为“未定”。 1 0 第二章扩增式l l 预测分析表和线索化分析树 ( 2 ) 扫描文法中的产生式 ( a ) 删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产 生式都被删除，则将数组中对应非终结符的标记值改为“否”，说明该非终结符不能推出 6 ： 若某一非终结符的某一产生式右部为，则将数组中对应该非终结符的标志置为 “是”，并从文法中删除该非终结符的所有产生式。 ( 3 ) 扫描产生式右部的每一个符号 ( a ) 若扫描到的非终结符在数组中对应的标志是“是”，则删去该非终结符，若这使得 产生式右部为空，则将产生式左部的非终结符在数组中对应的标志改为“是”，并删除该 非终结符为左部的所有产生式； c o ) 若扫描到的非终结符在数组中对应的标志是“否”，则删去该产生式，若这使得 产生式左部非终结符的有关产生式都被删去，则把数组中该非终结符对应的标志改为 “否”。 ( 4 ) 重复( 3 ) ，直到扫描完一边文法的产生式，数组中非终结符对应的标志再没有改 交为止。 由定义，可按下述方法计算每一个文法符号x t = v 的f i r s t 集f i r s t ( x ) ： ( 1 ) 若x v r ，则f 峪t c ，0 = x ； ( 2 ) 者x v ，则有产生式x + 乱，a e v t ，则a f 峪t ( 两； ( 3 ) 若x e v n ，x _ + e ，则s f i r s t ( x ) ： ( 4 ) 若x a v n ，y l 、y i 都v n 而有产生式) 【_ y l y 2 y n 。当y l 、y 2 、 y i 都号8 时，( 其中l - - - - - i n ) ，则f 塔t 吖1 ) - 8 、f i r s t ( y 2 ) - ) 、 f i r s t c y i - i ) - 8 、f i r s t ( y 0 都包含在f i r s t c a 钟, ( 5 ) 当( 4 ) 中所有辛( i = 1 、2 、n ) ， i r , f i r s t ( x ) = f i r s t ( y 1 ) uf i r s t ( y 2 ) u uf i r s t ( y ) u ) 。 反复使用上述( 2 ) 到( 5 ) 步直到每个符号的f 如r s t 集合不再增大为止。 单个文法符号的f i r s t 集合求出来后，就可以求字符串的f i r s t 集合【l l - 1 2 1 ，求法如 下； 符号串a = = x l x 2 x ，a v 若x l 不能号8 ，则置f i r s t ( a ) = f i r s t ( x 1 ) ； 第二章扩增式l l 预测分析表和线索化分析树 若对任巾巧( 1 割主i - 1 ，2 耋i 耋n ) ，8 f i r s t ( x j ) ，则f i r s t ( 岬涔t ( x 1 ) ) ) u 0 7 i r s t c x 2 ) - ) u u ( f i r s t ( x i 0 - ) uf i r s t ( x i ) ) 当所有的f i r s t c x j ) ( i 割耋n ) 都含有s 时，贴i r s t ( c 0 = f i r s t ( x 0uf i r s t ( x 2 ) u u f i r s t ( x n ) u ) 为所有的非终结符a 计算f i r s t ( a ) i 鬟 j 算法o f o ra l l m e r ，n i n a l sad of 1 r s t ( a ) ：= ； w h i l et h c r ea r cc h a n g e st oa n yf i r s t ( a ) d o f o r e a c h p r o d u c t i o n c h o i c e a - - * x i x 2 】矗d 0 k 1 ： 触：- - t r u e ； w h i l ec o n t i n u e - 咖a n dk 蜘d o a d df 噶t ( x k ) - b t of i r s t ( a ) ； i r ei sn o ti nf i r s t c 瓦) t h e nc o n t i n u e ：- - - f a l s e ； k ：= - k 十1 ： i f c o n 6 u e = 由舱t h e na d d8t of i r s t ( a ) ； b 求f o l l o w 集合 对文法中的每一个a v n ，可按下述方法计算f o l l o w ( a ) ： ( 1 ) 设s 为文法中开始符号，把加a f o l l o w ( s ) q b ( 这里咩 为句子括号) ； c 2 ) 若a 加b p 是一个空产生式，则把f i r s t ( i s ) 的非空元素加a f o l l o w ( b ) 中； 如果p e ，则把f o l l o w ( a ) 也加i x f o l l o w ( b ) 中； ( 3 ) 反复使用( 2 ) 直到每个非终结符的f o l l o w 集不再增大为止。 计算f o l l o w 集合的算法雪 f o l l o w ( s t a r t - s y m b 0 1 ) ：= $ ； f o ra l ln o n t c r m i n a l sa os t a r t - s y m b o ld of o l l o w ( a ) ：= ； w h i l et h e r ea c h a n g e st oa n yf o l l o ws e t sd o f o re a c hp r o d u c t i o n a - - x i x 2 ) k d o f o re a c hx 2t h a ti san o n t c n n i n a ld o a d df i r s t c x w , x i + 2 x 小 ) t of o l l o w ( x i ) ( * n o t e ：i f i - - - nt h e nx 件t ) + 2 k - ) i f ei si nf i r s t ( x i + tx 件2 j 0t h e n ok e n n e t hc l o u d e n 著冯博琴，冯岚等译编译原理及实践 1 i 北京l 机械工业出版社，2 0 0 0 = 1 2 6 ok e n n e t hc l o u d e n 著冯博琴，冯岚等译编译原理及实践 蝴北京：机械工业出版社，2 0 0 0 , 1 3 1 1 2 第二章扩增式l l 预测分析表和线索化分析树 a d df o l l o w ( a ) t of o l l o w ( x i ) c 求s e l e c t 集合 对文法中的任意产生式a a ，a v n ，a v ，其s e l e c t 集合可按下列算法求得： i f ( a 不能推出g ) s e l e c t ( a 甘f 刀憋t ( e l s es e l e c t ( a _ c 0 = f i r s t ( a ) uf o l l o w ( a ) 2 4l l ( 1 ) 文法 2 4 1 基本概念 自顶向下文法分析可分为确定和不确定两大类，其中不确定的分析方法是带回溯的 试探法，因为其分析效率低而很少使用，而确定的分析方法并非所有的文法都适用，它 对文法有一定的限制，例如含有左递归和含有左公共因子的文法就不能用确定的自顶向 下分析法。 确定的自项向下分析方法，首先要解决从某文法的开始符号出发，对给定的输入符 号串如何根据当前的输入符号( 单词符号) 唯一地确定选用哪个产生式替换相应非终结 符往下推导，或构造一棵相应的语法树，着能够推导出给定的输入符号串，或能构造出 语法树其末端结点以从左向右的顺序连接正好为给定的输入符号串，则所给的输入符号 串为该文法的句子。 u 1 1 ) 文法是可以进行确定性分析的一类文法。 l l o ) 文法的定义1 1 】：一个上下文无关文法是l h l ) 文法的充分必要条件是，对每个 非终结符a 的两个不同产生式：a a 、a p ，满足s e l e c t ( a a ) n s e l e c t ( a b 户a ， 其中d 和b 不能都推出e l l ( 1 汶法的含义；第一个l 表明自顶向下分析是从左向右扫描输入串，第二个l 表 明分析过程中将用最左推导，1 表明只需向右看一个符号就可以决定如何推导，即选择 哪个产生式进行推导。 l u l ) 文法的判别：l l ( 1 ) 文法的判别并不难，只需求出每个产生式的s e l e c t 集， 然后看相同左部的产生式的s e l e c t 集交集是否为空，若都为空，则是l l ( 1 ) 文法，否则 不是。 第二章扩增式l l 预测分析表和线索化分析树 2 4 2 非l l ( 1 ) 文法的等价变换 一个文法中含有左递归和左公共因子绝对不是l l ( 1 ) 文法，所以也就不可能用确定 的自顶向下分析法。 然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变 为l l ( 1 ) 文法，但需要用l l ( 1 ) 文法的定义判别，也就是说文法中不含左递归和左公共因 子，只是l l ( 1 ) 文法的必要条件。 因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在某 些特殊情况下可能使其变为l l ( 1 ) 文法。 ( 1 ) 提取左公共因子【1 ，1 2 】 若文法中含有形如：a q p m 的产生式，这导致了对相同左部的产生式其右部的 f i r s t 集相交，也就是s e l e c t ( a - - - , a 1 3 ) n s e l e c t ( a 一咖o ，不满足l l ( 1 ) 文法的充分必 要条件。 现将产生式h a p i 吖进行等价变换为： a + ( p i d 其中( 、) 为元符号，可进一步引进新非终结符a ，去掉( 、) 使产生式变换为： a 匝a a l 邯l 丫 写成一般形式为： a 一位p l i a 陀卜l a l 3 。，提取左公共因子后变为： a 一( p 1 倒l 附，再引进非终结符a ，变为： a + 仉a a 一p l i p 2 i 若在既、岛、p k ( 其中1 耋i 、j 、k 耋n ) 中仍含有左公共因子，这时可再次提取， 这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。 ( 2 ) 消除左递归 设一个文法含有下列形式的产生式： 1 ) a + a p ，a 、，n ，i b e v + 2 ) a b p b a n ，a 、b v n ，n 、b v + 1 4 第二章扩增式u 预测分析表和线索化分析树 可称含1 ) 中产生式的文法为含有左递归的规则或称直接左递归的。含2 ) 中产生式的 文法有a 号+ a 则称文法中含有左递归或间接左递归，文法中只要含有1 ) 或含有2 ) 的 产生式或二者皆有均认为文法是左递归的，然而，一个文法是左递归时不能采用自顶向 下分析法。 a