版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
中间代码生成
中间代码生成(一)◼运行时刻环境概要◼存储组织和帧栈设计方法运行时刻环境◼目标程序的代码放置在代码区◼静态区、堆区、栈区分别放置不同类型生命期的数据值◼实践中，栈是由低地址向高地址增长，而堆是由高地址向低地址增长存储分配的典型方式◼运行时刻环境概要◼存储组织和帧栈设计方法运行时刻环境◼静态分配O
编译器在编译时刻就可以做出存储分配决定，
不需要考虑程序运行时刻的情形O
全局变量◼动态分配O
栈式存储：和过程的调用/返回同步进行分配和回收，值的生命期和过程生命期相同O
堆存储：数据对象比创建它的过程调用更长寿◼手工进行回收：C++/C…◼垃圾回收机制:Java/C#/Python…静态和动态存储分配◼过程调用(过程活动)在时间上总是嵌套的O
后调用的先返回O
因此用栈式分配来分配过程活动所需内存空间◼程序运行的所有过程活动可以用树表示O
每个结点对应于一个过程活动O
根结点对应于main过程的活动O
过程p的某次活动对应的结点的所有子结点：此次活动所调用的各个过程活动(从左向右，表示
调用的先后顺序)活动树◼程序：P277，图7-2◼过程调用(返回)序列和活
动树的前序(后序)遍历对应◼假定当前活动对应结点N，那么所有尚未结束的活动对应于N及其祖先结点。活动树的例子(1)◼过程调用和返回由控制栈进行管理◼每个活跃的活动对应于栈中的一个活动记录◼活动记录按照活动的开始时间，从栈底到栈顶排列活动记录◼a[11]为全局变量◼main没有局部变量◼r有局部变量i◼q的局部变量i，和参数m,n运行时刻栈的例子◼调用代码序列(calling
sequence)为活动
记录分配空间，填写记录中的信息◼返回代码序列(return
sequence)恢复机
器状态，使调用者继续运行◼调用代码序列会分割到调用者和被调用者中O
根据源语言、目标机器、操作系统的限制，可以有不同的分割方案O
把代码尽可能放在被调用者中调用代码序列◼数据方面O
能够把参数正确地传递给被调用者O
能够把返回值传递给调用者◼控制方面O
能够正确转到被调用过程的代码开始位置O
能够正确转回调用者的调用位置(的下一条指令)◼调用代码序列和活动记录的布局相关调用/返回代码序列的要求◼调用者和被调用者之间传递的值放在被调用者活动记录的开始位置◼固定长度的项放在中间位置O
控制链、访问链、机器状态字段◼早期不知道大小的项在活动记录尾部◼栈顶指针(top_sp)通常指向固定长度字段的末端活动记录的布局原则◼调用代码序列(Calling
sequence)O
调用者计算实在参数的值O
将返回地址和原top_sp存放到被调用者的活动记录中。调用者增加top_sp的值(越过了局部数据、临时变量、被调用者的参数、机器状态字段)O
被调用者保存寄存器值和其他状态字段O
被调用者初始化局部数据、开始运行◼返回代码序列(Return
sequence)O
被调用者将返回值放到和参数相邻的位置O
恢复top_sp和寄存器，跳转到返回地址调用代码序列的例子调用者/被调用者的活动记录◼看一个实际的例子栈中的变长数据◼如果数据对象的生命期局限于过程活动的
生命期，就可以分配
在运行时刻栈中O
变长数组也可以放在栈中◼
top指向实际的栈顶◼top_sp用于寻找顶层记录的定长字段栈中的变长数据◼没有嵌套过程时的数据访问O
C语言中，每个函数能够访问的变量◼函数的局部变量：相对地址已知，且存放在当前活动记录内，top_sp指针加上相对地址即可访问◼全局变量：在静态区，地址在编译时刻可知O
很容易将C语言的函数作为参数进行传递◼参数中只需包括函数代码的开始地址。◼在函数中访问非局部变量的模式很简单，不需要考虑过程是如何激活的非局部数据的访问(无嵌套过程)◼
PASCAL中，如果过程A的声明中包含了过程B的声明，那么B可以使用在A中声明的变量。◼当B的代码运行时，如果它使用的是A中的变量。那么这个变量指向运行栈中最上层的同名变量。◼
但是，我们不能通过嵌套层次直接得到A的活动记录的相对位置，必须通过访问链访问非局部数据的访问(嵌套声明过程)A的活动记录C的活动记录B的活动记录A的活动记录B的活动记录void
A(){int
void
{}
voidC();B();}当A调用C，C又调用B时:x,y;
B()
int
b;
x
=
b+y;当A直接调用B时:C(){B();}◼ML是一种函数式语言．变量一旦被声明并初始化就不会在改变，只有少数几个例外．◼定义变量并设定它们不可更改的初始值的语句有如下形式val<name>=(expression)◼函数使用如下语法进行定义fun<name>(<arguments>)=<body>◼使用下列形式的let语句来定义函数体let<list
of
definitions>in<statements>
end其中，定义通常是val或fun语句．每个这样的定义的作用域包括从该定义之后直到in为止的所
有定义，及直到end为止的所有语句．函数可嵌套地定义．如函数p的函数体可能包括一个let语句，而该语句又包含了另一个函数q的
定义．
一个支持嵌套声明的例子◼嵌套深度是正文概念，可以根据源程序静态地确定O
不内嵌于任何其他过程中的过程，嵌套深度为1O
嵌套在深度为i的过程中的过程，深度为i+1深度为1sort深度为2
readArray，exchange，
quicksort深度为3
partition嵌套深度◼访问链O
当被调用过程需要其他地方的某个数据时需要使用访问链进行定位O
如果过程p在声明时嵌套在过程q的声明中，
那么p的活动记录中的访问链指向最上层的q的活动记录O
从栈顶活动记录开始，访问链形成了一个链路，嵌套深度沿着链路逐一递减访问链◼设深度为np
的过程p访问变量x，而变量x在
深度为nq
的过程中声明，那么O
np-nq在编译时刻已知O
从当前活动记录出发，沿访问链前进np-nq次
找到的活动记录中的x就是要找的变量位置O
x相对于这个活动记录的偏移量在编译时刻已访问链知访问链的例子◼当过程q调用过程p时，访问链的变化O
p的深度大于q：根据作用域规则，p必然在q中直接定义；那么p的访问链指向当前活动记录◼s调用q(1,9)O
递归调用(p=q)：新活动记录的访问链等于当
前记录的访问链◼q(1,9)调用q(1,3)O
p的深度小于等于q的深度：此时必然有过程r，p直接在r中定义，而q嵌套在r中；p的访问链指向访问链的维护(直接调用过程)栈最高的r的活动记录◼p调用exchange访问链的维护：访问链的定义+作用域规则◼在传递过程指针参数时，过程型参数中不仅包含过程的代码指针，还包括正确的访
问链访问链的维护(过程指针型参数)◼用访问链访问数据时，访问开销和嵌套深度差有关◼使用显示表可以提高效率，访问开销为常量◼显示表：数组d为每个嵌套深度保留一个指针O
指针d[i]指向栈中最高的、嵌套深度为i的活动记录。O
如果程序p中访问嵌套深度为i的过程q中声明的变量x，那么d[i]直接指向相应的(必然是q的)活动记录◼
注意：i在编译时刻已知◼显示表的维护O
调用过程p时，在p的活动记录中保存d[np]的值，并将d[np]设置为当前活动记录。O
从p返回时，恢复d[np]的值。显示表q(1,9)调用
q(1,3)时，
q的深度为2q(1,3)调用p，
p的深度为3显示表的例子q调用e，e
的深度为2◼堆空间O
用于存放生命周期不确定、或生存到被明确删除为止的数据对象O例如：new生成的对象可以生存到被delete为止O
malloc申请的空间生存到被free为止◼存储管理器O
分配/回收堆区空间的子系统O
根据语言而定◼C、C++需要手动回收空间◼Java可以自动回收空间(垃圾收集)堆管理◼基本功能O
分配：为每个内存请求分配一段连续的、适当大小的堆空间◼首先从空闲的堆空间分配◼如果不行则从操作系统中获取内存、增加堆空间O
回收：把被回收的空间返回空闲空间缓冲池，以满足其他内存需求◼评价存储管理器的特性O
空间效率：使程序需要的堆空间最小，即减小碎片O
程序效率：充分运用内存系统的层次，提高效率O
低开销：使分配/收回内存的操作尽可能高效存储管理器存储管理器◼局部性大部分程序表现出高度的局部性–程序的大部分运行时间花费在相对较小的一部分代码中(此时可能只涉及固定的一小部分数据)。程序中的局部性◼随着程序分配/回收内存，堆区逐渐被割裂成为若干空闲存储块(窗口，hole)和已用存储块的交错◼分配一块内存时，通常是把一个窗口的一部分分配出去，其余部分成为更小的块◼回收时，被释放的存储块被放回缓冲池。通常要把连续的窗口接合成为更大的窗口堆空间的碎片问题已分配空间碎片◼Best-FitO
总是将请求的内存分配在满足请求的最小的窗口中O
好处：可以将大的窗口保留下来，应对更大的请求◼First-FitO
总是将对象放置在第一个能够容纳请求的窗口中O
放置对象时花费时间较少，但是总体性能较差O
但是first-fit的分配方法通常具有较好的数据局部性◼同一时间段内的生成的对象经常被分配在连续的空间内堆空间分配方法◼设定不同大小的空闲块规格，相同规格的块放在同一容器中◼较小的(较常用的)尺寸设置较多的容器◼比如GNU的C编译器将所有存储块对齐到8字节边界O
空闲块的尺寸大小◼16,24,32,40,…,512◼大于512的按照对数划分：每个容器的最小尺寸是前一个容器的最小尺寸的两倍◼荒野块：可以扩展的内存块O
分配方法◼对于小尺寸的请求，直接在相应容器中找◼大尺寸的请求，在适当的容器中寻找适当的空闲块◼可能需要分割内存块◼可能需要从荒野块中分割出更多的块使用容器的堆管理方法◼当回收一个块时，可以把这个块和相邻的块接合起来，构成更大的块◼支持相邻块接合的数据结构O
边界标记：在每一块存储块的两端，
分别设置一个free/used位；相邻的位置上存放字节
总数O
双重链接的、嵌入式的空闲块列表：
列表的指针存放在空闲块中、用双向指针的方式记录了有哪些空闲块管理和接合空闲空间◼相邻的存储块A、B、CO
当回收B时，通过对free/used位的查询，可以知道B左边的A是空闲的，而C不空闲。O
同时还可以知道A、B合并为长度为300的块O
修改双重链表，把A替换为A、B接合后的空闲块◼注意：双重链表中一个结点的前驱并不一定是它邻近的块例子◼两大问题O
内存泄露：未能删除不可能再被引用的数据O
悬空指针引用：引用已被删除的数据◼其他问题O
空指针访问/数组越界访问◼解决方法O
自动存储管理O
正确的编程模式处理手工存储管理◼对象所有者(Object
ownership)O
每个对象总是有且只有一个所有者(指向此对象的指针)；只有通过Owner才能够删除这个对象O当Owner消亡时，这个对象要么也被删除，要么已
经被传递给另一个owner◼语句v=new
ClassA；创建的对象的所有者为v◼即将对v进行赋值的时刻(v的值即将消亡)O
要么v已经不是它所指对象的所有者；比如g=v可以把v的ownership传递给gO
要么需要在返回/赋值之前，执行delete
v操作O
编程时需要了解各个指针在不同时刻是否ownerO
防止内存泄漏，避免多次删除对象。不能解决悬空指针问题正确的编程模式(1)◼引用计数O
每个动态分配的对象附上一个计数：记录有多少个指针指向这个对象O
在赋值/返回/参数传递时维护引用计数的一致性O
在计数变成0之时删除这个对象O
可以解决悬空指针问题；但是在递归数据结构中仍然可能引起内存泄漏O
需要较大的运行时刻开销◼基于区域的分配O
将一些生命期相同的对象分配在同一个区域中O
整个区域同时删除正确的编程模式(2)中间代码生成(二)◼中间表示◼类型与声明◼表达式的翻译◼控制流与回填运行时刻环境◼静态类型检查和中间代码生成的过程都可以用语法制导的翻译来描述和实现◼对于抽象语法树这种中间表示的生成，
第五章已经介绍过编译器前端的逻辑结构◼每条指令右侧最多有一个运算符O
一般情况可以写成x=y
op
z◼允许的运算分量O
名字：源程序中的名字作为三地址代码的地址O
常量：源程序中出现或生成的常量O
编译器生成的临时变量三地址代码(1)◼指令集合
(1)O
运算/赋值指令：x=y
op
z
x
=opyO复制指令：x=yO
无条件转移指令：gotoLO
条件转移指令：if
x
goto
L
ifFalsexgoto
LO
条件转移指令：if
x
relop
ygotoL三地址代码(2)◼指令集合(2)O
过程调用/返回◼param
x1//设置参数◼
paramx2◼
…◼
paramxn◼call
p,n//调用子过程p，n为参数个数O
带下标的复制指令：x=y[i]x[i]=y◼注意：i表示离开数组位置第i个字节，而不是数组的第i个元素O
地址/指针赋值指令：三地址代码(3)◼
x=&yx=*y*x=y◼语句O
do
i=i+1;while(a[i]<v)；三地址代码实例◼在实现时，可以使用四元式/三元式/间接三元式来表示三地址指令◼四元式：可以实现为纪录(或结构)◼格式(字段)：op
arg1arg2resultO
op:运算符的内部编码O
arg1,arg2,result是地址O
x=y+z+y
z
x◼单目运算符不使用arg2◼param运算不使用arg2和result◼条件转移/非条件转移将目标标号放在result字段三地址指令的四元式表示方法◼赋值语句：a=b*-c+b*-c四元式的例子◼三元式(triple)op
arg1arg2◼使用三元式的位置来引用三元式的运算结果◼x[i]=y需要拆分为两个三元式O
求x[i]的地址，然后再赋值◼x=y
op
z需要拆分为(这里？是编号)O
(?)op
y
zO
=x
?◼问题：在优化时经常需要移动/删除/添加三元式，导致三元式的移动三元式表示三元式的例子◼包含了一个指向三元式的指针的列表◼我们可以对这个列表进行操作，完成优化功能；操作时不需要修改三元式中的参数间接三元式◼SSA中的所有赋值都是针对不同名的变量◼对于同一个变量在不同路径中定值的情况，可以使用φ函数来合并不同的定值O
if(flag)x=-1;else
x=1;y
=x*aO
if(flag)x1=-1;else
x2
=1;x3=φ(x1,x2)；静态单赋值(SSA)y=x3*a◼语法树中，公共子表达式每出现一次，就有一个对应的子树◼表达式的有向无环图(Directed
AcyclicGraph,DAG)能够指出表达式中的公共子表达式，更简洁地表示表达式表达式的有向无环图◼可以用和构造抽象语法树一样的SDD来构造DAG构造◼
不同的处理O
在函数Leaf和Node每次被调用时，构造新节点前先检查是否已存在同样的节点，如果已经存在，则返回这个已有的节点DAG构造◼
构造过程示例◼中间表示◼类型与声明◼表达式的翻译◼控制流与回填运行时刻环境◼类型检查(TypeChecking)O
利用一组规则来检查运算分量的类型和运算符的预期类型是否匹配◼类型信息的用途O
查错、确定名字需要的内存空间、计算数组元素的地址、类型转换、选择正确的运算符◼主要内容O
确定名字的类型O
变量的存储空间布局(相对地址)类型和声明◼类型系统O
给每一个组成部分赋予一个类型表达式O
通过一组逻辑规则来表示这些类型表达式必须满足的条件◼可发现错误、提高代码效率、确定临时变量的大小…类型检查和转换◼类型综合O
根据子表达式的类型构造出表达式的类型if
f的类型为st
t且x的类型为sthen
f(x)的类型为t◼类型推导O
根据语言结构的使用方式来确定该结构的类型：if
f(x)是一个表达式then对于某些类型α,β；f的类型为αtβ且x的类类型系统的分类型为α◼假设在表达式x*i中，x为浮点数、i为整数，则结果应该是浮点数O
x和i使用不同的二进制表示方式O
浮点*和整数*使用不同的指令◼t1=(float)i◼t2=xfmult1◼类型转换比较简单时的SDDO
E
t
E1+E2{if(E1.type=integer
and
E2.type=integer)E.type
=integer;else
if(E1.type=float
and
E2.type=integer)E.type
=float;}O
这个规则没有考虑生成类型转换代码类型转换◼编译器自动完成的转换为隐式转换，程序员用代码指定的转换为显式转换类型的widening和narrowing◼函数Max求的是两个参数在拓宽层次结构中
的最小公共祖先◼Widen函数已经生成了
必要的类型转换代码处理类型转换的SDT◼通过查看参数来解决函数重载问题◼E
t
f(E1){if
f.typeset={si
t
ti
|1<=i<=k}
andE1.type=skthen
E.type=
tk函数/运算符的重载}◼类型表达式(type
expression)：表示类型的结构O
基本类型O
类名O
类型构造算子作用于类型◼array[数字，类型表达式]◼record[字段/类型对的列表](可以用符号表表示)O
函数类型构造算子t
：参数类型t结果类型O笛卡尔积：sX
tO
可以包含取值为类型表达式的变量类型表达式◼类型例子O
元素个数为3X4的二维数组O
数组的元素的记录类型O
该记录类型中包含两个字段:
x和y,其类型分别是float和integer◼类型表达式O
array[3,
array[4,record[(x,float),(y,integer)]]]类型表达式的例子◼不同的语言有不同的类型等价的定义◼结构等价O
或者它们是相同的基本类型O
或者是相同的构造算子作用于结构等价的类型而得到的。O
或者一个类型是另一个类型表达式的名字◼名等价O
类型名仅仅代表其自身类型等价◼变量的类型可以确定变量需要的内存O
即类型的宽度O
可变大小的数据结构只需要考虑指针◼函数的局部变量总是分配在连续的区间O
因此给每个变量分配一个相对于这个区间开始处的相对地址◼变量的类型信息保存在符号表中局部变量名的存储布局计算类型和宽度的SDT◼综合属性：type,width◼全局变量t和w用于将类型和宽度信息从B传递到C
t
εO
相当于C的继承属性，因为总是通过拷贝来传递，所以在SDT中只赋值一次，也可以把t和w替换为C.t和C.w计算类型和宽度的SDT◼综合属性：type,width◼全局变量t和w用于将类型和宽度信息从B传递到C→εO
相当于C的继承属性，因为总是通过拷贝来传递，所以在SDT中只赋值一次，也可以把t和w替换为C.t和C.w计算类型和宽度的SDTSDT运行的例子◼输入：int[2][3]◼含义O
D生成一个声明列表O
T生成不同的类型O
B生成基本类型int/floatO
C表示分量，生成[num]序列O
注意record中包含了各个字段的声明，字段声明
和变量声明的文法一致◼文法声明◼除了确定类型和类型宽度，还有什么语义需要处理？O
符号表中的位置声明序列的SDT◼在处理一个过程/函数时，局部变量应该放到单独的符号表中去◼这些变量的内存布局独立O
相对地址从0开始O
假设变量的放置和声明的顺序相同◼SDT的处理方法O
变量offset记录当前可用的相对地址O每“分配”一个变量，offset的值增加相应的值◼top.put(id.lexeme,T.type,offset)O
在当前符号表(位于栈顶)中创建符号表条目，记录标识符的类型，偏移量声明序列的SDT
(1)◼我们可以把offset看作D的继承属性O
D.offset表示D中第一个变量的相对地址O
P
t
{D.offset=0}
DO
D
t
T
id;{D1.offset=D.offset
+T.width;}
D1声明序列的SDT
(2)◼Ttrecord‘{‘D‘}’◼为每个记录创建单独的符号表O
首先创建一个新的符号表，压到栈顶O
然后处理对应于字段声明的D，字段都被加入到新符号表中O最后根据栈顶的符号表构造出record类型表达式；
符号表出栈记录字段的处理◼中间表示◼类型与声明◼表达式的翻译◼控制流与回填运行时刻环境◼将表达式翻译成三地址指令序列◼表达式的SDDO
属性code表示代码O
addr表示存放表达式结果的地址
(临时变量)O
new
Temp()可以生成一个临时变量O
gen(…)生成一个指令表达式代码的SDD表达式代码的SDD◼主属性code满足增量式翻译的条件◼
注意O
top.get(…)从栈顶符号表开始，逐个向下寻找id的信息O
这里的gen发出相应的代码增量式翻译方案◼数组元素存储在一块连续的存储空间中，以方便快速的访问它们◼n个数组元素是0,1,…,n-1进行顺序编号的◼假设每个数组元素宽度是w，那么数组A的第i个元素的开始地址为base+i*w,base是A[0]的相对地址。◼推广到二维或多维数组。A[i1][i2]表示第i1行第i2个
元素。假设一行的宽度是w1
，同一行中每个元素
的宽度是w2
，
A[i1][i2]的相对地址是base+i1
*w1+i2
*w2◼
对于k维数组A[i1][i2]…[ik]，推广Obase+i1
*w1+i2
*w2+…+ik
*wk数组元素的寻址◼根据第j维上的数组元素的个数nj和该数组每个元素的宽度w进行计算的，如二维数组A[i1][i2]的地址base+(i1
*n2+i2)*w◼于k维数组A[i1][i2]…[ik]的地址base+((…(i1
*n2+i2)*n3+i3)…)*nk+ik)*w◼有时下标不一定从0开始，比如一维数组编号low,low+1,…,high，此时base是A[low]的相对地址。计算A[i]的地址变成base+(i-low)*w◼预先计算技术O
改写成i*w+c的形式，其中c=base-low*w可以在编译时刻预先计算出来，计算A[i]的相对地址只要计算i*w再加上c就可以了数组元素的寻址(续)
◼按行存放策略和按列存放策略可以推广到多维数组中数组元素的寻址(续)◼上述地址的计算是按行存放的◼为数组引用生成代码要解决的主要问题O
数组引用的文法和地址计算相关联◼假定数组编号从0开始，基于宽度来计算相对地址◼数组引用相关文法O
非终结符号L生成一个数组名字加上一个下标表达式序列数组引用的翻译◼非终结符号L的三个综合属性O
L.addr指示一个临时变量，计算数组引用的偏移量O
L.array是一个指向数组名字对应的符号表条
目的指针，L.array.base为该数组的基地址O
L.type是L生成的子数组的类型，对于任何数
组类型t，其宽度由t.width给出，t.elem给出其数组元素的类型数组引用生成代码的翻译方案数组引用生成代码的翻译方案核心是确定数组引用的地址◼
基于数组引用的翻译方案，表达式c+a[i][j]的注释语法树及三地址代码序列◼假设a是一个2*3的整数数组，c、i、j都是整数O
那么a的类型是array(2,array(3,integer)),a的宽度是24O
a[i]的类型是array(3,integer)，宽度是12O
a[i][j]的类型是整型数组引用翻译示例◼中间表示◼类型与声明◼表达式的翻译◼控制流与回填运行时刻环境◼if-else语句，while语句◼翻译目标：控制流语句翻译◼if-else语句，while语句◼需要将语句的翻译和布尔表达式的翻译结合在一起◼布尔表达式是被用作语句中改变控制流的条件表达式，通常用来O
改变控制流。布尔表达式的值由程序到达的某个位置隐含地指出。O
计算逻辑值。可以使用带有逻辑运算符的三地址指令进行求值。◼布尔表达式的使用意图要根据其语法上下文确定O
跟在关键字if后面的表达式用来改变控制流O
一个赋值语句右部的表达式用来计算一个逻辑值O
可以使用两个不同的非终结符号或其它方法来区分这两种使用控制流语句翻译◼将布尔运算符作用在布尔变量或关系表达式上，构成布尔表
达式◼引入新的非终结符号B表示布尔表达式◼布尔运算符:&&、||、
!◼关系表达式E1rel
E2◼关系运算符：<、<=、=、!=、>、>=◼其中布尔运算符&&和||是左结合的，优先级||最低，其次是&&，！最高◼表示布尔表达式的文法布尔表达式◼B1||B2,B1为真，则不用求B2也能断定整个表达式为真◼B1&&B2,B1为假，则整个表达式肯定为假◼如果某些程序设计语言允许这种高效的求值方式，则编译器可以优化布尔表达式的求值过程，只要已经求值部分足以确定整个表达式的值就可以了。布尔表达式的高效求值◼布尔运算符&&、||、!被翻译成跳转指令。
由跳转位置隐含的指出布尔表达式的值。◼if(x<100||x>200&&x!=y)x=0;短路(跳转)代码◼B和S有综合属性code，表示翻译得到的三地址代码。◼B的继承属性true和false
，S的继承属性next，表示跳转
的位置。◼
S.true是一个地址，用于存放了B为真时控制流转向的指令标号，S.false同理◼S.next也是一个地址，用于存放紧跟在S代码之后的指控制流语句翻译◼
语句及文法令标号◼B和S有综合属性code，表示翻译得到的三地址代码。◼B的继承属性true和false
，S的继承属性next，表示跳转控制流语句翻译◼
语句及文法的位置。◼几个核心函数回顾：O
newlabel
函数：生成一个用于存放标号的临
时变量L，返回变量地址；O
label(X)函数：将下一条指令的标号复制给参控制流语句翻译分析数X；翻译S→if(B)S1,创建B.true标号，并指向S1的第一条指令。
翻译S→if(B)S1else
S2,B为
真时，跳转到S1代码的第一条指令；当B为假时跳转到S2代码的第一条指令。然后，控制流从S1或S2转到紧跟在S的代码后面的三地址指令，该指令由继承属性S.next指定。while语句中有个begin局部变量……控制流语句翻译分析◼◼◼◼布尔表达式B被翻译成三地址
指令，生成的条件或无条件转
移指令反映B的值。B→E1
rel
E2，直接翻译成三地址比较指令，跳转到正确位置。B→B1||B2,如果B1为真，B
一定为真，所以B1.true和B.true相同。如果B1为假，那
就要对B2求值。因此B1.false
指向B2的代码开始的位置。B2
的真假出口分别等于B的真假
出口。……布尔表达式的控制流翻译及分析◼◼◼◼控制流语句及布尔表达式翻译◼布尔表达式翻译，a<bif
a<b
goto
B.truegoto
B.false◼控制流语句翻译if(x<100||x>200&&x!=y)x=0;布尔表达式及控制流语句翻译示例◼在上面的例子中gotoL3是冗余的◼X>200翻译成
◼可以替换成O
减少了一条goto指令O引入一个特殊标号“fall”(穿越，fallthrough)，表示
不要生成任何跳转指令。◼S→if(B)S1
的新语义规则◼对于if-else和while语句的规则也将B.true设为fall避免冗余的goto指令利用“穿越”修改布尔表达式的语义规则
注意B.true=fall时，还得为B1
.true
new一个labelB1
.false=if(B.false=fall)newlabel()else
B.falseB1
.true=fallB2
.true=B.trueB2
.false=B.falseB.code=if(B.false=fall)then
B1
.code||B2
.code||label(B1
.false)elseB1
.code||B2
.codeB
→B1&&B2带“穿越”的语义规则使用标号fall的控制流语句翻译示例◼if(x<100||x>200&&
x!=y)x=0;◼改变控制流，跳转O
刚刚前面重点讨论，用非终结符号B表示此种功能的布尔表达式以示区别◼
求值O
如x=true,x=a<b◼统一处理O使用不同的代码生成函数处理表达式的两种角色。E.n对应于抽象
语法树上的表达式节点。两个函数：◼
jump,对于出现在S→while(E)S1中的E，调用E.n.jump(t,f)◼
rvalue,对于出现在S→id=E中的E，在节点E.n上调用rvalue。如果E是算术表达式，按照算术表达式的翻译生成代码。如果E是布尔表达式，如E1&E2，首先为E生成跳转代码，然后在跳转代码的真假出口分别将true或false赋给一个新的临时变量t。布尔表达式的两个功能◼赋值语句x=a<b&&c<d示例◼为布尔表达式和控制流语句生成目标代码的关键问题：某些跳转指令应该跳转到哪里◼例如：if(B)SO
按照短路代码的翻译方法，B的代码中有一些跳转指令在B为假时执行，O
这些跳转指令的目标应该跳过S对应的代码,生成这些指令时，S的代码尚未生成，因此目标不
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论