漳州师范学院编译原理复习纲要.ppt

第十二章代码生成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:=L,B,C,A,D,E,2,F,G,H,M,L,*,*,*,*,+,/,F,A:=B*CD:=B/CE:=A+DG:=AH:=G*GF:=H*GL:=FM:=F,A:=B*CG:=AH:=G*GF:=H*GL:=FM:=F,G:=B*CH:=G*GL:=H*GM:=L,G,L,M被引用,G:=B*CH:=G*GL:=H*G,L被引用,合并,B,C,第十章目标程序运行时的存储组织1、存储分配策略：静态存储分配、动态存储分配（栈式，堆式）2、不同的程序结构应采用何种分配方案？如何实现此方案？,作业(1)对以下的Pascal程序画出过程C第二次被调用时的运行栈，控制链和存取链.(2)如果把存取链改成DISPLAY，重新做(1)programenv;procedureA;varx:integer;procedureB;procedureC;beginx:=2;Bend;(c过程)beginCend;(B过程)beginBend;(A过程)beginAend;(main),程序的调用过程为：envABCBC,第八章语法制导翻译和中间代码生成1、属性文法，语法制导定义的形式，综合属性，继承属性的概念。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、构造识别文法活前缀的DFAM。2、构造LR(0),SLR(1),LR(1)分析表。3、LR(0),SLR(1),LR(1)文法的概念。4、用LR(0),SLR(1),LR(1)对输入串进行分析。5、项目的分类:移进项目、待约项目、归约项目、接受项目。6、项目的冲突：归约移进冲突、归约归约冲突。例：P1663,LR分析表的构造算法1、GO(Ik,a)=Ij,aVT，则ACTIONk,a=Sj。2、若AIk,则对任何aVT(或),则ACTIONk,a=rj;其中j为产生式A的编号。（LR（0）若AIk,则对任何aFOLLOW(A),则ACTIONk,a=rj;其中j为产生式A的编号。（SLR（1）若项目(A,a)属于Ik，则置ACTIONk,a=rj;其中j为产生式A的编号；（LR（1）3、若SSIk,则ACTIONk,=acc。若(SS,#)属于Ik,则置ACTIONk,=acc;4、若GO(Ik，A)=Ij,AVN，则GOTOk,A=j;5、其余为“出错标志”。,P168、16给定文法：SdoSorS|doS|S;S|act(1)构造识别该文法活前缀的DFA(2)该文法是LR(0)吗?是SLR(1)吗?说明理由(3)构造SLR(1)分析表解:扩充文法后为:(0)ES(1)SdoSorS(2)SdoS(3)SS;S(4)Sact,0:ESSdoSorSSdoSSS;SSact,1:ESSS;S,3:Sact,2:SdoSorSSdoSSdoSorSSdoSSS;SSact,do,act,S,4:SS;SSdoSorSSdoSSS;SSact,;,do,6:SS;SSS;S,S,S,5:SdoSorSSdoSSS;S,or,7:SdoSorSSdoSorSSdoSSS;SSact,act,act,;,S,8:SdoSorSSS;S,;,do,act,3,do,;,例：有如下文法:1.ZS2.SL=R3.SR4.LaR5.Lb6.RL按照求LR(1)项目集规范族的算法，求G(S)文法的项目集族解：求初态项目集I0：从(ZS,#)项目开始求闭包得：,第六章自底向上优先分析法1、自底向上语法分析法基本思想：从输入的符号串开始，利用文法的规则步步向上进行直接归约，试图归约到文法的识别符号/开始符号。2、自底向上分析法：优先分析法、LR分析法。3、符优先分析表（表达式）的构造和算符优先分析算法。（求firstvt集和lastvt集，构造优先关系表，对输入串进行分析。）,例：根据下面文法及其算符优先表，按通用算符优先分析的算法分析语句(a,a)#。SaSS(T)TT,STS,解：1）求各非终结符的首终结符集和尾终结符集。对文法拓广，加一个产生式SSFIRSTVT(S)=a,(LASTVT(S)=a,)FIRSTVT(T)=,a,(LASTVT(T)=,a,)2)填写算符优先表,接受,归约,#,#N,9,移进,#,#(N),8,对,归约,)#,#(N,7,对a归约,)#,#(N,N,6,移进,)#,#(N,a,5,移进,a)#,#(N,4,a)#,#(N,3,0,动作,输入串,关系,下推栈,步骤,#,(a,a)#,移进,1,#(,a,a)#,移进,2,#(a,a)#,对a归约,第五章自顶向下语法分析方法1、向下语法分析基本思想：从识别符号出发，不断建立直接推导，试图构造一个推导系列，最终由它推导出与输入符号串相同的符号串。2、LL（1）文法的判别：相同左部产生式的SELECT交集为空则此文法为LL（1）文法。（若有一相同左部产生式的SELEC交集不空，则不是LL（1）文法）3、某些非LL（1）文法转换为LL（1）文法（提取左公因子，消除左递归）,5、自顶向下分析法（预测分析法）步骤：（1）求出FIRST和FOLLOW及SELECT集合。（2）构造预测分析表（LL（1）分析表）。（3）对输入串进行分析。,解：把ASA|a代入SAS|b中：SSAS|aS|b消除左递归：SaSS|bSSASS|把SaSS|bS代入ASA|a中：AaSSA|bSA|a提取左公因子：AaA|bSASSA|文法为：SaSS|bSSASS|AaA|bSASSA|,例：将文法GV改造为LL（1）文法G1，关给出预测分析表GV:VN|NEEV|V+ENi解答：提取左公因子得：G1:VNAAE|EVBB+E|Ni,G1:VNAAE|EVBB+E|NiFIRST(V)=FIRST(N)=FIRST(E)=iFIRST(A)=,FIRST(B)=+,FOLLOW(V)=#(FIRST(B)-)FOLLOW(E)FOLLOW(A)=FOLLOW(V)FOLLOW(B)=FOLLOW(E)FOLLOW(E)=FOLLOW(B)FOLLOW(N)=(FIRST(A)-)FOLLOW(V)FOLLOW(V)=#,+,FOLLOW(A)=#,+,FOLLOW(E)=FOLLOW(B)=FOLLOW(N)=#,+,FIRST(V)=FIRST(N)=FIRST(E)=iFIRST(A)=,FIRST(B)=+,FOLLOW(V)=#,+,FOLLOW(A)=#,+,FOLLOW(E)=FOLLOW(B)=FOLLOW(N)=#,+,SELECT(VNA)=iSELECT(AE)=SELECT(A)=#,+,SELECT(EVB)=iSELECT(B+E)=+SELECT(B)=SELECT(Ni)=i,SELECT(VNA)=iSELECT(AE)=SELECT(A)=#,+,SELECT(EVB)=iSELECT(B+E)=+SELECT(B)=SELECT(Ni)=i,第四章词法分析1、已知语言，能写出正规表达式。反之，给出正规表达式，能写出描述的语言。2、DFA，NFA概念以及它们之间的转换方法，DFA的化简。3、正规表达式转换成FA。4、词法分析器的功能。例P725,2.与正规式等价的NFA为01323.确定化,1.满足条件的正规式为R=(0|10)*,第三章文法和语言1、程序语言的形式描述，文法的分类