编译原理复习资料.ppt
67页
基本概念基本概念•第一章第一章计算机程序设计语言计算机程序设计语言高级语言的执行过程高级语言的执行过程解释程序、编译程序及其区别解释程序、编译程序及其区别编译过程的五个阶段编译过程的五个阶段编译程序的七个组成部分及其关系编译程序的七个组成部分及其关系“遍遍”的概念的概念编译程序的开发技术编译程序的开发技术构造编译程序所应掌握的内容构造编译程序所应掌握的内容 基本概念基本概念•第二章第二章单词符号的分类和输出形式单词符号的分类和输出形式状态转换图状态转换图正规表达式和正规集正规表达式和正规集符号、字母表、符号串、空符号串、符号串集合符号、字母表、符号串、空符号串、符号串集合自反闭包、正则闭包自反闭包、正则闭包有限自动机、确定有限自动机、非确定有限自动机有限自动机、确定有限自动机、非确定有限自动机有限自动机的表示有限自动机的表示词法分析器自动生成系统词法分析器自动生成系统LEX、语法分析器自动生、语法分析器自动生成工具成工具YACC 基本概念基本概念•第三章第三章文法和语言文法和语言文法的开始符号、终结符、非终结符和产生式文法的开始符号、终结符、非终结符和产生式直接推导和推导、最左推导、最右推导直接推导和推导、最左推导、最右推导文法产生的语言文法产生的语言形式语言分类、四类文法的关系与区别形式语言分类、四类文法的关系与区别规范推导、短语、句柄、素短语规范推导、短语、句柄、素短语语法树、子树和短语语法树、子树和短语文法的二义性文法的二义性 基本概念基本概念•第三章（续）第三章（续）自上而下分析法：递归下降分析、自上而下分析法：递归下降分析、LL(1)分析分析递归下降分析法递归下降分析法要点要点:自上而下分析存在的不确定性自上而下分析存在的不确定性 如何实现确定的如何实现确定的(即无回溯的即无回溯的)自上而下分析自上而下分析? 消除左递归、消除回溯消除左递归、消除回溯LL(1)分析法分析法要点要点: LL(1)分析法的基本思想分析法的基本思想 LL(1)分析器组成分析器组成 LL(1)文法的性质文法的性质 基本概念基本概念•第三章（续）第三章（续）自下而上分析法：算符优先分析法、自下而上分析法：算符优先分析法、LR分析法分析法归约、规范归约、可归约串、最左素短语归约、规范归约、可归约串、最左素短语算符文法和算符优先文法算符文法和算符优先文法算符优先关系表算符优先关系表LR分析法对文法的限制分析法对文法的限制LR分析器的工作原理分析器的工作原理活前缀、活前缀、 LR(0)项目、项目、 LR(0)项目集规范族项目集规范族拓广文法、拓广文法、 LR(0)文法文法SLR(1)分析法、分析法、 SLR(1)文法文法 基本概念基本概念•第四章第四章语义分析的概念语义分析的概念语法制导翻译方法语法制导翻译方法文法的属性、文法的属性、继承属性与综合属性继承属性与综合属性属性文法属性文法几种常见的中间语言几种常见的中间语言数组元素的地址计算数组元素的地址计算变址存数、变址取数变址存数、变址取数 基本概念基本概念•第五章第五章优化、优化三个不同的级别优化、优化三个不同的级别局部优化、循环优化和全局优化局部优化、循环优化和全局优化基本块、局部优化常用的优化技术基本块、局部优化常用的优化技术利用利用DAG进行基本块优化的基本思想进行基本块优化的基本思想程序流图、必经结点、必经结点集、回边、循环程序流图、必经结点、必经结点集、回边、循环可归约流图可归约流图循环循环优化常用的优化技术优化常用的优化技术 基本方法基本方法•正规表达式和正规集正规表达式和正规集•正规表达式到有限自动机的构造正规表达式到有限自动机的构造•文法和语言文法和语言•推导和归约推导和归约•文法二义性的消除文法二义性的消除•消除左递归、消除回溯消除左递归、消除回溯•LL(1)文法的判别文法的判别•FIRST集合、集合、FOLLOW集合的构造集合的构造•LL(1)分析表的构造分析表的构造 基本方法基本方法•算符优先文法的判别算符优先文法的判别•FIRSTVT集合、集合、LASTVT集合的构造集合的构造•算符优先关系表的构造算符优先关系表的构造•LR(0)分析表的构造分析表的构造•SLR(1)分析表的构造分析表的构造•表达式翻译成逆波兰式表达式翻译成逆波兰式•典型语句的翻译（生成四元式序列）典型语句的翻译（生成四元式序列）•基本块的划分、基本块的优化基本块的划分、基本块的优化•程序流图、必经结点集、回边、循环程序流图、必经结点集、回边、循环 正规式到正规文法的转换正规式到正规文法的转换与正规式与正规式R=a(a|d)*等价的正规文法等价的正规文法G的产生过程为的产生过程为1.正规式正规式a(a|d)*的字母表的字母表∑={a,d},故故G的的VT={a,d}2.设定开始符号设定开始符号S,生成产生式生成产生式S→ a(a|d)*3.按分解规则按分解规则: S→aA,A→(a|d)* S→aA,A→(a|d)A,A→εε S→aA,A→aA|dA,A→εε故得到等价的正规文法故得到等价的正规文法G: S→aA A→aA|dA|εε 正规文法到正规式的转换正规文法到正规式的转换与含有下列产生式的正规文法与含有下列产生式的正规文法G: S→aA A→aA|aB B→bC C→cB|c等价的正规式的产生过程为等价的正规式的产生过程为将将C→cB|c代入代入B→bC得得B→b(cB|c),即即B→bcB|bc也就是也就是B→(bc)*(bc)或者写成或者写成B→(bc)+将将B→(bc)+代入代入A→aA|aB得得A→aA|a(bc)+,即即A→a+(bc)+将将A→a+(bc)+代入代入S→aA得得S→aa+(bc)+因此因此,与文法与文法G等价的正规式为等价的正规式为aa+(bc)+ 正规文法到正规文法到FA的转换方法的转换方法设有正规文法设有正规文法G[S]: S→aA|bB|a A→aB|bA B→aS|bA|b则与则与G[S]等价的等价的FA构造过程如下构造过程如下:1.FA的的∑={a,d}.2.G[S]有三个非终结符有三个非终结符S、、A、、B,对应对应FA的三个状态的三个状态.3.S为开始状态为开始状态.4.另设一个状态另设一个状态Z作为作为FA的终态的终态.5.对对G[S]的每个产生式构造转换函数的每个产生式构造转换函数,画出画出FA的状态的状态转换图转换图. SBZAabbbaaab FA到正规文法的转换方法到正规文法的转换方法有有FA如右图所示。
如右图所示构造其对应的正规文构造其对应的正规文法法G=(VN,VT,S,P)1.VT={0,1}2.VN={A,B,C,D}3.开始符为开始符为A4.产生式为：产生式为： A→1D|0B|0 B→0D|1C C→0B|1D|0 D→0D|1B|1ADBC01111000 FA到正规式的转换方法到正规式的转换方法02413a,baba,ba,bba FA到正规式的转换方法到正规式的转换方法（续）（续）02413a,baba,ba,bbaXεεYεεεε FA到正规式的转换方法到正规式的转换方法（续）（续）024a|bbba|ba|baaXεεYεεεε FA到正规式的转换方法到正规式的转换方法（续）（续）0a|bbb(a|b)*aa(a|b)*XεεY FA到正规式的转换方法到正规式的转换方法（续）（续）0a|b(aa|bb)(a|b)*XεεYXY(a|b)*(aa|bb)(a|b)* 正规式到正规式到FA的转换方法的转换方法将正规式将正规式r=10|(0|11)0*1转换成等价的转换成等价的FA:XY10|(0|11)0*1XY(0|11)0*110 正规式到正规式到FA的转换方法的转换方法（续）（续）XY(0|11)0*1110 正规式到正规式到FA的转换方法的转换方法（续）（续）XY0*110230|111 正规式到正规式到FA的转换方法的转换方法（续）（续）XY0*110231110 正规式到正规式到FA的转换方法的转换方法（续）（续）XY0*1102311041 正规式到正规式到FA的转换方法的转换方法（续）（续）XYεε11023110415ε0 文法和语言文法和语言1.已知文法已知文法G，求，求L(G):例如：文法例如：文法G:S→0S1|01描述的语言是：描述的语言是： L(G)={0n1n|n≥1}也可以用文字描述。
也可以用文字描述特别，已知文法特别，已知文法G和若干句子，判断哪个（些）句和若干句子，判断哪个（些）句子是由文法子是由文法G产生的；产生的； 文法和语言文法和语言（续）（续）已知语言已知语言L(G)，构造文法，构造文法G:例如：例如：L(G)={abna|n≥0}，文法，文法G=(VT,VN,S,P): 其中：其中：VT={a,b}, VN={S,R}, S为开始符为开始符, P为：为：S→aa|aRa R→b|Rb 文法和语言文法和语言（续）（续）1.L(G)={0n|n≥1} G[S]:S→0|0S2.L(G)={0n|n≥0} G[S]:S→εε|0S3.L(G)={1n0m|n≥m≥1} G[S]:S→AB A→1|1A B→0|0B4.L(G)={1n0n|n≥1} G[S]:S→1S0|105.L(G)={1n0n|n≥0} G[S]:S→1S0|εε6.L(G)={anbmck|n,m,k≥1} G[S]:S→ABC A→a|aA B→b|bB C→c|cC 词法分析程序的自动生成工具词法分析程序的自动生成工具LEX简介简介 LEX是一个已被广泛使用的词法分析程序的自是一个已被广泛使用的词法分析程序的自动生成工具，在动生成工具，在UNIX系统中用系统中用lex命令调用，我们命令调用，我们只要告诉只要告诉LEX某种语言的单词是如何构成的，它就某种语言的单词是如何构成的，它就能够构造出该语言的词法分析程序。
能够构造出该语言的词法分析程序 我们知道，程序设计语言的单词可以用正规式 我们知道，程序设计语言的单词可以用正规式进行描述，根据正规式可以构造出识别单词的词法进行描述，根据正规式可以构造出识别单词的词法分析程序．分析程序．LEX接受这种正规式，然后自动生成单接受这种正规式，然后自动生成单词的识别程序（即词法分析程序），这一过程可以词的识别程序（即词法分析程序），这一过程可以理解为将正规式翻译成识别程序，所以理解为将正规式翻译成识别程序，所以LEX也被称也被称做做LEX编译程序编译程序 假定要做生成 假定要做生成A语言的词法分析程序，则语言的词法分析程序，则LEX编译程序、编译程序、A语言词法分析器的关系如下图所示语言词法分析器的关系如下图所示 词法分析程序的自动生成工具词法分析程序的自动生成工具LEX简介（续）简介（续）A语言的语言的LEX源程序源程序LEX编译程序编译程序A语言词法分析器语言词法分析器A语言源程序语言源程序A语言源程序语言源程序中的单词中的单词 词法分析程序的自动生成工具词法分析程序的自动生成工具LEX简介（续）简介（续） 具体来说， 具体来说，LEX用自己的一种语言用自己的一种语言——LEX语言来对语言来对A语言的词法分析器进行说明，形成一语言的词法分析器进行说明，形成一个个LEX源程序，其一般格式为源程序，其一般格式为 ｛辅助定义部分｝ ｛辅助定义部分｝ ％％ ％％ ｛识别规则部分｝ ｛识别规则部分｝ ％％ ％％ ｛用户子程序部分｝ ｛用户子程序部分｝ 词法分析程序的自动生成工具词法分析程序的自动生成工具LEX简介（续）简介（续）１．辅助定义部分１．辅助定义部分 这部分是为了给用户在后面的使用中提供方便而设计的， 这部分是为了给用户在后面的使用中提供方便而设计的，如为一个复杂的正规式定义一个名字，定义的格式为如为一个复杂的正规式定义一个名字，定义的格式为 名字 正规式 名字 正规式 例如，将标识符（字母开头的字母数字串）的正规式［例如，将标识符（字母开头的字母数字串）的正规式［a-zA-Z］［］［a-zA-Z0-9］＊定义为名字］＊定义为名字id、无符号整常数（数字、无符号整常数（数字串）的正规式［串）的正规式［0-9］［］［0-9］＊定义为名字］＊定义为名字number，则可以，则可以给出以下辅助定义：给出以下辅助定义： id ［［a-zA-Z］［］［a-zA-Z0-9］＊］＊ number ［［0-9］［］［0-9］＊］＊ 正规式被定义后，在后面的识别规则中就可以用名字替代 正规式被定义后，在后面的识别规则中就可以用名字替代这个正规式了，其使用方法是用这个正规式了，其使用方法是用“｛｝｛｝”将名字括起来，如将名字括起来，如｛｛id｝，这样｝，这样LEX就会自动用已定义的正规式去解释就会自动用已定义的正规式去解释id。
词法分析程序的自动生成工具词法分析程序的自动生成工具LEX简介（续）简介（续）２２.识别规则部分识别规则部分 这部分是一串如下形式的 这部分是一串如下形式的LEX语句：语句： P1 {A1} P2 {A2} …… Pn {An} 其中： 其中： ⑴⑴每一个每一个Pi都是一个正规式，定义了一种单词的词形都是一个正规式，定义了一种单词的词形 ⑵⑵每一个每一个Ai是配备给是配备给Pi的一小段程序代码，指出了即将生成的的一小段程序代码，指出了即将生成的词法分析程序在识别了词法分析程序在识别了Pi所定义的单词之后需要做的所定义的单词之后需要做的“动作动作”，例如向语法分析程序返回该单词的机内码例如向语法分析程序返回该单词的机内码 事实上， 事实上，LEX语言并不是一个完整的语言，它只是某种语言并不是一个完整的语言，它只是某种程序设计语言的扩充，这种程序设计语言也称做宿主语言，程序设计语言的扩充，这种程序设计语言也称做宿主语言，LEX本身没有描述本身没有描述“动作动作”的语句，的语句，“动作动作”的描述是由宿的描述是由宿主语言完成的，例如，宿主语言是主语言完成的，例如，宿主语言是C语言，则每个语言，则每个Ai就是一段就是一段C语言程序。
语言程序 词法分析程序的自动生成工具词法分析程序的自动生成工具LEX简介（续）简介（续）３．用户子程序部分３．用户子程序部分 当词法分析程序对源程序完成扫描时，用户 当词法分析程序对源程序完成扫描时，用户可能希望词法分析程序再做某些工作，如输出表可能希望词法分析程序再做某些工作，如输出表格、输出统计结果等，这时，用户就可以编写一格、输出统计结果等，这时，用户就可以编写一个子程序，并将该子程序放在这里个子程序，并将该子程序放在这里 若用户对 若用户对A语言编写了以上格式的语言编写了以上格式的LEX源程源程序，则序，则LEX编译程序会根据其中每个编译程序会根据其中每个Pi的定义，的定义，自动构造出识别这些单词的自动构造出识别这些单词的C程序段，并将其与程序段，并将其与相应的相应的Ai相结合，最后结合上相结合，最后结合上“用户子程序用户子程序”就就形成了一个完整的形成了一个完整的C语言程序，这个语言程序，这个C语言程序也语言程序也就是就是A语言的词法分析程序语言的词法分析程序 语法分析器自动生成工具语法分析器自动生成工具YACC简介简介 YACC(Yet Another Compiler_Compiler)是一是一个已被广泛使用的语法分析程序的自动生成工具。
个已被广泛使用的语法分析程序的自动生成工具 YACC的输入是某种语言的语法描述，输出是该的输入是某种语言的语法描述，输出是该语言的语法分析程序假定要生成语言的语法分析程序假定要生成A语言的语法分析语言的语法分析程序，则程序，则YACC、、A语言语法分析器的关系如下图所语言语法分析器的关系如下图所示：示：YACCA语言语法分析器语言语法分析器yyparse词法分析器词法分析器yylexA语言的语言的YACC源程序源程序A语言源程序语言源程序语法分析的输出语法分析的输出 语法分析器自动生成工具语法分析器自动生成工具YACC简介（续）简介（续） 1 YACC对语言的要求对语言的要求 YACC要求要求A语言必须是上下文无关语言，且描语言必须是上下文无关语言，且描述它的文法满足述它的文法满足LALR(1)的要求，用户必须采用的要求，用户必须采用YACC提供的语法描述规格说明来描述提供的语法描述规格说明来描述A语言的文法，语言的文法，这个这个A语言的语法描述规格说明也称作语言的语法描述规格说明也称作YACC源程序 2YACC的输入输出的输入输出 YACC以以YACC源程序为输入，自动生成用源程序为输入，自动生成用LALR(1)方法进行语法分析的方法进行语法分析的A语言的语法分析程序，语言的语法分析程序，也就是生成文法的也就是生成文法的LALR(1)分析表，并与总控程序和分析表，并与总控程序和分析栈相结合，构成一个完整的分析栈相结合，构成一个完整的LALR(1)语法分析器语法分析器yyparse。
语法分析器自动生成工具语法分析器自动生成工具YACC简介（续）简介（续） 与与LEX一样，一样，YACC的宿主语言也是的宿主语言也是C，生成的，生成的yyparse也是一个也是一个C语言的程序语言的程序 yyparse要求有一个名为要求有一个名为yylex的词法分析程的词法分析程序与它配合，用户可以借助序与它配合，用户可以借助LEX来构造来构造yylex，所以，所以LEX与与YACC可以配合使用可以配合使用 YACC源程序的作用是对源程序的作用是对A语言的语法进行说语言的语法进行说明，同时给出语义动作明，同时给出语义动作——语法规则用于归约时应语法规则用于归约时应完成的动作完成的动作 yyparse的输出可以是语法树，也可以是生成的输出可以是语法树，也可以是生成的中间代码、目标代码，或者是一些语法信息，究的中间代码、目标代码，或者是一些语法信息，究竟是什么完全由语义动作及竟是什么完全由语义动作及YACC源程序中给出的源程序中给出的一些辅助过程决定一些辅助过程决定 语法分析器自动生成工具语法分析器自动生成工具YACC简介（续）简介（续） 3。
YACC源程序源程序 YACC源程序由三部分组成：说明部分、语法规则部分和源程序由三部分组成：说明部分、语法规则部分和辅助过程部分，其一般格式为辅助过程部分，其一般格式为 {说明部分说明部分} %% {语法规则部分语法规则部分} %% {辅助过程部分辅助过程部分} ⑴⑴说明部分说明部分 这部分用以定义语法规则部分要用的终结符、语义动作这部分用以定义语法规则部分要用的终结符、语义动作中使用的数据类型、变量、语义值的联合类型以及运算符的中使用的数据类型、变量、语义值的联合类型以及运算符的优先级等，具体包括：优先级等，具体包括： 头文件表：一系列的头文件表：一系列的C语言的语言的#include语句；语句； 宏定义：用宏定义：用C语言的语言的#define语句定义程序中要用的宏；语句定义程序中要用的宏； 数据类型定义：定义语义动作或辅助过程中要用到的数数据类型定义：定义语义动作或辅助过程中要用到的数据类型；据类型； 语法分析器自动生成工具语法分析器自动生成工具YACC简介（续）简介（续） 全局变量定义：定义外部变量和全局变量定义：定义外部变量和YACC源程序中源程序中要用到的全局变量；要用到的全局变量； 文法开始符号定义：定义文法的开始符号，若文法开始符号定义：定义文法的开始符号，若不定义则语法规则中第一条规则的左部符号被认为不定义则语法规则中第一条规则的左部符号被认为是开始符号。
是开始符号YACC的开始符号定义语句为的开始符号定义语句为 %start 非终结符非终结符 语义值类型定义：语法动作中使用的语义值若语义值类型定义：语法动作中使用的语义值若不定义则都认为是整型的，因此，若语义值非整型，不定义则都认为是整型的，因此，若语义值非整型，则要在此进行说明；则要在此进行说明； 终结符定义：除文字字符外，语法规则中出现终结符定义：除文字字符外，语法规则中出现的所有终结符必须在这里进行定义，定义中可以给的所有终结符必须在这里进行定义，定义中可以给出终结符名和终结符的编码（整数）；出终结符名和终结符的编码（整数）； 语法分析器自动生成工具语法分析器自动生成工具YACC简介（续）简介（续） 运算符优先级和结合性定义：运算符的结合性运算符优先级和结合性定义：运算符的结合性用语句用语句%left(左结合左结合)和和%right(右结合右结合)定义，同一定义，同一%left(right)语句中的运算符的优先级相同，前面语句中的运算符的优先级相同，前面% left(right)语句中的运算符的优先级低于后面语句中的运算符的优先级低于后面%left(right)语句中的运算符的优先级。
如语句语句中的运算符的优先级如语句 %left ‘+’ ‘-’ %left ‘*’ 定义了定义了‘+’、、‘-’、、‘*’运算都是作左结合的，运算都是作左结合的， ‘+’、、‘-’运算的优先级低于运算的优先级低于‘*’运算，运算， ‘+’、、‘-’的优先级相同的优先级相同 ⑵⑵语法规则部分语法规则部分 这部分给出了要处理的语言的文法及每个产生这部分给出了要处理的语言的文法及每个产生式的语义动作式的语义动作 语法分析器自动生成工具语法分析器自动生成工具YACC简介（续）简介（续） 若文法有产生式若文法有产生式 A→αα1 1| |αα2 2| |… … |ααn n 则在则在YACC源程序的这部分中将写成源程序的这部分中将写成 A:α1 {语义动作语义动作1} |α2 {语义动作语义动作2} … … |αn {语义动作语义动作n} ; 其中，产生式中的终结符是用单引号括起来，没括起来其中，产生式中的终结符是用单引号括起来，没括起来的且在说明部分没有被说明的字母数字串被看成是非终结符；的且在说明部分没有被说明的字母数字串被看成是非终结符；{语义动作语义动作}是是C语言的语句序列，当它放在产生式的后边时，语言的语句序列，当它放在产生式的后边时，将在用该产生式进行归约前被执行。
语义动作可以是计算、将在用该产生式进行归约前被执行语义动作可以是计算、返回语法符号的语义值，也可以是建立语法树、产生中间代返回语法符号的语义值，也可以是建立语法树、产生中间代码、输出有关信息等码、输出有关信息等 语法分析器自动生成工具语法分析器自动生成工具YACC简介（续）简介（续）⑶⑶辅助过程部分辅助过程部分 这部分由一些这部分由一些C语言的函数组成主要包括：语言的函数组成主要包括： 主程序主程序main()：完成一些初始准备工作，然后：完成一些初始准备工作，然后调用调用YACC生成的生成的yyparse()完成语法分析完成语法分析 错误信息报告程序：用户可以在这里给出自己错误信息报告程序：用户可以在这里给出自己的错误信息报告程序的错误信息报告程序 词法分析程序：在这里必须给出名为词法分析程序：在这里必须给出名为yylex的的词法分析器，每次调用词法分析器，每次调用yylex()将得到一个单词符号，将得到一个单词符号，包括单词的种别（单词种别必须在包括单词的种别（单词种别必须在YACC源程序的源程序的第一部分中给出说明）和单词的自身值。
第一部分中给出说明）和单词的自身值 其他程序段：一些必要的例行子程序，这些程其他程序段：一些必要的例行子程序，这些程序都是序都是C语言程序语言程序 推导和归约推导和归约对文法对文法G[S]: S→0S1 S→01有直接推导序列：有直接推导序列： S=>0S1=>00S11=>000111 文法二义性的消除文法二义性的消除例例1：试判断文法：试判断文法G[S]: S→ibtSeS|ibtS|a 是否为二义性文法是否为二义性文法解答：所给文法存在句子解答：所给文法存在句子ibtibtaea，该句子有两棵，该句子有两棵不同的语法树，如下图所示不同的语法树，如下图所示SSSSSeibtibtaaibtSSSibteaa所以，该文法是二义性文法所以，该文法是二义性文法 文法二义性的消除（续）文法二义性的消除（续）例例2：下面的二义性文法描述命题演算公式，为它写一：下面的二义性文法描述命题演算公式，为它写一个等价的非二义性文法个等价的非二义性文法。
G[S]:S→S and S|S or S|not S|p|q|(S) 解答：上述文法产生二义性的原因在于：运算解答：上述文法产生二义性的原因在于：运算and和和or的优先级未确定，的优先级未确定，and、、or运算的结合顺序也未确定运算的结合顺序也未确定由于运算符优先级的高低在分析过程中反映为归约由于运算符优先级的高低在分析过程中反映为归约的先后，运算结合顺序是左结合还是右结合在产生的先后，运算结合顺序是左结合还是右结合在产生式规则中反映为递归的方向是左还是右，所以根据式规则中反映为递归的方向是左还是右，所以根据命题演算中各种运算的优先级规定，构造文法如下：命题演算中各种运算的优先级规定，构造文法如下： G[S]:S→S or A|A A→A and B|B B→not B|p|q|(S) 消除左递归、消除回溯消除左递归、消除回溯1.直接左递归的消除直接左递归的消除若有文法若有文法G[B]: B→Bb B→d含有直接左递归。
将两个产生式合并为：含有直接左递归将两个产生式合并为： B→Bb|d套用公式，引入非终结符套用公式，引入非终结符B’，可改写成以下两个产，可改写成以下两个产生式以消除直接左递归：生式以消除直接左递归： B→dB’ B→bB’|εε 消除左递归、消除回溯（续）消除左递归、消除回溯（续）2.间接左递归的消除间接左递归的消除 消除以下文法消除以下文法G[S]的左递归的左递归: S→Aa|b A→Ac|Sd| εε 该文法中有该文法中有A→Ac是直接左递归，同时有是直接左递归，同时有S→Aa、、 A→Sd使得使得S=>Aa=>Sda，是间接左递归，故消除左递归，是间接左递归，故消除左递归的过程如下：的过程如下： 用用S→Aa|b 替换替换A→Sd中的中的S，得，得 A→Ac|(Aa|b)d| εε 即即A→Ac|Aad|bd| εε 这样就将间接左递归变成了直接左递归，套用公式得这样就将间接左递归变成了直接左递归，套用公式得新文法新文法G’: S→Aa|b A→bdA’|A’ A’ →cA’|adA’|εε 消除左递归、消除回溯（续）消除左递归、消除回溯（续）3.回溯的消除回溯的消除 消除以下文法消除以下文法G[S]的回溯的回溯: A→aABe A→a 消除回溯的方法是提取左公共因子，故消除消除回溯的方法是提取左公共因子，故消除回溯的过程如下：回溯的过程如下： 将两个产生式改写成将两个产生式改写成 A→aABe|a 提取左公共因子提取左公共因子a，得到，得到 A→a(ABe|εε)，引入非终结符，引入非终结符A’ 得新文法得新文法G’: A→aA’ A’→ABe|εε LL(1)文法的判别文法的判别判断文法判断文法G[S]是否为是否为LL(1)文法。
文法 S→aA A→SBe B→dC C→bC S→bB A→εε B→e C→εε ⑴⑴关于关于S：：SELECT(S→aA)=FIRST(aA)={a} SELECT(S→bB)=FIRST(bB)={b} 故：故：SELECT(S→aA)∩SELECT(S→bB)= ФФ⑵⑵关于关于A：：SELECT(A→SBe)=FIRST(SBe)={a,b} SELECT(A→εε)=FOLLOW(A)={d,e,#} 故：故：SELECT(A→SBe)∩SELECT(A→εε)= ФФ⑶⑶关于关于B：：SELECT(B→dC)=FIRST(dC)={d} SELECT(B→e)=FIRST(e)={e} 故：故： SELECT(B→dC)∩SELECT(B→e)= ФФ⑷⑷关于关于C：：SELECT(C→bC)=FIRST(bC)={b} SELECT(C→εε)=FOLLOW(C)={d,e,#} 故：故： SELECT(C→bC)∩SELECT(C→εε)= ФФ因此，因此，G[S]为为LL(1)文法。
文法 FIRST集合、集合、FOLLOW集合的构造集合的构造为文法为文法G[S]构造构造FIRST集合、集合、FOLLOW集合 S→aA A→SBe B→dC C→bC S→bB A→ε B→e C→ε SELECT(S→aA)=FIRST(aA)={a} SELECT(S→bB)=FIRST(bB)={b} SELECT(A→SBe)=FIRST(SBe)={a,b} SELECT(A→ε)=FOLLOW(A)={d,e,#} SELECT(B→dC)=FIRST(dC)={d} SELECT(B→e)=FIRST(e)={e} SELECT(C→bC)=FIRST(bC)={b} SELECT(C→ε)=FOLLOW(C)={d,e,#} LL(1)分析表的构造分析表的构造abde#SS→ aAS→ bBAA→ SBeA→ SBeA→ ε εA→ ε εA→ ε εBB→ dCB→ e eCC→ bCC→ ε εC→ ε εC→ ε ε 算符优先文法的判别算符优先文法的判别1.判断是否为算符文法；判断是否为算符文法；2.确定任意两终结符间的优先关系：确定任意两终结符间的优先关系：⑴⑴构造每个非终结符的构造每个非终结符的FIRSTVT集合；集合；⑵⑵构造每个非终结符的构造每个非终结符的LASTVT集合；集合；⑶⑶寻找终结符间的优先关系，确定是否为算符优先寻找终结符间的优先关系，确定是否为算符优先文法。
文法 FIRSTVT集合、集合、LASTVT集合的构造集合的构造FIRSTVT(B)={b|B=>b……，或，或B=>Cb……}LASTVT(B)={b|B=>……b，或，或B=>……bC}例如：有文法例如：有文法G: E→E+T|T T→T*F|F F→P^F|P P→(E)|iFIRSTVT(E)={+,*,^,(,i} LASTVT(E)={+,*,^,),i}FIRSTVT(T)={*,^,(,i} LASTVT(T)={*,^,),i}FIRSTVT(F)={^,(,i} LASTVT(F)={^,),i}FIRSTVT(P)={(,i} LASTVT(P)={),i} 算符优先关系表的构造算符优先关系表的构造⑴⑴计算计算FIRSTVT集合、集合、LASTVT集合；集合；⑵⑵拓展文法，增加一个产生式：拓展文法，增加一个产生式：S→#E#⑶⑶计算终结符间的优先关系计算终结符间的优先关系 关系：关系：∵∵ S→#E# ∴ ∴ # # P→(E) ( ) ⋖ ⋖ 、、⋗ ⋗关系：关系：∵∵ S→#E# ∴ ∴ LASTVT(E)中的每个元素中的每个元素⋗ ⋗# #⋖ ⋖FIRSTVT(E)中的每个元素中的每个元素∵∵ E→E+T ∴ ∴ LASTVT(E)中的每个元素中的每个元素⋗ ⋗+ +⋖ ⋖FIRSTVT(T)中的每个元素中的每个元素∵∵ T→T*F ∴ ∴ LASTVT(T)中的每个元素中的每个元素⋗ ⋗* *⋖ ⋖FIRSTVT(F)中的每个元素中的每个元素∵∵ F→P^F ∴ ∴ LASTVT(P)中的每个元素中的每个元素⋗ ⋗^ ^⋖ ⋖FIRSTVT(F)中的每个元素中的每个元素∵∵ P→(E) ∴ ∴ LASTVT(E)中的每个元素中的每个元素⋗ ⋗) (⋖ ⋖FIRSTVT(E)中的每个元素中的每个元素 算符优先关系表的构造（续）算符优先关系表的构造（续）+*^i()#+⋗ ⋗⋖ ⋖⋖ ⋖⋖ ⋖⋖ ⋖⋗ ⋗⋗ ⋗*⋗ ⋗⋗ ⋗⋖ ⋖⋖ ⋖⋖ ⋖⋗ ⋗⋗ ⋗^⋗ ⋗⋗ ⋗⋖ ⋖⋖ ⋖⋖ ⋖⋗ ⋗⋗ ⋗i⋗ ⋗⋗ ⋗⋗ ⋗⋗ ⋗⋗ ⋗(⋖ ⋖⋖ ⋖⋖ ⋖⋖ ⋖⋖ ⋖)⋗ ⋗⋗ ⋗⋗ ⋗⋗ ⋗⋗ ⋗#⋖ ⋖⋖ ⋖⋖ ⋖⋖ ⋖⋖ ⋖ LR(0)分析表的构造分析表的构造步骤如下：步骤如下：•将文法将文法G[S]拓广为文法拓广为文法G'[S'];•列出列出LR(0)的所有项目的所有项目;•用用ε_CLOSURE办法构造文法办法构造文法G‘[S’]的的LR(0)项目项目集规范族集规范族•根据状态转换函数根据状态转换函数GO构造出文法构造出文法G'[S']的的DFA•构造其构造其LR(0)分析表分析表 SLR(1)分析表的构造分析表的构造步骤如下：步骤如下：•将文法将文法G[S]拓广为文法拓广为文法G'[S'];•列出列出LR(0)的所有项目的所有项目;•用用ε_CLOSURE办法构造文法办法构造文法G‘[S’]的的LR(0)项目项目集规范族集规范族•根据状态转换函数根据状态转换函数GO构造出文法构造出文法G'[S']的的DFA•构造其构造其LR(0)分析表分析表•检查检查“冲突冲突”，解决，解决“冲突冲突”：计算：计算FOLLOW集集合合•修改其修改其LR(0)分析表，使之成为分析表，使之成为SLR(1)分析表分析表 1. -a+b*(-c+d)2. X:=-(a+b)/(c-d)-(a+b*c)3. a=c ∧ b=d4. a≤b+c ∧ a>d∨a+b≠ea-bc-d+*+Xab+-cd-/abc*+-:=ac= bd=∧abc+ ≤ad >∧ab+e ≠ ∨表达式翻译成逆波兰式表达式翻译成逆波兰式 典型语句的翻译（生成四元式序列）典型语句的翻译（生成四元式序列）•简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译赋值语句赋值语句:x=b*(c+d)+a⑴⑴(+,c,d,T1)⑵⑵(*,b,T1,T2)⑶⑶(+,T2,a,T3)⑷⑷(=,T3, ,x) 典型语句的翻译（生成四元式序列）典型语句的翻译（生成四元式序列） （续）（续）•布尔表达式的翻译布尔表达式的翻译 (a>b) ∧ ∧(c
一个元素占一个字节赋值语句：赋值语句：a=A[2,3]+x1.(*,2,4,t1)2.(+,t1,3,t2) ;偏移量偏移量=i*d2+j3.(-,A,5,t3) ;首地址首地址=A-54.(=[],t3[t2], ,t4)5.(+,t4,x,t5)6.(=,t5, ,a) 基本块的划分、基本块的优化基本块的划分、基本块的优化1.基本块的划分基本块的划分 read(n) i=1 FEN=1L1:if i<=N goto L2 goto L3L2:T1=FEN*i FEN=T1 i= i+1 goto L1L3:write(FEN)B1B2B3B4B5 基本块的划分、基本块的优化（续）基本块的划分、基本块的优化（续）S0=2S1=3/S0S2=T-CS3=T+CR=S0/S3H=RS4=3/S1S5=T+CS6=S4/S5H=S6*S2⑴⑴应用应用DAG对该基对该基本块进行优化；本块进行优化；⑵⑵假定只有假定只有R、、H在在基本块出口是活基本块出口是活跃的，试写出优跃的，试写出优化后的四元式代化后的四元式代码。
码n1S02n2S11.5n4n3n5n6n8n7S2TCS3RH,S4,S5,H,S6*/-+ 基本块的划分、基本块的优化（续）基本块的划分、基本块的优化（续）S0=2S4=2S1=1.5S2=T-CS3=T+CS5=S3 R=2/S3S6=RH=R*S2n1S02n2S11.5n4n3n5n6n8n7S2TCS3RH,S4,S5,S6*/-+ 程序流图、必经结点集、回边、循环程序流图、必经结点集、回边、循环求右图所示流图中的循环求右图所示流图中的循环1.各结点的必经结点集分别为：各结点的必经结点集分别为：D(n0)={n0}D(n1)={n0,n1 }D(n2)={n0,n1,n2 }D(n3)={n0,n1,n3 }D(n4)={n0,n1,n3,n4 }D(n5)={n0,n1,n3,n5 }D(n6)={n0,n1,n3,n6 }D(n7)={n0,n1,n3,n6 ,n7}2. ∵ ∵n1 DOM n6 ∴ ∴n6→n1是一条回边是一条回边3.该回边所表示的循环为该回边所表示的循环为{n1,n2,n3,n4,,n5,n6 } n2n7n6n0n3n4n5n1 。
