编译原理中间代码生成

1、machunyan西北工业大学软件与微电子学院1词词法法分分析析程程序序语语法法分分析析程程序序语语义义分分析析程程序序中中间间代代码码生生成成代代码码优优化化程程序序目目标标代代码码生生成成源源代代码码目目标标代代码码常数表常数表符号表符号表 错误处理器错误处理器编译器逻辑结构的组成编译器逻辑结构的组成machunyan西北工业大学软件与微电子学院2第第6 6章章 代码生成代码生成6 6.1 .1 中间代码概览中间代码概览6 6.2 .2 基本的代码生成技术基本的代码生成技术6 6.3 .3 数据结构引用的代码生成数据结构引用的代码生成6 6.4 .4 控制语句和逻辑表达式的代码生成控制语句

2、和逻辑表达式的代码生成6 6.5 .5 过程和函数调用的代码生成过程和函数调用的代码生成machunyan西北工业大学软件与微电子学院36 6.1 .1 中间代码概览中间代码概览o 编译程序的任务是把源程序翻译成等价的目标程序。所谓编译程序的任务是把源程序翻译成等价的目标程序。所谓等价，是指两者之间的语法结构不同，但它们表述的功能等价，是指两者之间的语法结构不同，但它们表述的功能和结果是完全相同的，即语义相同。和结果是完全相同的，即语义相同。o 中间代码，也称中间语言，是复杂性介于源程序和目标程中间代码，也称中间语言，是复杂性介于源程序和目标程序之间的一种机内表达形式，它是编译程序产生的中间临

3、序之间的一种机内表达形式，它是编译程序产生的中间临时结果。中间代码程序同源程序和目标程序的关系也同样时结果。中间代码程序同源程序和目标程序的关系也同样是等价的，即结构不同，但语义相同。是等价的，即结构不同，但语义相同。machunyan西北工业大学软件与微电子学院4尽管源程序可以直接翻译成目标语言，但使用与机器尽管源程序可以直接翻译成目标语言，但使用与机器无关的中间代码形式具有如下优点：无关的中间代码形式具有如下优点：使编译程序的算法清晰，便于分工、修改、维护和移植等；使编译程序的算法清晰，便于分工、修改、维护和移植等；中间代码使编译器更容易重定向：不同机器上的编译器可以在中间代码使编译器更容

4、易重定向：不同机器上的编译器可以在已有前端的基础上附加一个适合这这台新机器的后端来生成；已有前端的基础上附加一个适合这这台新机器的后端来生成；可以在中间代码上进行与机器无关的代码优化，优化过程实际可以在中间代码上进行与机器无关的代码优化，优化过程实际上是对程序的操作过程，对程序进行操作必须首先把程序转换上是对程序的操作过程，对程序进行操作必须首先把程序转换成其结构便于操作的数据，而中间代码正是为此设计的一种程成其结构便于操作的数据，而中间代码正是为此设计的一种程序的数据结构表示。序的数据结构表示。两种常见的中间代码的普遍形式：三地址码和两种常见的中间代码的普遍形式：三地址码和P-P-代码代码6

5、 6.1 .1 中间代码概览（续）中间代码概览（续）machunyan西北工业大学软件与微电子学院56 6.1.1 .1.1 三地址码三地址码6 6.1.2 .1.2 用于实现三地址码的数据结构用于实现三地址码的数据结构6 6.1.3 .1.3 P-P-代码代码6 6.1 .1 中间代码概览（续）中间代码概览（续）machunyan西北工业大学软件与微电子学院66 6.1.1 .1.1 三地址码（续）三地址码（续）+ +* *- -2 2a ab b3 3相应的三地址码为：相应的三地址码为：t1=2t1=2* *a at2=b-3t2=b-3t3=t1+t2t3=t1+t2o 三地址码是下列一

6、般形式的语句序列：三地址码是下列一般形式的语句序列：n x:=y op z 其中，其中，x，y及及z是名字、常是名字、常量或编译器生成的临时变量，量或编译器生成的临时变量， op代表任何代表任何操作符。操作符。o 例例6.1：算术表达式的：算术表达式的2*a+(b-3) 语法树如下：语法树如下：machunyan西北工业大学软件与微电子学院76 6.1.1 .1.1 三地址码（续）三地址码（续）o 三地址码是语法树的从左到右的线性化表示，三地址码三地址码是语法树的从左到右的线性化表示，三地址码的的生成所依据的是语言的语义规则。生成所依据的是语言的语义规则。o 为适应标准程序语言的使用结构，在具

7、体为每个结构生为适应标准程序语言的使用结构，在具体为每个结构生成三地址码时，必须为每个结构改变三地址码的形式。成三地址码时，必须为每个结构改变三地址码的形式。n 例如：为了生成数组引用的三地址码可以引入两个新例如：为了生成数组引用的三地址码可以引入两个新的三地址指令：的三地址指令： 获取数组元素值的三地址指令：获取数组元素值的三地址指令：t2=at1 给数组元素赋值的三地址指令：给数组元素赋值的三地址指令：at2=t1machunyan西北工业大学软件与微电子学院86 6.1.1 .1.1 三地址码三地址码6 6.1.2 .1.2 用于实现三地址码的数据结构用于实现三地址码的数据结构6 6.1

8、.3 .1.3 P-P-代码代码6 6.1 .1 中间代码概览（续）中间代码概览（续）machunyan西北工业大学软件与微电子学院96 6.1.2 .1.2 用于实现三地址码的数据结构用于实现三地址码的数据结构o 三地址码是中间代码的一种抽象形式。在编译器中，三地址码是中间代码的一种抽象形式。在编译器中，这些语句可以以带有操作符和操作数域的记录来实现。这些语句可以以带有操作符和操作数域的记录来实现。三地址码常见的实现有四元式和三元式。三地址码常见的实现有四元式和三元式。o 四元式四元式是带有四个域的记录结构，即是带有四个域的记录结构，即op,arg1,arg2,resultop,arg1,a

9、rg2,result，可以写成可以写成( (op,arg1,arg2,result) op,arg1,arg2,result) 。arg1,arg2arg1,arg2及及resultresult域的内域的内容正常情况下是指这些域所代表的名字在符号表表项的容正常情况下是指这些域所代表的名字在符号表表项的指针。临时名字指针。临时名字resultresult在生成时一定要被填入符号表。在生成时一定要被填入符号表。n四元式之间的联系是通过临时变量实现的四元式之间的联系是通过临时变量实现的, ,便于优化处理；便于优化处理；machunyan西北工业大学软件与微电子学院10o 三元式：为了避免临时名字被填

10、入符号表中，可以通过临三元式：为了避免临时名字被填入符号表中，可以通过临时值的语句位置来引用临时变量。可以用只包含三个域的时值的语句位置来引用临时变量。可以用只包含三个域的记录表示，即用三元式来表示。记录表示，即用三元式来表示。o 三元式之间的联系是通过三元式编号实现的三元式之间的联系是通过三元式编号实现的, ,对三元对三元式表变动较为困难，花费较大的代价。式表变动较为困难，花费较大的代价。6 6.1.2 .1.2 用于实现三地址码的数据结构（续）用于实现三地址码的数据结构（续）machunyan西北工业大学软件与微电子学院11例例6 6.2.2：6 6.1.1中算术表达式中算术表达式：2 2

11、* *a+(b-3)a+(b-3)的三地址码：的三地址码：t1=2t1=2* *a at2=b-3t2=b-3t3=t1+t2t3=t1+t2四元式实现：四元式实现： （* *，2 2，a,t1a,t1） （-,-,b,3,t2b,3,t2） （+,+,t1,t2,t3t1,t2,t3）三元式实现：三元式实现： (0) (0)（* *,2,2,a a） (1) (1)（-,-,b,3b,3） (2) (2)（+,(0)+,(0),(1),(1)）6 6.1.2 .1.2 用于实现三地址码的数据结构（续）用于实现三地址码的数据结构（续）machunyan西北工业大学软件与微电子学院126 6.1

12、.1 .1.1 三地址码三地址码6 6.1.2 .1.2 用于实现三地址码的数据结构用于实现三地址码的数据结构6 6.1.3 .1.3 P-P-代码代码6 6.1 .1 中间代码概览（续）中间代码概览（续）machunyan西北工业大学软件与微电子学院136 6.1.3 .1.3 P-P-代码代码o 在在20世纪世纪70年代和年代和60年代早期，年代早期，P-代码作为由代码作为由许多许多Pascal编译器产生的标准目标汇编代码被编译器产生的标准目标汇编代码被设计成称作设计成称作P-机器机器(P-machine)的假想的假想栈机器栈机器(Stack machine)的实际代码。的实际代码。n P

13、-机器在不同的平台上由不同的解释器实现。机器在不同的平台上由不同的解释器实现。n 该思想使得该思想使得pascal编译器变得容易移植，编译器变得容易移植，只需对新平台重写只需对新平台重写P-机器解释器即可。机器解释器即可。machunyan西北工业大学软件与微电子学院14例例6 6.3:.3:算术表达式：算术表达式：2 2* *a+(b-3)a+(b-3)的的P-P-代码如下：代码如下：ldc 2 ; load constant 2lod a ; load value of variable ampi ; integer multiplicationlod b ; load value of

14、variable bldc 3 ; load constant 3sbi ; integer subtractionadi ; integer addition6 6.1.3 .1.3 P-P-代码（续）代码（续）machunyan西北工业大学软件与微电子学院156 6.1 .1 中间代码概览中间代码概览6 6.2 .2 基本的代码生成技术基本的代码生成技术6 6.3 .3 数据结构引用的代码生成数据结构引用的代码生成6 6.4 .4 控制语句和逻辑表达式的代码生成控制语句和逻辑表达式的代码生成6 6.5 .5 过程和函数调用的代码生成过程和函数调用的代码生成第第6 6章章 代码生成（续）代码

15、生成（续）machunyan西北工业大学软件与微电子学院166 6.2 .2 基本的代码生成技术基本的代码生成技术6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法作为合成属性的中间代码或目标代码生成方法6 6.2.2 .2.2 实际的代码生成方法实际的代码生成方法6 6.2.3 .2.3 从中间代码生成目标代码从中间代码生成目标代码machunyan西北工业大学软件与微电子学院176 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法作为合成属性的中间代码或目标代码生成方法o 中间代码生成中间代码生成(或直接目标代码生成或直接目标代码生成)可被看作可被看作属性计算

16、，这类似于第属性计算，这类似于第5章中研究的许多属性问章中研究的许多属性问题。题。n 假如将假如将生成的代码生成的代码看作一个看作一个字符串属性字符串属性(每条指令用换行符分隔每条指令用换行符分隔)，这个代码就，这个代码就成了一个成了一个合成属性合成属性并能用属性文法定义，并能用属性文法定义，并且能在并且能在语法分析期间直接生成语法分析期间直接生成或者通过或者通过语法树的语法树的后序遍历后序遍历生成。生成。machunyan西北工业大学软件与微电子学院18例例6 6.4.4：为表达式文法：为表达式文法expid = exp|aexpaexpaexp + factor|factorfactor(

17、exp) | num | id写出计算三地址码的属性文法。写出计算三地址码的属性文法。tacodetacode属性：表示文法的三地址码属性；属性：表示文法的三地址码属性；namename属性属性: : 表示参与三地址码运算的标示符表示参与三地址码运算的标示符、常、常量或编译器生成的临时变量；量或编译器生成的临时变量；用用+表示所连的符号串换行表示；表示所连的符号串换行表示；|表示相连的符号串之间用空格相隔。表示相连的符号串之间用空格相隔。6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法（续）作为合成属性的中间代码或目标代码生成方法（续）machunyan西北工业大学软件与微电

18、子学院19exp.tacode=t1 = x + 3 x = t1exp.tacode=t1 = x + 36 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法（续）作为合成属性的中间代码或目标代码生成方法（续）factorfactorfactorfactor= =numnum(3)(3)aexpaexpexpexp+ + id id（x x）idid( (x)x)expexpaexpaexp表达式表达式x=x+3x=x+3的的tacodetacode属性计算属性计算: :machunyan西北工业大学软件与微电子学院20exp1id=exp2expaexp文法规则文法规则语义规

19、则语义规则= exp1.tacode= exp2.tacode+id.strval |”=” | = exp.tacode=aexp.tacode6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法（续）作为合成属性的中间代码或目标代码生成方法（续）machunyan西北工业大学软件与微电子学院21aexp1aexp2+=newtemp()aexp1.tacode= aexp2.tacode+factor.tacode +|”=”|aexp2

20、.name |”+”|6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法（续）作为合成属性的中间代码或目标代码生成方法（续）machunyan西北工业大学软件与微电子学院22aexpfactorfactor(exp)factornumfactorid文法规则文法规则语义规则语义规则= aexp.tacode==factor.tacode==num.strvalfactor.tacode=“”

21、=id.strvalfactor.tacode=“”6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法作为合成属性的中间代码或目标代码生成方法( (续续) )machunyan西北工业大学软件与微电子学院23exp.tacode=t1 = x + 3 x = t1根据上述属性根据上述属性文法，表达式文法，表达式（x=x+3)+4x=x+3)+4的的tacodetacode属性计属性计算如右：算如右：factorfactorexpexp= =expexpaexpaexpfactorfactorfactorfactornumnum(3)(3)aexpaexpfactorfactor

22、expexpfactorfactoraexpaexp+ + + id id（x x）id(x)id(x)numnum(4)(4)（）exp.tacode=t1 = x + 3aexp.tacode=t1 = x + 3 x = t1t2 = t1 + 46 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法（续）作为合成属性的中间代码或目标代码生成方法（续）machunyan西北工业大学软件与微电子学院24其中语义动作使用函数其中语义动作使用函数emit()emit() 将三地址语句输出到文件中。将三地址语句输出到文件中。为其产生三地址码的翻译模式如下：为其产生三地址码的翻译模式如

23、下：对于表达式文法对于表达式文法expexpid=id=expexp| |aexpaexpaexpaexpaexpaexp+ +factorfactor| |factorfactorfactorfactor(expexp)|num|id)|num|id对于将文法符号同属性相关联的上下文无关文法，也可对于将文法符号同属性相关联的上下文无关文法，也可以将以将语义动作语义动作( (包含在包含在 中中) )插入产生式右部的某个位置插入产生式右部的某个位置。6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法作为合成属性的中间代码或目标代码生成方法( (续续) )machunyan西北工业

24、大学软件与微电子学院25exp1id=exp2expaexpaexp1aexp2+= emit(id.strval =)= =newtemp() emit(= aexp2 .name + )6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法（续）作为合成属性的中间代码或目标代码生成方法（续）machunyan西北工业大学软件与微电子学院26aexpfactorfactor(exp)factornumfactorid

25、== ==num.strval6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法作为合成属性的中间代码或目标代码生成方法( (续续) )machunyan西北工业大学软件与微电子学院27o 为表达式文法为表达式文法expexp+term|exp-term|termtermterm*factor|factor factor(exp)|number写出计算三地址码的属性文法。写出计算三地址码的属性文法。n tacode属性：表示文法的三地址码属

26、性属性：表示文法的三地址码属性n name属性属性: 表示相应的标示符表示相应的标示符、常量或、常量或编译器生成的临时变量编译器生成的临时变量6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法（续）作为合成属性的中间代码或目标代码生成方法（续）machunyan西北工业大学软件与微电子学院286 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法作为合成属性的中间代码或目标代码生成方法6 6.2.2 .2.2 实际的代码生成方法实际的代码生成方法6 6.2.3 .2.3 从中间代码生成目标代码（自学内容）从中间代码生成目标代码（自学内容）6 6.2 .2 基本的代码

27、生成技术基本的代码生成技术machunyan西北工业大学软件与微电子学院296 6.2.2 .2.2 实际的代码生成方法实际的代码生成方法实际代码生成的基本算法由下面的递归过程描述实际代码生成的基本算法由下面的递归过程描述( (用于二叉树，用于二叉树，但容易将其推广到节点子树多于但容易将其推广到节点子树多于2 2的情况的情况) )：void genCode ( T: treenode ) ; if T is not nil ;/generate code to prepare for code of left child of T;genCode (left child of T ) ;/ge

28、nerate code to prepare for code of right child of T;genCode (right child of T ) ;generate code to implement the action of T;注：中间代码生成所依据的是语言的语义规则，即在遍历树生注：中间代码生成所依据的是语言的语义规则，即在遍历树生成代码之前，应该首先规定各节点对应代码生成的语义规则。成代码之前，应该首先规定各节点对应代码生成的语义规则。machunyan西北工业大学软件与微电子学院30对于上述简单表达式文法对于上述简单表达式文法expid=exp|aexpaexpaex

29、p+factor|factorfactor(exp)|num|id考虑其三地址码的代码生成过程实现。考虑其三地址码的代码生成过程实现。6 6.2.2 .2.2 实际的代码生成方法（续）实际的代码生成方法（续）machunyan西北工业大学软件与微电子学院31例例6 6.5.5：表达式（：表达式（x=x+3)+4x=x+3)+4相应的语法树如下：相应的语法树如下：+ +x=x=4 4x x3 3+ +生成的相应的三地码如下：生成的相应的三地码如下：t1 = x + 3 x = t1t2 = t1 + 46 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）machunyan西北工业大

30、学软件与微电子学院32typedef enum Plus, Assign Optype;typedef enum OpKind, ConstKind, IdKind NodeKind;typedef struct streenode NodeKind kind; Optype op; struct streenode lchild, rchild; char strval; STreeNode;typedef STreeNode *SyntaxTree;简单算术表达式抽象语法树的简单算术表达式抽象语法树的C C语言定义语言定义: :每个节点都有每个节点都有个名字属性，个名字属性，用该节点的用该

31、节点的strvalstrval域来存域来存储其名字储其名字假设数字也当作假设数字也当作字符串保存在字符串保存在strvalstrval域中域中6 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）machunyan西北工业大学软件与微电子学院33+left operandright operand上述表达式的语法树结构和节点中间代码的生成规则如下：上述表达式的语法树结构和节点中间代码的生成规则如下：t1 = t.leftchild.strval+t.rightchild.strvalt.strval = t16 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）mach

32、unyan西北工业大学软件与微电子学院34left oper =left operandt.strval = t.leftchild.strval6 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）t.strval = t.leftchild.strval生成的生成的三地址三地址码码赋值运赋值运算算machunyan西北工业大学软件与微电子学院35o 中间代码生成的辅助函数：中间代码生成的辅助函数：n emit()：函数：函数emit() 将三地址语句输出将三地址语句输出到文件中；到文件中；n Newtemp()：函数：函数Newtemp()产生一产生一个临时名字系列个临时名字系

33、列t1，t2，t3，；6 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）machunyan西北工业大学软件与微电子学院36Void genCode(SyntaxTree t)if(t!=NULL) switch(t kind) case OpKind: switch(t op) case Plus: genCode(t lchild); genCode(t rchild); t strval=newtemp(); emit(t strval= t lchild strval +t rchild strval) break; 简单算术表达式的三地址码生成过程的实现：简单算术表达式

34、的三地址码生成过程的实现：6 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）machunyan西北工业大学软件与微电子学院37case Assign: genCode(t lchild); emit(t strval= t lchild strval); t strval= t lchild strval; break; default: emit(“error”); break; 6 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）machunyan西北工业大学软件与微电子学院38 break;case ConstKind: break;case IdKind:

35、 break;default: emit(“error”); break; 6 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）machunyan西北工业大学软件与微电子学院39+ +x=x=4 4x x3 3+ +根据上述三地址码的生成过程，表达式（根据上述三地址码的生成过程，表达式（x=x+3)+4x=x+3)+4相应的三地码如下：相应的三地码如下：t1 = x + 3t1 = x + 3x = t1x = t1t2 = t1 + 4t2 = t1 + 46 6.2.2 .2.2 实际的代码生成（续）实际的代码生成（续）machunyan西北工业大学软件与微电子学院406 6

36、.2 .2 基本的代码生成技术基本的代码生成技术6 6.2.1 .2.1 作为合成属性的中间代码或目标代码生成方法作为合成属性的中间代码或目标代码生成方法6 6.2.2 .2.2 实际的代码生成方法实际的代码生成方法6 6.2.3 .2.3 从中间代码生成目标代码（自学内容）从中间代码生成目标代码（自学内容）machunyan西北工业大学软件与微电子学院416 6.2.3 .2.3 从中间代码生成目标代码（续）从中间代码生成目标代码（续）o 如果编译器从一棵语法树产生了中间代码，下一如果编译器从一棵语法树产生了中间代码，下一步就是产生最后的目标代码步就是产生最后的目标代码( (通常在对中间代码

37、通常在对中间代码的进一步处理之后的进一步处理之后) )；o 目标代码的生成相当复杂，特别是当中间代码高目标代码的生成相当复杂，特别是当中间代码高度抽象，且只包含了很少或根本没包含目标机器度抽象，且只包含了很少或根本没包含目标机器和运行时环境的信息。和运行时环境的信息。o 在上述情况下，在上述情况下，目标代码的生成必须支持变量和目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所临时变量的实际定位，并增加支持运行时环境所必需的代码必需的代码。现在仅讨论这个处理的通用技术。现在仅讨论这个处理的通用技术。machunyan西北工业大学软件与微电子学院42通常，从中间代码到目标代码的

38、生成涉及了两个标通常，从中间代码到目标代码的生成涉及了两个标准技术：宏扩展准技术：宏扩展( (macro expansion) )和静态模拟和静态模拟宏扩展宏扩展涉及到用一系列等效的目标代码指令涉及到用一系列等效的目标代码指令代替每一种中间代码指令。代替每一种中间代码指令。静态模拟静态模拟包括中间代码效果的直线模拟和生包括中间代码效果的直线模拟和生成匹配这些效果的目标代码。成匹配这些效果的目标代码。6 6.2.3 .2.3 从中间代码生成目标代码（续）从中间代码生成目标代码（续）machunyan西北工业大学软件与微电子学院43用用宏扩展宏扩展来完成将三地址码到来完成将三地址码到P-P-代码的

39、翻译。代码的翻译。 例如一个三地址指令例如一个三地址指令 a=b+c a=b+c 可翻译成如下的可翻译成如下的P-P-代码指令序列：代码指令序列： lda a lod b; /or ldc b if b is a const lod c; /or ldc c if c is a const adi sto6 6.2.3 .2.3 从中间代码生成目标代码（续）从中间代码生成目标代码（续）machunyan西北工业大学软件与微电子学院44用用静态模拟静态模拟来完成将来完成将P-P-代码到三地址码的翻译。代码到三地址码的翻译。例如例如: : 表达式表达式( (x=x+3)+4x=x+3)+4的的P-

40、P-代码如下：代码如下： lda x lod x ldc 3 adi stn ldc 4 adi执行一个执行一个P-P-机器栈的静态模拟用以发现机器栈的静态模拟用以发现P-P-代码的三代码的三地址码等效式：地址码等效式：6 6.2.3 .2.3 从中间代码生成目标代码（续）从中间代码生成目标代码（续）machunyan西北工业大学软件与微电子学院453 3栈顶栈顶x xx x的地址的地址现在当处理现在当处理adiadi操作时，产生三地址指令操作时，产生三地址指令 t1=x+3 t1=x+3 栈的状态为：栈的状态为：假定前三条假定前三条P-P-代码语句执行后，栈的状态如下：代码语句执行后，栈的状

41、态如下：栈顶栈顶t1t1x x的地址的地址6 6.2.3 .2.3 从中间代码生成目标代码（续）从中间代码生成目标代码（续）machunyan西北工业大学软件与微电子学院46下一条下一条stnstn指令翻译为如下的三地址指令：指令翻译为如下的三地址指令：x=t1x=t1栈变成：栈变成：栈顶栈顶t1t1下一条指令下一条指令ldc 4 ldc 4 将常量将常量4 4压入栈：压入栈：4 4栈顶栈顶t1t1最后指令最后指令adiadi生成三地址指令：生成三地址指令：t2=t1+4t2=t1+4栈变成：栈变成：栈顶栈顶t2t26 6.2.3 .2.3 从中间代码生成目标代码（续）从中间代码生成目标代码（

42、续）machunyan西北工业大学软件与微电子学院47第第6 6章章 代码生成代码生成6 6.1 .1 中间代码概览中间代码概览6 6.2 .2 基本的代码生成技术基本的代码生成技术6 6.3 .3 数据结构引用的中间代码生成数据结构引用的中间代码生成6 6.4 .4 控制语句和逻辑表达式的中间代码生成控制语句和逻辑表达式的中间代码生成6 6.5 .5 过程和函数调用的中间代码生成过程和函数调用的中间代码生成machunyan西北工业大学软件与微电子学院486 6.3 .3 数据结构引用的中间代码生成数据结构引用的中间代码生成6 6.3.1 .3.1 地址计算地址计算6 6.3.2 .3.2

43、数组引用的三地址码生成数组引用的三地址码生成6 6.3.3 .3.3 记录结构和指针引用记录结构和指针引用( (自学内容自学内容) )machunyan西北工业大学软件与微电子学院496 6.3.1 .3.1 地址计算地址计算o 为了定位实际地址，对于数组、记录域和指为了定位实际地址，对于数组、记录域和指针引用的中间代码生成通常需要执行地址计针引用的中间代码生成通常需要执行地址计算。引入用于地址计算的三地址码：算。引入用于地址计算的三地址码：n 假设把假设把2存放在变量存放在变量x所在位置加上所在位置加上10个个字节的地址处，用三地址码表示如下：字节的地址处，用三地址码表示如下：n t1=&a

44、mp;x+10 t1=2machunyan西北工业大学软件与微电子学院506 6.3 .3 数据结构引用的代码生成数据结构引用的代码生成6 6.3.1 .3.1 地址计算地址计算6 6.3.2 .3.2 数组引用的三地址码生成数组引用的三地址码生成6 6.3.3 .3.3 记录结构和指针引用（自学内容）记录结构和指针引用（自学内容）machunyan西北工业大学软件与微电子学院516 6.3.2 .3.2 数组引用的三地址码生成数组引用的三地址码生成例例6 6. .6 6: C: C数组引用数组引用ai的地址是：的地址是： base_address(a) + i * * sizeof(int)

45、赋值语句：赋值语句：t2 = a t1翻译成如下的三地址码：翻译成如下的三地址码：t3 = t1 elem_size (a)t4 = &a + t3t2 = t4赋值语句：赋值语句： at2 = t1翻译成如下的三地址码：翻译成如下的三地址码：t3 = t2 elem_size(a)t4 = &a + t3 t4 = t1返回数组元素所返回数组元素所占字节数占字节数machunyan西北工业大学软件与微电子学院52考虑一维数组引用的简单算术表达式文法考虑一维数组引用的简单算术表达式文法 expsubs = exp|aexp aexpaexp + factor|factor fa

46、ctor(exp)|num|subs subsid|idexp对应的三地址码的生成过程实现。对应的三地址码的生成过程实现。6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院53表达式表达式（ai+1=2)+aj的语法树结构如下：的语法树结构如下：i+1a2=+aj6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）t1 = i+1t2 = t1*elem_size(a)t3 = &a+t2t4 = j*elem_size(a)t5 = &a+t4t6 = *t5 +2*t

47、3 = 2machunyan西北工业大学软件与微电子学院54typedef enum OpKind, ConstKind, IdKind NodeKind;typedef enum Plus, Assign，Subs Optype;typedef struct streenode NodeKind kind; Optype op; struct streenode lchild, rchild; char strval; STreeNode;typedef STreeNode SyntaxTree;其语法树的其语法树的c语言定义如下：语言定义如下：6 6.3.2 .3.2 数组引用的三地址码生

48、成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院55opleft operand right operandt1 = t.leftchild.strval+t.rightchild.strval t.strval = t1t.leftchild.strval = t.rightchild.strval t.strval = t.rightchild.strval6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院56id subscript expt1 = t.lchild.strva

49、l * * elem_size (t.strval)t2 = &t.strval + t1t.strval = * *t2subsidexp6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）id根节点进一步参与运根节点进一步参与运算的名字属性算的名字属性machunyan西北工业大学软件与微电子学院57表达式表达式（ai+1=2)+aj的语法树结构如下：的语法树结构如下：i+1a2=+ajt1 = i+1t2 = t1 elem_size(a)t3 = &a+t2t4 = j elem_size(a)t5 = &a+t4t6 = t5 +

50、2 t3 = 26 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院58数组引用的算术表达式文法对应的三地址码的生成过程实现：数组引用的算术表达式文法对应的三地址码的生成过程实现：Void genCode(SyntaxTree t)if(t!=NULL) switch(t kind) case OpKind: switch(t op) case Plus: genCode(t lchild);genCode(t rchild);t.strval=newtemp();emit(t strval = t lchild st

51、rval +t rchild.strval)break; 6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院59case Assign: genCode(t lchild); genCode(t rchild); emit(t lchild.strval = t rchild strval); t strval= t rchild strval; break; 6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院60case Subs:gen

52、Code(tlchild);temp1=newtemp();emit(temp1 =tlchildstrval * *elem_size(tstrval);temp2=newtemp();emit(temp2 = &t strval +temp1);t strval = * *temp2;break;default:emit(“Error”);break; 6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院61 break; case ConstKind: break; case IdKind: break;

53、 default: emit(“error”); break; 6 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院62根据上述三地址码的生成过程，表达式（根据上述三地址码的生成过程，表达式（ai+1=2)+ajai+1=2)+aj相应的三地码如下：相应的三地码如下：i+1a2=+ajt1 = i+1t2 = t1*elem_size(a)t3 = &a+t2t4 = j*elem_size(a)t5 = &a+t4t6 = *t5 +2*t3 = 26 6.3.2 .3.2 数组引用的三地址码生成（续

54、）数组引用的三地址码生成（续）machunyan西北工业大学软件与微电子学院63id subscript exp1subscript exp26 6.3.2 .3.2 数组引用的三地址码生成（续）数组引用的三地址码生成（续）o思考题：撰写下述简单算术表达式文法对应的三地址码生成的递思考题：撰写下述简单算术表达式文法对应的三地址码生成的递归程序归程序.n expsubs=exp|aexpn aexpaexp+factor|factorn factor(exp)|num|subsn subsid|idexp，expo二维下标运算的语法树：二维下标运算的语法树：machunyan西北工业大学软件与微

55、电子学院646 6.3 .3 数据结构引用的代码生成数据结构引用的代码生成6 6.3.1 .3.1 地址计算地址计算6 6.3.2 .3.2 数组引用的三地址码生成数组引用的三地址码生成6 6.3.3 .3.3 记录结构和指针引用（自学内容）记录结构和指针引用（自学内容）machunyan西北工业大学软件与微电子学院656 6.3.3 .3.3 记录结构和指针引用记录结构和指针引用计算记录结构的域地址提出了一个同计算下标数组地址相计算记录结构的域地址提出了一个同计算下标数组地址相同的问题。同的问题。首先，计算结构变量的基地址，首先，计算结构变量的基地址，然后，找到域偏移量，两者相加得到结果地址

56、。然后，找到域偏移量，两者相加得到结果地址。例如，考虑例如，考虑C C语言声明：语言声明：typedef struct rec int i ; char c; int j ; Rec;. . .Rec x;machunyan西北工业大学软件与微电子学院66第一个参数是第一个参数是结构变量名，结构变量名，第二个参数是第二个参数是域名域名; ;函数的函数的返回值是返回值是x.jx.j的偏移量的偏移量6 6.3.3 .3.3 记录结构和指针引用（续）记录结构和指针引用（续）o 用于域地址计算的三地址码：为了计算用于域地址计算的三地址码：为了计算x.j的地址并的地址并存入临时变量存入临时变量t1，使用

57、如下的三地址指令：使用如下的三地址指令：o t1 =&x + field_offset(x,j)o 如如C语句的一个域赋值表达式：语句的一个域赋值表达式：x.j=x.i ;n被翻译成如下的三地址码被翻译成如下的三地址码:t1=&x+field_offset(x,j)t2 =&x+field_offset(x,i) t1= t2machunyan西北工业大学软件与微电子学院676 6.3.3 .3.3 记录结构和指针引用（续）记录结构和指针引用（续）o 对于指针引用，例如假设对于指针引用，例如假设x被定义成整型指针：被定义成整型指针：n int x;o 假设假设i是一个普

58、通整型变量，是一个普通整型变量，C赋值语句：赋值语句：n x = i; 翻译成三地址指令翻译成三地址指令:n x = io 赋值语句赋值语句n i = x; 翻译成三地址指令翻译成三地址指令n i = xmachunyan西北工业大学软件与微电子学院68C变量声明如下：变量声明如下：typedef struct treeNode int val; struct treeNode * lchild, * rchild;TreeNode; .TreeNode *p;6 6.3.3 .3.3 记录结构和指针引用（续）记录结构和指针引用（续）machunyan西北工业大学软件与微电子学院69现在考虑两

59、个典型的赋值现在考虑两个典型的赋值p-lchild=p;p=p-rchild;这些语句翻译成三地址码如下：这些语句翻译成三地址码如下：t1=p+field_offset( p,lchild) t1=pt2=p+field_offset( p,rchild )p= t26 6.3.3 .3.3 记录结构和指针引用（续）记录结构和指针引用（续）machunyan西北工业大学软件与微电子学院70第第6 6章章 代码生成代码生成6 6.1 .1 中间代码概览中间代码概览6 6.2 .2 基本的代码生成技术基本的代码生成技术6 6.3 .3 数据结构引用的代码生成数据结构引用的代码生成6 6.4 .4

60、控制语句和逻辑表达式的代码生成控制语句和逻辑表达式的代码生成6 6.5 .5 过程和函数调用的代码生成过程和函数调用的代码生成machunyan西北工业大学软件与微电子学院716 6.4 .4 控制语句和逻辑表达式的代码生成控制语句和逻辑表达式的代码生成6 6.4.1 .4.1 if if和和whilewhile语句的代码生成语句的代码生成6 6.4.2 .4.2 逻辑表达式的代码生成（自学内容）逻辑表达式的代码生成（自学内容）6 6.4.3 .4.3 if if和和whilewhile语句的代码生成过程举例语句的代码生成过程举例machunyan西北工业大学软件与微电子学院726 6.4.1 .4.1 if if和和whilewhile语句的代码生成语句的代码生成o 考虑下面两种考虑下面两种