《编译原理复习纲要》由会员分享，可在线阅读，更多相关《编译原理复习纲要（20页珍藏版）》请在金锄头文库上搜索。
1、第十二章 代码生成1、代码生成的任务。2、目标代码的三种形式。3、寄存器的分配原则。编译原理复习纲要第十一章 代码优化1、代码优化的概念2、代码优化的原则：等价原则、有效原则 。3、代码优化的阶段及优化的分类。4、6种常用优化技术。5、基本块及基本块划分方法。6、利用DAG图进行局部优化。 7、求必经结点集、回边，寻找循环。例P268 6 B1： A:=B*C D:=B/C E :=A+D F :=2*E G :=B*C H :=G*G F :=H*G L :=F M :=Ln1n2n3n4n5n8n6n7BCADE2F,GH,M,L* *+/n9FA:=B*C D:=B/C E :=A+D
2、G :=A H :=G*G F :=H*G L :=F M :=FA:=B*C G :=A H :=G*G F :=H*G L :=F M :=FG := B*C H :=G*G L := H*G M :=LG,L,M被引用G := B*C H :=G*G L := H*GL被引用合并BCn1n2n3n4n5n8n6n7ADE2,GH,M,L* *+/n9F第十章 目标程序运行时的存储组织1、存储分配策略：静态存储分配、动态存 储分配（栈式，堆式）2、不同的程序结构应采用何种分配方案？ 如何实现此方案？作业 (1)对以下的Pascal程序画出过 程C第二次被调用时的运行栈 ，控制链和存取链.
3、(2)如果把存取链改成DISPLAY ，重新做(1) program env;procedure A;var x :integer;procedure B;procedure C;begin x:=2; B end; (c过程)begin C end; (B过程)begin B end ; (A过程)begin A end; (main)程序的结构为：envAB Ccall Bcall C call Bcall A 程序的调用过程为： envA B C B C程序的结构为：envAB Ccall Bcall C call Bcall A第八章 语法制导翻译和中间代码生成1、属性文法，语法制导定
4、义的形式，综合 属性，继承属性的概念。2、中间代码的表示形式。3、根据语法制导翻译的方法，写出产生式 相应的语义规则。 例 B:=2*Pi*(R+r)*(R-r)(5)B:=T2*T3(*，2，Pi，T0)(+，R，r，T1)(*，T0，T1，T2)(-，R，r，t3)(*，T2，T3，B)或(1)T0:=2*Pi(2)T1:=R+r(3)T2:=T0*T1 (4)T3:=R-r逆波兰式：B2Pi*Rr+*Rr-*=第七章 LR分析法1、构造识别文法活前缀的DFA M。2、构造LR(0),SLR(1),LR(1)分析表。3、LR(0),SLR(1),LR(1)文法的概念。4、用LR(0),SL
5、R(1),LR(1)对输入串进行分析。5、项目的分类:移进项目、待约项目、归约项目、接受项目 。6、项目的冲突：归约移进冲突、归约归约冲突。例：P166 3 LRLR分析表的构造算法分析表的构造算法 1 1、GO(IGO(Ik k,a,a)=)=I Ij j,a,a V VT T，则，则ACTIONk,aACTIONk,a=S Sj j。2 2、若、若A A I Ik k, ,则对任何则对任何a a V VT T( (或或),),则则ACTIONk,aACTIONk,a=r rj j; ; 其中其中j j为产生式为产生式A A的编号。（的编号。（LRLR（0 0）若若A A I Ik k, ,
6、则对任何则对任何a a FOLLOW(AFOLLOW(A) ), ,则则ACTIONk,aACTIONk,a=r rj j; ; 其中其中j j为产生式为产生式A A 的编号。（的编号。（SLRSLR（1 1）若项目若项目( (A A,a,a) )属于属于I Ik k，则置，则置ACTIONk,aACTIONk,a=r rj j; ; 其中其中j j 为为产生式产生式A A的编号的编号；（；（LRLR（1 1）3 3、若、若SSSS I Ik k, , 则则ACTIONkACTIONk, ,=acc=acc。若若(S(SS,#)S,#)属于属于I Ik k, ,则置则置ACTIONkACTIO
7、Nk, ,=acc;=acc;4 4、若、若GO(GO(I Ik k，A)=A)=I Ij j,A,A V VN N，则，则GOTOk,AGOTOk,A=j;=j;5 5、其余为、其余为“出错标志出错标志”。 P168、16 给定文法： Sdo S or S|do S|S;S|act (1)构造识别该文法活前缀的DFA (2)该文法是LR(0)吗?是SLR(1)吗?说明理由 (3)构造SLR(1)分析表 解:扩充文法后为: (0)ES (1)S do S or S (2)S do S (3)S S;S (4)S act0: E S S do S or S S do S S S;S S act1
8、:ES SS ;S 3: S act 2:Sdo S or S S do S S do S or S S do S S S;S S actdoactS4:SS; S S do S or S S do S S S;S S act;do6:SS; S S S ;SSS5:Sdo S or S S do S S S ;Sor7:Sdo S or S S do S or S S do S S S;S S actactact;S8:Sdo S or S S S ;S;doact3do; 例：有如下文法: 1. Z S 2. S L=R 3. S R 4. L aR 5. L b 6. R L 按照求LR
9、(1)项目集规范族的算法，求 G(S)文法的项目集族 解：求初态项目集I0：从(Z S,#)项 目开始求闭包得：第六章 自底向上优先分析法1、自底向上语法分析法基本思想：从输入的符 号串开始，利用文法的规则步步向上进行直接 归约，试图归约到文法的识别符号/开始符号 。2、自底向上分析法：优先分析法、LR分析法。3、符优先分析表（表达式）的构造和算符优先 分析算法。（求firstvt集和lastvt集，构造 优先关系表，对输入串进行分析。）第五章 自顶向下语法分析方法1、向下语法分析基本思想：从识别符号出发 ，不断建立直接推导，试图构造一个推导 系列，最终由它推导出与输入符号串相同 的符号串。2
10、、LL（1）文法的判别：相同左部产生式的 SELECT交集为空则此文法为LL（1）文法。 （若有一相同左部产生式的SELEC交集不空 ，则不是LL（1）文法）3、某些非LL（1）文法转换为LL（1）文法（ 提取左公因子，消除左递归）5、自顶向下分析法（预测分析法）步骤：（1）求出FIRST和FOLLOW及SELECT集合。（2）构造预测分析表（LL（1）分析表）。（3）对输入串进行分析。P100 第2题第四章 词法分析1、已知语言，能写出正规表达式。反之， 给出正规表达式，能写出描述的语言。2、DFA，NFA概念以及它们之间的转换方法 ，DFA的化简。3、正规表达式转换成FA。 4、词法分析器的功能。第三章 文法和语言1、程序语言的形式描述，文法的分类，推导，句型，句 子的概念。2、对程序语言来说，已知语言，能写出其文法；反之， 根据文法，能描述出文法定义的语言。3、分析树，二义性，短语，直接短语，句柄，素短语， 用分析树图示对句型的推导，并解释上述概念。 例：对于文法GS：S(L)|aS|a LL,S|S (1)画出句型(S,(a)的语法树。 (2)写出上述句型的所有短语，直接短语，句柄和素短语 。第一章 编译程序概论1、编译程序功能。2、编译方式、解释方式及其区别。3、编译程序的构成，工作流程及各部分的功能 。4、“遍”的概念。5、有害规则、多余规则。
