编译原理复习纲要

《编译原理复习纲要》由会员分享，可在线阅读，更多相关《编译原理复习纲要（20页珍藏版）》请在金锄头文库上搜索。

1、第十二章第十二章 代码生成代码生成1 1、代码生成的任务。、代码生成的任务。2 2、目标代码的三种形式。、目标代码的三种形式。3 3、寄存器的分配原则。、寄存器的分配原则。编译原理复习纲要编译原理复习纲要第十一章第十一章 代码优化代码优化1 1、代码优化的概念、代码优化的概念2 2、代码优化的原则：等价原则、有效原则。、代码优化的原则：等价原则、有效原则。3 3、代码优化的阶段及优化的分类。、代码优化的阶段及优化的分类。4 4、6 6种常用优化技术。种常用优化技术。5 5、基本块及基本块划分方法。、基本块及基本块划分方法。6 6、利用、利用DAGDAG图进行局部优化。图进行局部优化。 7 7、

2、求必经结点集、回边，寻找循环。、求必经结点集、回边，寻找循环。例例P268 6B1：A:=B*CD:=B/CE :=A+DF :=2*EG :=B*CH :=G*GF :=H*GL :=FM :=Ln1n2n3n4n5n8n6n7BCADE2F,GH,M,L*+/n9FA:=B*CD:=B/CE :=A+DG :=AH :=G*GF :=H*GL :=FM :=FA:=B*CG :=AH :=G*GF :=H*GL :=FM :=FG := B*CH :=G*GL := H*GM :=LG,L,M被引用被引用G := B*CH :=G*GL := H*GL被引用被引用合并合并BCn1n2n3n

3、4n5n8n6n7ADE2,GH,M,L*+/n9F第十章第十章 目标程序运行时的存储组织目标程序运行时的存储组织1 1、存储分配策略：静态存储分配、动态存、存储分配策略：静态存储分配、动态存储分配（栈式，堆式）储分配（栈式，堆式）2 2、不同的程序结构应采用何种分配方案？、不同的程序结构应采用何种分配方案？如何实现此方案？如何实现此方案？作业作业(1)(1)对以下的对以下的PascalPascal程序画出过程序画出过程程C C第二次被调用时的运行栈，第二次被调用时的运行栈，控制链和存取链控制链和存取链. .(2)(2)如果把存取链改成如果把存取链改成DISPLAYDISPLAY，重新做，重新

4、做(1) (1) program program envenv; ; procedure A; procedure A; varvar x :integer; x :integer; procedure B; procedure B; procedure C; procedure C; begin x:=2; B end; begin x:=2; B end; (c(c过程过程) ) begin C end; (B begin C end; (B过程过程) ) begin B end ; (A begin B end ; (A过程过程) ) begin A end; (main) begin

5、A end; (main)程序的结构为：env A B C call B call C call B call A程序的调用过程为：程序的调用过程为：envA B C B C程序的结构为：env A B C call B call C call B call A第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成1 1、属性文法，语法制导定义的形式，综合、属性文法，语法制导定义的形式，综合属性，继承属性的概念。属性，继承属性的概念。2 2、中间代码的表示形式。、中间代码的表示形式。3 3、根据语法制导翻译的方法，写出产生式、根据语法制导翻译的方法，写出产生式相应的语义规则。相应的

6、语义规则。 例例 B:=2*Pi*(B:=2*Pi*(R+rR+r)*(R-r)*(R-r)(5)B:=T2*T3(5)B:=T2*T3(*(*，2 2，PiPi，T0)T0)(+(+，R R，r r，T1)T1)(*(*，T0T0，T1T1，T2)T2)(-(-，R R，r r，t3)t3)(*(*，T2T2，T3T3，B)B)或或(1)T0:=2*Pi(1)T0:=2*Pi(2)T1:=(2)T1:=R+rR+r(3)T2:=T0*T1(3)T2:=T0*T1(4)T3:=R-r(4)T3:=R-r逆波兰式：逆波兰式：B2Pi*B2Pi*RrRr+*+*RrRr-*=-*=第七章第七章 L

7、RLR分析法分析法1 1、构造识别文法活前缀的、构造识别文法活前缀的DFA MDFA M。2 2、构造、构造LR(0),SLR(1),LR(1)LR(0),SLR(1),LR(1)分析表。分析表。3 3、LR(0),SLR(1),LR(1)LR(0),SLR(1),LR(1)文法的概念。文法的概念。4 4、用用LR(0),SLR(1),LR(1)LR(0),SLR(1),LR(1)对输入串进行分析。对输入串进行分析。5 5、项目的分类、项目的分类: :移进项目、待约项目、归约项目、接受项目。移进项目、待约项目、归约项目、接受项目。6 6、项目的冲突：归约、项目的冲突：归约移进冲突、归约移进冲突

8、、归约归约冲突。归约冲突。例：例：P166 3 P166 3 LRLRLRLR分析表的构造算法分析表的构造算法分析表的构造算法分析表的构造算法1 1 1 1、GO(IGO(IGO(IGO(Ik k k k,a,a,a,a)=)=)=)=I I I Ij j j j,a,a,a,a V V V VT T T T，则，则，则，则ACTIONk,aACTIONk,aACTIONk,aACTIONk,a=S S S Sj j j j。2 2 2 2、若、若、若、若A A A A I I I Ik k k k, , , ,则对任何则对任何则对任何则对任何a a a a V V V VT T T T( (

9、 ( (或或或或),),),),则则则则ACTIONk,aACTIONk,aACTIONk,aACTIONk,a=r r r rj j j j; ; ; ; 其中其中其中其中j j j j为产生式为产生式为产生式为产生式A A A A的编号。的编号。的编号。的编号。（LRLRLRLR（0 0 0 0） 若若若若A A A A I I I Ik k k k, , , ,则对任何则对任何则对任何则对任何a a a a FOLLOW(AFOLLOW(AFOLLOW(AFOLLOW(A) ) ) ), , , ,则则则则ACTIONk,aACTIONk,aACTIONk,aACTIONk,a=r r

10、r rj j j j; ; ; ; 其中其中其中其中j j j j为产生式为产生式为产生式为产生式A A A A 的编号。（的编号。（的编号。（的编号。（SLRSLRSLRSLR（1 1 1 1） 若项目若项目若项目若项目( ( ( (A A A A,a,a,a,a) ) ) )属于属于属于属于I I I Ik k k k，则置，则置，则置，则置ACTIONk,aACTIONk,aACTIONk,aACTIONk,a=r r r rj j j j; ; ; ; 其中其中其中其中j j j j为为为为产生式产生式产生式产生式A A A A的编号的编号的编号的编号；（；（；（；（LRLRLRLR（

11、1 1 1 1）3 3 3 3、若、若、若、若SSSSSSSS I I I Ik k k k, , , , 则则则则ACTIONkACTIONkACTIONkACTIONk, , , ,=acc=acc=acc=acc。 若若若若(S(S(S(SS,#)S,#)S,#)S,#)属于属于属于属于I I I Ik k k k, , , ,则置则置则置则置ACTIONkACTIONkACTIONkACTIONk, , , ,=acc;=acc;=acc;=acc;4 4 4 4、若、若、若、若GO(GO(GO(GO(I I I Ik k k k，A)=A)=A)=A)=I I I Ij j j j,

12、A,A,A,A V V V VN N N N ，则，则，则，则GOTOk,AGOTOk,AGOTOk,AGOTOk,A=j;=j;=j;=j;5 5 5 5、其余为、其余为、其余为、其余为“出错标志出错标志出错标志出错标志”。P168P168、16 16 给定文法：给定文法：SdoSdo S or S or S|doS|do S|S;S|actS|S;S|act(1)(1)构造识别该文法活前缀的构造识别该文法活前缀的DFADFA(2)(2)该文法是该文法是LR(0)LR(0)吗吗? ?是是SLR(1)SLR(1)吗吗? ?说明理由说明理由(3)(3)构造构造SLR(1)SLR(1)分析表分析表

13、解解: :扩充文法后为扩充文法后为: :(0)ES(0)ES(1)S do S or S(1)S do S or S(2)S do S(2)S do S(3)S S;S(3)S S;S(4)S act(4)S act0: E SS do S or SS do SS S;SS act1:ES SS ;S 3: S act 2:Sdo S or SS do SS do S or SS do SS S;SS act do act S4:SS; SS do S or SS do SS S;SS act ; do6:SS; S S S ;S S S5:Sdo S or SS do S S S ;S or

14、7:Sdo S or SS do S or SS do SS S;SS act actact ; S8:Sdo S or S S S ;S ; do act 3 do ;例：有如下文法例：有如下文法: : 1. Z 1. Z S 2. S S 2. S L=RL=R 3. S 3. S R 4. L R 4. L aRaR 5. L 5. L b 6. R b 6. R L L按照求按照求LR(1)LR(1)项目集规范族的算法，求项目集规范族的算法，求G(S)G(S)文法的项目集族文法的项目集族解：求初态项目集解：求初态项目集I0I0：从：从(Z (Z S,#)S,#)项目项目开始求闭包得：开

15、始求闭包得：第六章第六章 自底向上优先分析法自底向上优先分析法1 1、自底向上语法分析法基本思想：从输入的符、自底向上语法分析法基本思想：从输入的符号串开始，利用文法的规则步步向上进行直接号串开始，利用文法的规则步步向上进行直接归约，试图归约到文法的识别符号归约，试图归约到文法的识别符号/ /开始符号。开始符号。2 2、自底向上分析法：优先分析法、自底向上分析法：优先分析法、LRLR分析法。分析法。3 3、符优先分析表（表达式）的构造和算符优先、符优先分析表（表达式）的构造和算符优先分析算法。（求分析算法。（求firstvtfirstvt集和集和lastvtlastvt集，构造集，构造优先关系

16、表，对输入串进行分析。）优先关系表，对输入串进行分析。） 第五章第五章 自顶向下语法分析方法自顶向下语法分析方法1 1、向下语法分析基本思想：从识别符号出发，、向下语法分析基本思想：从识别符号出发，不断建立直接推导，试图构造一个推导系不断建立直接推导，试图构造一个推导系列，最终由它推导出与输入符号串相同的列，最终由它推导出与输入符号串相同的符号串。符号串。2 2、LLLL（1 1）文法的判别：相同左部产生式的）文法的判别：相同左部产生式的SELECTSELECT交集为空则此文法为交集为空则此文法为LLLL（1 1）文法。）文法。（若有一相同左部产生式的（若有一相同左部产生式的SELECSELE

17、C交集不空，交集不空，则不是则不是LLLL（1 1）文法）文法）3 3、某些非、某些非LLLL（1 1）文法转换为）文法转换为LLLL（1 1）文法）文法（提取左公因子，消除左递归）（提取左公因子，消除左递归）5 5、自顶向下分析法（预测分析法）步骤：、自顶向下分析法（预测分析法）步骤：（1 1）求出）求出FIRSTFIRST和和FOLLOWFOLLOW及及SELECTSELECT集合。集合。（2 2）构造预测分析表（）构造预测分析表（LLLL（1 1）分析表）。）分析表）。（3 3）对输入串进行分析。）对输入串进行分析。P100 P100 第第2 2题题第四章第四章 词法分析词法分析1 1、

18、已知语言，能写出已知语言，能写出正规表达式。反之，正规表达式。反之，给出正规表达式，能写出描述的语言。给出正规表达式，能写出描述的语言。2 2、DFADFA，NFANFA概念以及它们之间的转换方法，概念以及它们之间的转换方法，DFADFA的化简。的化简。3 3、正规表达式转换成、正规表达式转换成FAFA。 4 4、词法分析器的功能。、词法分析器的功能。第三章第三章 文法和语言文法和语言1 1、程序语言的形式描述，文法的分类，推导，句型，句、程序语言的形式描述，文法的分类，推导，句型，句子的概念。子的概念。2 2、对程序语言来说，已知语言，能写出其文法；反之，、对程序语言来说，已知语言，能写出其

19、文法；反之，根据文法，能描述出文法定义的语言。根据文法，能描述出文法定义的语言。3 3、分析树，二义性，短语，直接短语，句柄，素短语，、分析树，二义性，短语，直接短语，句柄，素短语，用分析树图示对句型的推导，并解释上述概念。用分析树图示对句型的推导，并解释上述概念。 例：对于文法例：对于文法GSGS：S(L)|aS|aS(L)|aS|a LL,S|S LL,S|S(1)(1)画出句型画出句型( (S,(aS,(a)的语法树。的语法树。(2)(2)写出上述句型的所有短语，直接短语，句柄和素短语。写出上述句型的所有短语，直接短语，句柄和素短语。第一章第一章 编译程序概论编译程序概论1 1、编译程序功能。、编译程序功能。2 2、编译方式、解释方式及其区别。、编译方式、解释方式及其区别。3 3、编译程序的构成，工作流程及各部分的功能。、编译程序的构成，工作流程及各部分的功能。4 4、“遍遍”的概念。的概念。5 5、有害规则、多余规则。、有害规则、多余规则。