《《编译原理复习》ppt课件》由会员分享，可在线阅读，更多相关《《编译原理复习》ppt课件（69页珍藏版）》请在金锄头文库上搜索。
1、复习内容,基本概念 基本方法 期末考试题型分布,基本概念,第一章 计算机程序设计语言 高级语言的执行过程 解释程序、编译程序及其区别 编译过程的五个阶段 编译程序的七个组成部分及其关系 “遍”的概念 编译程序的开发技术 构造编译程序所应掌握的内容,基本概念,第二章 单词符号的分类和输出形式 状态转换图 正规表达式和正规集 符号、字母表、符号串、空符号串、符号串集合 自反闭包、正则闭包 有限自动机、确定有限自动机、非确定有限自动机 有限自动机的表示 词法分析器自动生成系统LEX、语法分析器自动生成工具YACC,基本概念,第三章 文法和语言 文法的开始符号、终结符、非终结符和产生式 直接推导和推导
2、、最左推导、最右推导 文法产生的语言 形式语言分类、四类文法的关系与区别 规范推导、短语、句柄、素短语 语法树、子树和短语 文法的二义性,基本概念,第三章（续） 自上而下分析法：递归下降分析、LL(1)分析 递归下降分析法 要点:自上而下分析存在的不确定性 如何实现确定的(即无回溯的)自上而下分析? 消除左递归、消除回溯 LL(1)分析法 要点: LL(1)分析法的基本思想 LL(1)分析器组成 LL(1)文法的性质,基本概念,第三章（续） 自下而上分析法：算符优先分析法、LR分析法 归约、规范归约、可归约串、最左素短语 算符文法和算符优先文法 算符优先关系表 LR分析法对文法的限制 LR分析
3、器的工作原理 活前缀、 LR(0)项目、 LR(0)项目集规范族 拓广文法、 LR(0)文法 SLR(1)分析法、 SLR(1)文法,基本概念,第四章 语义分析的概念 语法制导翻译方法 文法的属性、继承属性与综合属性 属性文法 几种常见的中间语言 数组元素的地址计算 变址存数、变址取数,基本概念,第五章 优化、优化三个不同的级别 局部优化、循环优化和全局优化 基本块、局部优化常用的优化技术 利用DAG进行基本块优化的基本思想 程序流图、必经结点、必经结点集、回边、循环 可归约流图 循环优化常用的优化技术,基本方法,正规表达式和正规集 正规表达式到有限自动机的构造 文法和语言 推导和归约 文法二
4、义性的消除 消除左递归、消除回溯 LL(1)文法的判别 FIRST集合、FOLLOW集合的构造 LL(1)分析表的构造,基本方法,算符优先文法的判别 FIRSTVT集合、LASTVT集合的构造 算符优先关系表的构造 LR(0)分析表的构造 SLR(1)分析表的构造 表达式翻译成逆波兰式 典型语句的翻译（生成四元式序列） 基本块的划分、基本块的优化 程序流图、必经结点集、回边、循环,正规式到正规文法的转换,与正规式R=a(a|d)*等价的正规文法G的产生过程为 正规式a(a|d)*的字母表=a,d,故G的VT=a,d 设定开始符号S,生成产生式S a(a|d)* 按分解规则: SaA,A(a|d
5、)* SaA,A(a|d)A,A SaA,AaA|dA,A 故得到等价的正规文法G: SaA AaA|dA|,正规文法到正规式的转换,与含有下列产生式的正规文法G: SaA AaA|aB BbC CcB|c 等价的正规式的产生过程为 将CcB|c代入BbC得Bb(cB|c),即BbcB|bc 也就是B(bc)*(bc)或者写成B(bc)+ 将B(bc)+代入AaA|aB得AaA|a(bc)+,即Aa+(bc)+ 将Aa+(bc)+代入SaA得Saa+(bc)+ 因此,与文法G等价的正规式为aa+(bc)+,正规文法到FA的转换方法,设有正规文法GS: SaA|bB|a AaB|bA BaS|b
6、A|b 则与GS等价的FA构造过程如下: FA的=a,d. GS有三个非终结符S、A、B,对应FA的三个状态. S为开始状态. 另设一个状态Z作为FA的终态. 对GS的每个产生式构造转换函数,画出FA的状态转换图.,S,B,Z,A,a,b,b,b,a,a,a,b,FA到正规文法的转换方法,有FA如右图所示。 构造其对应的正规文法G=(VN,VT,S,P) VT=0,1 VN=A,B,C,D 开始符为A 产生式为： A1D|0B|0 B0D|1C C0B|1D|0 D0D|1B|1,A,D,B,C,0,1,1,1,1,0,0,0,FA到正规式的转换方法,0,2,4,1,3,a,b,a,b,a,b
7、,a,b,b,a,FA到正规式的转换方法（续）,0,2,4,1,3,a,b,a,b,a,b,a,b,b,a,X,Y,FA到正规式的转换方法（续）,0,2,4,a|b,bb,a|b,a|b,aa,X,Y,FA到正规式的转换方法（续）,0,a|b,bb(a|b)*,aa(a|b)*,X,Y,FA到正规式的转换方法（续）,0,a|b,(aa|bb)(a|b)*,X,Y,X,Y,(a|b)*(aa|bb)(a|b)*,正规式到FA的转换方法,将正规式r=10|(0|11)0*1转换成等价的FA:,X,Y,10|(0|11)0*1,X,Y,(0|11)0*1,10,正规式到FA的转换方法（续）,X,Y,
8、(0|11)0*1,1,1,0,正规式到FA的转换方法（续）,X,Y,0*,1,1,0,2,3,0|11,1,正规式到FA的转换方法（续）,X,Y,0*,1,1,0,2,3,11,1,0,正规式到FA的转换方法（续）,X,Y,0*,1,1,0,2,3,1,1,0,4,1,正规式到FA的转换方法（续）,X,Y,1,1,0,2,3,1,1,0,4,1,5,0,文法和语言,1.已知文法G，求L(G): 例如：文法G:S0S1|01描述的语言是： L(G)=0n1n|n1 也可以用文字描述。 特别，已知文法G和若干句子，判断哪个（些）句子是由文法G产生的；,文法和语言（续）,已知语言L(G)，构造文法
9、G: 例如：L(G)=abna|n0，文法G=(VT,VN,S,P): 其中：VT=a,b, VN=S,R, S为开始符, P为：Saa|aRa Rb|Rb,文法和语言（续）,L(G)=0n|n1 GS:S0|0S L(G)=0n|n0 GS:S|0S L(G)=1n0m|nm1 GS:SAB A1|1A B0|0B L(G)=1n0n|n1 GS:S1S0|10 L(G)=1n0n|n0 GS:S1S0| L(G)=anbmck|n,m,k1 GS:SABC Aa|aA Bb|bB Cc|cC,词法分析程序的自动生成工具LEX简介,LEX是一个已被广泛使用的词法分析程序的自动生成工具，在UN
10、IX系统中用lex命令调用，我们只要告诉LEX某种语言的单词是如何构成的，它就能够构造出该语言的词法分析程序。 我们知道，程序设计语言的单词可以用正规式进行描述，根据正规式可以构造出识别单词的词法分析程序LEX接受这种正规式，然后自动生成单词的识别程序（即词法分析程序），这一过程可以理解为将正规式翻译成识别程序，所以LEX也被称做LEX编译程序。 假定要做生成A语言的词法分析程序，则LEX编译程序、A语言词法分析器的关系如下图所示。,词法分析程序的自动生成工具LEX简介（续）,A语言的LEX源程序,LEX编译程序,A语言词法分析器,A语言源程序,A语言源程序中的单词,词法分析程序的自动生成工具
11、LEX简介（续）,具体来说，LEX用自己的一种语言LEX语言来对A语言的词法分析器进行说明，形成一个LEX源程序，其一般格式为 辅助定义部分 识别规则部分 用户子程序部分,词法分析程序的自动生成工具LEX简介（续）,辅助定义部分 这部分是为了给用户在后面的使用中提供方便而设计的，如为一个复杂的正规式定义一个名字，定义的格式为 名字 正规式 例如，将标识符（字母开头的字母数字串）的正规式a-zA-Za-zA-Z0-9定义为名字id、无符号整常数（数字串）的正规式0-90-9定义为名字number，则可以给出以下辅助定义： id a-zA-Za-zA-Z0-9 number 0-90-9 正规式被
12、定义后，在后面的识别规则中就可以用名字替代这个正规式了，其使用方法是用“”将名字括起来，如id，这样LEX就会自动用已定义的正规式去解释id。,词法分析程序的自动生成工具LEX简介（续）,.识别规则部分 这部分是一串如下形式的LEX语句： P1 A1 P2 A2 Pn An 其中： 每一个Pi都是一个正规式，定义了一种单词的词形。 每一个Ai是配备给Pi的一小段程序代码，指出了即将生成的词法分析程序在识别了Pi所定义的单词之后需要做的“动作”，例如向语法分析程序返回该单词的机内码。 事实上，LEX语言并不是一个完整的语言，它只是某种程序设计语言的扩充，这种程序设计语言也称做宿主语言，LEX本身
13、没有描述“动作”的语句，“动作”的描述是由宿主语言完成的，例如，宿主语言是C语言，则每个Ai就是一段C语言程序。,词法分析程序的自动生成工具LEX简介（续）,用户子程序部分 当词法分析程序对源程序完成扫描时，用户可能希望词法分析程序再做某些工作，如输出表格、输出统计结果等，这时，用户就可以编写一个子程序，并将该子程序放在这里。 若用户对A语言编写了以上格式的LEX源程序，则LEX编译程序会根据其中每个Pi的定义，自动构造出识别这些单词的C程序段，并将其与相应的Ai相结合，最后结合上“用户子程序”就形成了一个完整的C语言程序，这个C语言程序也就是A语言的词法分析程序。,语法分析器自动生成工具YA
14、CC简介,YACC(Yet Another Compiler_Compiler)是一个已被广泛使用的语法分析程序的自动生成工具。 YACC的输入是某种语言的语法描述，输出是该语言的语法分析程序。假定要生成A语言的语法分析程序，则YACC、A语言语法分析器的关系如下图所示：,YACC,A语言语法分析器 yyparse,词法分析器 yylex,A语言的YACC源程序,A语言源程序,语法分析的输出,语法分析器自动生成工具YACC简介（续）,1。 YACC对语言的要求 YACC要求A语言必须是上下文无关语言，且描述它的文法满足LALR(1)的要求，用户必须采用YACC提供的语法描述规格说明来描述A语言
15、的文法，这个A语言的语法描述规格说明也称作YACC源程序。 2。YACC的输入输出 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源程序由三部分组成：说明部分、语法规则部分和辅助过程部分，其一般格式为 说明
