09级编译原理复习纲要

《09级编译原理复习纲要》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十二章代码生成1、代码生成的任务。2、目标代码的三种形式。3、寄存器的分配原则。编译原理复习纲要第十一章代码优化1、代码优化的原则：等价原则、有效原则。2、代码优化的阶段及优化的分类。3、6种常用优化技术。4、基本块及基本块划分方法。5、利用DAG图进行局部优化。6、求必经结点集、回边，寻找循环。例P2686B1：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:=

2、AH:=G*GF:=H*GL:=FM:=FG:=B*CH:=G*GL:=H*GM:=LG,L,M被引用G:=B*CH:=G*GL:=H*GL被引用合并BCn1n2n3n4n5n8n6n7ADE2,GH,M,L****+/n9F第十章目标程序运行时的存储组织1、存储分配策略：静态存储分配、动态存储分配（栈式，堆式）2、不同的程序结构应采用何种分配方案？如何实现此方案？作业(1)对以下的Pascal程序画出过程C第二次被调用时的运行栈，控制链和存取链.(2)如果把存取链改成DISPLAY，重新做(1)programenv;procedureA;varx:integer;procedureB;pr

3、ocedureC;beginx:=2;Bend;(c过程)beginCend;(B过程)beginBend;(A过程)beginAend;(main)程序的结构为：envABCcallBcallCcallBcallA程序的调用过程为：env→A→B→C→B→C程序的结构为：envABCcallBcallCcallBcallA第八章语法制导翻译和中间代码生成1、属性文法，语法制导定义的形式，综合属性，继承属性的概念。2、中间代码的表示形式。3、根据语法制导翻译的方法，写出产生式相应的语义规则。例B:=2*Pi*(R+r)*(R-r)(5)B:=T2*T3(*，2，Pi，T0)(+，R，r，T1

4、)(*，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、构造识别文法活前缀的DFAM。2、构造LR(0),SLR(1),LR(1)分析表。3、LR(0),SLR(1),LR(1)文法的概念。4、用LR(0),SLR(1),LR(1)对输入串进行分析。5、项目的分类:移进项目、待约项目、归约项目、接受项目。6、项目的冲突：归约—移进冲突、归约—归约冲突。例：P1663LR分析表的构造算法1、GO(Ik,a)=Ij,aVT，则ACTION

5、[k,a]=Sj。2、若A•Ik,则对任何aVT(或＃),则ACTION[k,a]=rj;其中j为产生式A的编号。（LR（0）若A•Ik,则对任何aFOLLOW(A),则ACTION[k,a]=rj;其中j为产生式A的编号。（SLR（1））若项目(A•,a)属于Ik，则置ACTION[k,a]=rj;其中j为产生式A的编号；（LR（1））3、若S`S•Ik,则ACTION[k,＃]=acc。若(S`S•,#)属于Ik,则置ACTION[k,＃]=acc;4、若GO(Ik，A)=Ij,AVN，则GOTO[k,A]=j;5、其余为“出错标志”。P168、1

6、6给定文法：S→doSorS

7、doS

8、S;S

9、act(1)构造识别该文法活前缀的DFA(2)该文法是LR(0)吗?是SLR(1)吗?说明理由(3)构造SLR(1)分析表解:扩充文法后为:(0)E→S(1)S→doSorS(2)S→doS(3)S→S;S(4)S→act0:E→•SS→•doSorSS→•doSS→•S;SS→•act1:ES•SS•;S3:Sact•2:Sdo•SorSSdo•SS→•doSorSS→•doSS→•S;SS→•actdoactS4:SS;•SS→•doSorSS→•doSS→•S;SS→•act;do6:SS;S•S→S•;SSS5:SdoS•

10、orSSdoS•S→S•;Sor7:SdoSor•SS→•doSorSS→•doSS→•S;SS→•actactact;S8:SdoSorS•S→S•;S;doact3do;例：有如下文法:1.ZS2.SL=R3.SR4.LaR5.Lb6.RL按照求LR(1)项目集规范族的算法，求G(S)文法的项目集族解：求初态项目集I0：从(Z•S,#)项目开始求闭包得：0ZSSL=RSRL