[2018年最新整理]2013编译原理复习.ppt

编译原理——复习 如何让计算机 认识、理解 和 执行 高级程序设计语言 ？ 李伟生 信科大厦19楼 Telliws@cqupt.edu.cn 课程基本框架 1、基础知识：文法 2、词法分析 理论模型——正规文法与有限自动机 实现——词法分析程序 3、语法分析 理论模型：自上而下分析 自下而上分析 4、中间代码生成 语法制导翻译 5、运行时数据区的管理 6、中间代码优化：局部优化、循环优化、全局优化 7、目标代码生成 复习范围 第1章——引论 第1章 第2章——形式语言基础 第2章 例如，考虑上下文无关文法： E→i|EAE A→+|* 其中，E、A是非终结符号，而i、+和*是终结符。 注意几个符号： ?：定义为 =：推导 *：表示定义符号串的全体 |：表示“或” ?：空字。 第2章 要求掌握最左推导并画出语法树： 最左推导：任何一步推导α=β都是对α中的最左终结符进行替换的。如文法E ?E+E|E*E|(E)|i，推导句子(i+i)： E ?(E) ?(E+E) ?(i+E) ?(i+i) 句子和句型 假定G是一个文法，S是它的开始符号。如果S=α，则称α是一个句型。仅含终结符的句型是一个句子。 第3章——词法分析 要求：掌握将正规式构造为最小DFA的过程。 步骤： 1.构造其NFA； 2.将构造的NFA确定化； 3.将确定的NFA(DFA)最小化。 第3章 第3章 第4章——自上而下语法分析 第4章 第4章 第4章 第4章 第5章——自下而上语法分析 第5章 第5章 算符优先分析 算符优先分析 2)填写算符优先表 第7章——语义分析和中间代码 掌握概念：语法制导翻译的概念 语法制导翻译：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种由源程序的语法结构得到翻译结果的处理方法称为语法制导翻译。 第7章 要求掌握：写出表达式的后缀式、三元式、四元式、间接三元式。 布尔表达式的翻译。 控制语句的翻译。 第9章——运行时存储空间组织 第9章 第9章 第10章——优化 第10章 第10章 第10章 得四元式序列为： 1)T0:=3.14 2) T1 :=6.28 3)T3:=6.28 4)T2:=R+r 5)T4:=T2 6)A:=6.28*T2 7)T5:=A 8)T6:=R-r 9)B:=A*T6 第10章 第10章 第11章——目标代码生成 谢谢收看！ DAG图可以做到3种优化：合并已知量;删除无用赋值;检查公共表达式。 利用DAG图还原成四元式序列： n2 n3 n6 6.28 R A,T5 + n8 B n4 r * n1 3.14 T1,T3 n5 n7 T2,T4 - T6 * T0 进一步优化 根据有关变量在基本块后面被引用的情况，可以进一步删除四元式序列中的无用赋值。 情况1：若DAG中某结点上附加的标识符，在该基本块后面不会被引用，则不生成对该标识符赋值的四元式。 情况2：若某结点上不附有任何标识符或者附加的标识符在基本块后面不会被引用，而且它没有父结点，即基本块内和基本块后都不会引用该结点的值，则不生成计算该结点的值的四元式。 情况3：若有两个相邻的四元式A:=C op D和B:=A，其中第一个四元式计算出来的A值仅仅在第二个四元式中引用，则重写四元式时写为：B:=C op D。 设在基本块后只有B被引用，经进一步优化后DAG可重写为： 1)S1:=R+r 2)A:=6.28*S1 3)S2:=R-r 4)B:=A*S2 其中S1和S2是用来存放中间结果的临时变量。 第一次优化的四元式序列为： 1)T0:=3.14 2) T1 :=6.28 3)T3:=6.28 4)T2:=R+r 5)T4:=T2 6)A:=6.28*T2 7)T5:=A 8)T6:=R-r 9)B:=A*T6 要求掌握优化的最终结果，并写出相应四元式 如何更有效利用寄存器？ 如果生成目标代码的运算对象的值在寄存器中，则把该寄存器作为操作数地址； 尽可能把个变量的现行值保存在寄存器中，把基本块中不再引用的变量所占用的寄存器及早释放； 对循环中的某些变量固定分配寄存器，减少执行代价的两种情况：（P318） * * 复习范围：第1~5章、7章、9~11章 复习方法： 1、认真理解书中的基本概念、基本原理与基本算法； 2