13级编译原理复习纲要.ppt

编译原理复习纲要 第十一章 代码优化 1、代码优化的原则：等价原则、有效原则。 2、代码优化的阶段及优化的分类。 3、6种常用优化技术。 4、基本块及基本块划分方法。 5、利用DAG图进行局部优化。 6、求必经结点集、回边，寻找循环。 例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 :=L A:=B*C D:=B/C E :=A+D G :=A H :=G*G F :=H*G L :=F M :=F 第十章 目标程序运行时的存储组织 1、存储分配策略：静态存储分配、动态存储分配（栈式，堆式） 2、不同的程序结构应采用何种分配方案？如何实现此方案？ 程序的调用过程为： env→A →B →C →B →C 第八章 语法制导翻译和中间代码生成 1、属性文法，语法制导定义的形式，综合属性，继承属性的概念。 2、中间代码的表示形式。 3、根据语法制导翻译的方法，写出产生式相应的语义规则。 例 B:=2*Pi*(R+r)*(R-r) 第七章 LR分析法 1、构造识别文法活前缀的DFA M。 2、构造LR(0),SLR(1),LR(1)分析表。 3、LR(0),SLR(1),LR(1)文法的概念。 4、用LR(0),SLR(1),LR(1)对输入串进行分析。 5、项目的分类 6、项目的冲突：归约—移进冲突、归约—归约冲突。 LR分析表的构造算法 1、GO(Ik,a)=Ij,a?VT，则ACTION[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、16 给定文法： S→do S or S|do S|S;S|act (1)构造识别该文法活前缀的DFA (2)该文法是LR(0)吗?是SLR(1)吗?说明理由 解:扩充文法后为: (0)E→S (1)S →do S or S (2)S →do S (3)S →S;S (4)S →act 第六章 自底向上优先分析法 1、自底向上语法分析法基本思想：从输入的符号串开始，利用文法的规则步步向上进行直接归约，试图归约到文法的识别符号/开始符号。 2、自底向上分析法：优先分析法、LR分析法。 3、符优先分析表（表达式）的构造和算符优先分析算法。（求firstvt集和lastvt集，构造优先关系表，对输入串进行分析。） 例：求下面文法的FIRSTVT和LASTVT集。 S→a S→∧ S → (T) T→T,S T →S 第五章 自顶向下语法分析方法 1、向下语法分析基本思想：从识别符号出发，不断建立直接推导，试图构造一个推导系列，最终由它推导出与输入符号串相同的符号串。 2、LL（1）文法的判别：相同左部产生式的SELECT交集为空则此文法为LL（1）文法。（若有一相同左部产生式的SELEC交集不空，则不是LL（1）文法） 3、某些非LL（1）文法转换为LL（1）文法（提取左公因子，消除左递归） 5、自顶向下分析法（预测分析法）步骤： （1）求出FIRST和FOLLOW及SELECT集合。 （2）构造预测分析表（LL（1）分析表）。 （3）对输入串进行分析。 第四章 词法分析 1、已知语言，能写出正规表达式。反之，给出正规表达式，能写出描述的语言。 2、词法分析的功能。 4、DFA，NFA概念，DFA的确定化和最小化。 5、正规表达式转换成FA。 例 P72 5 2.与正规式等价的NFA为 0 1 3 2 3.确定化 第三章 文法和语言 1、程序语言的形式描述，文法的分类，推导，最左推导，最右推导（规范推导），句型，规范句型，句子的概念。 2、对程序语言来说，已知语言，能写出其文法；反之，根据文法，能描述出文法定义的语言。