《编译第八章代码生成》由会员分享，可在线阅读，更多相关《编译第八章代码生成（77页珍藏版）》请在金锄头文库上搜索。
1、第 8 章 代码生成,学习目标 掌握 中间代码生成的基本结构 理解 三地址码; 三元式; 四元式,代码生成回顾 代码生成的任务是生成目标机器的可执行代码，这个可执行代码是源代码的忠实体现。 代码生成依赖于 源语言的特征 目标结构的细节信息 运行时环境的结构,代码生成一般分为以下几步： 中间代码生成 生成某种形式的汇编代码：没有生成真正的可执行代码 优化 为了改进目标代码的速度和大小,源程序虽然可以被直接翻译成目标语言，但是使用与机器无关的中间代码的好处在于： 方便于不同目标机的代码生成: 只需为新的机器加一个后端即可以生成不同机器的编译器了。 与机器无关的代码优化可应用于中间代码,我们将讨论代
2、码生成的一般技术，而不是针对某种特定的目标机器的详细描述,8.1 中间代码和用于代码生成的数据结构 8.2 基本的代码生成技术 8.3控制语句和逻辑表达式的代码生成 8.4 代码优化技术考察,8.1 中间代码和用于代码生成的数据结构,中间表示 (IR) 在翻译期间，中间表示代表了源程序的数据结构 例如: 抽象语法树,中间代码 中间代码的需求 抽象语法树与目标代码极不相像，在控制流构造的描述上尤为如此 中间代码 是语法树用顺序形式表示，更接近目标代码,中间代码的优点 当编译器的目标是产生非常高效的代码时，中间代码是极其有用的。 用于生成不同目标机的编译器 中间代码的普遍形式 三地址码,8.1.1
3、 三地址码,三地址码的最基本用法形如 x=y op z 表示算术表达式的求值 x,y,z 是名字，常量或编译器产生的临时变量名 op 表示任何一个算术运算符或逻辑运算符，例如 + ,and 形如这样的“三地址码”，一般来说 x,y 和 z 表示的是三个内存地址。,例如 表达式的计算用三地址码表示为： 2*a+(b-3),相应的三地址码是 t1 = 2*a t2 = b-3 t3 = t1+t2 其中 t1,t2,t3 是临时变量名，它们对应语法树的内部结点，并表示计算值,三地址码的其他用法说明 标准程序语言的每种结构的三地址码 赋值语句形如“x=y op z”, 其中op 为二元运算符 赋值语
4、句形如 “x=op y”, 其中 op 是一元运算符 赋值语句形如 “x=y” ，其中将 y赋值给 x,无条件跳转 “goto L” 条件跳转 ,例如 “if B goto L” , “if_false B goto L” 和 “if A rop B goto L” 语句 “Label L” 表示转移地址的位置 “read x” “write x” 语句 “halt” 表示代码的结束,例如 Sample TINY program read x; If 0x then fact:=1; repeat fact:=fact*x; x:=x-1; until x=0; write fact end,
5、它的三地址码： read x t1=0x if-false t1 goto L1 fact=1 label L2 t2=fact*x fact=t2 t3=x-1 x=t3,t4=x=0 if_false t4 goto L2 write fact Label L1 halt,8.1.2 三地址码的实现,三地址指令是中间代码的抽象形式 在编译器中，这些指令可以通过记录实现，域表示操作符和操作数。 两种这样的表示： 四元式 和 三元式,四元式 每条三地址指令包含四个域: 一个操作符和三个地址 对于那些少于三个地址的指令，将一个或更多的地址域置成 null 或 “empty”,四元式实现 (lab
6、, L2, _, _) (mul, fact, x, t2) (asn, t2, fact, _) (sub, x, 1, t3) (asn, t3, x, _) (eq, x, 0, t4) (if_f, t4, L2, _) (wri, fact, _, _) ,三地址码 label L2 t2=fact*x fact=t2 t3=x-1 x=t3 t4=x=0 if_false t4 goto L2 write fact ,三元式 每条三地址指令包含三个域: 一个操作符和两个地址 用自己的指令来代表临时变量来实现。,三地址码 label L2 t2=fact*x fact=t2 t3=x
7、-1 x=t3 t4=x=0 if_false t4 goto L2 write fact ,三元式实现 (4) (mul, fact, x) (5) (asn, (4), fact) (6) (sub, x, 1) (7) (asn, (6), x) (8) (eq, x, 0) (9) (if_f, (8), (4) (10) (wri, fact, _),注:label 指令被删除，替换为三元式索引的引用,三元式与四元式的比较 三元式是代表三地址码的有效方法，因为空间数量减少了，并且编译器不需要产生临时变量名 三元式使用指令索引表示临时变量，使得三元式的位置移动变得很困难。四元式更便于优
8、化。,8.2 基本的代码生成技术,代码生成的基本方法 (8.2) 单个语言结构的代码生成 (8.3),8.2.1 作为合成属性的中间代码或目标代码,代码生成被看作是属性计算 生成代码被看作一个字符串属性 这个代码就成了一个合成属性，能用属性文法定义，并能在分析期间直接生成或通过语法树的后序遍历生成。,例如 给定表达式的文法，看看代码是如何被定义为合成属性的。 exp - id=exp | aexp aexp - aexp+factor | factor factor - (exp) | num | id 假设记号 id 和 num 已经有一个预先计算过的 strval 属性，是 token的串
9、值。,生成三地址码的属性文法 属性 tacode 表示三地址码 name 表示表达式中生成的中间结果的临时变量名 符号 + 表示其间插有换行符的串连接 | 表示其间有空格的串连接 函数 newtemp( ) :返回一个新的临时变量名,表达式 “(x=x+3)+4” 的tacode 属性,name=x,name=x,name=3,name=t1;tacode=“t1=x+3”,name=t1;tacode=“t1=x+3 x=t1”,name=t1; tacode=“t1=x+3 x=t1”,name=4,name=t2;tacode=“t1=x+3 x=t1 t2=t1+4”,name=t1;
10、tacode=“t1=x+3”,8.3 控制语句和逻辑表达式的代码生成,一个程序包含声明和语句 声明不会生成中间代码，为每个已声明的名字，我们生成一个符号表入口 赋值语句和简单算术表达式的代码生成 (8.2) 控制语句和逻辑表达式的代码生成 (8.3),8.3.1 If- 和 While-语句的代码生成,If- 和 While-语句 if-stmt -if (exp) stmt | if (exp) stmt else stmt while-stmt -while (exp) stmt 这样语句的代码生成的主要问题是：将结构化的控制特性翻译成等价的非结构化转移.,典型的代码排列 If- 语句
11、if-stmt -if (exp) stmt | if (exp) stmt else stmt,While-语句 while-stmt - while (exp) stmt,注释: 仅有两种跳转 无条件跳转 (goto L) 条件为假时跳转 (if_falsegoto L) 条件为真时无需跳转。 这减少了编译器要产生的跳转的数量。,控制语句的三地址码 “if (E) S1 else S2”的代码模式： if_false t1 goto L1 goto L2 label L1 label L2,“while (E) S” 的代码模式： label L1 if_false t1 goto L2
12、goto L1 label L2,8.3.2 逻辑表达式的代码生成,1 逻辑表达式 (或布尔表达式) 逻辑表达式有两个主要的作用： 用来计算逻辑值 作为控制语句的测试而使用，如if-then 或 while-do,逻辑表达式的构成 由布尔运算符 (and,or,not) 及布尔遍历或关系表达式组成 关系表达式 形如“E1 relop E2”, 其中E1 和 E2 是 算术表达式, relop 是比较运算符，例如 , =,布尔表达式 由下面文法生成： E-E or E | E and E | not E | (E) | id relop id | true | false or 和 and 是左
13、结合，且运算优先级是 or and not,布尔表达式的代码生成,数值表示的直接计算 逻辑表示的短路计算,2 作为数值表示计算的布尔表达式的翻译,布尔表达式以类似于算术表达式的方式翻译 例如 “a or b and not c” 的翻译是三地址序列 t1= not c t2=b and t1 t3=a or t2,3 作为短路计算的布尔表达式的翻译,短路 一个逻辑运算是短路的，如果不需要再求它的第二个参数 例如 A and B: 若 已计算出A 是 false，则无需查看B即可确定 A and B 的结果是 false A or B: 若已知道 A 是 true, 则无需查看B即可确定A or
14、 B 的结果是true,作为条件控制的布尔表达式的翻译,控制语句的文法 S- if E then S1 | if E then S1 else S2 | while E do S1 E 是布尔表达式 翻译方法 当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。,代码生成中用到的函数 newlabel() 返回每次调用的新标号 属性 E.true(E.false) 是E为真（或假）时的控制转向标号 S.next 表示S后面的代码即将被执行的三地址指令的标号 S.begin 是S代码生成的第一条指令标号,1 S-if E then S1
15、,E.true 指向S1代码的第一条指令 E.false 指向S后面的代码即将被执行的第一条指令,语义规则 E.true=newlabel; E.false=S.next; S.code=E.code | Label E.true | S1.code,2 S-if E then S1 else S2,E.true 指向S1代码的第一条指令 E.false指向S2代码的第一条指令,语义规则 E.true=newlabel; E.false=newlabel; S1.next=S.next; S2.next=S.next S.code=E.code | Label E.true | S1.code
16、 |goto S.next | Label E.false | S2.code,3 S-while E do S1,E.true 指向S1代码的第一条指令 E.false指向S后面的代码即将被执行的第一条指令,语义规则 S.begin=newlabel; E.true=newlabel;E.false=S.next; S1.next=S.begin; S.code=Label S.begin | E.code | Label E.true | S1.code |goto S.begin,布尔表达式的翻译 E.code 是一段三地址指令序列，将E计算为一系列的到E.true和E.false中的条件转及无条件转语句 E 形如 a relop b, 生成的代码为 if a relop b goto E.true goto E.false,E 形如 E1 or E2,若 E1 是true, 则 E 是 true,因此 E1.true=E.true 若 E1 是false, 则要判断 E
