《编译原理-刘善梅》第12章编译原理总复习.ppt

,编译原理总复习,1.绪论,编译器概念 编译器的各个阶段,源程序,词法分析器,错 误 处 理 器,符 号 管 理 表,语法分析器,语义分析器,中间代码生成器,代码优化器,代码生成器,2.编译基础-形式语言,文法的形式定义（定义、分类） 重点掌握2型文法和3型文法 句型、句子、语言的概念 正规文法与有穷自动机 正规文法 产生的语言的推导 写出产生语言L(G)的正规文法 有穷自动机的形式定义 上下文无关文法 规范推导、规范句型 语法树,3.词法分析,词法分析的任务 词法分析器的功能和输出形式 正规表达式与有限自动机 1.正规式和正规集 2.确定有限自动机(DFA): DFA的 3种表示形式； 会分析DFA能识别的语言； 3.非确定有限自动机(NFA)： NFA与DFA的区别； NFA转换为等价的DFA，即NFA的确定化,3.词法分析,4.正规式与有限自动机的等价性 NFA to r； r to NFA; 5.确定有限自动机的化简 词法分析的任务 词法分析器的功能和输出形式 正规表达式与有限自动机 1.正规式和正规集 2.确定有限自动机(DFA): DFA的 3种表示形式； 会分析DFA能识别的语言； 3.非确定有限自动机(NFA)： NFA与DFA的区别； NFA转换为等价的DFA，即NFA的确定化,FA,正规集,正规式,DFA,NFA,正规文法,3.3.1,3.3.2 3.3.3,3.3.4,3.3.5,DFA,3.3.6,易于程序实现,易于人工设计,程序的单词集合,词法规则,词法规则,3.词法分析,4.自上而下语法分析,语法分析的任务 语法分析器的功能 自上而下语法分析的基本思想和2种分析方法 自上而下分析面临的问题： “回溯”，左递归 LL(1)分析法 1.直接左递归的消除、间接左递归的消除 2.消除回溯、提左因子 3. LL(1)分析条件：用于判断一个文法是否为LL(1)文法，first集和follow集的求法,4.自上而下语法分析,两种自上而下的语法分析方法： 递归下降分析法的主要思路 预测分析法： 掌握预测分析器器模型和分析过程； 给定LL(1)文法和输入串，会构造预测分析表、并利用预测分析表对输入串进行预测分析。,5.自下而上语法分析,自下而上语法分析的基本思想和2类分析方法 自下而上分析的核心问题：识别可归约串 基本概念：短语、直接短语、句柄、规范归约与规范推导 自下而上语法分析器的工作过程：符号栈的使用 算符优先分析法 算符优先分析的基本思想 算符优先文法及优先表构造（会求文法的FIRSTVT(P) 和LASTVT(P) 、会构造优先关系表、会判断文法是否为算符优先文法？） 会求短语，直接短语，句柄，素短语、最左素短语,5.自下而上语法分析,LR分析法 LR(0)分析法 SLR(1)分析法 LR(1)分析法 注意这3种分析方法的区别与联系，LR(0)分析是基础，在掌握LR(0)分析的基础上，依据这种方法的区别和联系，可很快掌握另外两种分析方法 几个基本概念：字的前缀、活前缀、拓广文法、项目、有效项目,结论: （构造LR(0)项目集族及构造识别活前缀的时要用） 若项目A .B对活前缀=是有效的且B 是一个产生式，则项目B .对=也是有效的。,5.自下而上语法分析,LR(0)分析法 先写出文法的拓广文法，然后写出拓广文法的所有项目，根据上页的结论构造LR(0)项目集族，进而构造识别活前缀的DFA，而后依据识别活前缀的DFA和LR(0)分析表的ACTION和GOTO子表构造方法构造LR(0)分析表。构造出LR(0)分析表后，要掌握依据LR(0)分析表对某个输入串（如i*i+i ）进行自下而上的语法分析的过程，要能写出来这个分析过程。 SLR(1)分析法 和 LR(1)分析法 与 LR(0)分析法的分析过程类似，只是构造其分析表的第步有些区别,LR(0)分析表的构造,假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况： 1) 既含移进项目又含归约项目， 2) 含有多个归约项目 则称G是一个LR(0)文法。,构造LR(0)分析表的算法,令每个项目集Ik的下标k作为分析器的状态，包含项目SS的集合Ik的下标k为分析器的初态。,LR(0)分析表的ACTION和GOTO子表构造方法： 1. 若项目Aa属于Ik且GO(Ik, a)Ij，a为终结符，则置ACTIONk,a 为“sj”。 2. 若项目A属于Ik，那么，对任何终结符a(或结束符#)，置ACTIONk,a为 “rj”(假定产生式A是文法G的第j个产生式)。 3. 若项目SS属于Ik，则置ACTIONk,#为 “acc”。 4. 若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j。 5. 分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。,假定LR(0)规范族的一个项目集I=A1a11，A2a22，Amamm，B1，B2，Bn 如果集合a1，am，FOLLOW(B1)，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则： 1. 若a是某个ai，i=1,2,m，则移进； 2. 若aFOLLOW(Bi)，i=1,2,n，则用产生式Bi进行归约； 3. 此外，报错。 冲突性动作的这种解决办法叫做SLR(1)解决办法。,SLR(1)分析表的ACTION和GOTO子表构造方法： 1. 若项目Aa属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTIONk,a为 “sj”； 2. 若项目A属于Ik，那么，对任何终结符a，aFOLLOW(A)，置ACTIONk,a为 “rj”；其中，假定A为文法G的第j个产生式； 3. 若项目SS属于Ik，则置ACTIONk,#为“acc”; 4. 若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j； 5. 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,I2：SL=R RL,I2含有“移进归约”冲突。 FOLLOW(R)#, =， 移进字符“=”与归约项目的FOLLOW集相交,LR（）文法提出：,结论: （构造LR()项目集族及构造识别活前缀的时要用） AB, a对活前缀是有效的，则对于每个形如B的产生式， 对任何bFIRST(a)，B, b对也是有效的。,构造LR(1)分析表的算法。 令每个Ik的下标k为分析表的状态，令含有SS, #的Ik的k为分析器的初态。,LR(1)分析表的构造算法,LR(1)分析表的ACTION和GOTO子表构造： 1. 若项目Aa, b属于Ik且GO(Ik, a)Ij， a为终结符，则置ACTIONk, a为 “sj”。 2. 若项目A，a属于Ik，则置ACTIONk, a为 “rj”；其中假定A为文法G的第j个产生式。 3. 若项目SS, #属于Ik，则置ACTIONk, #为 “acc”。 4. 若GO(Ik，A)Ij，则置GOTOk, A=j。 5. 分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。,.属性文法与语法制导翻译,这章主要掌握一些基本概念和基本分析方法 属性文法的相关概念和说明 对继承属性和综合属性的理解 S-属性文法的自下而上计算 L-属性文法和自顶向下的翻译 对翻译模式的理解 如何将属性文法改造成翻译模式？,.语义分析和中间代码产生,中间语言： 后缀式（逆波兰表示法）； 图表示法； 三地址码：四元式、三元式 、间接三元式 赋值语句的翻译 布尔表达式的翻译 控制语句的翻译 过程调用的处理 给出一段含有上述几种语句的语言程序，会写出其中间代码 （即能将其翻译成中间代码）,布尔表达式ab or cd and ef的翻译结果,100: if ab goto 103 101: T1:=0 102: goto 104 103: T1:=1 104: if cd goto 107 105: T2:=0 106: goto 108 107: T2:=1 108: if ef goto 111 109: T3:=0 110: goto 112 111: T3:=1 112: T4:=T2 and T3 113: T5:=T1 or T4,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) ,考虑如下表达式： ab or cd and ef 假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按以上属性定义将生成如下的代码：,if ab goto Ltrue goto L1 L1: if cd goto L2 goto Lfalse L2: if ef goto Ltrue goto Lfalse,考虑如下语句 : while ab do if cd then x:=y+z else x:=y-z,生成下列代码： L1: if ab goto L2 goto Lnext L2: if cd goto L3 goto L4 L3: T1:=y+z x:=T1 goto L1 L4: T2:=y-z x:=T2 goto L1 Lnext:,翻译语句 while (ab) do if (cd) then x:=y+z;,100 (j, a, b, 102) 101 (j, -, -, 107) 102 (j, c, d, 104) 103 (j, -, -, 100) 104 (+, y, z, T) 105 (:=, T, -, x) 106 (j, -, -, 100) 107,翻译方法：把实参的地址逐一放在转子指令的前面. 例如， CALL S(A，X+Y) 翻译为: 计算X+Y置于T中的代码 par A /*第一个参数的地址*/ par T /*第二个参数的地址*/ call S /*转子*/,过程调用的翻译,8.符号表,符号表作用 符号表的组织 整理和查找（杂凑查找） 名字的作用域 1. FORTRAN的符号表组织（并列结构语言） 2. 嵌套结构语言的符号表组织（按“栈“式思想组织符号表 ）,9.运行时存储空间组织,几个概念：活动，活动的生存期，活动记录，静态链，动态链 参数传递：传地址，得结果，传值，传名 一个目标程序运行所需的存储空间包括哪些？ 活动记录中老SP与返回地址的区别，静态链与动态链的区别？ 存储分配策略有哪两种？（静态分配策略，动态分配策略） C的过程调用、过程进入、过程返回 嵌套过程语言的栈式实现非局部名字的访问的实现：静态链和活动记录；嵌套层次显示表display,10.优化,优化 优化必须遵循一定的原则 优化的种类 局部优化（划分四元式程序为基本块的算法；借助优化工具DAG图进行优化