《编译原理课程教案》第五章：中间代码生成.ppt

语义分析和中间代码生成;本章要求;语义分析和中间代码生成所处的位置：;１. 语义分析和中间代码生成在编译器中的位置：;3. 为什么要此阶段? 逻辑结构清楚；利于不同目标机上实现同一种语言； 利于进行与机器无关的优化，这些内部形式也能用于解释。 4. 什么是中间代码(Intermediate code) 源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。 5. 中间代码的几种形式 逆波兰、三元式、间接三元式、四元式、树 ;1、逆波兰式： 运算对象写在前，运算符写在后(后缀表示形式) 例：a+b ? ab+ 　　(a+b)*c ? ab+c* 　　a+b*c ? abc*+ 　　a:=b*c+b*d ? abc*bd*+:=;练习;后缀式的推广;2、三元式 编号（运算符，第一运算数，第二运算数） 如：a：= b*c+b*d (1)（*，b，c） (2)（*，b，d） (3)（+，(1)，(2)） (4)（：=，(3)，a） 对于单目运算符，只有一个运算对象，另一个为空 注意：在三元式中的编号既代表了序号，又代表了结果的存放位置。;3、四元式P172 是目前最常用的中间代码形式: (运算符，第一运算数，第二运算数，结果) 例：a:=b*c+b*d 　 (1)(*,b,c,t1) 　 (2)(*,b,d,t2) 　 (3)(+,t1,t2,t3) 　 (4)(:=,t3, ,a) 也可以写成赋值语句形式： 　(1)t1:=b*c 　(2)t2:=b*d 　(3)t3:=t1+t2 (4)a:=t3;练习;到目前为止，已知 输入的语法单位，又知道 要翻译的结果的形式，翻译的方法是什么？;属性文法;属性分两类： 综合属性：用于自下而上传递信息 继承属性：用于自上而下传递信息 注意： 终结符只有综合属性，它由词法分析器提供； 非终结符可有综合属性，也可有继承属性，它由词法分析器提供； 文法的开始符号的所有继承属性作为属性计算前的初始值;产生式右边的文法符号的继承属性可以继承左边的文法符号的继承属性 产生式左边的文法符号可以通过综合右边的文法符号的综合属性而得到 但必须提供一个计算规则：计算规则中只能使用相应产生式中的文法符号的属性。 实际应用中，一个结点的综合属性的值由其子结点的综合属性值决定(产生式右边)。一个结点的继承属性由此结点的父结点和/或兄结点的某些属性决定(产生式左边)。 但产生式左边的继承属性和右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性计算规则提供。;digit?lexval:=3;C语言中变量定义： int id1,id2,id3;语法制导的翻译方法;语义规则描述的工作： 属性计算、静态语义检查、符号表的操作、代码生成等，通常写成过程和函数调用，称为语义子程序。;语法制导翻译的基本思想： 在语法分析过程中，根据语言的语义定义，随时翻译已识别的那部分语法成分的全部含义。;语法制导翻译的两种方法;自下而上分析的语法制导翻译;例：属性文法如下，输入串为：3*5+4，其语法树如下图：;在第一步规约时使用产生式6，执行的语义动作是将F.val的值置为单词digit的值3。把语法树中每个结点得语义值写在结点后的括号中，则第一步完成规约后的情形如右图所示： ;继续进行分析，逐步向上规约，得到下图所示的情形，最后用E E1+T规约到E时，它的值19就计算出来了。 ;在自下而上的LR语法分析过程中，首先把它的分析栈进行扩充，使得每个文法符号都带有语义值。修改后栈的结构如下图所示：;例：在3*5+4的LR分析过程中增加了语义栈后的语法制导的实现过程。;序号;启示：;常见语句的语法制导翻译;语义翻译过程中涉及的数据结构;说明语句的翻译;变量说明语句的翻译;３. 翻译的语义动作;VAR id1,id2,id3:integer;的归约过程;常量说明语句的翻译;Constant A=123;可执行语句的翻译;简单赋值语句的翻译;3. 简单赋值语句的翻译 此处只假定是整数运算;例：赋值句A:=B+C*(-D)的自底向上分析;1. A→i=E 2. E→E(1)+T 3. E→T 4. T→T(1)*F 5. T→F 6. F→-P 7. P→(E) 8. P→i;因此，四元式表中增加了4条四元式：;简单算术表达式和赋值语句的翻译;布尔表达式的翻译;3 .布尔表达式的文法描述;计算布尔表达式的值有两种方法： 一种是像计算算术表达式那样，对布尔表达式中的每个因子都计算其布尔值，最后求得整个表达式的布尔值。 另一种计算方法是根据布尔运算的特殊性采取某些优化措施，只计算部分表