第七章 编译程序
7.1 编译程序考虑的因素编译程序设计时，除了需用到前介绍的分析技术和制导翻译技术外，还要考虑如何从源程序数据空间映射到具体物理存储空间，也就是运行时的数据表示。在运行时如何组织或存放数据、在源程序中同名标识符是怎样描述不同的对象、
运行时的程序控制权是如何转移和参数是如何传递的以及如何生成质量较高的目标代码都是编译程序设计者需考虑的问题。
7.1.1 数据类型类型的合法性检查是判断数据的类型是否与上下文的要求相一致，例如 Pascal的运算符‘ +’不能作用在字符型数据上，而 C语言的‘ +’却能作用在字符型数据上。在数据类型上定义的各种运算通常包括赋值和一系列类型转换规则，这些规则保证了作用在数据对象上的某个运算符顺便通过由编译程序的类型的合法性检查，并实现其合法的算和赋值。因此，给出定义：
定义 7.1 数据类型是对该类型数据（变量或常量）的取值是否合法以及对该类型据的运算是否合法的一种说明。
实现和完成数据类型的合法性检查，它包括以下任务：
(1) 检查运算符作用在运算对象上的合法性，这一合法性保证了该运算能产生正确的运算结果。
(2) 根据程序设计语言运算符的类型转换规则，将一种类型数据转换成另一种数据类型。
(3) 能够使用相应的目标机器指令实现这种在上述类型上定义的运算。
例,设有 Pascal程序段
var
a,b:integer;
x:real;
begin
read(a);
b:=10;
x:=a mod b;
a:=a-x*10
end;
对于读语句 read(a)和赋值语句 b:=10都满足简单的类型检查。在赋值语句 x:=a mod b中虽然 a mod b的结果是整型的，但仍能满足将 a mod b的结果赋给实型变量 x。这是因为在 Pascal中定义了将整型转换成实型的转换规则，因而编译程序需生成将 a mod b的结果转换成实型的指令代码。而对于语句 a:=a-x*10，虽然通过 Pascal定义的类型规则可以将 a
转换成实型，求出 a-x*10的结果类型为实型，但 Pascal不允许将实型赋给整型，则出错。
例,设有 C语言程序段
{int a,b;
real x;
scanf(“%d”,&a);
b=10;
x:=a/b;
a:=a-x*10;
}
可以看出，上述二个程序段期望完成的功能是一样的，
但前者不能通过编译，而后者能顺利通过编译的类型检查，
这是因为 C语言中赋值语句 a:=a-x*10中也包含了强制将实型转换成整型。
根据语言的类型定义方式，可以将类型分为基本类型和构造类型，基本类型是指系统已定义的数据类型，如 C语言中的整型、浮点型（实型）、字符型。构造类型的指通过基本类型或已定义的类型构造出的新的数据类型，如 Pascal中的数组、记录和集合。引进了构造类型后，类型的合法性检查变得复杂。其检查方法有二大类，一类是名字等价，另一类是结构等价。
所谓名字等价也就是如果二个类型是等价的，当且仅当二个类型的名字或与类型名字的别名是等价的。
例,设有 Pascal程序段
type int=integer;
var
a:integer;
b:integer;
c:int;
……
a和 b是同一类型名 integer故它们是等价的；虽然 a和 c的类型名不同，但是 int是 integer的一种别名，故 a和 c的类型还是等价的。
所谓结构等价也就是如果二个类型是等价的，当且仅当二个类型具有相同的类型表达式。
定义 7.2 类型表达式是递归定义的,
(1) 类型表达式是基本数据类型
(2) 类型表达式是由数组、记录、集合、指针、函数等作用在类型表达式上的类型 。
检查类型的名字等价相对简单，只要为定义的类型名建立一张符号表，通过查表就可以判定二个类型是否名字等价。虽然，对于类型的等价的直观概念是结构等价，但结构等价检查的实现方法稍复杂。需为每个类型建立表示类型的结构树或无环有向图，如图为类型。
record
name,array[1..20] of char;
age:integer
end;
的树结构表示。
其中,array中的 integer
表示下标的类型对于如说明链表或树的数据结构的定义时，需递归定义。因此递归定义的类型图为无环有向图。图为类型
type link=↑node;
node=record
name,array[1..20] of char;
next:link
end;
的无环有向图。
检查二个类型是结构等价，只要二个类型结构树或无环有向图相等即可。检查类型等价也分成静态检查和动态检查。
由编译程序能完成的类型检查叫做静态类型检查；由目标程序运行时所作的类型检查就称为动态类型检查。一般地，如果要在生成的目标代码中完成类型检查，则目标代中不但要保存数据的值，而且还保存该数据的类型，则可完工成相应的动态类型检查。因算法语言的类型检查多数是静态的类型检查，在这里仅介绍了静态的类型检查。
7.1.2 数据结构一种程序设计语言如允许使用的数组、记录、集合、字符串、表、栈等形式的数据结构，在编译程序中应为它们提供相应的翻译。为了能对这些数据结构中的元素的引用，编译程序必须完成从这些数据的逻辑结构到访问这些数据元素的物理结构的映射。
使用上述数据结构应考虑：
(1) 映射算法相对简单，根据逻辑结构容易计算出物理地址。
(2) 从逻辑结构投影到物理结构时，不至于越界或存储溢出。
(3) 使用的数据结构承担这种程序设计语言的主要功能。
(4) 在这些数据结构上定义的运算。
例,设有类 Pascal程序段
program example(input,output);
type student=record
no:integer;
name:array[1..10] of char;
score:integer
end;
weekday=(sun,mon,tue,wed,thu,fri,sat);
var st:array[1..50] of student;
day:weekday;
i,j:integer;
begin
today:= sun;
i:=1;
st[i].no:=30;
st[i].name:=’wang fang’
……
end.
从上可以看出,st是一个记录型的数组，它首先通过数组的映射计算出 st[i]的地址，然后再通过记录的映射分别计算出 st[i].no 和 st[i].name的地址。对于枚举类型的数据
sun,mon,tue,wed,thu,fri,sat如何描述它们的值和在枚举类型的数据上的运算。对于字符串 st[i].name应考虑是否允许整体赋值和字符串是否允许连接等运算，运算后的结果到存储器中。连接后的结果如超出字符串设定的长度，如何强制或报错。
如要实现一个“栈”的数据类型，就应该考虑是否设置栈的最大容量，栈上的运算如,push和 pop。栈元素所允许的数据类型，如栈元素的类型允许是数组、记录、集合、字符串，但不能是表或栈。还要考虑如何将栈顶映射的物理存储空间。如设定静态的定长的栈空间用指针或下标指示当前栈顶或设定不定长的动态空间当入栈时申请存储空间，出栈时返回存储空间。
7.1.3 作用域规则一个程序设计语言的作用域规则确定了该程序设计语言的某个程序的不同程序块中所说明的标识符的可访问性。从另一个角度来看，在程序中当访问一个标识符通过作用域规则可确定究竟访问的是哪一个实体中说明的标识符。一般来说一个程序设计语言的一个标识符或数据项的作用域是在说明该标识符或数据项的程序块内，如 Pascal中的标识符的作用域规则，叙述如下：
(1) 一个标识符的作用域是从该标识符的定义点开始至定义该标识符的分程序结束为止，包含在这个分程序中的所有内分程序，并遵循规则 2。
(2) 当一个标识符 x在分程序 A中被定义，在 A所包含的分程序
B中又重新被定义，则分程序 B以及包含在 B中的所有分所出的 x不再是 A中定义的 x，而是 B中定义的 x。
例,设有 Pascal程序段
program example(input,output);
var x,y,real;
procedure pro;
var y,z,integer;
begin
……
x:=y;
……
end
begin
……
end.
在过程 pro中赋值语句 x:=y的 x为主程序中说明的 x，而 y为过程序中说明的 y。
作用域还包括文件作用域，如 C语言的函数作用域是从说明点开始，一直延伸到源文件结束。
作用域规则的不同直接影响到编译程序需生成的代码。
作用域规则分为静态作用域和动态作用域二种。静态作用域是指当标识符在本分程序中没有说明时，到说明该分程序的上一分程序中找相应的标识符，依次类推直至找到该标识符或整个上层分程序中均没找到该标识符为止。否则出错。动态作用域是指当标识符在本分程序逻辑中没有说明时，到调用该分程序的程序中找，依次类推直至找到该标识符或整个调用程序中均没找到该标识符为止，同样动态作用域也分为找到和出错。显然上述 Pascal中的作用域规则是静态作用域规则，静态作用域规则在编译中处理要比动态作用域的处理简单些。
7.1.4 控制结构一种程序设计语言的控制结构是该语言在程序运行期间用于改变控制流的语言特征集合。它包括有条件控制转移，
条件执行、循环控制、过程序调用、转移和出口。编译程序在翻译时必须保证源程序不能违法控制结构的语义。如
Pascal中只能从循环体内转向循环体外,C语言中不能从一个函数转向另一个函数,BASIC中不能在循环体内修改循环变量的值，而 C没有这种限制。
例,错误的控制结构
begin
for i:=1 to 10
begin
label:x:=x+1;
……
end;
goto label
……
end
程序的控制结构实际是程序执行权的转移。为了减少程序员编制的源程序中的错误。通常对程序的结构一定的约定。
因此，在设计或翻译程序设计语言的的控制结构时，需考虑：
设定或限制某种程序的控制，应满足程序设计的方法学或结构化程序设计的思想。
对每一种程序的控制结构，均能用编译的翻译技术来实现翻译。
提供程序的控制结构有利于程序员实现程序和查找源程序的错误。
综上所述，如何实现控制结构的翻译也是编译程序必须考虑的问题。
7.2 运行时的内存分配编译程序需要为常量或变量等数据分配运行时的存储空间。编译程序从操作系统中申请编译程序计算出的所需的内存或者编译程序生成在运时需申请内存的指令。
内存分配包括以下 3个任务：
(1) 确定用来表示某一数据项的内存的大小。
(2) 使用适当的内存分配策略实现具体数据的作用域和生命期。
(3) 确定以适当的算法访问生命期内的数据，包括基本型数据构造型数据。
以上三个任务实际上是完成逻辑数据到具体数据的映射。根据内存分配的时机，分为静态存储分配和动态存储分配方式。
采用哪一种分配策略是根据源语言的结构特点、源语言的数据类型、源语言中的作用域规则，源语言存储管理和组织的方式的复杂度都会影响到存储空间的分配策略。
下面就存储分配的主要技术，进行分析和讨论。
7.2.1 静态和动态内存分配为目标程序分配运行时所需的存储空间，一种是在目标程序运行前，由编译程序为数据分配存储空间，在程序的运行期间不再分配和解除这种内存分配。另一种在程序运行期间均可以对内存实现分配或解除分配，一旦存储分配解除该存储空间内的数据便失去意义。前者称为静态存储分配，后者称为动态存储分配。
定义 7.3 内存结合是指数据项的逻辑地址映射到内存物理地址的联系内存分配和内存结合是两个不同的概念，内存分配相当于在上网时用户申请了用户名，此时网络营运商将某个用户名“分配”给了该用户，但此时该用户不一定在上网。内存结合相当于网络用户用了申请到的用户名上网。网络用户的结合从用户的上网起至该用户下网止。
内存分配是实现内存结合的过程和手段，内存结合在内存解除分配时终止。源程序数据项的结合时刻决定编译程序的处理方式。当编译程序可以产生内存分配的代码时，不要在运行产生这种分配。这会影响到目标程序的效率。由于内存分配的时机不同，引入静态存储分配和动态存储分配的两种方式。
1,静态存储分配在静态存储分配中，编译程序在运行前为数据分配内存。
典型的静态存储分配是在编译时分配的。这要求编译程序在编译时能确定目标程序运行中据需的全部数据空间的大小，
编译程序将数据和内存结合从而实现存储分配。编译程序一旦实现静态存储分配，在整个程序运行期间不再进行存储分配或解除存储分配的工作直到整个程序运行结束。如 C语言中的全局变量和静态变量都是静态存储分配的。
例,图说明了下列 C语言程序段的静态数据存储分配
int a,b,c;
char d[100];
int f ();
main()
{int x=5,y=8;
printf(“%d,,f (x);)
printf(“%d,,g (y);)
}
int f(int n)
{static int p=0;
p+=n;
return(p);
}
int g(int m)
{static float q=0;
q+=m;
return(q);
}
图中的阴影部分表示其它数据的存储空间。
静态存储分配的限制：
(1) 数据对象的长度和它在内存中的位置在编译时都是已知的
(2) 不能建立如递归过程或递归函数中的一个名字对应多个存储空间的结合
(3) 不能建立数据对象长度不定的存储空间
2,动态存储分配为了避免上述对静态存储分配的限制，引进了动态存储分配。动态分配的数据区在运行不是一成不变的，它有时引入，有时退出，是一个动态的变化过程。动态存储分配分为二大类，一类是随着程序单元的进入而分配，随着程序单元的退出而撤销。另一类是由程序控制其分配和撤销。它们分别用栈和堆来实现，被称为栈式动态存储分配和堆式动态存储分配。
a)栈式动态分配当一个程序设计语言允许递归时，则每次进入该递归过程或函数时，就应分配一块大小相同的内存。当该过程或函数结束时相应的内存释放。由于递归过程或函数的进入和退出符合栈的先进后出的原则，故这一类存储分配可用栈实现。
把每次进入过程或函数需分配的数据区称为活动记录。
活动记录包括（如图所示）：
(1) 连接数据
a) 老的 SP。
每个活动记录，有一个基址指针称为 SP。为了撤销本活动记录时能指出上一个调用者的活动记录就应保存调用者的
SP称为老的 SP。而老的栈顶不必保存，因为老的栈顶为现
SP-1（设 SP占一个存储单元）
b) 返回地址返回地址是指子程序完成后的返回地址（对于函数还要返回其函数值）。
(2) 程序状态字为保存调用者的机器信息，如程序计数器、标志寄存器和寄存器的值，在返回时，预以恢复。
(3) 参数个数
(4)形式单元存放实在参数的值或地址。
(5) 局部数据局部数据包括：局部变量、静态数组的数据区、动态数组的内情向量和临时工作单元。
例,设有程序结构如下所示：
program main;
全局变量或数组说明；
proc R;
…
end R;
proc Q;
…
end Q;
在采用栈式动态分配时，因每进入一个过程就为该过程或函数分配存储空间。则图（ a）表示主程序中调用了 R；在
R中又调用了 Q的存储结构。图（ b）表示在 Q中又调用了 Q
的存储结构。图（ c）表示在 Q退出，又调用了 R的存储结构。
图（ d）表示在 R退出的存储结构。图（ e）表示在 Q退出的存储结构。图（ f）表示在 R退出的存储结构。
经过讨论了栈的存储分配，还要考虑过程式或函数调用和返回需完成的工作。前面第六章说过过程调用的四元式序列是：
par T1
par T2
par T3
…
par Tn
call P,n
现考虑四元式 par和 call是如何执行的，也就是 par和 call
要完成怎样的工作。对于每个 par Ti 需产生把参数填入活动记录的指令。由于 SP、返回地址、参数个数和程序状态字的所需的字节数对于某个过程来说是不变的且可以计算出的，
因此，每个参数存放的地址（相对于 SP的地址）也是可以计算出的,设其和为 m，则对于 par Ti可翻译成类似于如下指令：
[TOP+ i+m]:= Ti
这里 TOP为老的 TOP，每个参数均只占一个单元,Ti为参数的值或参数的地址。
四元式 call P,n应翻译成：
[TOP+1],= SP /*保护现行的 SP*/
[TOP+i+1],=当前寄存器值 /*保护现场 */
…
[TOP+m-1],=n /*保存参数个数 */
call P
进入过程 P后，应赋新的 SP，保护返回地址（返回地址也可以由指令 call P保存系统的栈中），定义新的 TOP值。
即执行指令：
SP:= TOP+1
[SP+1],=返回地址
TOP,=TOP+L /*L为 P过程所需的单元数 */
当执行到过程、函数的返回语句或过程、函数中的语句全部被执行完毕应返回调用者。其工作为计算出内存出栈后的 TOP、将复原老的 SP，对于函数还应将函数值存放到指定的连接单元中，然后执行返子指令：
TOP:= SP -1
SP:= [SP+0]
/*如返回的是函数则执行一条将函数值保存到指定单元或寄存中 */
RET /*返回调用程序 */
在这里 SP,TOP、参数等均只占一个单元，若它们占用不等长的单元在编译中也是可以计算出的，其实现方法类似。
b)堆式动态存储分配当一种程序设计语言允许用类似于 Pascal中 new和 dispose语句申请和释放内存，则不能用栈式存储分配，这因为其申请和释放的次序不满足先进后出的条件。这种数据只能借助于一种称为堆式动态存储分配的方法来实现。假定程序运行时有一个较大的存储空间，当用户申请堆内存时，就分配一块，
不用时返回。由于分配和返回的时间没有规律可循。当程序运行一段时间后，原来一块较大的存储空间很可能分成很多很多块。然而当需要长度为 N的存储空间只能寻找比 N大或相等的内存块分配，以此往复。最后在存储器池中出现了很多碎片。这些碎片就很难再为程序其它部分所用。为了解决碎片问题，一种方法是通过移动将碎片合并在一起，但这种方法是低效的，移动需化费很多机时。另一种方法是将原较大的存储空间分成若干等长的块，申请时分配以块为单位不足一块的长度也分配一块，返回时则必定也是以块为单位的。
这样解决了碎片问题，即外零头问题。但以块为单位分配浪费了块内的存储空间，也就是生成了内零头。这种方法虽然在分配时没有完全利用全部存储空间，但提高了系统的效率。
由于操作系统也需要管理内存，在编译实现时直接可以利用操作系统的内存管理，即需要内存时，向操作系统申请内存，
释放时直接将内存返回操作系统。
7.2.2 嵌套结构的内存分配前面介绍的栈式动态存储分配，每个过程或函数只能使用局部变量不能使用非局部变量，这与 Pascal语言结构的特点是不同的。 Pascal允许过程嵌套定义，也就是在过程或函数内需要使用非局部变量。下面是有嵌套过的 Pascal程序。
program sort(input,output);
var a:array[1..10] of integer;
x:integer;
procedure readarray;
var …a… end{readarray}
procedure exchange(i,j:integer);
begin
x:=a[i]; a[i]:=a[j]; a[j]:=x
end{exchange}
procedure quicksort(m,n:integer);
var k,v:integer;
function partition(y,z:integer):integer;
var i,j:integer;
begin
…a…
…v…
exchange(i,j);…
end{partition};
begin…end{quicksort};
begin…end{sort}
为了处理一致性，把主程序 sort看作最外层过程。这样过程说明的嵌套情况为：
sort
readarray
exchange
quicksort
partition
虽然在过程 readarray,exchange,partition引变量 a，
但该变量却为主程序中的 a。在过程 exchange中还引用了主程序中的 x。下面要解决如何调用外层中的变量。
在这里介绍静态作用域，动态作用域的调用方式可参照此方法稍作修改，也能完成。从上图中可以看出，无论是静态作用域还是动态作用域当内层过程需调用外层变量时，其外层过程的活动记录必然在栈中。要调用外层变量只要在内层过程中指出外层变量的活动记录的位置（ SP）值，再根据由符号表中指出的外层变量的相对位置就可以得到该外层变量的地址。
方法一：在活动记录中增加区头向量考虑程序的执行次序为：
sort→quicksort→quicksort→partition→exchange
对于 exchange可能用到的外层变量为 sort的变量；对于
partition可能用到的外层变量为 quicksort 和 sort的变量。以
sort标记为 0层；
readarray,exchange、
quicksort标记为 1层；
partition标记为 2层，则第 i层过程中除了能调用本层变量外，还能调用第 0层至第 i-1
层的外层变量。把从第 0层至第 i层活动记录的地址存放在一起组成了区头向量，如图所示。
当 sort调用 quicksort时,quicksort的区头向量为 sort的区头向量和 quicksort活动记录的地址。对于 quicksort调用
quicksort时，不能用前面一个 quicksort的区头向量再加上本层活动记录的地址，发现 quicksort和 quicksort是并列的，也就是层数相同的，因此允许调用的外层变量是相同的，故可从前面的 quicksort中拷贝层数个地址再加上本层活动记录的地址组成新的区头向量。类似地,partition从第 2个 quicksort
过程中拷贝层数个地址再加上本层活动记录地址组成新的区头向量。 exchange从 partition过程中拷贝层数个地址再加上本层活动记录地址组成新的区头向量。
设有图嵌套调用的情形，下面分另讨论不同之处调用 Pi的区头向量的构造情况。
在 Pi中调用 Pi，则从 P0~Pi-1均是 Pi可以调用的，因此从上一层 Pi的区头向量中拷贝 P0~Pi-1的地址，加上 Pi活动记录的地址组成新的区头向量。在 Pi+1中调用 Pi，则从 P0~Pi-1均是 Pi可以调用的，而 Pi 和 Pi+1不是 Pi的外层不要间接调用或不能调用，因此从上一层 Pi+1的区头向量中拷贝 P0~Pi-1
的地址，加上 Pi活动记录的地址组成新的区头向量。同理，在 P’i+1中调用 Pi，拷贝
P0~Pi-1的地址加上 Pi活动记录的地址组成新的区头向量。最后讨论在 Pi+2中调用 Pi，
则仍然是从 P0~Pi-1均是 Pi的外层，而 Pi,
P’i+1和 Pi+2不是 Pi的外层，因此从上一层
Pi+2的区头向量中拷贝 P0~Pi-1的地址，加上 Pi活动记录的地址也就组成了所需的区头向量。
综上所述，对于调用第 i层的过程只要从前面调用者中拷贝 0~i-1个地址，加上本数据区的地址组成新的区头向量。这样要在活动记录中增加称之为区头向量的部分，
如图所示。
每个过程的 d值和过程的层数 l在编译时都是可以计算出来的，则四元式 call P,n应翻译成：
[TOP+1],= SP /*保护现行的 SP*/
[TOP+i+1],=当前寄存器值 /*保护现场 */
…
[TOP+m-1],=n /*保存参数个数 */
从调用者的区头向量中拷贝 l个单元至进入过程的区头向量中；将 TOP+1即新的 SP放入区头向量的最后单元，组成新的区头向量。
call P
设访问外层变量的层数为 li，则访问外层变量的语句翻译成：
x:=SP[ li+d]
或 SP[ li+d]:=x
的指令。
图表示执行次序为
sort→quicksort→quicksort→partition→exchange的区头向量变化图。
方法二：在活动记录中增加访问链在过程的活动记录中增加一个称为访问链的的指针，当过程 q
在源程序中嵌套 p中，则将 q中访问链直接指向 p。那么执行次序为：
sort→quicksort→quicksort→partition→exchange
具有访问链的存储器栈变化图，如上所示。
下面需解决二个问题：
(1) 如何建立访问链
(2) 怎样根据访问链获得外层变量建立访问链也就是在运行时能求过程说明的直接外层。
由于主程序没有外层，故编译程序需为进入主程序时，生成置主程序的访问链为空指令。下面讨论执行中过程 R（可能为主程序）调用过程 S时，怎样求出 S的访问链。在编译时 R
和 S的层数都是可以求出分别记为 lR和 lS。 R可以调用 S，则 S
在 R的作用域内，可得 lS≤lR+1。当 lS = lR+1时，则 S是在 R内说明的，也就是 S是 R的直接外层，只要生成将 S的访问链置为指向 R的 SP（或 R的访问链）的指令。
当 lS = lR时，则 S和 R是并列的它们具有相同的直接外层，
也就是 R的外层也就是 S的外层，只要生成将 R的访问链赋给
S的访问链的指令即可。 lS<lR时,S的直接外层必然在栈中，
即 R必然被 S的直接外层直接或间接调用，否则 S不在作用域内。因此，只要对访问链向前搜索 lR - lS层，即可得到 S的直接外层。编译程序生对访问链向前搜索 lR - lS层的指令和将也为第 lS的访问链赋给 S的访问链。如 R的层数为 5,S的层数为
2，则向前搜索 3级求得层数也为 2的活动记录，它的访问链即为 S的访问链。
获得外层变量的方法与上述类似。设有 p过程中访问了变量 a，那么 p过程的层数记为 lp，变量 a层数记为 la，只要向前搜索 la - lp层,就可得到变量 a所在的活动记录中，由于 a的相对位置在编译中也是在符号表中可以查到的，故能生成对变量 a访问的指令。
分程序内含有数据说明语句起源于 Algol，但 C语言中延用此概念,C语言的分程序的语法为
{说明 语句 }
也就是在 C语言中的复合语句中，允许说明变量。而且在分程序的语句中还可以再有说明。这种具有嵌套性的分程序称为分程序结构。一个分程序结构的语言的说明作用域遵循最近嵌套原则：
(1) 一个分程序 B中说明的作用域包括 B，除了在 B内的分程序重新说明
(2) 如果名字 x不在 B中说明，则 x是最靠近且 B有说明 x的分程序说明的 x
设有程序段：
main()
{ /*分程序 B0开始 */
int a=0;
int b=0;
{ /*分程序 B1开始 */
int b=1;
{ /*分程序 B2开始 */
int a=2;
printf(“%d,%d\n”,a,b);
} /*分程序 B2结束 */
{ /*分程序 B3开始 */
int b=3;
printf(““%d,%d\n”,a,b);
} /*分程序 B3结束 */
printf(““%d,%d\n”,a,b);
} /*分程序 B1结束 */
printf(““%d,%d\n”,a,b);
} /*分程序 B0结束 */
则在 B0中说明的 int a=0的作用域为 B0- B2；在 B0中说明的 int
b=0的作用域为 B0- B1；在 B1中说明的 int b=1的作用域为 B1-
B3；在 B2中说明的 int a=2的作用域为 B2；在 B3中说明的 int
b=3的作用域为 B3。其变量标分别记为,a0,b0,b1,a2,b3。
分程序结构也可以用栈式存储分配来实现。因为每个变量作用域也符合先进后出的特点。解决分程序逻辑结构的存储分配，可采用下列二种方法。一是把分看成一个无参过程，
用上述过程嵌套的方法来解决。这种过程的特点是只说明一次，也只使用一次，它在分程序前调用，在分程序结束退出，
调用外即为说明之处。二是把一个过程体中所需的存储一次全部分配好。由于 B2中说明的 a和 B3中说明的 b的作用域不相交，故可分同一块存储空间，如下图所示。
在动态作用域中，进入新的过程时仅当新过程中说明了同名变量时，解释为新的存储。解决动态作用的方法也有二种，
一是所谓深访问，它在活动记录中存放一个控制链指向上一级调用过程，也可利用 SP指针。当发现非局部变量时从控制链一级一级向前搜索，直至搜索到为止，这种搜索可能深入栈中，因此而得名。搜索的深度取决于程序的运行，而编译时不能决定的。另一种所谓浅访问，它采用体外循环的方法，
为每个同名变量的名字分配静态的数据空间，当进入有同名变量的过程时将静态区的同名变量值保存到过程的同名变量的位置上，在过程的整个运行过程中，使用静态区同名变量，
过程结束后将先前保存在过程内的变量恢复。两种方法各有优缺点。深访问访问非局部变量是需较长的时间，但它不需要额外的开销。而浅访问可以直接访问非局部变量，但需要一些辅助的时间和空间来维护。
7.2.3 数组的分配和访问由于静态数组所需空间的大小是在编译时可以计算出来的，因此可在嵌套结构的栈式存储分配中只要为每个数组分直接分配相应的存储空间。下标变量的访问无论是本层变量还是外层变量都可以用前面介绍过的方法翻译成通过基址 SP
和相对位置访问下标变量的值。
动态数组的所需的空间在运行时才能确定，这样动态数组的存储空间也只能在运行时分配。前面说过编译程序需为内情向量分配了存储空间，然后生成填写内情向量的指令。
下面讨论动态数组的空间存放在何处。一种方法是将动态数组的空间存放在堆内存中，此时可以生成为动态数组申请堆存储的指令，并将首地址也填入内情向量中。当访问下标变量时，则编译程序可以生成要根据下标变量的下标和数组的内情向量求出数组元素在堆中的存储位置。
另外，应该注意在过程结束时，还需生成一条将堆内存返回的指令，不然会造成存储器的泄漏。严重时还会造成系统瘫痪。另一种方法也将动态数组的存储空间分配在栈中。当进入嵌套过程时，其活动记录的状态如图 (a)所示。此时应填写动态数组的内情向量,TOP+1作为第一个动态数组的首地址。此时该动态数组所需的存储空间可以计算出来了，可在栈顶分配该动态数组的存储空间。并将栈指针指向新的栈顶。
如有二个或二个以上的动态数组，则继续为每个动态数组分配内存。以次类推，最后栈指针指向如图 (b)中的 TOP位置。
此方法当过程退出时，则不必生成返回内存的指令，这是因为退出过程时 TOP赋的是 SP-1,SP赋的是过程中保存的老的 SP，指向调用者的活动记录。达到将动态数组分配的内存和原来的活动记录一起返回给栈。
7.3 代码优化作为一个高级语言的使用者很希望编译程序所产生的代码能够和直接用机器语言编写的程序的效果一样好。但事实上很难做到这一点，即使能做到这一点，也许所需化费实现优化的时间和空间比优化所得到的节省的时间多得多。在这里介绍的代码优化是指对原代码进行变换，从而获得时间和空间效率相对高的程序，而不一定且一般也不是时间和空间最省的程序。在进行优化时应做到：
(1) 代码的变换必须保持原程序的语义
(2) 从理论上，变换加快了程序的速度
(3) 这种变换是值得的如果一种所谓的优化改变了原程序的语义 —— 实际上产生了一个错误程序，这种变换也是无效的。尽管在优化后可能对于一些程序反而比原来增加了开销，但总体来说是节省的，而且节省应达到一个可度量的值，不然优化中的损失不可能在运行中弥补。由于各个机器的指令系统是不同的，即使是相同的四元式程序所生成的“最优”的代码也是不同的,
其优化算法也可能是不同的。为了算法的一致性在这里仅讨论与目标机器无关的优化算法。
一个程序的优化是由下面两个阶段构成的：
(1) 局部优化：应用于仅包括少量语句的小程序的优化变换。
(2) 全局优化：应用于一个程序单元，如一个函数或一个过程的优化变换。
7.3.1 优化变换程序的执行效率是可以通过地编译期优化变换是重写程序段以提高程序的工作效率而不改变语义。虽然变换的方法很多但常用的大致有下列几种：
1,编译求值一般来说程序的目标代码可能要运行多次，而编译只编译一次。如果一些原属于执行时完成的工作能在编译时解决，
则提前完成这些工作。如在计算 sin(3.1415927/6)时，
3.1415927/6的值在编译时可以计算的，其值为
0.523598783，运行时只要执行 sin(0.523598783)。因此程序的执行效率是可以通过地编译期间完成程序中的执行语义来提高的。这时编译程序消除了程序在执行时的需求，从而达到减少程序的执行时间、提高程序的工作效率。编译时的求值却体现了这一点。
2,合并运算设有程序段：
x:=a+b+c+d;
if a+b>0 then …;
y:=(a+b)*(b+c)+d;
则子表达式 a+b在不同的表达式中均使用过，因此只要计算一次 a+b的值，其余的值就可以使用该临时变量的值。
而将其它公共子表达式删除。
实现这种优化过程首先要识别产生相同值的表达式，在这里 a和 b都有没有重新被定值，故子表达式相同即为值相同。
其次计算相同的子表达式，用已存放在临时变量的值逐个代替试写出算术表达式。
表达式的等价可以考虑它们的运算对象是否程序所在位置处于相同的值。如一般情况下 a+b值和 b+a的值是等价的,
还有执行过 c:=b后,a*b和 a*c是等价的。实现这种“代数等价”，虽然提高了优化的效率，但同时也增加了优化的花费。
例,写出算术表达式 a+b*c-(c*b+a-c)/(b*c+d)优化后的四元式
（ 1）（ *,b,c,t1）
（ 2）（ +,a,t1,t2）
（ 3）（ -,t2,c,t3）
（ 4）（ +,t1,d,t4）
（ 5）（ /,t3,t4,t5）
（ 6）（ -,t2,t5,t6）
3,删除死码如果能在程序中删除其代码而不影响程序的运行结果的代码被称为“死码”，“死码”可以通过程序的控制流来获得，如条件语句：
if x>3 then
if x<3 then begin x:=x+1; y:=y*x end
else
x:=y*y
else
y:=25*x
此时可以从检查控制流发现代码 x:=x+1; y:=y*x无论何种情况总是不可能被执行。因此这一段代码可以被删除。另外，
设有一个赋值语句 x:=<表达式 >，而 x在程序的其它处从未被引用过，显然 x:=<表达式 >也为“死码”。删除这种“死码”
时应注意，只有当 <表达式 >的执行不会产生副作用时可以删除，也就是它不包含函数或过程，即使含有函数但没有函数的副作用，才能删除它。
4,减少频率减少频率是指程序中执行频率高的程序段移至程序执行频率低的程序部分中。其主要变换有相对循环不变量的内码外提。如程序段：
for i:=1 to 1000 do
begin
x:=1;
y:=5*x;
z:=y+i
end
此时循环体内的语句 x:=1和 y:=5*x;需执行 1000次，且它们相对于循环变量 i来说是不变的，因此将它们提出循环，置循环体外。即为：
x:=1;
y:=5*x;
for i:=1 to 1000 do
z:=y+i
这样对于语句 x:=1和 y:=5*x仅执行一次。
例,设有循环语句
c:=0;
FOR i:=1 TO n DO
BEGIN
a:=x*y;
b:=m*m;
c:=c+b*b
END
试写循环外提后的四元式序列。
根据题意，可写出循环语句的四元式序列为：
（ 1）（,= 0,_,c）
（ 2）（,= 1,_,i）
（ 3）（ jl,n,i,14）
（ 4）（ *,x,y,t1）
（ 5）（,=,t1,_,a）
（ 6）（ *,m,m,t2）
（ 7）（,=,t2,_,b）
（ 8）（ *,b,b,t3）
（ 9）（ +,c,t3,t4）
（ 10）（,=,t4,_,c）
（ 11）（ +,i,1,t5）
（ 12）（,=,t5,_,i）
（ 13）（ jmp,_,_,3）
由于 a:=x*y是循环不变运算，则可外提。 b2与 c之和虽然赋给了 c，但 b本身对于循环变量来说也是不变的，故也可以外提。其外提后生成的四元式如下：
（ 1）（,= 0,_,c）
（ 2）（,= 1,_,i）
（ 3）（ *,x,y,t1）
（ 4）（,=,t1,_,a）
（ 5）（ *,m,m,t2）
（ 6）（,=,t2,_,b）
（ 7）（ *,b,b,t3）
（ 8）（ jl,n,i,14）
（ 9）（ +,c,t3,t4）
（ 10）（,=,t4,_,c）
（ 11）（ +,i,1,t5）
（ 12）（,=,t5,_,i）
（ 13）（ jmp,_,_,8）
5,强度削弱和变换循环条件强度削弱是指用一个运算速度较快的运算符代替耗时较多的运算符，也就是将强度高的运算符削减为低强度的运算符。如,X 2写成 X*X,2*X写成 X+X。
在循环中的强度削弱方法为：
(1) 设循环变量为 i，对于循环体内的运算 L:=K*i+C可削弱为 T:=T+K
(2) 对临时变量 T赋初值 C
(3) 删除强度削弱后的无用变量例,设有循环语句
FOR i:=1 TO n DO
BEGIN
…
L:=K*i+C;
…
END
则削弱为：
T:=C;
FOR i:=1 TO n DO
BEGIN
…
T:=T+K
L:=T;
…
END
强度削弱对于程序循环中数组的访问是十分重要的，如在一个 Pascal循环中的数组引用 a[i,j]的地址，这样就造成了高强度的运算 i*n(按行存放 )，用上述方法就可以大地降低运算的强度。但需要注意的是这种方法不能适用于下标变量允许为实数（浮点数）类型，这是因为实数在累加时会产生积累误差，最后的 T中不是所需的 K*i+C。
设有循环语句,
for (i=1;i<=n;i++)
{t=4*i;
x=f(t);
…
}
由于在循环语句中 i和 t的关系始终保持 4倍的关系，而且循环内的其它部分也没有引用 i，则可将循环条件改变为
for (t=1;t<=4*n; t+=4)
这样经过变换后 i的值在循环内不再引用，故可在循环中删节除，从而达到优化的目的。
6,减少复写传播把形如 b:=a的赋值语句称为复写语句，简称复写。当
b:=a;c:=b时，只要 a在被新的赋值之后的程序不再引用 b，则可用 c:= a代替 c:=b。
【 例 7-10】 设有程序段
y:=x;z:=y;z:=y;
t1:=f(y);
t2:=g(z);
则改写为：
t1:=f(x);
t2:=g(x);
7.3.2 局部优化局部优化所需的化费相对较低，也就从优化所得到的收益也相对较低。局部优化顾名思义只是在较小的程序段中进行优化，从而达到优化的目的。这种程序段称为“基本块”。
定义 7.4 基本块是指程序中的一语句的顺序序列 (S1,S2,…,
Sn)，其中只有第一个语句 (S1)允许有是程序的控制语句转移的目的语句和最后一个语句 (Sn)允许是一个控制转移语句。
基本块划分算法：
(1) 求出称为入口的基本块的第一个语句，如：程序的第一个语句或有控制语句转入的语句。
(2) 对于每一入口语句构造其所属的基本块：
1)由入口语句到下一入口语句的前一语句
2)由入口语句到一转移语句
3)由入口语句到一停语句
(3) 对于未被划入任一基本块的语句，为通过任何基本块都不能到达该语句，故为无用语句应删除。
对于基本块内的公共子表达式的删除，可采用计算出每项个定值的四元式编号，当两个子表达式完全相同时，则它们具有相同的定值的四元式编号，表示在二个四元式之间没有新的定值。
为了简单起见。在基本块内将四元式编号以 1开始的连续号码编号。由于一个被定值的变号与被定值的变量有关，则在符号表中的每一变量增加一个称为定值编号的属性。设有
(n) A:=B op C，其中 n为对 A定值的四元式编号,B,C为变量,op为运算符。在符号表中需保存每个变量定值的位置 n，
对尚未定值的变量符号表中的定值编号的属性以 0表示。另外建立一四元式的符号表，为每个四元式的运算对象上都上都附加一个定值信息来指出该运算对象，这些信息也用四元式的编号表示。
再为每个四元式保存一个引用信息表示是否要为程序中的其它处引用而保留其值，其初值为 false。当设表达式 e是 e’
的子表达式，在翻译是时形成了关于 e的四元组时，其运算对象所关联的定值信息可从符号表中获得。将新产生的四元式和四元式符号表中现有的四元式比较，如果存在一个登记项为 k的与新的四元组完全匹配的四元式，则说明其值与新的表达式的值完全相同，也就是新的四元式不必存放在四元式符号表中，用四元式符号表 k的结果名代替 e’中的对象，
并对四元式 k的引用信息置为 true，以便决定该值是否保存到临时变量中。
例,设有基本块：
(:=,3.14,_,t1)
(*,2,t1,t2)
(*,x,y,t3)
(*,t1,t2,a)
(:=,a,_,b)
(*,2,t1,t4)
(*,x,y,t5)
(*,t4,t5,t6)
(*,x,y,t7)
(*,t6,t7,b)
其局部优化的过程为设所有变量的定值编号为 0，当四元式
(:=,3.14,_,t1),(*,2,t1,t2)和 (*,x,y,t3)进入时为图 (a)；
当四元式 (*,t1,t2,a)和 (:=,a,_,b)进入时，如图 (b)；
优化四元式 (*,2,t1,t4)时，在四元式表中查到匹配的四元式
(2)，故该四元不要入表，以后以 t2代替原来的 t4；同样四元式
(*,x,y,t5)只要用 t3代替 t5；则对于四元式 (*,t4,t5,t6)将改为
(*,t2,t3,t4)填表。四元式 (*,x,y,t7) 也能找到匹配的四元式，
则不要添加到表中；最后 (*,t6,t7,b)添入表中为 (*,t4,t3,b)，并将 t2 和 t3的引用信息改为 true,如图 (c)。
上述方法很容易地扩充到编译时的合并常量。对于语句
a:=n，其中 a为变量,n为常量。则在在常量表中加入常量 n，
其登记项为 k，并将定值位置 k与 a相关联用 -k表示。当生成一个四元组是，如果每个运算对象都是一个常量或是一个负的定值位置时，就可以实常量合并。
例,将上例中加入用合并常量算法加入用合并常量算法后其结果，如图所示。
7.3.3 全局优化要产生高效的代码，编译程序仅在基本块内优化是不够的。编译程序应把程序作为一整体来考虑，对各个基本块的信息进行数据流的分析从而达到优化的目的。全局优化和局部优化相比，全局优化需要更多的分析，以便确定优化的可行性。这里仅介绍全局子表达式的消除，包括公共表达式的消除和死代码的消除。
设有子表达式 α存在于程序的若干基本块中，记为 SB = {bi|bi
是基本块 }。设子表达式 α存在于程序的一组基本块中，且在某个 bk中存在对子表达式 α的求值。当程序的每次执行，都能满足下列两个条件，则在基本块 bi中子表达式 α是可以消除的。
(1) 基本块 bi只在已执行了一次或多次的某个 bk后执行。
(2) 在基本块 bk对 α的最后一次求值后，没有改变 α中的变量的值。
第一个条件保证了基本块 bi中的子表达式 α已被求值；第二个条件则保证了在基本块 bk求得 α的值和在基本块 bi求得 α
的值是等价的。如子表达式为 x*y，则不能改变变量 x或 y的值。
定义 7.5 程序流程图是一个三元组 G=(N,E,n0)，其中,N
为图的所有结点的集合也就是基本块的集合。 E表示图中的有向图中的边集，边 (bi,bj)它表示基本块 bi的最后一个语句转向基本块 bj的第一个语句。 n0表示程序的开始结点。
利用程序流程图分析基本块的控制和数据流的关系，实际上是分析基本块之间的关系是否满足上述二个条件。下面介绍一些基本概念：
(1) 前趋和后继：若 (bi,bj)∈ E，则称 bi是 bj的前趋,bj是 bi的后继。
(2) 路径：路径是从一个结点沿边序列到另一个结点的边的有序序列。
(3) 祖先和后代：若存在一条从 bi到 bj的路径，则称为 bi是 bj的祖先,bj是 bi的后代。
(4) 活跃变量：如果变量 a在一个基本块 bi的某个程序点 pi处定值，并在以后的程序中引用该值，则称变量 a是活跃的控制流分析是对一个程序进行分析以收集与程序结构相关的信息。数据流分析是对程序中使用的数据进行分析，以收集对优化有用的信息，能用来判断是否能对程序段进行优化。
定义 7.6
如果在基本块 bi包含一个对子表达式 α求值，且从求值之后不再包括对表达式中的运算对象的赋值，或子表达式 α在基本块是入口有效 bi不再包括对表达式中的运算对象的赋值称子表达式 α在基本块 bi出口有效的。
定义 7.7
对于基本块 bi的子表达式 α,如果它在流程图中的所有前趋的出口均是有效的，则子表达式 α在基本块 bi的入口是有效的。
由于表达式的出口有效性和入口有效性的定义是递归的，
也就是出口有效性是由入口有效性的来保证的，入口有效性是由出口有效性来保证的。因此有效表达式的概念是一个全路径的概念。为此对于全局优化需分析每个基本块的子表达式的有效性。设布尔变量 A_ini 和 A_outi分别表示表达式 α在基本块 bi的入口和出口的有效性； Evali当且仅当表达式 α在基本块 bi中求值为 true，否则为 false。 Emodifyi当且仅当表达式
α的某个运算对象在基本块 bi中被修改为 true，否则为 false。
这样每个基本块的入口有效性和出口有效性可用下列方程计算：
A_ini= A_outk1∧ A_outk2∧ A_outk3…… ∧ A_outkn (其中：
bj是 bi的前趋,j= k1,k2,k3……,kn)
A_outi= ~ Emodifyi∧ (Evali∨ A_ini)
消除全局性的子表达式 α的算法：
(1) 对于基本块 n0置 A_in0为 false，其它 N -n0中的基本块的
A_ini为 true。任意 A_outi为 true。
(2) 对 N中的每个基本块，做入口有效性和出口有效性计算，
直至每个基本块的任何有效性不再改变为止。
(3) 对满足 A_ini为 true且在基本块 bi中的 α求值前其任何运算对象不能被赋值，用代表表达式 α的临时变量代替 α。
例,设有程序流程图如图（ a）试用消除全局性的子表达式的算法，消除其公共子表达式。
由于四元式（ 1）和四元式（ 2）的表达式均为常量故不必优化。对于四元式（ 3）中的表达式 D+D进行优化。 D+D
对于基本块 B1,B2,B3,B4,B5,B6的 A_in1~A_ in6的初始值分别为,false,true,true,true,true,true。
A_out1~A_ out6均为 true。由于在基本块 B1中，对 D求值。故
Eval1为 true，而 D在中没有被修改 Emodify1为 false。这 样
A_out1仍为 true。由于 B1和 B5的 A_out1和 A_ out5均为 true，
故 B2的 A_in2仍为 true，由于表达式 D+D的二个运算分量 D均没有被赋值，也没有改变其值，则 A_ out2也为 true。同理基本块 B3,B4的 A_in3,A_in4,A_out3和 A_ out4均为 true。在基本块 B5中 D被修改,Emodify5为 true，故 A_ out5为 false。
此时 A_in2为 false，至此重复计算 B3,B4,B5 的 A_in、
A_out3均没有改变,B6的 A_ in6为 false则 B6的 A_ out6也为
false。这样任何基本块的任何有效性不再改变。故可用临时变量 t1来代替基本块 B5中的 D+D。以同样的方法考察对表达式 B+C的优化。对于基本块 B1,B2,B3,B4,B5,B6的
A_in1~A_ in6的初始值分别为,false,true,true,true、
true,true。 A_out1~A_ out6均为 true。求得 B2的 A_in2为
true,A_out2为 true。 B3的 A_in3为 true，由于 B3修改了变量
B的值，故 Emodify3为 true,因而 A_out3为 false 。
而 B4的 A_in4和 A_out4均为
true。 B5 的 A_in5为 false，而
B+C在 B5中求过值故 A_out5
为 true。 B6的 A_in6和 A_out6
均为 true。至此任何基本块的任何有效性不再改变。故可用临时变量 t2来代替基本块
B3 和 B4的表达式 B+C，但不能代替基本块 B5中的 B+C，
这因为 B5的 A_in5为 false。消除公共子表达式的如图 (b)
需要指出的是这种算法只能适用于基本块外的公共子表达式的删除，而不能用于基本块内的公共子表达式的删除。因此一般情况下应先用局部的公共子表达式的消除算法消除基本块内的公共子表达式，然后再用全局优化的算法消除基本块外的公共子表达式。
一个变量的活跃性可以根据下面的方法确定：
(1) 变量 a如果满足基本块的 bi中包含一个对 a的使用，且在 bi的祖先基本块中存在对 a的赋值，或者 a在 bi的出口是活跃的且中不再包含对 a的赋值则基本块 bi的入口处是活跃的。
(2) 如果 a在程序流图中 bi的某个的后继入口是活跃的，则
a在 bi的出口处是活跃的。
变量活跃的概念也是一个全局的概念。定义与活跃变量有关的布尔变量如 live_ini为 true表示变量 a在基本块的 bi入口是活跃的； live_outi为 true表示变量 a在基本块的 bi出口是活跃的； Refi为 true表示变量 a在基本块 bi内引用且在引用之前没有被赋值。 Defi为 true表示变量 a在基本块 bi内被赋值。
这样每个变量的活跃性可用下列方程计算：
live_ini= ~ Defi∧ (Refi∨ live_outi)
live_outi= live_ink1∨ live_intk2∨ live_ink3…… ∨ live_intkn
(其中,bj是 bi的后继,j= k1,k2,k3……,kn)
由于活跃变量的有效性是由下一个基本块向前一个基本块传递的。因此计算变量 a的活跃性算法如下：
(1) 对于程序流程图中的最后一个基本块 m置 live_outm为
false，其它 N -nm中的基本块的 live_outi为 true。任意 live_ini
为 false。
(2) 对 N中的每个基本块，做活跃入口有效性和活跃出口有效性计算，直至每个基本块的任何有效性不再改变为止。
(3) 删除变量在不活跃的基本块中的赋值。
考虑上图中变量 F，由 B6的出口是不活跃的求得它的入口也是不活跃的；再求得 B5的出口是不活跃的，那么 B5的入口也是不活跃的。同理求得 B3,B4的出口也是不活跃的。由于
Def3和 Def4为 true，根据方程式 live_ini= ~ Defi
(Refi∨ live_outi )求出 live_in3和 live_in4也是不活跃的。进而求得在基本块 B1,B2的入口和出口都是不活跃的。且重复完成求各活跃性时没有改变任何值，所有属性即为所求。最后删除变量在 B3,B4中的赋值即四元式（ 7）和四元式（ 9）。
同理考虑变量 G的活跃性,四元式（ 2）和四元式（ 10）也应删除
7.4 赋值语句、输入和输出语句的编译前面第一章中已经介绍了编译程序的作用是将源程序翻译成可运行的目标程序。通过语法制导翻译可以将源程序翻译成中间代码，在本节中主要讨论四元式翻译成目标代码需解决的问题。另外也可以在制导翻译中直接产生汇编代码，
但也同样需考虑如怎样充分利用寄存器，如何使生成的代码较短等问题。虽然由于目标机器的不同其指令结构、指令格式、字长和寄存器的个数和种类均有所不同，但其翻译的方法和原理是基本相同的。下面以 IBM-PC机 Intel 8088处理器作为目标机器，以记忆方便用汇编语言的符号指令作为目标机器语言的指令。
7.4.1 赋值语句的代码生成器代码生成器是把经过语法分析或优化后的中间代码作为输入，将它们翻译成特定的目标机器的语言或相应的汇编语言作为输出。赋值语句的代码生成器介绍与赋值语句有关的表达式的代码生成和赋值时的类型转换的代码生成。
代码生成器需要考虑二个问题，一是如何使生成的目标代码较短，另一是如何充分利用寄存器。生成的目标代码较短可以减少 CPU存取指令的时间同时也压缩了程序的存储空间。
由于数据在寄存器中运算的速度要比在存储器中运算的速度快，在生成的代码中如将以后需要继续引用的数据存放在寄存器中，也可以减少访问存储器的次数，从而达到目标程序运行的效率较高。
为了简单起见,这里只考虑在基本块内充分利用寄存器,设翻译四元式 A:=B op C时,需要确定变量 A,B,C变量在基本块内是否被其它四元式所引用，并确定在哪些四元式引用。
由于该四元式是对变量 A的定值，故应对 A的引用信息符加到该条四元式上。另外从变量 A出了基本块的是否活跃的活跃信息也决定了变量的值出了基本块是否要保存。为此对每个四元式在基本块中建立引用信息链和活跃变量链。这样在符号表中需增加引用信息栏外和一个活跃信息栏。求基本块内的引用信息可以从基本块的出口从后向前反向扫描基本块内的四元式，从而建立引用信息链和活跃信息链。如果对程序流程式做过全局的数据流分析，已计算出每个变量的活跃性，
则使用这些变量的活跃性；如没有做过全局的数据流分析，
那么没有做过全局的优化，此时临时变量出了基本块不会有引用，则认为临时变量出了基本块是不活跃的，而所有非临时变量出了基本块是活跃的。
计算引用信息链和活跃信息链算法：
(1) 对基本块中的每个变量在符号表中的引用信息栏置为
false用 0表示，并根据该变量出了基本块是否是活跃的置活跃信息为 true或 false。
(2) 从基本块出口到基本块入口由后向前处理各四元式。对于每个形如 (n) A:=B op C的四元式，依次完成下列步骤：
a) 把符号表中变量 A的引用信息和活跃信息拷贝到四元式 (n)的相应的属性上；
b) 把符号表中 A的引用信息和活跃信息置为 0和 false；
c) 把符号表中变量 B和 C的引用信息和息和活跃信息拷贝到四元式 (n)的相应的属性上；
d) 把符号表中 B和 C引用信息置为 n和活跃信息置为 true；
步骤 1,2说明了由于对变量 A赋值，此时四元式 (n)的引用信息和活跃信息却在符号表中，并再向前扫描是不能引用到第
(n)条四元式对 A的赋值。步骤 3,4说明了 B,C的引用信息位置已找到，故应复制其信息。注意上述四个步骤次序不能颠倒，因为变量 A和变量 B或 C有可能为同一变量。
例,设有如下基本块，其中 A,B,C,D为变量,t1,t2,t3为临时变量。
t1:=A+B
t2:=A*C
t3:= t1+ t2
D:=t3/ t2
如图 (a)为符号表和四元式表的初始值，图 (b)为四元式 (1)、
(2),(3),(4)从后向前分析后的结果。
要生成目标代码还要考虑如何充分利用寄存器的问题。为此需记录寄存器的使用情况，对于 Intel 8088 CPU中的每个寄存器用 REGISTER集合表示该寄存器中的现行值，如：
REGISTER(AX)={A,C}表示寄存器 AX中的现行值是 A,C；但由于在 Intel 8088中还允许用寄存器 AL和 AH则应允许用
REGISTER(AL)=… 和 REGISTER(AH)=… 。另外，要判断是否生成将寄存器中的数值保存到存储器的指令，用
VARIABLE(A)={AX,M}表示变量 A的值既在寄存器 AX中，又在存储器中。
根据上述描述，可给出代码生成算法：
(1) 对每个四元式 (n) A:=B op C依次执行下述步骤：
以四元式 (n) A:=B op C为参数，调用函数过 GETREG（ (n)
A:=B op C）当从 GETREG返回时，得到一个寄存器或寄存器对用 R表示，将它们存放现行变量 A的值；
(2) 利用变量描述集合 VARIABLE(B)和 VARIABLE(C)确定现行变量 B和 C的存放位置，设其存入位置为 Baddr和 Caddr。
若 VARIABLE(B)和 VARIABLE(C)中存在寄存器则 Baddr和
Caddr分别取作 VARIABLE(B)和 VARIABLE(C)中的寄存器；
(3) 如果 Baddr≠R，则根据变量 B的类型分别生成 MOV R,
byte PTR Baddr或 MOV R,word PTR Baddr和 op R,
Caddr，对于寄存器对 R和 R’，则要生成指令 MOV R,word
PTR Baddr,MOV R’,word PTR Baddr+2,op R,Caddr
和 op R’,Caddr（其中 R和 R’组成寄存器对，如 dx,ax寄存器对）
否则生成目标代码 op R,Caddr或 op R,Caddr和 op’ R’,
Caddr(op’为带进位的 op运算 )
如果 Baddr和 Caddr为 R或 R和 R’则删除 VARIABLE(B)和
VARIABLE(C)中的 R或 R和 R’；
(4) 令 VARIABLE(A)={R}或 VARIABLE(A)={R,R’}，并置
REGISTER[R]=A或 REGISTER[R]=A和 REGISTER[R’]=A，
以表示变量 A的值仅在寄存器或寄存器对中；
(5) 从四元式中的引用信息和活跃信息可知，若变量 B或 C在基本块中不再被引用，且它占用了寄存器或寄存器对，则从
REGISTER[R]和 REGISTER[R’]中删除其占用的寄存器或寄存器对。
注意，在具体实现中对于一些运算符没有单条指令实现其运算，可以编写相应的子程序来计算或用几条指令代替。
GETREG（）是一个函数过程，其结果是申请一个寄存器或寄存器对来存放结果的值。其算法如下：
（ 1）如果 B的现行值在某个寄存器或寄存器对中，而该寄存器或寄存器对中没有其变量，另外 B和 A为同一标识符，或者
B的现行值在执行该四元式后不会再被引用。则选取该寄存器或寄存器对作为 R或 R和 R’，返回；
（ 2）如果有可以满足相应运算的寄存器或寄存器对则从中选取一个或一对作用 R或 R和 R’,返回；
（ 3） 不满足上两个条件则必须从已分配的寄存器中选取，
但在选取过程中应首先满足占用寄存器的变量在内存中同时有值，其次是在基本块的很后面才能用到，这一点可以通过四元式表上的引用信息获得。对于选中的寄存器或寄存器对，
则对于 REGISTER[R]或 REGISTER[R]和 REGISTER[R’]中的每个变量 M，若 M不是 A则，或者 M既是 A又是 C，但不是 B且
B不在 R或 R和 R’中，则：
a)若 M不在存储器中，需生成将 M保存到存储器中的指令；
b)如果 M是 B，或 M是 C但同时 B也在 REGISTER[R]或
REGISTER[R]和 REGISTER[R’]中，则令 VARIABLE(M)={M，
R}或 VARIABLE(A)={R,R’,M}，否则令 VARIABLE(M)={M}
c)删除 REGISTER[R]或 REGISTER[R]和 REGISTER[R’]
中的 M
7.4.2 输入、输出语句的代码生成器一个程序设计语言都离不开输入、输出语句。由于输入、
输出语句均要和外部设备交换信息。如何翻译这些输入、输出语句也就是要取决于这些外部设备。实现输入、输出语句的翻译可采用调用有关输入、输出子程序的方法。将有关输入、输出功能写成一系列子程序，其子程序的实现应尽可能地调用由系统提供的程序，如操作系统提供的 DOS功能调用，
从而避免过多的消耗精力在完成这些外部设备的驱动程序上。
定义 7.8 输入、输出语句是作用在外部设备上的语句集合。
设有 Pascal语句 read(x)在语法制导翻译中,根据变量 x的类型，已翻译成相应的四元式（ ini,_,_x）或（ inr,_,_x）。现在讨论如何将它们翻译成目标指令。对于四元式（ ini,_,_x）可生成一条子程序的调用指令 call readi。
其中 readi表示输入整型数子程序的入口,readi子程序首先执行输入的功能调用将用户输入的数据存放到内存的缓冲区中，
然后从缓冲区中逐个读入字符判别是否是数字，则拼写成相应的数值，若是将控制字符，如回车换行等则结束数值的输入。对于四元式（ inr,_,_x）同样生成一条子程序的调用指令
call readr，其功能也是将用户输入数据存入缓冲区中，并将其转达换成浮点格式，如四字节的浮点数前三个字节表示尾数，最后一个字节表示阶码。
输出语句的翻译与输入语句的翻译方法基本相同，其主要区别是一个是从缓冲区中读出数据，另一个是往缓冲区中写入数据。对于输出的四元式（ outi,_,_x）或（ outr,_,_x），也是翻译成一条转子指令。其子程序中首先析出输出数据的每一位数符可标点符号，同时将它们转换成相应的字符填入输出缓冲区。最后调用输出的功能调用，达到输出的目的。如果允许使用字符串的输入、输出则要求考虑输入输出缓冲区最大长度。
7.5 控制结构的编译在编译程序中，存在程序的控制权转移的问题。如何生成控制权转移的代码，也是编译程序需要考虑的问题。
7.5.1 控制转移定义 7.9 一个程序设计语言的控制结构就是在一个程序中决定控制的顺序的语句或指令集合。
一个程序设计语言的控制结构通常是由控制的转移、条件执行、循环控制和过程或函数调用组成的。
基本的控制结构的转移可以通过条件转移或无条件转移实现，
这些控制结构如：四元式 (jmp,_,_n),(jz,a,b,n),(jnz,a,b,n)、
(jg,a,b,n),(jl,a,b,n),(jle,a,b,n),(jge,a,b,n),(j,a,p,q),在编译程序中通常翻译成条件判断指令 jz,jnz,jg,jl,jle,jge
等到六条指令和无条件转移指令 JMP。考虑到指令 JZ,JNZ、
JG,JL,JLE,JGE等六条指令的转移范围为 -128~+127，
现给出控制结构的翻译算法。
根据基本块的划分算法，这些控制结构的四元式必定是基本块的最后一个语句。由 VARIABLE(a) 和 VARIABLE(b)求得当前变量 a和 b位置，记为 aaddr和 baddr。用
GETREG(op,a,b,n)申请寄存器，返回 R或 R和 R’。以 a和 b均不在寄存器中，为例，则根据 a和 b的类型及 n的位置生成指令为：
(1) a和 b为单字节，转移范围不超过 -128~+127则生成指令：
MOV R,byte PTR aaddr
CMP R,baddr
op n
转移范围超过 -128~+127则生成指令：
MOV R,byte PTR aaddr
CMP R,baddr
L
JMP n
L:
(2) a和 b为双字节，转移范围不超过 -128~+127则生成指令：
MOV R,word PTR aaddr
CMP R,baddr
op n
转移范围超过 -128~+127则生成指令：
MOV R,word PTR aaddr
CMP R,baddr
L
JMP n
L:
(3) a和 b为四字节（需保存在寄存器对中），转移范围不超过 -128~+127则生成指令：
MOV R’,word PTR aaddr+2
MOV R,word PTR aaddr
CMP R’,baddr+2
JNZ L1
CMP R,baddr
op n
JMP L2
L1,op n
JMP L2
L2:
转移范围超过 -128~+127则生成指令：
同上注意,op操作符和的关系是反向转移；当 a和 b有一个在寄存器中，则不必生成从内存中取数指令直接与 aaddr进行比较即可。另外对于判断转移是否在 -128~+127内，当向前转达移时，可利用为每个四元式填写分配运行时的相对地址计算相对差；对于向后转移，可采用所谓估算的方法，设计一个为每一种类型的四元式与最大字节数的对照表。以对照计算从转移源到转移目的的最大字节数代替转移字节数。
7.5.2 函数和过程的调用函数与过程序调用的场合有所不同，但其控制权的转移和返回都有是相同的。函数比过程多一个返回值。
翻译函数或过程时，编译程序应保证以下几点：
(1) 被调用的函数或过程能对实际参数进行访问，包括传值和传地址等各种参数。
(2) 控制可转移到被调用函数或过程，并能从被调用函数中返回。
(3) 若是函数应保证调用者能正确取到函数的返回值。
完成函数或过程代码生成需考虑函数或过程的调用规范、
参数传递的形式，如是否允许递归、参数是值传递还是地址传递或者是其它传递方式。
设函数或过程的调用已翻译成四元式序列：
par T1
par T2
par T3
…
par Tn
call P,n
前面已经说过对于每个四元式 par Ti 根据其参数的传递类型应产生填写相应活动记录的指令。设寄存器 SI存放的是
SP指针，寄存器 DI中存放的是 TOP指针，数据段和堆栈段为同一段。由于 SP、返回地址、参数个数和程序状态字等所需的字节数在前面翻译成四元式时都可以计算出来的。因此，
每个参数存放的地址（相对于 SP的地址）也是可以计算出的,
设其和为 m，则对于 par Ti可翻译成类似于如下指令：
MOV [DI+ i+m],Ti
四元式 call P,n应翻译成：
MOV [SI+2],DI /*保护现行的 SP*/
MOV [SI+4],AX /*保护现场 */
MOV [SI+6],BX
…
MOV [DI+m-1],n
call P
进入过程 P后，应赋新的 SP(SI)，保护返回地址（此时在调用 call P已保存栈中），定义新的 TOP值。即执行指令：
MOV SI,DI
INC SI
ADD DI,L /*L为 P过程所需的单元数 */
MOV SP,DI
当翻译到函数的返回值的语句时，如 PSACAL中的函数标识符,=表达式，或 C语言中的 return（表达式）语句对应的四元式时，生成指令 MOV R,ti。其中 R为函数返回约定的寄存器,ti存放返回值的表达式的临时变量。
翻译到过程或函数的返回语句或过程或函数中的语句全部被完毕，则应生成返回调用者的指令。其工作为计算出内存出栈后的 TOP、将复原老的 SP即生成指令：
MOV SI,DI
DEC SI
MOV SI,[SI]
RET L
在函数或过程体的语句翻译时还要注意，对外层变量的引用需生成先取该层变量的基址的指令，然后生成根据相对位移访问相应外层变量。
7.6 程序重定位概述编译程序生成的目标代码一般有三种形式：一是能立即执行的机器语言代码，所有地址均已定位；二是待装配的机器语言模块。这种模块需要执行时，由连接程序和其它模块连接起来，转换成能执行的机器语言代码；三是汇编语言代码，这种代码需用汇编程序汇编后转换成机器代码才能执行。
第一种所有地址是直接定位的，一般不能装入不同的内存执行。因此编译程序翻译成的目标代码，通常希望为可以装入不同内存的执行，也就是可以对目标程序进行重定位。
7.6.1 程序的重定位定义 7.10 当程序 P中包含任何绝对地址的指令，称为该程序是对地址是敏感的，其中绝对地址可以指令地址也可以数据地址。
定义 7.11 程序重定位是一种修正用于地址敏感指令中的地址的过程以便程序可以在指定的内存区域正确地执行。
地址的定位的时刻也有三种：编译时定位，连接时定位和装入时定位。为此给这三种翻译时刻，为：
翻译源：由翻译程序决定的源地址。地址由程序员在程序中用类似于 ORG伪操作完成的。
连接源：由连接程序在生成二进制程序时指定的源地址。
装入源：地装入一个执行程序时由装入程序指定的源地址。
如果连接源不同于翻译源则重定位应该是在连接时完成的。如果连接的地址和装入的地址不一致时，即连接源不同于装入源则重定位必须由装入程序完成。通常连接程序总是需要进行重定位，而装入程序则不一定进行重定位。如果程序的地址对于程序的不同执行可能是不同的，那么这种绝对装入方式在实际应用中是很不方便的。重定位装入程序在装入一个程序执行时将对该程序实施重新定位。这样就允许程序在内存的不同位置被执行。
例,设有程序
ORG 100
ARRAY DW 100 DUP (?)
VAR DW 4 (?)
JMP NEXT
…
NEXT
其中,ARRAY 为 100,VAR的地址为 300,NEXT的地址为 540则编译源为 100，当连接源为 500时，在连接时的重定位将敏感的地址 ARRAY的地址,VAR的地址和 NEXT的地址替换为 500,700,940，即每个敏感地址加上一个常量 400，
注意当连接源小于编译源时，其常量为负的。当连接源等于编译源时，其常量为 0。
7.6.2 连接如果编译程序的目标代码是可连接的程序模块，那么应了解程序的模块需提供连接程序的信息。
当一个程序分别编译时，产生若干个程序序列，在这些序列中存在一个指令序列中通过修改自已内部的指令修改地址而影响到其它序列中的程序或数据的地址。这种影响是相互影响的。因此对每个程序序列中需定义调用外部其它信息，
这些信息分为 PUBLIC和 EXTRN。用 PUBLIC说明的信息表示本程序序列中定义的信息是公用信息，可供其它模块使用。
用 EXTRN说明表示本程序序列中的那些信息是外部定义的。
连接程序需解决外部引用的问题，在应用程序被执行前需为每个被连接的模块给予正确的地址分配，避免模块间的地址冲突。对于外部说明的信息应在各模块间注意其一致性。在连接完成前，存在外部引用没有被解决，而一旦连接完成对于外部说明的信息在各模块间是一致性的，则所有外部引用都可以解决的。
连接的实质是若干个由二进制程序组成的一种机器语言，
重定位在连接源开始的内存区域中，并完成对每个外部引用的地址分配。连接提供了不同语言编写的程序组成一个应用程序的可能。
7.6.3 目标模块编译程序输出的目标语言，最常用的是目标模块。要使编译程序能生成这些模块也就要求编译程序的设计者了解目标模块的构造。
一个程序的目标模块包括了所有重定位和与其它程序连接的所需的所有信息。一个程序模块是由 4个部分组成的：
(1) 头文件：头文件包含了翻译源（用户定义的地址）、程序的大小 （占字节数）、程序执行的起始地址（程序的入口）。
(2) 程序：即与源程序对应的机器语言目标程序。
(3) 重定位表：重定位表的每个记录只有一个域，它记录了程序中的所有敏感指令的翻译地址。
(4) 链接表：这个表包括程序涉及的所有公共定义和外部引用。每个记录包括 3个域，它们是变量域、类型域和翻译地址。
其中：
a) 变量：变量名。
b) 类型,PUBLIC或 EXTRN表示公共定义或外部引用。
c) 翻译地址：对公共定义来说，这是分配给变量在内存中的首字节的地址。对外部变量，这是保存变量地址的内存地址。
例,设有汇编语言程序如下：
0000 subcode segment
00C8 ORG 200
PUBLIC _f
EXTRN
MAX:WORD,ALPHA:WORD
assume CS:subcode
00C8 _f PROC far
00C8 B8 0041 LOOP,mov ax,65
00CB 2E,A1 0000 E mov ax,ALPHA
00CF 2E,03 06 0000 E ADD ax,MAX
00D4 23 C0 AND AX,AX
00D6 75 F0 JNZ LOOP
00D8 CB ret
00D9 TOTAL DW?
_f ENDP
00DB subcode ends
end _f
则目标模块包括以下信息：
翻译源 =200，大小 13h，目标地址 =200
机器语言指令（在上面汇编语言左面的二进制指令）
重定位表和连接表名字 类型 属性
ALPHA V WORD 0000 SUBCODE
External
LOOP L NEAR 00C8 SUBCODE
MAX V WORD 0000 SUBCODE
External
TOTAL L WORD 00D9 SUBCODE
7.1 编译程序考虑的因素编译程序设计时，除了需用到前介绍的分析技术和制导翻译技术外，还要考虑如何从源程序数据空间映射到具体物理存储空间，也就是运行时的数据表示。在运行时如何组织或存放数据、在源程序中同名标识符是怎样描述不同的对象、
运行时的程序控制权是如何转移和参数是如何传递的以及如何生成质量较高的目标代码都是编译程序设计者需考虑的问题。
7.1.1 数据类型类型的合法性检查是判断数据的类型是否与上下文的要求相一致，例如 Pascal的运算符‘ +’不能作用在字符型数据上，而 C语言的‘ +’却能作用在字符型数据上。在数据类型上定义的各种运算通常包括赋值和一系列类型转换规则，这些规则保证了作用在数据对象上的某个运算符顺便通过由编译程序的类型的合法性检查，并实现其合法的算和赋值。因此，给出定义：
定义 7.1 数据类型是对该类型数据（变量或常量）的取值是否合法以及对该类型据的运算是否合法的一种说明。
实现和完成数据类型的合法性检查，它包括以下任务：
(1) 检查运算符作用在运算对象上的合法性，这一合法性保证了该运算能产生正确的运算结果。
(2) 根据程序设计语言运算符的类型转换规则，将一种类型数据转换成另一种数据类型。
(3) 能够使用相应的目标机器指令实现这种在上述类型上定义的运算。
例,设有 Pascal程序段
var
a,b:integer;
x:real;
begin
read(a);
b:=10;
x:=a mod b;
a:=a-x*10
end;
对于读语句 read(a)和赋值语句 b:=10都满足简单的类型检查。在赋值语句 x:=a mod b中虽然 a mod b的结果是整型的，但仍能满足将 a mod b的结果赋给实型变量 x。这是因为在 Pascal中定义了将整型转换成实型的转换规则，因而编译程序需生成将 a mod b的结果转换成实型的指令代码。而对于语句 a:=a-x*10，虽然通过 Pascal定义的类型规则可以将 a
转换成实型，求出 a-x*10的结果类型为实型，但 Pascal不允许将实型赋给整型，则出错。
例,设有 C语言程序段
{int a,b;
real x;
scanf(“%d”,&a);
b=10;
x:=a/b;
a:=a-x*10;
}
可以看出，上述二个程序段期望完成的功能是一样的，
但前者不能通过编译，而后者能顺利通过编译的类型检查，
这是因为 C语言中赋值语句 a:=a-x*10中也包含了强制将实型转换成整型。
根据语言的类型定义方式，可以将类型分为基本类型和构造类型，基本类型是指系统已定义的数据类型，如 C语言中的整型、浮点型（实型）、字符型。构造类型的指通过基本类型或已定义的类型构造出的新的数据类型，如 Pascal中的数组、记录和集合。引进了构造类型后，类型的合法性检查变得复杂。其检查方法有二大类，一类是名字等价，另一类是结构等价。
所谓名字等价也就是如果二个类型是等价的，当且仅当二个类型的名字或与类型名字的别名是等价的。
例,设有 Pascal程序段
type int=integer;
var
a:integer;
b:integer;
c:int;
……
a和 b是同一类型名 integer故它们是等价的；虽然 a和 c的类型名不同，但是 int是 integer的一种别名，故 a和 c的类型还是等价的。
所谓结构等价也就是如果二个类型是等价的，当且仅当二个类型具有相同的类型表达式。
定义 7.2 类型表达式是递归定义的,
(1) 类型表达式是基本数据类型
(2) 类型表达式是由数组、记录、集合、指针、函数等作用在类型表达式上的类型 。
检查类型的名字等价相对简单，只要为定义的类型名建立一张符号表，通过查表就可以判定二个类型是否名字等价。虽然，对于类型的等价的直观概念是结构等价，但结构等价检查的实现方法稍复杂。需为每个类型建立表示类型的结构树或无环有向图，如图为类型。
record
name,array[1..20] of char;
age:integer
end;
的树结构表示。
其中,array中的 integer
表示下标的类型对于如说明链表或树的数据结构的定义时，需递归定义。因此递归定义的类型图为无环有向图。图为类型
type link=↑node;
node=record
name,array[1..20] of char;
next:link
end;
的无环有向图。
检查二个类型是结构等价，只要二个类型结构树或无环有向图相等即可。检查类型等价也分成静态检查和动态检查。
由编译程序能完成的类型检查叫做静态类型检查；由目标程序运行时所作的类型检查就称为动态类型检查。一般地，如果要在生成的目标代码中完成类型检查，则目标代中不但要保存数据的值，而且还保存该数据的类型，则可完工成相应的动态类型检查。因算法语言的类型检查多数是静态的类型检查，在这里仅介绍了静态的类型检查。
7.1.2 数据结构一种程序设计语言如允许使用的数组、记录、集合、字符串、表、栈等形式的数据结构，在编译程序中应为它们提供相应的翻译。为了能对这些数据结构中的元素的引用，编译程序必须完成从这些数据的逻辑结构到访问这些数据元素的物理结构的映射。
使用上述数据结构应考虑：
(1) 映射算法相对简单，根据逻辑结构容易计算出物理地址。
(2) 从逻辑结构投影到物理结构时，不至于越界或存储溢出。
(3) 使用的数据结构承担这种程序设计语言的主要功能。
(4) 在这些数据结构上定义的运算。
例,设有类 Pascal程序段
program example(input,output);
type student=record
no:integer;
name:array[1..10] of char;
score:integer
end;
weekday=(sun,mon,tue,wed,thu,fri,sat);
var st:array[1..50] of student;
day:weekday;
i,j:integer;
begin
today:= sun;
i:=1;
st[i].no:=30;
st[i].name:=’wang fang’
……
end.
从上可以看出,st是一个记录型的数组，它首先通过数组的映射计算出 st[i]的地址，然后再通过记录的映射分别计算出 st[i].no 和 st[i].name的地址。对于枚举类型的数据
sun,mon,tue,wed,thu,fri,sat如何描述它们的值和在枚举类型的数据上的运算。对于字符串 st[i].name应考虑是否允许整体赋值和字符串是否允许连接等运算，运算后的结果到存储器中。连接后的结果如超出字符串设定的长度，如何强制或报错。
如要实现一个“栈”的数据类型，就应该考虑是否设置栈的最大容量，栈上的运算如,push和 pop。栈元素所允许的数据类型，如栈元素的类型允许是数组、记录、集合、字符串，但不能是表或栈。还要考虑如何将栈顶映射的物理存储空间。如设定静态的定长的栈空间用指针或下标指示当前栈顶或设定不定长的动态空间当入栈时申请存储空间，出栈时返回存储空间。
7.1.3 作用域规则一个程序设计语言的作用域规则确定了该程序设计语言的某个程序的不同程序块中所说明的标识符的可访问性。从另一个角度来看，在程序中当访问一个标识符通过作用域规则可确定究竟访问的是哪一个实体中说明的标识符。一般来说一个程序设计语言的一个标识符或数据项的作用域是在说明该标识符或数据项的程序块内，如 Pascal中的标识符的作用域规则，叙述如下：
(1) 一个标识符的作用域是从该标识符的定义点开始至定义该标识符的分程序结束为止，包含在这个分程序中的所有内分程序，并遵循规则 2。
(2) 当一个标识符 x在分程序 A中被定义，在 A所包含的分程序
B中又重新被定义，则分程序 B以及包含在 B中的所有分所出的 x不再是 A中定义的 x，而是 B中定义的 x。
例,设有 Pascal程序段
program example(input,output);
var x,y,real;
procedure pro;
var y,z,integer;
begin
……
x:=y;
……
end
begin
……
end.
在过程 pro中赋值语句 x:=y的 x为主程序中说明的 x，而 y为过程序中说明的 y。
作用域还包括文件作用域，如 C语言的函数作用域是从说明点开始，一直延伸到源文件结束。
作用域规则的不同直接影响到编译程序需生成的代码。
作用域规则分为静态作用域和动态作用域二种。静态作用域是指当标识符在本分程序中没有说明时，到说明该分程序的上一分程序中找相应的标识符，依次类推直至找到该标识符或整个上层分程序中均没找到该标识符为止。否则出错。动态作用域是指当标识符在本分程序逻辑中没有说明时，到调用该分程序的程序中找，依次类推直至找到该标识符或整个调用程序中均没找到该标识符为止，同样动态作用域也分为找到和出错。显然上述 Pascal中的作用域规则是静态作用域规则，静态作用域规则在编译中处理要比动态作用域的处理简单些。
7.1.4 控制结构一种程序设计语言的控制结构是该语言在程序运行期间用于改变控制流的语言特征集合。它包括有条件控制转移，
条件执行、循环控制、过程序调用、转移和出口。编译程序在翻译时必须保证源程序不能违法控制结构的语义。如
Pascal中只能从循环体内转向循环体外,C语言中不能从一个函数转向另一个函数,BASIC中不能在循环体内修改循环变量的值，而 C没有这种限制。
例,错误的控制结构
begin
for i:=1 to 10
begin
label:x:=x+1;
……
end;
goto label
……
end
程序的控制结构实际是程序执行权的转移。为了减少程序员编制的源程序中的错误。通常对程序的结构一定的约定。
因此，在设计或翻译程序设计语言的的控制结构时，需考虑：
设定或限制某种程序的控制，应满足程序设计的方法学或结构化程序设计的思想。
对每一种程序的控制结构，均能用编译的翻译技术来实现翻译。
提供程序的控制结构有利于程序员实现程序和查找源程序的错误。
综上所述，如何实现控制结构的翻译也是编译程序必须考虑的问题。
7.2 运行时的内存分配编译程序需要为常量或变量等数据分配运行时的存储空间。编译程序从操作系统中申请编译程序计算出的所需的内存或者编译程序生成在运时需申请内存的指令。
内存分配包括以下 3个任务：
(1) 确定用来表示某一数据项的内存的大小。
(2) 使用适当的内存分配策略实现具体数据的作用域和生命期。
(3) 确定以适当的算法访问生命期内的数据，包括基本型数据构造型数据。
以上三个任务实际上是完成逻辑数据到具体数据的映射。根据内存分配的时机，分为静态存储分配和动态存储分配方式。
采用哪一种分配策略是根据源语言的结构特点、源语言的数据类型、源语言中的作用域规则，源语言存储管理和组织的方式的复杂度都会影响到存储空间的分配策略。
下面就存储分配的主要技术，进行分析和讨论。
7.2.1 静态和动态内存分配为目标程序分配运行时所需的存储空间，一种是在目标程序运行前，由编译程序为数据分配存储空间，在程序的运行期间不再分配和解除这种内存分配。另一种在程序运行期间均可以对内存实现分配或解除分配，一旦存储分配解除该存储空间内的数据便失去意义。前者称为静态存储分配，后者称为动态存储分配。
定义 7.3 内存结合是指数据项的逻辑地址映射到内存物理地址的联系内存分配和内存结合是两个不同的概念，内存分配相当于在上网时用户申请了用户名，此时网络营运商将某个用户名“分配”给了该用户，但此时该用户不一定在上网。内存结合相当于网络用户用了申请到的用户名上网。网络用户的结合从用户的上网起至该用户下网止。
内存分配是实现内存结合的过程和手段，内存结合在内存解除分配时终止。源程序数据项的结合时刻决定编译程序的处理方式。当编译程序可以产生内存分配的代码时，不要在运行产生这种分配。这会影响到目标程序的效率。由于内存分配的时机不同，引入静态存储分配和动态存储分配的两种方式。
1,静态存储分配在静态存储分配中，编译程序在运行前为数据分配内存。
典型的静态存储分配是在编译时分配的。这要求编译程序在编译时能确定目标程序运行中据需的全部数据空间的大小，
编译程序将数据和内存结合从而实现存储分配。编译程序一旦实现静态存储分配，在整个程序运行期间不再进行存储分配或解除存储分配的工作直到整个程序运行结束。如 C语言中的全局变量和静态变量都是静态存储分配的。
例,图说明了下列 C语言程序段的静态数据存储分配
int a,b,c;
char d[100];
int f ();
main()
{int x=5,y=8;
printf(“%d,,f (x);)
printf(“%d,,g (y);)
}
int f(int n)
{static int p=0;
p+=n;
return(p);
}
int g(int m)
{static float q=0;
q+=m;
return(q);
}
图中的阴影部分表示其它数据的存储空间。
静态存储分配的限制：
(1) 数据对象的长度和它在内存中的位置在编译时都是已知的
(2) 不能建立如递归过程或递归函数中的一个名字对应多个存储空间的结合
(3) 不能建立数据对象长度不定的存储空间
2,动态存储分配为了避免上述对静态存储分配的限制，引进了动态存储分配。动态分配的数据区在运行不是一成不变的，它有时引入，有时退出，是一个动态的变化过程。动态存储分配分为二大类，一类是随着程序单元的进入而分配，随着程序单元的退出而撤销。另一类是由程序控制其分配和撤销。它们分别用栈和堆来实现，被称为栈式动态存储分配和堆式动态存储分配。
a)栈式动态分配当一个程序设计语言允许递归时，则每次进入该递归过程或函数时，就应分配一块大小相同的内存。当该过程或函数结束时相应的内存释放。由于递归过程或函数的进入和退出符合栈的先进后出的原则，故这一类存储分配可用栈实现。
把每次进入过程或函数需分配的数据区称为活动记录。
活动记录包括（如图所示）：
(1) 连接数据
a) 老的 SP。
每个活动记录，有一个基址指针称为 SP。为了撤销本活动记录时能指出上一个调用者的活动记录就应保存调用者的
SP称为老的 SP。而老的栈顶不必保存，因为老的栈顶为现
SP-1（设 SP占一个存储单元）
b) 返回地址返回地址是指子程序完成后的返回地址（对于函数还要返回其函数值）。
(2) 程序状态字为保存调用者的机器信息，如程序计数器、标志寄存器和寄存器的值，在返回时，预以恢复。
(3) 参数个数
(4)形式单元存放实在参数的值或地址。
(5) 局部数据局部数据包括：局部变量、静态数组的数据区、动态数组的内情向量和临时工作单元。
例,设有程序结构如下所示：
program main;
全局变量或数组说明；
proc R;
…
end R;
proc Q;
…
end Q;
在采用栈式动态分配时，因每进入一个过程就为该过程或函数分配存储空间。则图（ a）表示主程序中调用了 R；在
R中又调用了 Q的存储结构。图（ b）表示在 Q中又调用了 Q
的存储结构。图（ c）表示在 Q退出，又调用了 R的存储结构。
图（ d）表示在 R退出的存储结构。图（ e）表示在 Q退出的存储结构。图（ f）表示在 R退出的存储结构。
经过讨论了栈的存储分配，还要考虑过程式或函数调用和返回需完成的工作。前面第六章说过过程调用的四元式序列是：
par T1
par T2
par T3
…
par Tn
call P,n
现考虑四元式 par和 call是如何执行的，也就是 par和 call
要完成怎样的工作。对于每个 par Ti 需产生把参数填入活动记录的指令。由于 SP、返回地址、参数个数和程序状态字的所需的字节数对于某个过程来说是不变的且可以计算出的，
因此，每个参数存放的地址（相对于 SP的地址）也是可以计算出的,设其和为 m，则对于 par Ti可翻译成类似于如下指令：
[TOP+ i+m]:= Ti
这里 TOP为老的 TOP，每个参数均只占一个单元,Ti为参数的值或参数的地址。
四元式 call P,n应翻译成：
[TOP+1],= SP /*保护现行的 SP*/
[TOP+i+1],=当前寄存器值 /*保护现场 */
…
[TOP+m-1],=n /*保存参数个数 */
call P
进入过程 P后，应赋新的 SP，保护返回地址（返回地址也可以由指令 call P保存系统的栈中），定义新的 TOP值。
即执行指令：
SP:= TOP+1
[SP+1],=返回地址
TOP,=TOP+L /*L为 P过程所需的单元数 */
当执行到过程、函数的返回语句或过程、函数中的语句全部被执行完毕应返回调用者。其工作为计算出内存出栈后的 TOP、将复原老的 SP，对于函数还应将函数值存放到指定的连接单元中，然后执行返子指令：
TOP:= SP -1
SP:= [SP+0]
/*如返回的是函数则执行一条将函数值保存到指定单元或寄存中 */
RET /*返回调用程序 */
在这里 SP,TOP、参数等均只占一个单元，若它们占用不等长的单元在编译中也是可以计算出的，其实现方法类似。
b)堆式动态存储分配当一种程序设计语言允许用类似于 Pascal中 new和 dispose语句申请和释放内存，则不能用栈式存储分配，这因为其申请和释放的次序不满足先进后出的条件。这种数据只能借助于一种称为堆式动态存储分配的方法来实现。假定程序运行时有一个较大的存储空间，当用户申请堆内存时，就分配一块，
不用时返回。由于分配和返回的时间没有规律可循。当程序运行一段时间后，原来一块较大的存储空间很可能分成很多很多块。然而当需要长度为 N的存储空间只能寻找比 N大或相等的内存块分配，以此往复。最后在存储器池中出现了很多碎片。这些碎片就很难再为程序其它部分所用。为了解决碎片问题，一种方法是通过移动将碎片合并在一起，但这种方法是低效的，移动需化费很多机时。另一种方法是将原较大的存储空间分成若干等长的块，申请时分配以块为单位不足一块的长度也分配一块，返回时则必定也是以块为单位的。
这样解决了碎片问题，即外零头问题。但以块为单位分配浪费了块内的存储空间，也就是生成了内零头。这种方法虽然在分配时没有完全利用全部存储空间，但提高了系统的效率。
由于操作系统也需要管理内存，在编译实现时直接可以利用操作系统的内存管理，即需要内存时，向操作系统申请内存，
释放时直接将内存返回操作系统。
7.2.2 嵌套结构的内存分配前面介绍的栈式动态存储分配，每个过程或函数只能使用局部变量不能使用非局部变量，这与 Pascal语言结构的特点是不同的。 Pascal允许过程嵌套定义，也就是在过程或函数内需要使用非局部变量。下面是有嵌套过的 Pascal程序。
program sort(input,output);
var a:array[1..10] of integer;
x:integer;
procedure readarray;
var …a… end{readarray}
procedure exchange(i,j:integer);
begin
x:=a[i]; a[i]:=a[j]; a[j]:=x
end{exchange}
procedure quicksort(m,n:integer);
var k,v:integer;
function partition(y,z:integer):integer;
var i,j:integer;
begin
…a…
…v…
exchange(i,j);…
end{partition};
begin…end{quicksort};
begin…end{sort}
为了处理一致性，把主程序 sort看作最外层过程。这样过程说明的嵌套情况为：
sort
readarray
exchange
quicksort
partition
虽然在过程 readarray,exchange,partition引变量 a，
但该变量却为主程序中的 a。在过程 exchange中还引用了主程序中的 x。下面要解决如何调用外层中的变量。
在这里介绍静态作用域，动态作用域的调用方式可参照此方法稍作修改，也能完成。从上图中可以看出，无论是静态作用域还是动态作用域当内层过程需调用外层变量时，其外层过程的活动记录必然在栈中。要调用外层变量只要在内层过程中指出外层变量的活动记录的位置（ SP）值，再根据由符号表中指出的外层变量的相对位置就可以得到该外层变量的地址。
方法一：在活动记录中增加区头向量考虑程序的执行次序为：
sort→quicksort→quicksort→partition→exchange
对于 exchange可能用到的外层变量为 sort的变量；对于
partition可能用到的外层变量为 quicksort 和 sort的变量。以
sort标记为 0层；
readarray,exchange、
quicksort标记为 1层；
partition标记为 2层，则第 i层过程中除了能调用本层变量外，还能调用第 0层至第 i-1
层的外层变量。把从第 0层至第 i层活动记录的地址存放在一起组成了区头向量，如图所示。
当 sort调用 quicksort时,quicksort的区头向量为 sort的区头向量和 quicksort活动记录的地址。对于 quicksort调用
quicksort时，不能用前面一个 quicksort的区头向量再加上本层活动记录的地址，发现 quicksort和 quicksort是并列的，也就是层数相同的，因此允许调用的外层变量是相同的，故可从前面的 quicksort中拷贝层数个地址再加上本层活动记录的地址组成新的区头向量。类似地,partition从第 2个 quicksort
过程中拷贝层数个地址再加上本层活动记录地址组成新的区头向量。 exchange从 partition过程中拷贝层数个地址再加上本层活动记录地址组成新的区头向量。
设有图嵌套调用的情形，下面分另讨论不同之处调用 Pi的区头向量的构造情况。
在 Pi中调用 Pi，则从 P0~Pi-1均是 Pi可以调用的，因此从上一层 Pi的区头向量中拷贝 P0~Pi-1的地址，加上 Pi活动记录的地址组成新的区头向量。在 Pi+1中调用 Pi，则从 P0~Pi-1均是 Pi可以调用的，而 Pi 和 Pi+1不是 Pi的外层不要间接调用或不能调用，因此从上一层 Pi+1的区头向量中拷贝 P0~Pi-1
的地址，加上 Pi活动记录的地址组成新的区头向量。同理，在 P’i+1中调用 Pi，拷贝
P0~Pi-1的地址加上 Pi活动记录的地址组成新的区头向量。最后讨论在 Pi+2中调用 Pi，
则仍然是从 P0~Pi-1均是 Pi的外层，而 Pi,
P’i+1和 Pi+2不是 Pi的外层，因此从上一层
Pi+2的区头向量中拷贝 P0~Pi-1的地址，加上 Pi活动记录的地址也就组成了所需的区头向量。
综上所述，对于调用第 i层的过程只要从前面调用者中拷贝 0~i-1个地址，加上本数据区的地址组成新的区头向量。这样要在活动记录中增加称之为区头向量的部分，
如图所示。
每个过程的 d值和过程的层数 l在编译时都是可以计算出来的，则四元式 call P,n应翻译成：
[TOP+1],= SP /*保护现行的 SP*/
[TOP+i+1],=当前寄存器值 /*保护现场 */
…
[TOP+m-1],=n /*保存参数个数 */
从调用者的区头向量中拷贝 l个单元至进入过程的区头向量中；将 TOP+1即新的 SP放入区头向量的最后单元，组成新的区头向量。
call P
设访问外层变量的层数为 li，则访问外层变量的语句翻译成：
x:=SP[ li+d]
或 SP[ li+d]:=x
的指令。
图表示执行次序为
sort→quicksort→quicksort→partition→exchange的区头向量变化图。
方法二：在活动记录中增加访问链在过程的活动记录中增加一个称为访问链的的指针，当过程 q
在源程序中嵌套 p中，则将 q中访问链直接指向 p。那么执行次序为：
sort→quicksort→quicksort→partition→exchange
具有访问链的存储器栈变化图，如上所示。
下面需解决二个问题：
(1) 如何建立访问链
(2) 怎样根据访问链获得外层变量建立访问链也就是在运行时能求过程说明的直接外层。
由于主程序没有外层，故编译程序需为进入主程序时，生成置主程序的访问链为空指令。下面讨论执行中过程 R（可能为主程序）调用过程 S时，怎样求出 S的访问链。在编译时 R
和 S的层数都是可以求出分别记为 lR和 lS。 R可以调用 S，则 S
在 R的作用域内，可得 lS≤lR+1。当 lS = lR+1时，则 S是在 R内说明的，也就是 S是 R的直接外层，只要生成将 S的访问链置为指向 R的 SP（或 R的访问链）的指令。
当 lS = lR时，则 S和 R是并列的它们具有相同的直接外层，
也就是 R的外层也就是 S的外层，只要生成将 R的访问链赋给
S的访问链的指令即可。 lS<lR时,S的直接外层必然在栈中，
即 R必然被 S的直接外层直接或间接调用，否则 S不在作用域内。因此，只要对访问链向前搜索 lR - lS层，即可得到 S的直接外层。编译程序生对访问链向前搜索 lR - lS层的指令和将也为第 lS的访问链赋给 S的访问链。如 R的层数为 5,S的层数为
2，则向前搜索 3级求得层数也为 2的活动记录，它的访问链即为 S的访问链。
获得外层变量的方法与上述类似。设有 p过程中访问了变量 a，那么 p过程的层数记为 lp，变量 a层数记为 la，只要向前搜索 la - lp层,就可得到变量 a所在的活动记录中，由于 a的相对位置在编译中也是在符号表中可以查到的，故能生成对变量 a访问的指令。
分程序内含有数据说明语句起源于 Algol，但 C语言中延用此概念,C语言的分程序的语法为
{说明 语句 }
也就是在 C语言中的复合语句中，允许说明变量。而且在分程序的语句中还可以再有说明。这种具有嵌套性的分程序称为分程序结构。一个分程序结构的语言的说明作用域遵循最近嵌套原则：
(1) 一个分程序 B中说明的作用域包括 B，除了在 B内的分程序重新说明
(2) 如果名字 x不在 B中说明，则 x是最靠近且 B有说明 x的分程序说明的 x
设有程序段：
main()
{ /*分程序 B0开始 */
int a=0;
int b=0;
{ /*分程序 B1开始 */
int b=1;
{ /*分程序 B2开始 */
int a=2;
printf(“%d,%d\n”,a,b);
} /*分程序 B2结束 */
{ /*分程序 B3开始 */
int b=3;
printf(““%d,%d\n”,a,b);
} /*分程序 B3结束 */
printf(““%d,%d\n”,a,b);
} /*分程序 B1结束 */
printf(““%d,%d\n”,a,b);
} /*分程序 B0结束 */
则在 B0中说明的 int a=0的作用域为 B0- B2；在 B0中说明的 int
b=0的作用域为 B0- B1；在 B1中说明的 int b=1的作用域为 B1-
B3；在 B2中说明的 int a=2的作用域为 B2；在 B3中说明的 int
b=3的作用域为 B3。其变量标分别记为,a0,b0,b1,a2,b3。
分程序结构也可以用栈式存储分配来实现。因为每个变量作用域也符合先进后出的特点。解决分程序逻辑结构的存储分配，可采用下列二种方法。一是把分看成一个无参过程，
用上述过程嵌套的方法来解决。这种过程的特点是只说明一次，也只使用一次，它在分程序前调用，在分程序结束退出，
调用外即为说明之处。二是把一个过程体中所需的存储一次全部分配好。由于 B2中说明的 a和 B3中说明的 b的作用域不相交，故可分同一块存储空间，如下图所示。
在动态作用域中，进入新的过程时仅当新过程中说明了同名变量时，解释为新的存储。解决动态作用的方法也有二种，
一是所谓深访问，它在活动记录中存放一个控制链指向上一级调用过程，也可利用 SP指针。当发现非局部变量时从控制链一级一级向前搜索，直至搜索到为止，这种搜索可能深入栈中，因此而得名。搜索的深度取决于程序的运行，而编译时不能决定的。另一种所谓浅访问，它采用体外循环的方法，
为每个同名变量的名字分配静态的数据空间，当进入有同名变量的过程时将静态区的同名变量值保存到过程的同名变量的位置上，在过程的整个运行过程中，使用静态区同名变量，
过程结束后将先前保存在过程内的变量恢复。两种方法各有优缺点。深访问访问非局部变量是需较长的时间，但它不需要额外的开销。而浅访问可以直接访问非局部变量，但需要一些辅助的时间和空间来维护。
7.2.3 数组的分配和访问由于静态数组所需空间的大小是在编译时可以计算出来的，因此可在嵌套结构的栈式存储分配中只要为每个数组分直接分配相应的存储空间。下标变量的访问无论是本层变量还是外层变量都可以用前面介绍过的方法翻译成通过基址 SP
和相对位置访问下标变量的值。
动态数组的所需的空间在运行时才能确定，这样动态数组的存储空间也只能在运行时分配。前面说过编译程序需为内情向量分配了存储空间，然后生成填写内情向量的指令。
下面讨论动态数组的空间存放在何处。一种方法是将动态数组的空间存放在堆内存中，此时可以生成为动态数组申请堆存储的指令，并将首地址也填入内情向量中。当访问下标变量时，则编译程序可以生成要根据下标变量的下标和数组的内情向量求出数组元素在堆中的存储位置。
另外，应该注意在过程结束时，还需生成一条将堆内存返回的指令，不然会造成存储器的泄漏。严重时还会造成系统瘫痪。另一种方法也将动态数组的存储空间分配在栈中。当进入嵌套过程时，其活动记录的状态如图 (a)所示。此时应填写动态数组的内情向量,TOP+1作为第一个动态数组的首地址。此时该动态数组所需的存储空间可以计算出来了，可在栈顶分配该动态数组的存储空间。并将栈指针指向新的栈顶。
如有二个或二个以上的动态数组，则继续为每个动态数组分配内存。以次类推，最后栈指针指向如图 (b)中的 TOP位置。
此方法当过程退出时，则不必生成返回内存的指令，这是因为退出过程时 TOP赋的是 SP-1,SP赋的是过程中保存的老的 SP，指向调用者的活动记录。达到将动态数组分配的内存和原来的活动记录一起返回给栈。
7.3 代码优化作为一个高级语言的使用者很希望编译程序所产生的代码能够和直接用机器语言编写的程序的效果一样好。但事实上很难做到这一点，即使能做到这一点，也许所需化费实现优化的时间和空间比优化所得到的节省的时间多得多。在这里介绍的代码优化是指对原代码进行变换，从而获得时间和空间效率相对高的程序，而不一定且一般也不是时间和空间最省的程序。在进行优化时应做到：
(1) 代码的变换必须保持原程序的语义
(2) 从理论上，变换加快了程序的速度
(3) 这种变换是值得的如果一种所谓的优化改变了原程序的语义 —— 实际上产生了一个错误程序，这种变换也是无效的。尽管在优化后可能对于一些程序反而比原来增加了开销，但总体来说是节省的，而且节省应达到一个可度量的值，不然优化中的损失不可能在运行中弥补。由于各个机器的指令系统是不同的，即使是相同的四元式程序所生成的“最优”的代码也是不同的,
其优化算法也可能是不同的。为了算法的一致性在这里仅讨论与目标机器无关的优化算法。
一个程序的优化是由下面两个阶段构成的：
(1) 局部优化：应用于仅包括少量语句的小程序的优化变换。
(2) 全局优化：应用于一个程序单元，如一个函数或一个过程的优化变换。
7.3.1 优化变换程序的执行效率是可以通过地编译期优化变换是重写程序段以提高程序的工作效率而不改变语义。虽然变换的方法很多但常用的大致有下列几种：
1,编译求值一般来说程序的目标代码可能要运行多次，而编译只编译一次。如果一些原属于执行时完成的工作能在编译时解决，
则提前完成这些工作。如在计算 sin(3.1415927/6)时，
3.1415927/6的值在编译时可以计算的，其值为
0.523598783，运行时只要执行 sin(0.523598783)。因此程序的执行效率是可以通过地编译期间完成程序中的执行语义来提高的。这时编译程序消除了程序在执行时的需求，从而达到减少程序的执行时间、提高程序的工作效率。编译时的求值却体现了这一点。
2,合并运算设有程序段：
x:=a+b+c+d;
if a+b>0 then …;
y:=(a+b)*(b+c)+d;
则子表达式 a+b在不同的表达式中均使用过，因此只要计算一次 a+b的值，其余的值就可以使用该临时变量的值。
而将其它公共子表达式删除。
实现这种优化过程首先要识别产生相同值的表达式，在这里 a和 b都有没有重新被定值，故子表达式相同即为值相同。
其次计算相同的子表达式，用已存放在临时变量的值逐个代替试写出算术表达式。
表达式的等价可以考虑它们的运算对象是否程序所在位置处于相同的值。如一般情况下 a+b值和 b+a的值是等价的,
还有执行过 c:=b后,a*b和 a*c是等价的。实现这种“代数等价”，虽然提高了优化的效率，但同时也增加了优化的花费。
例,写出算术表达式 a+b*c-(c*b+a-c)/(b*c+d)优化后的四元式
（ 1）（ *,b,c,t1）
（ 2）（ +,a,t1,t2）
（ 3）（ -,t2,c,t3）
（ 4）（ +,t1,d,t4）
（ 5）（ /,t3,t4,t5）
（ 6）（ -,t2,t5,t6）
3,删除死码如果能在程序中删除其代码而不影响程序的运行结果的代码被称为“死码”，“死码”可以通过程序的控制流来获得，如条件语句：
if x>3 then
if x<3 then begin x:=x+1; y:=y*x end
else
x:=y*y
else
y:=25*x
此时可以从检查控制流发现代码 x:=x+1; y:=y*x无论何种情况总是不可能被执行。因此这一段代码可以被删除。另外，
设有一个赋值语句 x:=<表达式 >，而 x在程序的其它处从未被引用过，显然 x:=<表达式 >也为“死码”。删除这种“死码”
时应注意，只有当 <表达式 >的执行不会产生副作用时可以删除，也就是它不包含函数或过程，即使含有函数但没有函数的副作用，才能删除它。
4,减少频率减少频率是指程序中执行频率高的程序段移至程序执行频率低的程序部分中。其主要变换有相对循环不变量的内码外提。如程序段：
for i:=1 to 1000 do
begin
x:=1;
y:=5*x;
z:=y+i
end
此时循环体内的语句 x:=1和 y:=5*x;需执行 1000次，且它们相对于循环变量 i来说是不变的，因此将它们提出循环，置循环体外。即为：
x:=1;
y:=5*x;
for i:=1 to 1000 do
z:=y+i
这样对于语句 x:=1和 y:=5*x仅执行一次。
例,设有循环语句
c:=0;
FOR i:=1 TO n DO
BEGIN
a:=x*y;
b:=m*m;
c:=c+b*b
END
试写循环外提后的四元式序列。
根据题意，可写出循环语句的四元式序列为：
（ 1）（,= 0,_,c）
（ 2）（,= 1,_,i）
（ 3）（ jl,n,i,14）
（ 4）（ *,x,y,t1）
（ 5）（,=,t1,_,a）
（ 6）（ *,m,m,t2）
（ 7）（,=,t2,_,b）
（ 8）（ *,b,b,t3）
（ 9）（ +,c,t3,t4）
（ 10）（,=,t4,_,c）
（ 11）（ +,i,1,t5）
（ 12）（,=,t5,_,i）
（ 13）（ jmp,_,_,3）
由于 a:=x*y是循环不变运算，则可外提。 b2与 c之和虽然赋给了 c，但 b本身对于循环变量来说也是不变的，故也可以外提。其外提后生成的四元式如下：
（ 1）（,= 0,_,c）
（ 2）（,= 1,_,i）
（ 3）（ *,x,y,t1）
（ 4）（,=,t1,_,a）
（ 5）（ *,m,m,t2）
（ 6）（,=,t2,_,b）
（ 7）（ *,b,b,t3）
（ 8）（ jl,n,i,14）
（ 9）（ +,c,t3,t4）
（ 10）（,=,t4,_,c）
（ 11）（ +,i,1,t5）
（ 12）（,=,t5,_,i）
（ 13）（ jmp,_,_,8）
5,强度削弱和变换循环条件强度削弱是指用一个运算速度较快的运算符代替耗时较多的运算符，也就是将强度高的运算符削减为低强度的运算符。如,X 2写成 X*X,2*X写成 X+X。
在循环中的强度削弱方法为：
(1) 设循环变量为 i，对于循环体内的运算 L:=K*i+C可削弱为 T:=T+K
(2) 对临时变量 T赋初值 C
(3) 删除强度削弱后的无用变量例,设有循环语句
FOR i:=1 TO n DO
BEGIN
…
L:=K*i+C;
…
END
则削弱为：
T:=C;
FOR i:=1 TO n DO
BEGIN
…
T:=T+K
L:=T;
…
END
强度削弱对于程序循环中数组的访问是十分重要的，如在一个 Pascal循环中的数组引用 a[i,j]的地址，这样就造成了高强度的运算 i*n(按行存放 )，用上述方法就可以大地降低运算的强度。但需要注意的是这种方法不能适用于下标变量允许为实数（浮点数）类型，这是因为实数在累加时会产生积累误差，最后的 T中不是所需的 K*i+C。
设有循环语句,
for (i=1;i<=n;i++)
{t=4*i;
x=f(t);
…
}
由于在循环语句中 i和 t的关系始终保持 4倍的关系，而且循环内的其它部分也没有引用 i，则可将循环条件改变为
for (t=1;t<=4*n; t+=4)
这样经过变换后 i的值在循环内不再引用，故可在循环中删节除，从而达到优化的目的。
6,减少复写传播把形如 b:=a的赋值语句称为复写语句，简称复写。当
b:=a;c:=b时，只要 a在被新的赋值之后的程序不再引用 b，则可用 c:= a代替 c:=b。
【 例 7-10】 设有程序段
y:=x;z:=y;z:=y;
t1:=f(y);
t2:=g(z);
则改写为：
t1:=f(x);
t2:=g(x);
7.3.2 局部优化局部优化所需的化费相对较低，也就从优化所得到的收益也相对较低。局部优化顾名思义只是在较小的程序段中进行优化，从而达到优化的目的。这种程序段称为“基本块”。
定义 7.4 基本块是指程序中的一语句的顺序序列 (S1,S2,…,
Sn)，其中只有第一个语句 (S1)允许有是程序的控制语句转移的目的语句和最后一个语句 (Sn)允许是一个控制转移语句。
基本块划分算法：
(1) 求出称为入口的基本块的第一个语句，如：程序的第一个语句或有控制语句转入的语句。
(2) 对于每一入口语句构造其所属的基本块：
1)由入口语句到下一入口语句的前一语句
2)由入口语句到一转移语句
3)由入口语句到一停语句
(3) 对于未被划入任一基本块的语句，为通过任何基本块都不能到达该语句，故为无用语句应删除。
对于基本块内的公共子表达式的删除，可采用计算出每项个定值的四元式编号，当两个子表达式完全相同时，则它们具有相同的定值的四元式编号，表示在二个四元式之间没有新的定值。
为了简单起见。在基本块内将四元式编号以 1开始的连续号码编号。由于一个被定值的变号与被定值的变量有关，则在符号表中的每一变量增加一个称为定值编号的属性。设有
(n) A:=B op C，其中 n为对 A定值的四元式编号,B,C为变量,op为运算符。在符号表中需保存每个变量定值的位置 n，
对尚未定值的变量符号表中的定值编号的属性以 0表示。另外建立一四元式的符号表，为每个四元式的运算对象上都上都附加一个定值信息来指出该运算对象，这些信息也用四元式的编号表示。
再为每个四元式保存一个引用信息表示是否要为程序中的其它处引用而保留其值，其初值为 false。当设表达式 e是 e’
的子表达式，在翻译是时形成了关于 e的四元组时，其运算对象所关联的定值信息可从符号表中获得。将新产生的四元式和四元式符号表中现有的四元式比较，如果存在一个登记项为 k的与新的四元组完全匹配的四元式，则说明其值与新的表达式的值完全相同，也就是新的四元式不必存放在四元式符号表中，用四元式符号表 k的结果名代替 e’中的对象，
并对四元式 k的引用信息置为 true，以便决定该值是否保存到临时变量中。
例,设有基本块：
(:=,3.14,_,t1)
(*,2,t1,t2)
(*,x,y,t3)
(*,t1,t2,a)
(:=,a,_,b)
(*,2,t1,t4)
(*,x,y,t5)
(*,t4,t5,t6)
(*,x,y,t7)
(*,t6,t7,b)
其局部优化的过程为设所有变量的定值编号为 0，当四元式
(:=,3.14,_,t1),(*,2,t1,t2)和 (*,x,y,t3)进入时为图 (a)；
当四元式 (*,t1,t2,a)和 (:=,a,_,b)进入时，如图 (b)；
优化四元式 (*,2,t1,t4)时，在四元式表中查到匹配的四元式
(2)，故该四元不要入表，以后以 t2代替原来的 t4；同样四元式
(*,x,y,t5)只要用 t3代替 t5；则对于四元式 (*,t4,t5,t6)将改为
(*,t2,t3,t4)填表。四元式 (*,x,y,t7) 也能找到匹配的四元式，
则不要添加到表中；最后 (*,t6,t7,b)添入表中为 (*,t4,t3,b)，并将 t2 和 t3的引用信息改为 true,如图 (c)。
上述方法很容易地扩充到编译时的合并常量。对于语句
a:=n，其中 a为变量,n为常量。则在在常量表中加入常量 n，
其登记项为 k，并将定值位置 k与 a相关联用 -k表示。当生成一个四元组是，如果每个运算对象都是一个常量或是一个负的定值位置时，就可以实常量合并。
例,将上例中加入用合并常量算法加入用合并常量算法后其结果，如图所示。
7.3.3 全局优化要产生高效的代码，编译程序仅在基本块内优化是不够的。编译程序应把程序作为一整体来考虑，对各个基本块的信息进行数据流的分析从而达到优化的目的。全局优化和局部优化相比，全局优化需要更多的分析，以便确定优化的可行性。这里仅介绍全局子表达式的消除，包括公共表达式的消除和死代码的消除。
设有子表达式 α存在于程序的若干基本块中，记为 SB = {bi|bi
是基本块 }。设子表达式 α存在于程序的一组基本块中，且在某个 bk中存在对子表达式 α的求值。当程序的每次执行，都能满足下列两个条件，则在基本块 bi中子表达式 α是可以消除的。
(1) 基本块 bi只在已执行了一次或多次的某个 bk后执行。
(2) 在基本块 bk对 α的最后一次求值后，没有改变 α中的变量的值。
第一个条件保证了基本块 bi中的子表达式 α已被求值；第二个条件则保证了在基本块 bk求得 α的值和在基本块 bi求得 α
的值是等价的。如子表达式为 x*y，则不能改变变量 x或 y的值。
定义 7.5 程序流程图是一个三元组 G=(N,E,n0)，其中,N
为图的所有结点的集合也就是基本块的集合。 E表示图中的有向图中的边集，边 (bi,bj)它表示基本块 bi的最后一个语句转向基本块 bj的第一个语句。 n0表示程序的开始结点。
利用程序流程图分析基本块的控制和数据流的关系，实际上是分析基本块之间的关系是否满足上述二个条件。下面介绍一些基本概念：
(1) 前趋和后继：若 (bi,bj)∈ E，则称 bi是 bj的前趋,bj是 bi的后继。
(2) 路径：路径是从一个结点沿边序列到另一个结点的边的有序序列。
(3) 祖先和后代：若存在一条从 bi到 bj的路径，则称为 bi是 bj的祖先,bj是 bi的后代。
(4) 活跃变量：如果变量 a在一个基本块 bi的某个程序点 pi处定值，并在以后的程序中引用该值，则称变量 a是活跃的控制流分析是对一个程序进行分析以收集与程序结构相关的信息。数据流分析是对程序中使用的数据进行分析，以收集对优化有用的信息，能用来判断是否能对程序段进行优化。
定义 7.6
如果在基本块 bi包含一个对子表达式 α求值，且从求值之后不再包括对表达式中的运算对象的赋值，或子表达式 α在基本块是入口有效 bi不再包括对表达式中的运算对象的赋值称子表达式 α在基本块 bi出口有效的。
定义 7.7
对于基本块 bi的子表达式 α,如果它在流程图中的所有前趋的出口均是有效的，则子表达式 α在基本块 bi的入口是有效的。
由于表达式的出口有效性和入口有效性的定义是递归的，
也就是出口有效性是由入口有效性的来保证的，入口有效性是由出口有效性来保证的。因此有效表达式的概念是一个全路径的概念。为此对于全局优化需分析每个基本块的子表达式的有效性。设布尔变量 A_ini 和 A_outi分别表示表达式 α在基本块 bi的入口和出口的有效性； Evali当且仅当表达式 α在基本块 bi中求值为 true，否则为 false。 Emodifyi当且仅当表达式
α的某个运算对象在基本块 bi中被修改为 true，否则为 false。
这样每个基本块的入口有效性和出口有效性可用下列方程计算：
A_ini= A_outk1∧ A_outk2∧ A_outk3…… ∧ A_outkn (其中：
bj是 bi的前趋,j= k1,k2,k3……,kn)
A_outi= ~ Emodifyi∧ (Evali∨ A_ini)
消除全局性的子表达式 α的算法：
(1) 对于基本块 n0置 A_in0为 false，其它 N -n0中的基本块的
A_ini为 true。任意 A_outi为 true。
(2) 对 N中的每个基本块，做入口有效性和出口有效性计算，
直至每个基本块的任何有效性不再改变为止。
(3) 对满足 A_ini为 true且在基本块 bi中的 α求值前其任何运算对象不能被赋值，用代表表达式 α的临时变量代替 α。
例,设有程序流程图如图（ a）试用消除全局性的子表达式的算法，消除其公共子表达式。
由于四元式（ 1）和四元式（ 2）的表达式均为常量故不必优化。对于四元式（ 3）中的表达式 D+D进行优化。 D+D
对于基本块 B1,B2,B3,B4,B5,B6的 A_in1~A_ in6的初始值分别为,false,true,true,true,true,true。
A_out1~A_ out6均为 true。由于在基本块 B1中，对 D求值。故
Eval1为 true，而 D在中没有被修改 Emodify1为 false。这 样
A_out1仍为 true。由于 B1和 B5的 A_out1和 A_ out5均为 true，
故 B2的 A_in2仍为 true，由于表达式 D+D的二个运算分量 D均没有被赋值，也没有改变其值，则 A_ out2也为 true。同理基本块 B3,B4的 A_in3,A_in4,A_out3和 A_ out4均为 true。在基本块 B5中 D被修改,Emodify5为 true，故 A_ out5为 false。
此时 A_in2为 false，至此重复计算 B3,B4,B5 的 A_in、
A_out3均没有改变,B6的 A_ in6为 false则 B6的 A_ out6也为
false。这样任何基本块的任何有效性不再改变。故可用临时变量 t1来代替基本块 B5中的 D+D。以同样的方法考察对表达式 B+C的优化。对于基本块 B1,B2,B3,B4,B5,B6的
A_in1~A_ in6的初始值分别为,false,true,true,true、
true,true。 A_out1~A_ out6均为 true。求得 B2的 A_in2为
true,A_out2为 true。 B3的 A_in3为 true，由于 B3修改了变量
B的值，故 Emodify3为 true,因而 A_out3为 false 。
而 B4的 A_in4和 A_out4均为
true。 B5 的 A_in5为 false，而
B+C在 B5中求过值故 A_out5
为 true。 B6的 A_in6和 A_out6
均为 true。至此任何基本块的任何有效性不再改变。故可用临时变量 t2来代替基本块
B3 和 B4的表达式 B+C，但不能代替基本块 B5中的 B+C，
这因为 B5的 A_in5为 false。消除公共子表达式的如图 (b)
需要指出的是这种算法只能适用于基本块外的公共子表达式的删除，而不能用于基本块内的公共子表达式的删除。因此一般情况下应先用局部的公共子表达式的消除算法消除基本块内的公共子表达式，然后再用全局优化的算法消除基本块外的公共子表达式。
一个变量的活跃性可以根据下面的方法确定：
(1) 变量 a如果满足基本块的 bi中包含一个对 a的使用，且在 bi的祖先基本块中存在对 a的赋值，或者 a在 bi的出口是活跃的且中不再包含对 a的赋值则基本块 bi的入口处是活跃的。
(2) 如果 a在程序流图中 bi的某个的后继入口是活跃的，则
a在 bi的出口处是活跃的。
变量活跃的概念也是一个全局的概念。定义与活跃变量有关的布尔变量如 live_ini为 true表示变量 a在基本块的 bi入口是活跃的； live_outi为 true表示变量 a在基本块的 bi出口是活跃的； Refi为 true表示变量 a在基本块 bi内引用且在引用之前没有被赋值。 Defi为 true表示变量 a在基本块 bi内被赋值。
这样每个变量的活跃性可用下列方程计算：
live_ini= ~ Defi∧ (Refi∨ live_outi)
live_outi= live_ink1∨ live_intk2∨ live_ink3…… ∨ live_intkn
(其中,bj是 bi的后继,j= k1,k2,k3……,kn)
由于活跃变量的有效性是由下一个基本块向前一个基本块传递的。因此计算变量 a的活跃性算法如下：
(1) 对于程序流程图中的最后一个基本块 m置 live_outm为
false，其它 N -nm中的基本块的 live_outi为 true。任意 live_ini
为 false。
(2) 对 N中的每个基本块，做活跃入口有效性和活跃出口有效性计算，直至每个基本块的任何有效性不再改变为止。
(3) 删除变量在不活跃的基本块中的赋值。
考虑上图中变量 F，由 B6的出口是不活跃的求得它的入口也是不活跃的；再求得 B5的出口是不活跃的，那么 B5的入口也是不活跃的。同理求得 B3,B4的出口也是不活跃的。由于
Def3和 Def4为 true，根据方程式 live_ini= ~ Defi
(Refi∨ live_outi )求出 live_in3和 live_in4也是不活跃的。进而求得在基本块 B1,B2的入口和出口都是不活跃的。且重复完成求各活跃性时没有改变任何值，所有属性即为所求。最后删除变量在 B3,B4中的赋值即四元式（ 7）和四元式（ 9）。
同理考虑变量 G的活跃性,四元式（ 2）和四元式（ 10）也应删除
7.4 赋值语句、输入和输出语句的编译前面第一章中已经介绍了编译程序的作用是将源程序翻译成可运行的目标程序。通过语法制导翻译可以将源程序翻译成中间代码，在本节中主要讨论四元式翻译成目标代码需解决的问题。另外也可以在制导翻译中直接产生汇编代码，
但也同样需考虑如怎样充分利用寄存器，如何使生成的代码较短等问题。虽然由于目标机器的不同其指令结构、指令格式、字长和寄存器的个数和种类均有所不同，但其翻译的方法和原理是基本相同的。下面以 IBM-PC机 Intel 8088处理器作为目标机器，以记忆方便用汇编语言的符号指令作为目标机器语言的指令。
7.4.1 赋值语句的代码生成器代码生成器是把经过语法分析或优化后的中间代码作为输入，将它们翻译成特定的目标机器的语言或相应的汇编语言作为输出。赋值语句的代码生成器介绍与赋值语句有关的表达式的代码生成和赋值时的类型转换的代码生成。
代码生成器需要考虑二个问题，一是如何使生成的目标代码较短，另一是如何充分利用寄存器。生成的目标代码较短可以减少 CPU存取指令的时间同时也压缩了程序的存储空间。
由于数据在寄存器中运算的速度要比在存储器中运算的速度快，在生成的代码中如将以后需要继续引用的数据存放在寄存器中，也可以减少访问存储器的次数，从而达到目标程序运行的效率较高。
为了简单起见,这里只考虑在基本块内充分利用寄存器,设翻译四元式 A:=B op C时,需要确定变量 A,B,C变量在基本块内是否被其它四元式所引用，并确定在哪些四元式引用。
由于该四元式是对变量 A的定值，故应对 A的引用信息符加到该条四元式上。另外从变量 A出了基本块的是否活跃的活跃信息也决定了变量的值出了基本块是否要保存。为此对每个四元式在基本块中建立引用信息链和活跃变量链。这样在符号表中需增加引用信息栏外和一个活跃信息栏。求基本块内的引用信息可以从基本块的出口从后向前反向扫描基本块内的四元式，从而建立引用信息链和活跃信息链。如果对程序流程式做过全局的数据流分析，已计算出每个变量的活跃性，
则使用这些变量的活跃性；如没有做过全局的数据流分析，
那么没有做过全局的优化，此时临时变量出了基本块不会有引用，则认为临时变量出了基本块是不活跃的，而所有非临时变量出了基本块是活跃的。
计算引用信息链和活跃信息链算法：
(1) 对基本块中的每个变量在符号表中的引用信息栏置为
false用 0表示，并根据该变量出了基本块是否是活跃的置活跃信息为 true或 false。
(2) 从基本块出口到基本块入口由后向前处理各四元式。对于每个形如 (n) A:=B op C的四元式，依次完成下列步骤：
a) 把符号表中变量 A的引用信息和活跃信息拷贝到四元式 (n)的相应的属性上；
b) 把符号表中 A的引用信息和活跃信息置为 0和 false；
c) 把符号表中变量 B和 C的引用信息和息和活跃信息拷贝到四元式 (n)的相应的属性上；
d) 把符号表中 B和 C引用信息置为 n和活跃信息置为 true；
步骤 1,2说明了由于对变量 A赋值，此时四元式 (n)的引用信息和活跃信息却在符号表中，并再向前扫描是不能引用到第
(n)条四元式对 A的赋值。步骤 3,4说明了 B,C的引用信息位置已找到，故应复制其信息。注意上述四个步骤次序不能颠倒，因为变量 A和变量 B或 C有可能为同一变量。
例,设有如下基本块，其中 A,B,C,D为变量,t1,t2,t3为临时变量。
t1:=A+B
t2:=A*C
t3:= t1+ t2
D:=t3/ t2
如图 (a)为符号表和四元式表的初始值，图 (b)为四元式 (1)、
(2),(3),(4)从后向前分析后的结果。
要生成目标代码还要考虑如何充分利用寄存器的问题。为此需记录寄存器的使用情况，对于 Intel 8088 CPU中的每个寄存器用 REGISTER集合表示该寄存器中的现行值，如：
REGISTER(AX)={A,C}表示寄存器 AX中的现行值是 A,C；但由于在 Intel 8088中还允许用寄存器 AL和 AH则应允许用
REGISTER(AL)=… 和 REGISTER(AH)=… 。另外，要判断是否生成将寄存器中的数值保存到存储器的指令，用
VARIABLE(A)={AX,M}表示变量 A的值既在寄存器 AX中，又在存储器中。
根据上述描述，可给出代码生成算法：
(1) 对每个四元式 (n) A:=B op C依次执行下述步骤：
以四元式 (n) A:=B op C为参数，调用函数过 GETREG（ (n)
A:=B op C）当从 GETREG返回时，得到一个寄存器或寄存器对用 R表示，将它们存放现行变量 A的值；
(2) 利用变量描述集合 VARIABLE(B)和 VARIABLE(C)确定现行变量 B和 C的存放位置，设其存入位置为 Baddr和 Caddr。
若 VARIABLE(B)和 VARIABLE(C)中存在寄存器则 Baddr和
Caddr分别取作 VARIABLE(B)和 VARIABLE(C)中的寄存器；
(3) 如果 Baddr≠R，则根据变量 B的类型分别生成 MOV R,
byte PTR Baddr或 MOV R,word PTR Baddr和 op R,
Caddr，对于寄存器对 R和 R’，则要生成指令 MOV R,word
PTR Baddr,MOV R’,word PTR Baddr+2,op R,Caddr
和 op R’,Caddr（其中 R和 R’组成寄存器对，如 dx,ax寄存器对）
否则生成目标代码 op R,Caddr或 op R,Caddr和 op’ R’,
Caddr(op’为带进位的 op运算 )
如果 Baddr和 Caddr为 R或 R和 R’则删除 VARIABLE(B)和
VARIABLE(C)中的 R或 R和 R’；
(4) 令 VARIABLE(A)={R}或 VARIABLE(A)={R,R’}，并置
REGISTER[R]=A或 REGISTER[R]=A和 REGISTER[R’]=A，
以表示变量 A的值仅在寄存器或寄存器对中；
(5) 从四元式中的引用信息和活跃信息可知，若变量 B或 C在基本块中不再被引用，且它占用了寄存器或寄存器对，则从
REGISTER[R]和 REGISTER[R’]中删除其占用的寄存器或寄存器对。
注意，在具体实现中对于一些运算符没有单条指令实现其运算，可以编写相应的子程序来计算或用几条指令代替。
GETREG（）是一个函数过程，其结果是申请一个寄存器或寄存器对来存放结果的值。其算法如下：
（ 1）如果 B的现行值在某个寄存器或寄存器对中，而该寄存器或寄存器对中没有其变量，另外 B和 A为同一标识符，或者
B的现行值在执行该四元式后不会再被引用。则选取该寄存器或寄存器对作为 R或 R和 R’，返回；
（ 2）如果有可以满足相应运算的寄存器或寄存器对则从中选取一个或一对作用 R或 R和 R’,返回；
（ 3） 不满足上两个条件则必须从已分配的寄存器中选取，
但在选取过程中应首先满足占用寄存器的变量在内存中同时有值，其次是在基本块的很后面才能用到，这一点可以通过四元式表上的引用信息获得。对于选中的寄存器或寄存器对，
则对于 REGISTER[R]或 REGISTER[R]和 REGISTER[R’]中的每个变量 M，若 M不是 A则，或者 M既是 A又是 C，但不是 B且
B不在 R或 R和 R’中，则：
a)若 M不在存储器中，需生成将 M保存到存储器中的指令；
b)如果 M是 B，或 M是 C但同时 B也在 REGISTER[R]或
REGISTER[R]和 REGISTER[R’]中，则令 VARIABLE(M)={M，
R}或 VARIABLE(A)={R,R’,M}，否则令 VARIABLE(M)={M}
c)删除 REGISTER[R]或 REGISTER[R]和 REGISTER[R’]
中的 M
7.4.2 输入、输出语句的代码生成器一个程序设计语言都离不开输入、输出语句。由于输入、
输出语句均要和外部设备交换信息。如何翻译这些输入、输出语句也就是要取决于这些外部设备。实现输入、输出语句的翻译可采用调用有关输入、输出子程序的方法。将有关输入、输出功能写成一系列子程序，其子程序的实现应尽可能地调用由系统提供的程序，如操作系统提供的 DOS功能调用，
从而避免过多的消耗精力在完成这些外部设备的驱动程序上。
定义 7.8 输入、输出语句是作用在外部设备上的语句集合。
设有 Pascal语句 read(x)在语法制导翻译中,根据变量 x的类型，已翻译成相应的四元式（ ini,_,_x）或（ inr,_,_x）。现在讨论如何将它们翻译成目标指令。对于四元式（ ini,_,_x）可生成一条子程序的调用指令 call readi。
其中 readi表示输入整型数子程序的入口,readi子程序首先执行输入的功能调用将用户输入的数据存放到内存的缓冲区中，
然后从缓冲区中逐个读入字符判别是否是数字，则拼写成相应的数值，若是将控制字符，如回车换行等则结束数值的输入。对于四元式（ inr,_,_x）同样生成一条子程序的调用指令
call readr，其功能也是将用户输入数据存入缓冲区中，并将其转达换成浮点格式，如四字节的浮点数前三个字节表示尾数，最后一个字节表示阶码。
输出语句的翻译与输入语句的翻译方法基本相同，其主要区别是一个是从缓冲区中读出数据，另一个是往缓冲区中写入数据。对于输出的四元式（ outi,_,_x）或（ outr,_,_x），也是翻译成一条转子指令。其子程序中首先析出输出数据的每一位数符可标点符号，同时将它们转换成相应的字符填入输出缓冲区。最后调用输出的功能调用，达到输出的目的。如果允许使用字符串的输入、输出则要求考虑输入输出缓冲区最大长度。
7.5 控制结构的编译在编译程序中，存在程序的控制权转移的问题。如何生成控制权转移的代码，也是编译程序需要考虑的问题。
7.5.1 控制转移定义 7.9 一个程序设计语言的控制结构就是在一个程序中决定控制的顺序的语句或指令集合。
一个程序设计语言的控制结构通常是由控制的转移、条件执行、循环控制和过程或函数调用组成的。
基本的控制结构的转移可以通过条件转移或无条件转移实现，
这些控制结构如：四元式 (jmp,_,_n),(jz,a,b,n),(jnz,a,b,n)、
(jg,a,b,n),(jl,a,b,n),(jle,a,b,n),(jge,a,b,n),(j,a,p,q),在编译程序中通常翻译成条件判断指令 jz,jnz,jg,jl,jle,jge
等到六条指令和无条件转移指令 JMP。考虑到指令 JZ,JNZ、
JG,JL,JLE,JGE等六条指令的转移范围为 -128~+127，
现给出控制结构的翻译算法。
根据基本块的划分算法，这些控制结构的四元式必定是基本块的最后一个语句。由 VARIABLE(a) 和 VARIABLE(b)求得当前变量 a和 b位置，记为 aaddr和 baddr。用
GETREG(op,a,b,n)申请寄存器，返回 R或 R和 R’。以 a和 b均不在寄存器中，为例，则根据 a和 b的类型及 n的位置生成指令为：
(1) a和 b为单字节，转移范围不超过 -128~+127则生成指令：
MOV R,byte PTR aaddr
CMP R,baddr
op n
转移范围超过 -128~+127则生成指令：
MOV R,byte PTR aaddr
CMP R,baddr
L
JMP n
L:
(2) a和 b为双字节，转移范围不超过 -128~+127则生成指令：
MOV R,word PTR aaddr
CMP R,baddr
op n
转移范围超过 -128~+127则生成指令：
MOV R,word PTR aaddr
CMP R,baddr
L
JMP n
L:
(3) a和 b为四字节（需保存在寄存器对中），转移范围不超过 -128~+127则生成指令：
MOV R’,word PTR aaddr+2
MOV R,word PTR aaddr
CMP R’,baddr+2
JNZ L1
CMP R,baddr
op n
JMP L2
L1,op n
JMP L2
L2:
转移范围超过 -128~+127则生成指令：
同上注意,op操作符和的关系是反向转移；当 a和 b有一个在寄存器中，则不必生成从内存中取数指令直接与 aaddr进行比较即可。另外对于判断转移是否在 -128~+127内，当向前转达移时，可利用为每个四元式填写分配运行时的相对地址计算相对差；对于向后转移，可采用所谓估算的方法，设计一个为每一种类型的四元式与最大字节数的对照表。以对照计算从转移源到转移目的的最大字节数代替转移字节数。
7.5.2 函数和过程的调用函数与过程序调用的场合有所不同，但其控制权的转移和返回都有是相同的。函数比过程多一个返回值。
翻译函数或过程时，编译程序应保证以下几点：
(1) 被调用的函数或过程能对实际参数进行访问，包括传值和传地址等各种参数。
(2) 控制可转移到被调用函数或过程，并能从被调用函数中返回。
(3) 若是函数应保证调用者能正确取到函数的返回值。
完成函数或过程代码生成需考虑函数或过程的调用规范、
参数传递的形式，如是否允许递归、参数是值传递还是地址传递或者是其它传递方式。
设函数或过程的调用已翻译成四元式序列：
par T1
par T2
par T3
…
par Tn
call P,n
前面已经说过对于每个四元式 par Ti 根据其参数的传递类型应产生填写相应活动记录的指令。设寄存器 SI存放的是
SP指针，寄存器 DI中存放的是 TOP指针，数据段和堆栈段为同一段。由于 SP、返回地址、参数个数和程序状态字等所需的字节数在前面翻译成四元式时都可以计算出来的。因此，
每个参数存放的地址（相对于 SP的地址）也是可以计算出的,
设其和为 m，则对于 par Ti可翻译成类似于如下指令：
MOV [DI+ i+m],Ti
四元式 call P,n应翻译成：
MOV [SI+2],DI /*保护现行的 SP*/
MOV [SI+4],AX /*保护现场 */
MOV [SI+6],BX
…
MOV [DI+m-1],n
call P
进入过程 P后，应赋新的 SP(SI)，保护返回地址（此时在调用 call P已保存栈中），定义新的 TOP值。即执行指令：
MOV SI,DI
INC SI
ADD DI,L /*L为 P过程所需的单元数 */
MOV SP,DI
当翻译到函数的返回值的语句时，如 PSACAL中的函数标识符,=表达式，或 C语言中的 return（表达式）语句对应的四元式时，生成指令 MOV R,ti。其中 R为函数返回约定的寄存器,ti存放返回值的表达式的临时变量。
翻译到过程或函数的返回语句或过程或函数中的语句全部被完毕，则应生成返回调用者的指令。其工作为计算出内存出栈后的 TOP、将复原老的 SP即生成指令：
MOV SI,DI
DEC SI
MOV SI,[SI]
RET L
在函数或过程体的语句翻译时还要注意，对外层变量的引用需生成先取该层变量的基址的指令，然后生成根据相对位移访问相应外层变量。
7.6 程序重定位概述编译程序生成的目标代码一般有三种形式：一是能立即执行的机器语言代码，所有地址均已定位；二是待装配的机器语言模块。这种模块需要执行时，由连接程序和其它模块连接起来，转换成能执行的机器语言代码；三是汇编语言代码，这种代码需用汇编程序汇编后转换成机器代码才能执行。
第一种所有地址是直接定位的，一般不能装入不同的内存执行。因此编译程序翻译成的目标代码，通常希望为可以装入不同内存的执行，也就是可以对目标程序进行重定位。
7.6.1 程序的重定位定义 7.10 当程序 P中包含任何绝对地址的指令，称为该程序是对地址是敏感的，其中绝对地址可以指令地址也可以数据地址。
定义 7.11 程序重定位是一种修正用于地址敏感指令中的地址的过程以便程序可以在指定的内存区域正确地执行。
地址的定位的时刻也有三种：编译时定位，连接时定位和装入时定位。为此给这三种翻译时刻，为：
翻译源：由翻译程序决定的源地址。地址由程序员在程序中用类似于 ORG伪操作完成的。
连接源：由连接程序在生成二进制程序时指定的源地址。
装入源：地装入一个执行程序时由装入程序指定的源地址。
如果连接源不同于翻译源则重定位应该是在连接时完成的。如果连接的地址和装入的地址不一致时，即连接源不同于装入源则重定位必须由装入程序完成。通常连接程序总是需要进行重定位，而装入程序则不一定进行重定位。如果程序的地址对于程序的不同执行可能是不同的，那么这种绝对装入方式在实际应用中是很不方便的。重定位装入程序在装入一个程序执行时将对该程序实施重新定位。这样就允许程序在内存的不同位置被执行。
例,设有程序
ORG 100
ARRAY DW 100 DUP (?)
VAR DW 4 (?)
JMP NEXT
…
NEXT
其中,ARRAY 为 100,VAR的地址为 300,NEXT的地址为 540则编译源为 100，当连接源为 500时，在连接时的重定位将敏感的地址 ARRAY的地址,VAR的地址和 NEXT的地址替换为 500,700,940，即每个敏感地址加上一个常量 400，
注意当连接源小于编译源时，其常量为负的。当连接源等于编译源时，其常量为 0。
7.6.2 连接如果编译程序的目标代码是可连接的程序模块，那么应了解程序的模块需提供连接程序的信息。
当一个程序分别编译时，产生若干个程序序列，在这些序列中存在一个指令序列中通过修改自已内部的指令修改地址而影响到其它序列中的程序或数据的地址。这种影响是相互影响的。因此对每个程序序列中需定义调用外部其它信息，
这些信息分为 PUBLIC和 EXTRN。用 PUBLIC说明的信息表示本程序序列中定义的信息是公用信息，可供其它模块使用。
用 EXTRN说明表示本程序序列中的那些信息是外部定义的。
连接程序需解决外部引用的问题，在应用程序被执行前需为每个被连接的模块给予正确的地址分配，避免模块间的地址冲突。对于外部说明的信息应在各模块间注意其一致性。在连接完成前，存在外部引用没有被解决，而一旦连接完成对于外部说明的信息在各模块间是一致性的，则所有外部引用都可以解决的。
连接的实质是若干个由二进制程序组成的一种机器语言，
重定位在连接源开始的内存区域中，并完成对每个外部引用的地址分配。连接提供了不同语言编写的程序组成一个应用程序的可能。
7.6.3 目标模块编译程序输出的目标语言，最常用的是目标模块。要使编译程序能生成这些模块也就要求编译程序的设计者了解目标模块的构造。
一个程序的目标模块包括了所有重定位和与其它程序连接的所需的所有信息。一个程序模块是由 4个部分组成的：
(1) 头文件：头文件包含了翻译源（用户定义的地址）、程序的大小 （占字节数）、程序执行的起始地址（程序的入口）。
(2) 程序：即与源程序对应的机器语言目标程序。
(3) 重定位表：重定位表的每个记录只有一个域，它记录了程序中的所有敏感指令的翻译地址。
(4) 链接表：这个表包括程序涉及的所有公共定义和外部引用。每个记录包括 3个域，它们是变量域、类型域和翻译地址。
其中：
a) 变量：变量名。
b) 类型,PUBLIC或 EXTRN表示公共定义或外部引用。
c) 翻译地址：对公共定义来说，这是分配给变量在内存中的首字节的地址。对外部变量，这是保存变量地址的内存地址。
例,设有汇编语言程序如下：
0000 subcode segment
00C8 ORG 200
PUBLIC _f
EXTRN
MAX:WORD,ALPHA:WORD
assume CS:subcode
00C8 _f PROC far
00C8 B8 0041 LOOP,mov ax,65
00CB 2E,A1 0000 E mov ax,ALPHA
00CF 2E,03 06 0000 E ADD ax,MAX
00D4 23 C0 AND AX,AX
00D6 75 F0 JNZ LOOP
00D8 CB ret
00D9 TOTAL DW?
_f ENDP
00DB subcode ends
end _f
则目标模块包括以下信息：
翻译源 =200，大小 13h，目标地址 =200
机器语言指令（在上面汇编语言左面的二进制指令）
重定位表和连接表名字 类型 属性
ALPHA V WORD 0000 SUBCODE
External
LOOP L NEAR 00C8 SUBCODE
MAX V WORD 0000 SUBCODE
External
TOTAL L WORD 00D9 SUBCODE
