编译原理[强化版].

1、2010计算机科学与技术编译原理资料整理知识点强化版杨磊2013/12/22 Sunday注：本资料用于知识点全面复习，内容经PPT及整理得到，分成知识点，补充重点，例题三部分适用于有一定时间（至少3天）复习的同学。 目录第一章 编译系统概述2第二章 词法分析3第三章 程序设计语言的语法描述5第四章 自上而下的语法分析7第五章 自下而上的语法分析13第六章 语法制导翻译和中间代码生成24第七章 目标代码生成32第一章 编译系统概述源语言和源程序 用程序设计语言书写的程序，称为源程序，该程序设计语言称为源语言。源程序通常用编辑程序输入，用字符(ASCII码)表示，以文本文件形式存储。目标语言和目

2、标程序 目标语言可以是机器语言(二进制)，也可以是汇编语言(字符)，但最终结果必定是机器语言。机器语言程序用二进制文件存储，汇编语言用文本文件存储。目标程序是经翻译程序加工后用目标语言表示的程序。翻译程序将源程序译成逻辑上等价的目标程序的程序。翻译程序有二种工作方式：编译和解释解释方式以源程序作为输入，输入一句解释执行一句，不产生完整的目标程序本文红色字体为个人认为重点的部分，相应的翻译程序称为解释程序编译方式将源程序全部译为目标程序，该目标程序可在操作系统环境下直接执行，相应的翻译程序称为编译程序。解释方式和编译方式比较 解释方式和编译方式的主要区别是：目标代码的执行方式不同，基本原理和方法

3、没有本质上的区别。解释方式的优点 提供一种直接的交互调试功能，容易获得较好的动态调试效果。（结构简单本文所有蓝色字体为个人理解部分仅供参考）解释方式的缺点 在执行时需动态地对程序进行分析翻译，开销大，其执行速度相当于编译方式的1/10至1/100。（执行速度慢，占用空间大）编译程序过程（有哪几部分） 从数据加工的角度来看，可将其分成4个逻辑阶段，词法分析、语法分析、语义分析（中间代码产生）、目标代码生成编译程序各个部分的工作、依据以及输入输出（一）词法分析执行词法分析任务的程序称为词法分析器。 任务：字符串形式单词 编码形式单词内部码（二元式） 依据：语言的构词规则（二）语法分析 执行语法分析

4、任务的程序称为语法分析器。 任务：检查源程序的语法结构是否正确 依据：语言的语法规则（三）语义分析 执行语义分析任务的程序称为语义分析器或中间代码产生器。 任务：建立符号表和常数表，记录源程序中标识符属性和常数值，根据语言的语义规定生成中间代码。 依据：语言的语义内涵 语义分析主要工作为：语义正确性检查、语义翻译中间代码 结构简单、意义明确的记号系统，非常接近机器指令，又独立于具体机器。常用的中间代码有三元式和四元式。符号表 符号表用于记录源程序中出现的标识符(Identifier)，一个标识符往往具有一系列的语义值，它包括标识符的名称、标识符的种属、标识符的类型、标识符值的存放地址等等。而在

5、四元式中填写的是标识符在符号表中的记录地址，通常称为符号表入口。常数表 常数表用于记录在源程序中出现的常数。假定，每个整常数在常数表中占2个字节，每个实常数在常数表中占4个字节。目标代码生成 执行目标代码生成的程序称为目标代码生成器。 任务：中间代码 目标代码（机器指令或汇编语言） 依据：目标机器的系统结构编译程序的前端和后端由于在编译程序的内部引入了中间代码，这样可将编译程序分为二个相互独立部分。（一）编译程序前端 组成：词法分析器、语法分析器和中间代码产生器 特点：依赖于被编译的源语言，输出结果用中间代码描述，和目标机器无关。（二）编译程序后端 组成：目标代码生成器 特点：和源语言无关，以

6、中间代码形式的源程序为输入进行处理，输出结果依赖于目标机器。第二章 词法分析词法分析器的构成及各部分的功能（一）预处理程序 功能：1）删除注释 2）删除续行符和后续换行符 3）换行符、TAB替换成空格（二）扫描器（单词识别程序） 读入字符并识别单词词法分析任务： 从文件读入源程序，去除源程序中与编译无关的编辑字符、注释等，得到由字符拼接的单词。每当识别出一个单词，就用单词的内部码（单词二元式）替换。执行词法分析任务的程序称为词法分析器。单词二元式编码 经词法分析后，单词用二元式 (Code , Val ) 表示。 code表示单词的种别，用整数码表示。单词种别表示单词的语法特性，在语法分析时使

7、用。 Val表示单词的值，在本书中用字符串表示。单词值表示了单词的语义特性，在语义分析时使用。手工构造词法分析器的方法是 先用状态转换图描述出所有单词，然后用程序实现状态转换图，最简单的办法是让每个状态对应一小段程序。正规式(构词规则)和正规集（有穷字母表所有字的特殊子集）的定义： 和是上的正规式，相应的正规集为、 。 若字符a，则字符a是正规式，相应正规集为a。 若、为正规式，相应正规集分别记为L()和L()，则| 是正规式，其相应正规集记 为L(|)=L() L() 若、为正规式，相应正规集分别记为L()和L()，则(或)、 是正规式，其相应正规集记为L()= L()L() ， 若、为正规

8、式，相应正规集分别记为 *是正规式，其相应正规集记为L(*)=L()n正规式和正规集实际意义 有穷字母表是程序设计语言所使用的字符集的抽象 正规集是程序设计语言单词集的抽象 正规式是程序设计语言构词规则的抽象DFA定义 一个确定有限自动机M是一个五元式M = ( S，f，s0，Z ) S是一个有限集，它的每一个元素称为状态。是一个有穷字母表，它的每个元素称为一个输入字符。f是一个从S至S的映射，即f：SS（单值函数）s0S，是唯一的一个初态。 ZS，是一个终态集。NFA定义 一个非确定的有限自动机M是一个五元式M=（S，f，S0，Z）S是一个有限集，它的每一个元素称为状态。是一个有穷字母表，它

9、的每个元素称为一个输入字符。f是一个从S （）到S的幂集的映射，即f：S（）P(S)(多值函数）S0S，是一个非空初态集，即NFA的初态不一定唯一。ZS，是一个终态集。NFADFA（NFA到DFA的转换，要会过程并标明初态和终态）为了便于描述NFA确定化算法，我们引进二个概念。（一）I的闭包 I的闭包记为_CLOSURE(I)或CLOSURE(I)，设I是NFA M状态集的一个子集，I的闭包定义为：若状态sI，则s_CLOSURE(I)。若状态sI，则从状态s出发，经一条或多条弧所能到达的状态s_CLOSURE(I)。（二）Ia INFA M状态集的一个子集 Ja从I出发经一条a弧所能到达的状

10、态全体Ia_CLOSURE(Ja)若掌握计算过程并理解含义则紫色部分可以略过，这部分是有助于理解的定义补充说明扫描器控制程序工作原理每次识别单词，控制程序总是从初态出发，不断读入字符，进入下一状态，寻求最长匹配，直到无法前进为止，这样始终都读一个字符。（从左往右扫描）在状态迁移过程中，需用Token数组保存读入字符。在无法前进时，若发现当前状态为终态，则认为识别出一个单词，反之出错，即Token数组所保存的字符串不构成一个单词，而是源程序中的一个错误词形。事先设置一个单词二元式编码表，它包括除标识符和整常数以外的所有单词（基本字、运算符和界符）。当DFA识别出一个单词，就根据Token数组所保

11、存的字符串去查表。若该单词在表中存在，即可获得二元式编码；若不存在，则该单词必为标识符和整常数二者之一，只要稍加判断即可区分。首字符为字母的是标识符，首字符为数字的是无符号整常数。练习：2-6,2-7第三章 程序设计语言的语法描述语法树 非叶结点称为语法单位，在形式语言中称为非终结符。 处于根结点位置的结点在形式语言中又称为开始符号。 叶结点称为单词符号，在形式语言中称为终结符。规则 可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。规则推导句子 可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。文法 是由

12、终结符、非终结符、开始符号（特殊非终结符）及产生式四个要素构成。 作用：从开始符号出发，根据产生式能推导出的句子全体称为文法所规定的语言递归文法： 含有递归规则和间接递归的文法，称为递归文法。 利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。形式文法分类 0型文法：短语结构文法 1型文法：上下文有关文法 2型文法：上下文无关文法 3型文法：正规文法文法和语言 一个文法G是一个四元式(VT,VN,S,P)，其中 VT是一个终结符的非空有限集，终结符通常用小写字母表示。 VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。 S是

13、一个特殊的非终结符（SVN），称为开始符号。P是一个产生式（规则）的有限集合，每个产生式的形式是A ，其中AVN，(VTVN)*。（一）终结符是语言的基本符号，即程序设计语言的单词。语法分析时，终结符用单词的种别表示。（二）非终结符表示抽象的语法单位. 例“算术表达式”、“布尔表达式”、“赋值语句”、“说明语句”和“程序”等。非终结符通常用大写字母表示，也可以用带尖括号的汉字表示。（三）开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法单位。 例如讨论算术表达式，那么描述算术表达式文法的开始符号就是。在程序设计语言中，我们最感兴趣的语法单位是“程序”。（四）产生式是定义语法单位的一种书写规

14、则。上下文无关文法产生式的左部必定是一个非终结符，该非终结符称为左部符号。产生式的右部是终结符和非终结符经有限次连接构成的文法符号串，可以是空字。基本术语 （一）直接推出和直接归约 = （二）推导和归约推导：用产生式右部代替左部规约：用产生式左部代替右部 1=+n：从1始，经一步或一步以上可推导出n。 1=*n：从1始，经步或步以上可推导出n，即1=+n或1=n。 （三）句型 若存在推导S=*（S为文法的开始符号），则称是文法的一个句型。 （四）句子: 仅包含终结符的句型称为句子。 （五）语言文法所能推导出的句子全体称为该文法的语言，记为：L(G) （六）等价文法 1和2是二个不同的文法，若L

15、(G1)=L(G2)， 则称G1和G2是等价文法。 等价文法的存在，使我们能够在不改变文法所规定的语言的前提下，为了某种目的改造文法。 （七）最左推导和最右推导 在各种推导中，考虑今后语法分析的需要，我们仅对两种推导感兴趣。 1）最左推导 在推导过程中始终对最左面的非终结符进行替换，记为=L 2）最右推导（规范规约的逆过程）在推导过程中始终对最右面的非终结符进行替换，记为=R语法树 我们可以用一个有向图表示一个句型的推导，这种表示称为语法树。二义文法 若一个文法所产生的语言中，只要存在一个句子，它有二个最左推导，或有二个最右推导，或句子的推导对应两棵语法树，则称该文法为二义文法。二义文法的利用

16、和处理 （一）根据条件修改文法，语言不变。算符优先性：规定*优先于+，i+i*i等价于i+(i*i)。算符结合性：规定同级运算服从左结合，i+i+i等价于(i+i)+i。 （二）根据条件修改编译程序的语法分析表，文法保持不变（详见第四、五章）。练习：见期中复习题第四章 自上而下的语法分析带回溯的自上而下分析法从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。问题和困难（一） 对于左递归文法定义的语言，不能采用自上而下的语法分析法。试图用非终结符去推导和匹配输入串，而推导所得到的子树第一个子结是该非终结符本身，这样就陷入了死循环。（二）存在虚

17、假匹配，回溯不可避免。（三）编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。（四）当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。（五）带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。 总上所述，必须消除分析过程中的回溯，只有不带回溯的分析方法才是实际可使用的。直接左递归消除方法 假定关于非终结符P的规则为PP|其中，不以P开头。可以把关于P的规则变换为如下形式：PPPP|由于二者推导出

18、的句型均为n(n0)，故上述变换是等价的。 例文法G：EE+T|TTT*F|FF(E)|i|x|y经消除直接左递归后变成ETE E+TE|TFTT*FT|F(E)|i|x|y不带回溯的自上而下的分析法 在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。 对于文法某一句型，只要该文法不是二义文法，从非终结符A出发的最左推导只有一个候选是正确的。 如果该候选式获得匹配，那么这个匹配决不会是虚假的。若该候选式无法完成后续匹配任务，则任何其它候选式也肯定无法完成。提取左因子实例引入 例定义无符号整数的文法NDN|D D0|1|2|3|4|5|6|7|8|9因first(DN)first(D)

19、=0,1,2,3,4,5,6,7,8,9，故文法含有左因子。解决方法 提取左因子，引进产生式，将文法改造为G。ND NNN| D0|1|2|3|4|5|6|7|8|9|0提取左因子一般规则 考虑一般情况，设非终结符P的规则为P1|2|n，(VTVN)+，i(VTVN)*引进非终结符P，可以把这些规则改写成PPP1|2|nfirst集定义 是文法G的任一符号串（包括候选式），(VTVN)* first()=aa，aVT若，则规定first()。 first()直观意义是：从推导出的所有符号串的第一个终结符。或者，从可推导至空字。文法符号(X,x)first集构造算法（一）终结符x 的first集

20、为终结符本身。（二）观察每个产生式，若有Xa，其中aVT，则afirst(X)；若X，则first(X)。（三）观察每个产生式，若有XY，其中YVN，则将first(Y)中的非元素（记为first(Y)/）加到first(X)中。文法G如下所示, 求文法符号的first集。ETE E+TE| TFT T*FT|F(E) | i | x | y棕色是本章节有代表性的练习题，来源于教师PPT解：文法符号first集的计算规则如下:First集 规则（一） 规则（二） 规则（三） Efirst(E)first(T)/ E+,Tfirst(T)first(F)/ T*, F(,i,x,y+ 在“规则（

21、三）”列处填入的是计算公式，需多次重复计算，直至每个非终结符的first集不再增长为止。计算过程如下：First集规则规则（三）1规则（三）2规则（三）3E(,i,x,y(,i,x,yE+,+,+,+,T(,i,x,y(,i,x,y(,i,x,yT*, *, *, *, F(,i,x,y(,i,x,y(,i,x,y(,i,x,y说明： 由于终结符的first集计算较为简单，在计算过程中不再列出。 在计算E的 first集时（ETE），因first(T)不含，故没有必要考虑E的first集，同理T的first集计算（TFT）。 计算也可从下至上进行。follow集定义 设S是文法开始符号，对于文

22、法的任何非终结符A follow(A)=aS=*Aa，aVT 特别是，若S=*A，规定#follow(A)。（注：由于算法的需要，人为地在源程序尾部添加了#，特别规定因此而来） follow(A)直观意义是：在所有句型中紧跟在非终结符A之后的终结符或#。follow集构造算法（一）对于文法开始符号S，因为S=*S，故#follow(S)。（二）观察每个产生式，若AB，其中、(VTVN)+， BVN，则把first()/加至follow(B)。（三）观察每个产生式，若AB或AB()，则把follow(A)加至follow(B)。例，文法G如下所示，求非终结符的follow集。ET Efirst(

23、E) /= + E+TEETFTfirst(T) /= * T*FT TF(E)|i|x|yfirst( ) )=)解：根据上述规则，非终结符follow集的计算规则如下规则（一）规则（二）规则（三）E#)Efollow(E)follow(E)T+follow(T)follow(E)follow(E)Tfollow(T)follow(T)F*follow(F)follow(T)follow(T) “规则（三）”列处填入的是计算公式，需多次重复计算，直至每个非终结符的follow集不再增长为止。计算过程如下规则（一） 规则（三）1规则（三）2E#,)#,)#,)E#,)#,)T+, #,)+,

24、#,)T+, #,)+, #,)F*, +, #,)*, +, #,) 根据ETE，follow(E)应加至follow(E)；因E=*，所以follow(E)还应加至follow(T)。同理E+TE、TFT、T*FT。 follow集的计算也可从下至上进行。预测分析法基本原理产生式的一般形式为：A1|2|n|设当前输入符号为a，根据下述原则if (afirst(i) 用Ai推导（1in）else if (afollow(A)用A推导else报错文法G候选式的first集：ETEfirst(TE)=first(T) /=(,i,x,yE+TE|first(+TE)=+,first()=TFTf

25、irst(FT)=first(F) /=(,i,x,yT*FT|first(*FT)=*,first()=F(E)|ifirst(E)=( 、first(i)=iFx|yfirst(x)=x、first(y)=y非终结符的follow集规则（一）（二） 规则（三）-1规则（三）-2 E#,) #,) #,) E#,) #,) T+, #,) +, #,) T+, #,)+, #,)F*, +, #,) *, +, #,) 分析表构造规则（一）构造所有候选式的first集，构造所有非终结符的follow集。（二）对于文法的每个产生式A执行（三）和（四）。（三）对于每个终结符afirst()，把A

26、加至MAa。（四）若first()，则对于每个终结符bfollow(A)，把A加至MAb。（五）把所有未定义的MAc标上“出错标志”（cVT）。+*()ixy#EETE ETE ETE ETE EE+TE E E TTFT TFT TFT TFT TT T*FTTT FF(E) Fi Fx Fy 预测分析控制程序实现（一）数据结构M:二维数组，存放预测分析表。stack:符号栈，初始时为#S（S为开始符号）。 X:表示栈顶符号 t.code:当前处理单词种别（二）算法描述（暂不考虑出错情况） 预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code行事（ XPop(stack

27、) ），控制程序每次执行下述三种可能的动作之一。若X 和 t.code 均为 #，则分析成功，输入串为合法句子，终止分析过程。若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等，则读入下一个单词二元式。若X是非终结符，则查预测分析表。若MXt.code存放着一条关于X的一个产生式，那么把产生式右部符号串按反序压入stack栈。若右部符号串为空字，则意味着无任何文法符号进栈。假设由单词种别构成的源程序为“i+i#”，手工计算如下：step stackXt.code 文件Lex_r.txt0) #Ei+i#1) #Ei+i# #ET（入栈顺序相反）i+i#2) #ETi+i#

28、 #ETFi+i#3) #ETFi+i# #ETii+i#4)#ETii+i#ET+i#5)#ET+i#E+i#6)#E+i#ET+i#7)#ET+i#ETi#8)#ETi#ETFi#9)#ETFi#ETii#10)#ETii#ET#11)#ET#E#12)#E#13) #Acc 预测分析法不仅避免了过程（函数）的递归调用，并且使得自上而下的语法分析器的自动构造成为可能。预测分析法讨论 （一）预测分析法是由分析表和控制程序构成的，控制程序与文法无关，分析表随文法而异。 （二）在预测分析表中，若某一单元持有一个以上产生式，则称该预测分析表含多重定义，多重定义使得控制程序无法工作。 （三）一个文法

29、，若它的预测分析表不含多重定义，则称该文法是LL(1)文法、分析表为LL(1)分析表（LL是指从左到右的左分析器，1表示向前看一个符号）。 （四）一个文法是LL(1)的，对于文法的每一个非终结符的任何两个不同候选式（A|），下述条件成立：first()first()=若=*，则first()follow(A)=（五）二义文法不是LL(1)文法。二义文法在预测分析法中的应用 手工方法来修改二义文法的分析表,消除分析表的二重定义练习：4-3 4-4第五章 自下而上的语法分析自下而上的语法分析 从叶结点出发，步步向上归约。若能归约到根结点，说明输入串是文法的一个句子，否则输入串存在语法错误。 LR分

30、析器组成 由控制程序和分析表组成。控制程序与文法无关，分析表随文法而异。LR分析法的优点 适用范围大，对文法要求低，无需消除左递归，无需消除左因子。LR分析法的缺点 实现代价高，LR分析表的规模要比同一文法的LL(1)分析表大得多。LR分析法的分类（一）LR(0)分析法 简单、分析能力弱，是LR分析法的基础。（二）SLR(1)分析法 或称简单LR分析法。分析能力中，实现代价同LR(0)，比较容易实现，具有实用价值。（三）LR(1)分析法（本书略） 或称规范LR分析法，分析能力强，实现代价高，或者说分析表的规模非常大。自下而上的语法分析概述 实质上是一种移进归约法，设置一个栈，将输入串符号逐个移

31、进栈内，一旦发现栈顶形成某个产生式的候选式时，立即将栈顶这一部分符号替换（归约）成该产生式的左部符号。短语 子树端末结点的自左至右的排列，称为相对于子树根的短语。 设是文法G的一个句型。如果有S=*A 且 A=+，则称是句型中相对于非终结符A的短语，其中、(VTVN)*。直接短语（简单短语）二代子树端末结点的自左至右的排列，称为相对于两代子树根的直接短语。 设是文法G的一个句型。若有S=+A且A=，则称是句型中相对于非终结符A（或称相对于规则A）的直接短语，其中、(VTVN)*。句柄 最左面的二代子树的端末结点的自左至右的排列，称为句柄。 一个句型的最左面的直接短语称为该句型的句柄。已知文法G

32、: SaAcBe Ab AAb Bd的一个句型aAbcde的语法树如右图： 句型aAbcde中存在三个短语，它们是Ab、d和aAbcde Ab是句型aAbcde中相对于非终结符A的短语 d是句型aAbcde中相对于非终结符B的短语 aAbcde是句型aAbcde中相对于非终结符S的短语 Ab和d是直接短语，句柄是Ab总结 一个文法是无二义的，则句型的短语和直接短语是确定的，句柄是唯一的。 在LR分析法中，句柄就是可归约串。规范归约（最左归约） 设是文法G的一个句子，并且序列n、n-1、0满足下列三个条件，称该序列是的一个规范归约。 1)n= 2)0=S 3)i-1是将i中的句柄替换成产生式的左

33、部符号而得到的 (1in) 例：句子abbcde的归约过程如下 句型句柄归约规则 ab1b2cde b1Ab aAb2cdeAb2AAb aAcdedBd aAcBe aAcBeSaAcBe S 根据定义，序列abbcde、aAbcde、aAcde、aAcBe、S是句子abbcde的一个规范归约规范句型 由规范归约所得到的句型称为规范句型。规范推导(最右推导) 若文法是无二义的，规范归约和最右推导互为逆过程，最右推导又称为规范推导。LR分析法的基本原理（一）前缀 符号串的任意首部。 例=abc，前缀有、a、ab及abc。（二）活前缀 规范句型的一个前缀，不包括句柄之后的任何符号。 接上例= a

34、Abcde，因Ab是该句型的句柄，所以该句型的活前缀有、a、aA及aAb。（三）LR分析法的基本思想 LR分析法严格执行最左归约(规范规约)，每次按句柄归约。LR分析法把句柄的识别过程划分为若干状态，每个状态只识别一个符号，若干个状态就可识别句柄的一部分左端符号。识别了句柄的这一部分就相当于识别了规范句型的左起部分，即活前缀。这样，对句柄的识别变成了对活前缀的识别。可以构造一个DFA，用于识别给定文法所有规范句型的活前缀。LR(0)项目（简称项目） 在产生式右部的某个位置添加一个园点“.”。特例，A的项目为A. 例如，产生式AXYZ包含4个项目： A.XYZ AX.YZ AXY.Z AXYZ.

35、项目的直观意义是，指明了在分析过程的某一时刻，已经看到一个产生式的多少。A.XYZ表示：希望能从后面的输入串看到从XYZ推出的符号串。AX.YZ表示：已经从输入串中看到从X推出的符号串，希望能从后面的输入串进一步看到从YZ推出的符号串。AXYZ.表示：已经从输入串看到从XYZ推出的全部符号串，此时可将句柄XYZ归约为A。例：文法0. SE1. EaA2. AcA3. Ad4. Ed这个文法的项目有S.ESE.E.aAEa.AEaA.A.cAAc.AAcA.A.dAd. E.dEd.项目分类（一）归约项目：园点在最右端的项目称为归约项目，例EaA.（二）接受项目：左部符号是开始符号的归约项目，例

36、SE.。（三）移进项目：形如A.a的项目，aVT。（四）待约项目：形如A.B的项目，BVN。构造识别活前缀的NFA（一）将每个项目视为识别活前缀NFA的一个状态。（二）规定状态S.S为NFA的唯一初态，状态SS.为NFA的唯一接受态（S为原文法开始符号，S为拓广文法开始符号）。（三）因在每个状态都可识别出一个活前缀（初态可识别出活前缀），故NFA的每个状态都是终态，终态又称为活前缀识别态。（四）如果状态i和状态j源自于同一产生式，而且状态i和状态j的园点位置相差一个文法符号，例状态i为i:XX1Xi-1 .XiXi+1Xn 状态j为j:XX1Xi-1Xi .Xi+1Xn 那么状态i和j之间存在

37、一条弧，标记为Xi，表示在状态i读入Xi进入状态j。（五）若状态i园点之后的符号为非终结符（例i:X.A），那么从状态i画一条弧到所有k:A.状态。表示只有看到了从A推出的全部符号，状态i: X.A才可经A弧进入状态j: XA.。构造识别活前缀的DFA LR(0)项目集规范族（简称项目集规范族） 识别文法活前缀的DFA的项目集（状态）的全体。 接上例，文法G项目集规范族C=I0,I1,I2,I3,I4,I5,I6,I7= S.E, E.aA, E.d ,SE. Ea.A, A.cA, A.d, Ed., EaA., Ac.A , A.cA , A.d ,Ad., AcA.项目集规范族的构造（简

38、洁实用的方法与上一种方法相比）文法拓广 引进产生式SS（S为原文法开始符号，S为拓广文法开始符号），将文法拓广成G，使得活前缀识别DFA的初态和接受态唯一。项目集I 的闭包（CLOSURE(I)）设I是文法G的任一项目集，项目集I 的闭包定义为：1）I的任何项目CLOSURE(I)。若待约项目A.BCLOSURE(I)，那么对任何关于非终结符B的产生式，项目B.也属于CLOSURE(I)。2）重复步骤2直至CLOSURE(I)不再增长。状态转换函数（GO(I,X)） 设I是一个项目集， XVTVN，GO(I,X)定义为：GO(I,X)= CLOSURE(JX)其中JX = AX.| A.XI（

39、AX.和A.X源自于同一个产生式，仅园点相差一个位置）。例：已知文法G，构造项目集规范族0. SE1. EaA2. AcA3. Ad4. Ed 解： I0= S.E, E.aA, E.d 由接受态S.E开始当”.”遇到非终结符，将非终结符的产生式加入当x=E JE=SE. I1=GO(I0,E)=CLOSURE(JE)=SE. I0遇到E则跳过成为”E.”加入到I1当x=a Ja=Ea.AI0遇到a则跳过成为”a.A”加入到I2并且将A的产生式加入到I2 I2=GO(I0,a)=CLOSURE(Ja)=Ea.A, A.cA, A.d当x=d Jd=Ed. I3=GO(I0,d)=CLOSURE

40、(Jd)=Ed.当x=A JA=EaA. I4=GO(I2,A)=CLOSURE(JA)=EaA.当x=c Jc=Ac.A I5=GO(I2,c)=CLOSURE(Jc)=Ac.A, A.cA, A.d当x=d Jd=Ad. I6=GO(I2,d)=CLOSURE(Jd)=Ad.当x=A JA=AcA. I7=GO(I5,A)=CLOSURE(JA)=AcA.项目集规范族C共有8个状态（项目集），编号为I0至I7。状态转换函数GO(I,X)将8个状态连接成一个识别活前缀的DFA，其中I0为初态，I1为接受态LR(0)分析表的构造（一）预备工作1)引入产生式SS，将文法拓广成G。2)对G的产生式

41、进行编号。3)构造文法G的状态转换函数GO(I,X)和项目集规范族C。（二）构造法 设项目集规范族C=I0、I1、In，将I0、I1、In视为分析表状态0、1、n。LR(0)分析表存放在二维数组M中，第一维为状态，第二维为文法符号。构造方法如下：1)若移进项目A.aIi且GO(Ii,a)= Ij，其中aVT，则置Mia=sj（s表示移进）。2)若归约项目A.Ii，对于任何aVT#，置Mia=rk（k是产生式A的编号，r表示归约）。3)若接受项目SS.Ii，则置Mi#=Acc（Acc表示接受）。4)若待约项目A.BIi且GO(Ii,B)= Ij，其中BVN，则置MiB=j。5)分析表中的空白表示

42、出错。例:已知文法GEaAE dAcAA d构造它的LR(0)分析表。解：（一）预备工作1）引入产生式SE，将文法G拓广成G。2）产生式编号如下：0. SE1. EaA2. Ed3. AcA4. Ad3）构造上述文法的状态转换函数GO(I,X)和项目集规范族I0= S.E, E.aA, E.dI1=GO(I0,E)=SE.I2=GO(I0,a)=Ea.A, A.cA, A.dI3=GO(I0,d)=Ed.I4=GO(I2,A)=EaA.I5=GO(I2,c)=Ac.A, A.cA, A.dI6=GO(I2,d)=Ad.I7=GO(I5,A)=AcA.LR(0)分析表和LR(0)文法 根据上述方

43、法构造的分析表若不含多重定义入口，则称该分析表是LR(0)分析表， 相应文法是LR(0)文法。冲突项目若一个项目集 既含有移进项目，又含有归约项目（称为移-归冲突）。 含有多个归约项目（称为归-归冲突）。 则称该LR(0)项目集含有冲突项目，冲突项目使得分析表含有多重定义入口。LR(0)分析法的分析能力LR(0)分析法不带任何展望，当归约项目属于某一状态，则在该状态遇到任何终结符号就进行归约，因此分析能力相当弱。SLR(1)分析法的引出LR(0)文法是一类非常简单的文法，这种文法的活前缀识别DFA的每一个状态（项目集）都不包含冲突项目。但遗憾的是，就连定义算术表达式这样简单的文法也不是LR(0

44、)文法。SLR(1)分析表的构造SLR(1)分析表的构造是在LR(0)分析表基础上进行的，只要对LR(0)分析表的构造方法稍加修改，就可获得SLR(1)分析表的构造方法，修改部分如下所述：（一）准备工作（增加 ） 4）计算非终结符的follow集。（二）构造法（一）（三）（四）（五）同LR(0) 分析表构造法）2）若归约项目A.Ii，对于任何afollow(A)，置Mia=rk（k是产生式A的编号，r表示归约）。接上例，构造G的SLR(1)分析表。解：（一）预备工作1）文法拓广2）产生式编号3）构造状态转换函数GO(I,X)和项目集规范族4）计算非终结符的follow集folow(S)=#、f

45、olow(E)=#,+,)、folow(T)=#,+,),*、folow(F)=#,+,),*（二）构造分析表SLR(1)分析表和SLR(1)文法 根据上述方法构造的分析表若不含多重定义入口，则该表是SLR(1)分析表，相应文法是SLR(1)文法。LR(0)文法一定是SLR(1)文法，反之未必成立。SLR(1)分析法在理论上并不严格，但SLR(1)分析法很实用，又比较容易实现，能解决大部分语言的识别问题。理由： 根据follow集的定义，afollow(A)仅仅表示在某些句型中终结符a紧跟在非终结符A的后面，并不是表示在所有包含A的句型中，终结符a都紧跟在非终结符A的后面。要真正严格地并且精确

46、地向前看一个输入符号的话，那就要使用规范LR分析法，即LR(1)分析法。LR语法分析器的控制程序（一）数据结构1）LR分析表2）状态栈 在归约时，控制程序应按原路径折回，故在分析过程中需将所经历的状态记录下来，以便获得折回点。设置状态栈，用于记录分析过程中所经历的状态，即路径。3）符号栈 用于记录路径的符号，它和状态栈等高。符号栈的设置是为了便于说明，实际语法分析器无符号栈。4）产生式右部符号串长度 因每个状态仅识别一个符号，退回的状态数和构成句柄的字符数相等，故需存储产生式右部符号串长度。5）产生式左部符号 归约后，根据左部符号进入下一状态。手工模拟控制程序计算假设源程序为：a*b+c。经词法分析，用单词种别表示为：i*i+i#。栈的内容采用水平方式表示，分析过程如下step状态栈符号栈输入串动作0)0#i*i+i#初始1)05#i*i+i#移进2)03#F*i+i#归约3)02 #T*i+i#归约4)027#T*i+i#移进5)0275#T*i+i#移进6)02710#T*F+i#归约7)02#T+i#归约8)01#E+i#归约9)016#E+i#移进10)016