编译 第八章 代码生成

《编译 第八章 代码生成》由会员分享，可在线阅读，更多相关《编译 第八章 代码生成（77页珍藏版）》请在金锄头文库上搜索。

1、第 8 章 代码生成n学习目标n掌握 中间代码生成的基本结构n理解 三地址码; 三元式; 四元式n代码生成回顾n代码生成的任务是生成目标机器的可执行代码， 这个可执行代码是源代码的忠实体现。n代码生成依赖于n源语言的特征n目标结构的细节信息n运行时环境的结构n代码生成一般分为以下几步：1)中间代码生成2)生成某种形式的汇编代码：没有生成真正 的可执行代码3)优化 为了改进目标代码的速度和大小词法分析语法分析语义分析中间代码生成目标代码生成中间代码优化目标代码优化n源程序虽然可以被直接翻译成目标语 言，但是使用与机器无关的中间代码 的好处在于：方便于不同目标机的代码生成: 只需为新的 机器加一个

2、后端即可以生成不同机器的编 译器了。与机器无关的代码优化可应用于中间代码我们将讨论代码生成的一般技术，而不是 针对某种特定的目标机器的详细描述8.1 中间代码和用于代码生成的数据结构 8.2 基本的代码生成技术 8.3控制语句和逻辑表达式的代码生成 8.4 代码优化技术考察8.1 中间代码和用于代码生成的数据结构n中间表示 (IR)在翻译期间，中间表示代表了源程序的数 据结构例如: 抽象语法树n中间代码中间代码的需求 抽象语法树与目标代码极不相像，在控制 流构造的描述上尤为如此中间代码 是语法树用顺序形式表示，更接近目标代 码中间代码的优点v当编译器的目标是产生非常高效的代码时，中间 代码是极

3、其有用的。v用于生成不同目标机的编译器中间代码的普遍形式 三地址码8.1.1 三地址码n三地址码的最基本用法形如 x=y op z表示算术表达式的求值x,y,z 是名字，常量或编译器产生的临时变 量名op 表示任何一个算术运算符或逻辑运算符 ，例如 + ,and形如这样的“三地址码”，一般来说 x,y 和 z 表示的是三个内存地址。例如 表达式的计算用三地址码表示为： 2*a+(b-3) 相应的三地址码是t1 = 2*at2 = b-3t3 = t1+t2其中 t1,t2,t3 是临时变量名，它们对应语法树的内 部结点，并表示计算值+*-2ab3n三地址码的其他用法说明标准程序语言的每种结构的

4、三地址码1.赋值语句形如“x=y op z”, 其中op 为二元 运算符2.赋值语句形如 “x=op y”, 其中 op 是一元运 算符3.赋值语句形如 “x=y” ，其中将 y赋值给 x4.无条件跳转 “goto L”5.条件跳转 ,例如 “if B goto L” , “if_false B goto L” 和 “if A rop B goto L”6.语句 “Label L” 表示转移地址的位置7.“read x” 8.“write x”9.语句 “halt” 表示代码的结束例如Sample TINY programread x;If 0 id=exp | aexp aexp - aex

5、p+factor | factor factor - (exp) | num | id假设记号 id 和 num 已经有一个预先计算 过的 strval 属性，是 token的串值。n生成三地址码的属性文法属性vtacode 表示三地址码vname 表示表达式中生成的中间结果的临时变 量名符号v+ 表示其间插有换行符的串连接v| 表示其间有空格的串连接函数vnewtemp( ) :返回一个新的临时变量名文法规则 语义规则exp1 - id=exp2exp1.name=exp2.name exp1.tacode=exp2.tacode+id.strval | “=”| exp2.nameexp

6、- aexpexp.name=aexp.name exp.tacode=aexp.tacode aexp1 -aexp2+factor aexp1.name=newtemp() aexp1.tacode=aexp2.code + factor.tacode+aexp1.name | ”=” |exp2.name|”+”|factor.nameaexp - factoraexp.name=factor.name aexp.tacode=factor.tacode factor - (exp)factor.name=exp.name factor.tacode=exp.tacode factor

7、- numfactor.name=num.strval factor.tacode=“ ” factor - idfactor.name=id.strval factor.tacode=“ ”表达式 “(x=x+3)+4” 的tacode 属性name=xname=xname=3name=t1;tacode=“t1=x+3 ”name=t1;tacode=“t1=x+3 x=t1”name=t1;tacode=“t1=x+3 x=t1”name=4name=t2;tacode=“t1=x+3 x=t1 t2=t1+4”expaexpfactor( exp )id = expaexp + fac

8、toraexp + factorfactorid (x)num (3)num (4)aexp(x) name=t1;tacode=“t1=x+3 ”8.3 控制语句和逻辑表达式的代码生成 一个程序包含声明和语句声明不会生成中间代码，为每个已声明的名字， 我们生成一个符号表入口赋值语句和简单算术表达式的代码生成 (8.2)控制语句和逻辑表达式的代码生成 (8.3)8.3.1 If- 和 While-语句的代码生成nIf- 和 While-语句 if-stmt-if (exp) stmt | if (exp) stmt else stmt while-stmt-while (exp) stmtn这

9、样语句的代码生成的主要问题是：将结 构化的控制特性翻译成等价的非结构化转 移.n典型的代码排列nIf- 语句 if-stmt -if (exp) stmt | if (exp) stmt else stmtIf语句前的代码if 测试的代码条件跳转TRUE情况下的代码无条件跳转FALSE情况下的代码If语句后的代码TRUEFALSEnWhile-语句 while-stmt- while (exp) stmtWhile语句前的代码while 测试的代码条件跳转While体的代码无条件跳转While语句后的代码TRUEFALSE注释:仅有两种跳转v无条件跳转 (goto L)v条件为假时跳转 (if

10、_falsegoto L)条件为真时无需跳转。这减少了编译器要产生的跳转的数量。n控制语句的三地址码n“if (E) S1 else S2”的代码模式：if_false t1 goto L1goto L2 label L1label L2n“while (E) S” 的代码模式： label L1if_false t1 goto L2goto L1 label L28.3.2 逻辑表达式的代码生成1 逻辑表达式 (或布尔表达式)n逻辑表达式有两个主要的作用：n用来计算逻辑值n作为控制语句的测试而使用，如if-then 或 while-don逻辑表达式的构成由布尔运算符 (and,or,not)

11、 及布尔遍历或关 系表达式组成关系表达式 形如“E1 relop E2”, 其中E1 和 E2 是 算术表达式, relop 是比较运算符，例 如 , =布尔表达式 由下面文法生成： E-E or E | E and E | not E | (E) | id relop id | true | falsevor 和 and 是左结合，且运算优先级是 or if E then S1 | if E then S1 else S2 | while E do S1 E 是布尔表达式n翻译方法 当布尔表达式用于控制条件时，并不需要计算表 达式的值，而是一旦确定了表达式为真或为假， 就将控制转向相应的代码

12、序列。代码生成中用到的函数 newlabel() 返回每次调用的新标号属性vE.true(E.false) 是E为真（或假）时的控制转 向标号vS.next 表示S后面的代码即将被执行的三地址 指令的标号vS.begin 是S代码生成的第一条指令标号1 S-if E then S1S1.codeE.codeto E.trueto E.falseE.true:E.false: E.true 指向S1代码的第 一条指令 E.false 指向S后面的代码 即将被执行的第一条指令语义规则 E.true=newlabel;E.false=S.next;S.code=E.code | Label E.tr

13、ue | S1.code2 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.nextS.code=E.code | Label E.true | S1.code |goto S.next | Label E.false | S2.code to E.trueto E.falseE.true:E.false:S2.codegoto S.nextS1.codeE.codeS.next3 S-w

14、hile 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 to E.falseto E.trueE.true:E.false:goto S.beginS1.codeE.codeS.begin :n布尔表达式的翻译E.code 是一段三地址指令序列，将E计算

15、 为一系列的到E.true和E.false中的条件转 及无条件转语句E 形如 a relop b, 生成的代码为 if a relop b goto E.true goto E.falseE 形如 E1 or E2E1.codeE2.codeE1.falseE2.falseE.falseE1.trueE2.trueE.truev若 E1 是true, 则 E 是 true,因此 E1.true=E.truev若 E1 是false, 则要判断 E2, 因此 E1.false 是E2 代码的第一个语句序号vE2的真假出口分别与 E的相同v“E - E1 or E2”的语义规则 E1.true=E

16、.true; E1.false=newlabel; E2.true=E.true; E2.false=E.false; E.code=E1.code | Label E1.false | E2.codeE 形如 E1 and E2E1.codeE2.codeE1.falseE2.falseE.falseE1.trueE2.true E.true语义规则 E1.true=newlabel; E1.false=E.false; E2.true=E.true; E2.false=E.false; E.code=E1.code | Label E1.true | E2.codeE 形如 not E1 只需将E1的真假出口调换，即为 E 的真假出口 语义规则 E1.true=E.false; E1.false=E.tr