编译原理演示文稿7.ppt

1、第七章 编译程序 7.1 编译程序考虑的因素 编译程序设计时，除了需用到前介绍的分析技术和制导翻译技术外，还要考虑如何从源程序数据空间映射到具体物理存储空间，也就是运行时的数据表示。在运行时如何组织或存放数据、在源程序中同名标识符是怎样描述不同的对象、运行时的程序控制权是如何转移和参数是如何传递的以及如何生成质量较高的目标代码都是编译程序设计者需考虑的问题。,7.1.1 数据类型 类型的合法性检查是判断数据的类型是否与上下文的要求相一致，例如Pascal的运算符+不能作用在字符型数据上，而C语言的+却能作用在字符型数据上。在数据类型上定义的各种运算通常包括赋值和一系列类型转换规则，这些规则保证

2、了作用在数据对象上的某个运算符顺便通过由编译程序的类型的合法性检查，并实现其合法的算和赋值。因此，给出定义： 定义7.1 数据类型是对该类型数据（变量或常量）的取值是否合法以及对该类型据的运算是否合法的一种说明。,实现和完成数据类型的合法性检查，它包括以下任务： (1) 检查运算符作用在运算对象上的合法性，这一合法性保证了该运算能产生正确的运算结果。 (2) 根据程序设计语言运算符的类型转换规则，将一种类型数据转换成另一种数据类型。 (3) 能够使用相应的目标机器指令实现这种在上述类型上定义的运算。,例:设有Pascal程序段 var a,b:integer; x:real; begin re

3、ad(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;

4、 scanf(“%d”, ,可以看出，上述二个程序段期望完成的功能是一样的，但前者不能通过编译，而后者能顺利通过编译的类型检查，这是因为C语言中赋值语句a:=a-x*10中也包含了强制将实型转换成整型。 根据语言的类型定义方式，可以将类型分为基本类型和构造类型，基本类型是指系统已定义的数据类型，如C语言中的整型、浮点型（实型）、字符型。构造类型的指通过基本类型或已定义的类型构造出的新的数据类型，如Pascal中的数组、记录和集合。引进了构造类型后，类型的合法性检查变得复杂。其检查方法有二大类，一类是名字等价，另一类是结构等价。 所谓名字等价也就是如果二个类型是等价的，当且仅当二个类型的名字或与

5、类型名字的别名是等价的。,例:设有Pascal程序段 type int=integer; var a:integer; b:integer; c:int; a和b是同一类型名integer故它们是等价的；虽然a和c的类型名不同，但是int是integer的一种别名，故a和c的类型还是等价的。 所谓结构等价也就是如果二个类型是等价的，当且仅当二个类型具有相同的类型表达式。,定义7.2 类型表达式是递归定义的: (1) 类型表达式是基本数据类型 (2) 类型表达式是由数组、记录、集合、指针、函数等作用在类型表达式上的类型。 检查类型的名字等价相对简单，只要为定义的类型名建立一张符号表，通过查表就可

6、以判定二个类型是否名字等价。虽然，对于类型的等价的直观概念是结构等价，但结构等价检查的实现方法稍复杂。需为每个类型建立表示类型的结构树或无环有向图，如图为类型。 record name :array1.20 of char; age:integer end; 的树结构表示。 其中，array中的integer 表示下标的类型,对于如说明链表或树的数据结构的定义时，需递归定义。因此递归定义的类型图为无环有向图。图为类型 type link=node; node=record name :array1.20 of char; next:link end; 的无环有向图。,检查二个类型是结构等价，只

7、要二个类型结构树或无环有向图相等即可。检查类型等价也分成静态检查和动态检查。由编译程序能完成的类型检查叫做静态类型检查；由目标程序运行时所作的类型检查就称为动态类型检查。一般地，如果要在生成的目标代码中完成类型检查，则目标代中不但要保存数据的值，而且还保存该数据的类型，则可完工成相应的动态类型检查。因算法语言的类型检查多数是静态的类型检查，在这里仅介绍了静态的类型检查。,7.1.2 数据结构 一种程序设计语言如允许使用的数组、记录、集合、字符串、表、栈等形式的数据结构，在编译程序中应为它们提供相应的翻译。为了能对这些数据结构中的元素的引用，编译程序必须完成从这些数据的逻辑结构到访问这些数据元素

8、的物理结构的映射。 使用上述数据结构应考虑： (1) 映射算法相对简单，根据逻辑结构容易计算出物理地址。 (2) 从逻辑结构投影到物理结构时，不至于越界或存储溢出。 (3) 使用的数据结构承担这种程序设计语言的主要功能。 (4) 在这些数据结构上定义的运算。,例:设有类Pascal程序段 program example(input,output); type student=record no:integer; name:array1.10 of char; score:integer end; weekday=(sun,mon,tue,wed,thu,fri,sat); var st:arr

9、ay1.50 of student; day:weekday; i,j:integer; begin today:= sun; i:=1; sti.no:=30; :=wang fang end.,从上可以看出，st是一个记录型的数组，它首先通过数组的映射计算出sti的地址，然后再通过记录的映射分别计算出sti.no 和 的地址。对于枚举类型的数据sun,mon,tue,wed,thu,fri,sat如何描述它们的值和在枚举类型的数据上的运算。对于字符串应考虑是否允许整体赋值和字符串是否允许连接等运算，运算后的结果到存储器中。连接后的结果如超出字

10、符串设定的长度，如何强制或报错。 如要实现一个“栈”的数据类型，就应该考虑是否设置栈的最大容量，栈上的运算如：push和pop。栈元素所允许的数据类型，如栈元素的类型允许是数组、记录、集合、字符串，但不能是表或栈。还要考虑如何将栈顶映射的物理存储空间。如设定静态的定长的栈空间用指针或下标指示当前栈顶或设定不定长的动态空间当入栈时申请存储空间，出栈时返回存储空间。,7.1.3 作用域规则 一个程序设计语言的作用域规则确定了该程序设计语言的某个程序的不同程序块中所说明的标识符的可访问性。从另一个角度来看，在程序中当访问一个标识符通过作用域规则可确定究竟访问的是哪一个实体中说明的标识符。一般来说一个

11、程序设计语言的一个标识符或数据项的作用域是在说明该标识符或数据项的程序块内，如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;

12、 begin x:=y; end begin end.,在过程pro中赋值语句x:=y的x为主程序中说明的x，而y为过程序中说明的y。 作用域还包括文件作用域，如C语言的函数作用域是从说明点开始，一直延伸到源文件结束。 作用域规则的不同直接影响到编译程序需生成的代码。作用域规则分为静态作用域和动态作用域二种。静态作用域是指当标识符在本分程序中没有说明时，到说明该分程序的上一分程序中找相应的标识符，依次类推直至找到该标识符或整个上层分程序中均没找到该标识符为止。否则出错。动态作用域是指当标识符在本分程序逻辑中没有说明时，到调用该分程序的程序中找，依次类推直至找到该标识符或整个调用程序中均没找到该

13、标识符为止，同样动态作用域也分为找到和出错。显然上述Pascal中的作用域规则是静态作用域规则，静态作用域规则在编译中处理要比动态作用域的处理简单些。,7.1.4 控制结构 一种程序设计语言的控制结构是该语言在程序运行期间用于改变控制流的语言特征集合。它包括有条件控制转移，条件执行、循环控制、过程序调用、转移和出口。编译程序在翻译时必须保证源程序不能违法控制结构的语义。如Pascal中只能从循环体内转向循环体外、C语言中不能从一个函数转向另一个函数、BASIC中不能在循环体内修改循环变量的值，而C没有这种限制。 例:错误的控制结构 begin for i:=1 to 10 begin labe

14、l:x:=x+1; end; goto label end,程序的控制结构实际是程序执行权的转移。为了减少程序员编制的源程序中的错误。通常对程序的结构一定的约定。因此，在设计或翻译程序设计语言的的控制结构时，需考虑： 设定或限制某种程序的控制，应满足程序设计的方法学或结构化程序设计的思想。 对每一种程序的控制结构，均能用编译的翻译技术来实现翻译。 提供程序的控制结构有利于程序员实现程序和查找源程序的错误。 综上所述，如何实现控制结构的翻译也是编译程序必须考虑的问题。,7.2 运行时的内存分配 编译程序需要为常量或变量等数据分配运行时的存储空间。编译程序从操作系统中申请编译程序计算出的所需的内存

15、或者编译程序生成在运时需申请内存的指令。 内存分配包括以下3个任务： (1) 确定用来表示某一数据项的内存的大小。 (2) 使用适当的内存分配策略实现具体数据的作用域和生命期。 (3) 确定以适当的算法访问生命期内的数据，包括基本型数据构造型数据。 以上三个任务实际上是完成逻辑数据到具体数据的映射。根据内存分配的时机，分为静态存储分配和动态存储分配方式。采用哪一种分配策略是根据源语言的结构特点、源语言的数据类型、源语言中的作用域规则，源语言存储管理和组织的方式的复杂度都会影响到存储空间的分配策略。 下面就存储分配的主要技术，进行分析和讨论。,7.2.1 静态和动态内存分配 为目标程序分配运行时

16、所需的存储空间，一种是在目标程序运行前，由编译程序为数据分配存储空间，在程序的运行期间不再分配和解除这种内存分配。另一种在程序运行期间均可以对内存实现分配或解除分配，一旦存储分配解除该存储空间内的数据便失去意义。前者称为静态存储分配，后者称为动态存储分配。 定义7.3 内存结合是指数据项的逻辑地址映射到内存物理地址的联系 内存分配和内存结合是两个不同的概念，内存分配相当于在上网时用户申请了用户名，此时网络营运商将某个用户名“分配”给了该用户，但此时该用户不一定在上网。内存结合相当于网络用户用了申请到的用户名上网。网络用户的结合从用户的上网起至该用户下网止。,内存分配是实现内存结合的过程和手段，

17、内存结合在内存解除分配时终止。源程序数据项的结合时刻决定编译程序的处理方式。当编译程序可以产生内存分配的代码时，不要在运行产生这种分配。这会影响到目标程序的效率。由于内存分配的时机不同，引入静态存储分配和动态存储分配的两种方式。 1. 静态存储分配 在静态存储分配中，编译程序在运行前为数据分配内存。典型的静态存储分配是在编译时分配的。这要求编译程序在编译时能确定目标程序运行中据需的全部数据空间的大小，编译程序将数据和内存结合从而实现存储分配。编译程序一旦实现静态存储分配，在整个程序运行期间不再进行存储分配或解除存储分配的工作直到整个程序运行结束。如C语言中的全局变量和静态变量都是静态存储分配的

18、。,例:图说明了下列C语言程序段的静态数据存储分配 int a,b,c; char d100; 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) 不能建立如递归过程或递归函数中的一个名字

19、对应多个存储空间的结合 (3) 不能建立数据对象长度不定的存储空间,2. 动态存储分配 为了避免上述对静态存储分配的限制，引进了动态存储分配。动态分配的数据区在运行不是一成不变的，它有时引入，有时退出，是一个动态的变化过程。动态存储分配分为二大类，一类是随着程序单元的进入而分配，随着程序单元的退出而撤销。另一类是由程序控制其分配和撤销。它们分别用栈和堆来实现，被称为栈式动态存储分配和堆式动态存储分配。 a)栈式动态分配 当一个程序设计语言允许递归时，则每次进入该递归过程或函数时，就应分配一块大小相同的内存。当该过程或函数结束时相应的内存释放。由于递归过程或函数的进入和退出符合栈的先进后出的原则

20、，故这一类存储分配可用栈实现。把每次进入过程或函数需分配的数据区称为活动记录。,活动记录包括（如图所示）： (1) 连接数据 a) 老的SP。 每个活动记录，有一个基址指针称为SP。为了撤销本活动记录时能指出上一个调用者的活动记录就应保存调用者的SP称为老的SP。而老的栈顶不必保存，因为老的栈顶为现SP-1（设SP占一个存储单元） b) 返回地址 返回地址是指子程序完成后的返回地址（对于函数还要返回其函数值）。 (2) 程序状态字 为保存调用者的机器信息，如程序计数器、标志寄存器和寄存器的值，在返回时，预以恢复。 (3) 参数个数 (4)形式单元 存放实在参数的值或地址。,(5) 局部数据 局

21、部数据包括：局部变量、静态数组的数据区、动态数组的内情向量和临时工作单元。,例:设有程序结构如下所示： 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退出的存储结构。,经过讨论了栈的存储分配，还要考虑过程式或函数调用和返回需完成的工作。前面第六

22、章说过过程调用的四元式序列是： 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

23、+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:=

24、 SP+0 /*如返回的是函数则执行一条将函数值保存到指定单元或寄存中*/ RET /*返回调用程序*/ 在这里SP、TOP、参数等均只占一个单元，若它们占用不等长的单元在编译中也是可以计算出的，其实现方法类似。,b)堆式动态存储分配 当一种程序设计语言允许用类似于Pascal中new和dispose语句申请和释放内存，则不能用栈式存储分配，这因为其申请和释放的次序不满足先进后出的条件。这种数据只能借助于一种称为堆式动态存储分配的方法来实现。假定程序运行时有一个较大的存储空间，当用户申请堆内存时，就分配一块，不用时返回。由于分配和返回的时间没有规律可循。当程序运行一段时间后，原来一块较大的存储

25、空间很可能分成很多很多块。然而当需要长度为N的存储空间只能寻找比N大或相等的内存块分配，以此往复。最后在存储器池中出现了很多碎片。这些碎片就很难再为程序其它部分所用。为了解决碎片问题，一种方法是通过移动将碎片合并在一起，但这种方法是低效的，移动需化费很多机时。另一种方法是将原较大的存储空间分成若干等长的块，申请时分配以块为单位不足一块的长度也分配一块，返回时则必定也是以块为单位的。这样解决了碎片问题，即外零头问题。但以块为单位分配浪费了块内的存储空间，也就是生成了内零头。这种方法虽然在分配时没有完全利用全部存储空间，但提高了系统的效率。由于操作系统也需要管理内存，在编译实现时直接可以利用操作系

26、统的内存管理，即需要内存时，向操作系统申请内存，释放时直接将内存返回操作系统。,7.2.2 嵌套结构的内存分配 前面介绍的栈式动态存储分配，每个过程或函数只能使用局部变量不能使用非局部变量，这与Pascal语言结构的特点是不同的。Pascal允许过程嵌套定义，也就是在过程或函数内需要使用非局部变量。下面是有嵌套过的Pascal程序。 program sort(input,output); var a:array1.10 of integer; x:integer; procedure readarray; var a endreadarray procedure exchange(i,j:in

27、teger); begin x:=ai; ai:=aj; aj:=x endexchange,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); endpartition; beginendquicksort; beginendsort,为了处理一致性，把主程序sort看作最外层过程。这样过程说明的嵌套情况为： sort readarray exchange quicksort p

28、artition 虽然在过程readarray、exchange、partition引变量a，但该变量却为主程序中的a。在过程exchange中还引用了主程序中的x。下面要解决如何调用外层中的变量。 在这里介绍静态作用域，动态作用域的调用方式可参照此方法稍作修改，也能完成。从上图中可以看出，无论是静态作用域还是动态作用域当内层过程需调用外层变量时，其外层过程的活动记录必然在栈中。要调用外层变量只要在内层过程中指出外层变量的活动记录的位置（SP）值，再根据由符号表中指出的外层变量的相对位置就可以得到该外层变量的地址。,方法一：在活动记录中增加区头向量 考虑程序的执行次序为： sortquicks

29、ortquicksortpartitionexchange 对于exchange可能用到的外层变量为sort的变量；对于partition可能用到的外层变量为quicksort 和sort的变量。以sort标记为0层；,readarray、exchange、quicksort标记为1层；partition标记为2层，则第i层过程中除了能调用本层变量外，还能调用第0层至第i-1层的外层变量。把从第0层至第i层活动记录的地址存放在一起组成了区头向量，如图所示。,当sort调用quicksort时，quicksort的区头向量为sort的区头向量和quicksort活动记录的地址。对于quickso

30、rt调用quicksort时，不能用前面一个quicksort的区头向量再加上本层活动记录的地址，发现quicksort和quicksort是并列的，也就是层数相同的，因此允许调用的外层变量是相同的，故可从前面的quicksort中拷贝层数个地址再加上本层活动记录的地址组成新的区头向量。类似地，partition从第2个quicksort过程中拷贝层数个地址再加上本层活动记录地址组成新的区头向量。exchange从partition过程中拷贝层数个地址再加上本层活动记录地址组成新的区头向量。,设有图嵌套调用的情形，下面分另讨论不同之处调用Pi的区头向量的构造情况。 在 Pi中调用Pi，则从P0

31、Pi-1均是Pi可以调用的，因此从上一层Pi的区头向量中拷贝P0Pi-1的地址，加上Pi活动记录的地址组成新的区头向量。在 Pi+1中调用Pi，则从P0Pi-1均是Pi可以调用的，而Pi 和Pi+1不是Pi的外层不要间接调用或不能调用，因此从上一层Pi+1的区头向量中拷贝P0Pi-1的地址，加上Pi活动记录的地址组成新的区头向量。同理，在 Pi+1中调用Pi，拷贝P0Pi-1的地址加上Pi活动记录的地址组成新的区头向量。最后讨论在 Pi+2中调用Pi，则仍然是从P0Pi-1均是Pi的外层，而Pi 、Pi+1和Pi+2不是Pi的外层，因此从上一层Pi+2的区头向量中拷贝P0Pi-1的地址，加上P

32、i活动记录的地址也就组成了所需的区头向量。,综上所述，对于调用第i层的过程只要从前面调用者中拷贝0i-1个地址，加上本数据区的地址组成新的区头向量。这样要在活动记录中增加称之为区头向量的部分，如图所示。 每个过程的d值和过程的层数l在编译时都是可以计算出来的，则四元式call P,n应翻译成： TOP+1 := SP /*保护现行的SP*/ TOP+i+1 :=当前寄存器值 /*保护现场*/ TOP+m-1 :=n /*保存参数个数*/,从调用者的区头向量中拷贝l个单元至进入过程的区头向量中；将TOP+1即新的SP放入区头向量的最后单元，组成新的区头向量。 call P设访问外层变量的层数为l

33、i，则访问外层变量的语句翻译成： x:=SP li+d,或SP li+d:=x 的指令。 图表示执行次序为sortquicksortquicksortpartitionexchange的区头向量变化图。 方法二：在活动记录中增加访问链 在过程的活动记录中增加一个称为访问链的的指针，当过程q在源程序中嵌套p中，则将q中访问链直接指向p。那么执行次序为： sortquicksortquicksortpartitionexchange,具有访问链的存储器栈变化图，如上所示。下面需解决二个问题： (1) 如何建立访问链 (2) 怎样根据访问链获得外层变量 建立访问链也就是在运行时能求过程说明的直接外层

34、。由于主程序没有外层，故编译程序需为进入主程序时，生成置主程序的访问链为空指令。下面讨论执行中过程R（可能为主程序）调用过程S时，怎样求出S的访问链。在编译时R和S的层数都是可以求出分别记为lR和lS。R可以调用S，则S在R的作用域内，可得lSlR+1。当lS = lR+1时，则S是在R内说明的，也就是S是R的直接外层，只要生成将S的访问链置为指向R的SP（或R的访问链）的指令。,当lS = lR时，则S和R是并列的它们具有相同的直接外层，也就是R的外层也就是S的外层，只要生成将R的访问链赋给S的访问链的指令即可。lSlR时，S的直接外层必然在栈中，即R必然被S的直接外层直接或间接调用，否则S

35、不在作用域内。因此，只要对访问链向前搜索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语言的分程序的语法为 说明

36、 语句 也就是在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,%dn”,a,b); /*分程序B2结束*/ /*分程序B3开始*/ int b=3

37、; printf(“%d,%dn”,a,b); /*分程序B3结束*/,printf(“%d,%dn”,a,b); /*分程序B1结束*/ printf(“%d,%dn”,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。 分程序结构也可以用栈式存储分配来实现。因为每个变量作用域也符合先进后出的特点。解决分程序逻辑结构

38、的存储分配，可采用下列二种方法。一是把分看成一个无参过程，用上述过程嵌套的方法来解决。这种过程的特点是只说明一次，也只使用一次，它在分程序前调用，在分程序结束退出，调用外即为说明之处。二是把一个过程体中所需的存储一次全部分配好。由于B2中说明的a和B3中说明的b的作用域不相交，故可分同一块存储空间，如下图所示。,在动态作用域中，进入新的过程时仅当新过程中说明了同名变量时，解释为新的存储。解决动态作用的方法也有二种，一是所谓深访问，它在活动记录中存放一个控制链指向上一级调用过程，也可利用SP指针。当发现非局部变量时从控制链一级一级向前搜索，直至搜索到为止，这种搜索可能深入栈中，因此而得名。搜索的

39、深度取决于程序的运行，而编译时不能决定的。另一种所谓浅访问，它采用体外循环的方法，为每个同名变量的名字分配静态的数据空间，当进入有同名变量的过程时将静态区的同名变量值保存到过程的同名变量的位置上，在过程的整个运行过程中，使用静态区同名变量，过程结束后将先前保存在过程内的变量恢复。两种方法各有优缺点。深访问访问非局部变量是需较长的时间，但它不需要额外的开销。而浅访问可以直接访问非局部变量，但需要一些辅助的时间和空间来维护。,7.2.3 数组的分配和访问 由于静态数组所需空间的大小是在编译时可以计算出来的，因此可在嵌套结构的栈式存储分配中只要为每个数组分直接分配相应的存储空间。下标变量的访问无论是

40、本层变量还是外层变量都可以用前面介绍过的方法翻译成通过基址SP和相对位置访问下标变量的值。 动态数组的所需的空间在运行时才能确定，这样动态数组的存储空间也只能在运行时分配。前面说过编译程序需为内情向量分配了存储空间，然后生成填写内情向量的指令。下面讨论动态数组的空间存放在何处。一种方法是将动态数组的空间存放在堆内存中，此时可以生成为动态数组申请堆存储的指令，并将首地址也填入内情向量中。当访问下标变量时，则编译程序可以生成要根据下标变量的下标和数组的内情向量求出数组元素在堆中的存储位置。,另外，应该注意在过程结束时，还需生成一条将堆内存返回的指令，不然会造成存储器的泄漏。严重时还会造成系统瘫痪。

41、另一种方法也将动态数组的存储空间分配在栈中。当进入嵌套过程时，其活动记录的状态如图(a)所示。此时应填写动态数组的内情向量，TOP+1作为第一个动态数组的首地址。此时该动态数组所需的存储空间可以计算出来了，可在栈顶分配该动态数组的存储空间。并将栈指针指向新的栈顶。如有二个或二个以上的动态数组，则继续为每个动态数组分配内存。以次类推，最后栈指针指向如图(b)中的TOP位置。此方法当过程退出时，则不必生成返回内存的指令，这是因为退出过程时TOP赋的是SP-1，SP赋的是过程中保存的老的SP，指向调用者的活动记录。达到将动态数组分配的内存和原来的活动记录一起返回给栈。,7.3 代码优化 作为一个高级

42、语言的使用者很希望编译程序所产生的代码能够和直接用机器语言编写的程序的效果一样好。但事实上很难做到这一点，即使能做到这一点，也许所需化费实现优化的时间和空间比优化所得到的节省的时间多得多。在这里介绍的代码优化是指对原代码进行变换，从而获得时间和空间效率相对高的程序，而不一定且一般也不是时间和空间最省的程序。在进行优化时应做到： (1) 代码的变换必须保持原程序的语义 (2) 从理论上，变换加快了程序的速度 (3) 这种变换是值得的 如果一种所谓的优化改变了原程序的语义 实际上产生了一个错误程序，这种变换也是无效的。尽管在优化后可能对于一些程序反而比原来增加了开销，但总体来说是节省的，而且节省应

43、达到一个可度量的值，不然优化中的损失不可能在运行中弥补。由于各个机器的指令系统是不同的，即使是相同的四元式程序所生成的“最优”的代码也是不同的.其优化算法也可能是不同的。为了算法的一致性在这里仅讨论与目标机器无关的优化算法。,一个程序的优化是由下面两个阶段构成的： (1) 局部优化：应用于仅包括少量语句的小程序的优化变换。 (2) 全局优化：应用于一个程序单元，如一个函数或一个过程的优化变换。 7.3.1 优化变换 程序的执行效率是可以通过地编译期优化变换是重写程序段以提高程序的工作效率而不改变语义。虽然变换的方法很多但常用的大致有下列几种： 1. 编译求值 一般来说程序的目标代码可能要运行多

44、次，而编译只编译一次。如果一些原属于执行时完成的工作能在编译时解决，则提前完成这些工作。如在计算sin(3.1415927/6)时，3.1415927/6的值在编译时可以计算的，其值为0.523598783，运行时只要执行sin(0.523598783)。因此程序的执行效率是可以通过地编译期间完成程序中的执行语义来提高的。这时编译程序消除了程序在执行时的需求，从而达到减少程序的执行时间、提高程序的工作效率。编译时的求值却体现了这一点。,2. 合并运算 设有程序段： x:=a+b+c+d; if a+b0 then ; y:=(a+b)*(b+c)+d; 则子表达式a+b在不同的表达式中均使用过

45、，因此只要计算一次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

46、） （2）（+,a,t1,t2） （3）（-, t2,c,t3） （4）（+,t1,d,t4） （5）（/, t3,t4,t5） （6）（-, t2,t5,t6）,3. 删除死码 如果能在程序中删除其代码而不影响程序的运行结果的代码被称为“死码”，“死码”可以通过程序的控制流来获得，如条件语句： if x3 then if x，而x在程序的其它处从未被引用过，显然x:=也为“死码”。删除这种“死码”时应注意，只有当的执行不会产生副作用时可以删除，也就是它不包含函数或过程，即使含有函数但没有函数的副作用，才能删除它。,4. 减少频率 减少频率是指程序中执行频率高的程序段移至程序执行频率低的程序部

47、分中。其主要变换有相对循环不变量的内码外提。如程序段： 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 试写循环外提后的四元式序列。 根据题意，可

48、写出循环语句的四元式序列为： （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

49、,_,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. 强度削弱和变换循环条件 强度削弱是指用一个运算速度较快的运算符代替耗时较多的运算符，也就是将强度高的运算符削减为低强度的运算符。如：X2写成X*X，2*X写成X+X。 在循环中的强度削弱方法为： (1)

50、 设循环变量为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循环中的数组引用ai,j的地址，这样就造成了高强度的运算i*n(按行存放)，用上述方法就可以大地降低运算的强度。但需要注意的是这种方法不能适用于下标变量允许为实数（浮点数）类型，这是因为实数在累加时会

51、产生积累误差，最后的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); t

52、2:=g(z); 则改写为： t1:=f(x); t2:=g(x);,7.3.2 局部优化 局部优化所需的化费相对较低，也就从优化所得到的收益也相对较低。局部优化顾名思义只是在较小的程序段中进行优化，从而达到优化的目的。这种程序段称为“基本块”。 定义7.4 基本块是指程序中的一语句的顺序序列(S1,S2, Sn)，其中只有第一个语句(S1)允许有是程序的控制语句转移的目的语句和最后一个语句(Sn)允许是一个控制转移语句。 基本块划分算法： (1) 求出称为入口的基本块的第一个语句，如：程序的第一个语句或有控制语句转入的语句。 (2) 对于每一入口语句构造其所属的基本块： 1)由入口语句到下一

53、入口语句的前一语句 2)由入口语句到一转移语句 3)由入口语句到一停语句 (3) 对于未被划入任一基本块的语句，为通过任何基本块都不能到达该语句，故为无用语句应删除。,对于基本块内的公共子表达式的删除，可采用计算出每项个定值的四元式编号，当两个子表达式完全相同时，则它们具有相同的定值的四元式编号，表示在二个四元式之间没有新的定值。 为了简单起见。在基本块内将四元式编号以1开始的连续号码编号。由于一个被定值的变号与被定值的变量有关，则在符号表中的每一变量增加一个称为定值编号的属性。设有(n) A:=B op C，其中n为对A定值的四元式编号，B、C为变量，op为运算符。在符号表中需保存每个变量定

54、值的位置n，对尚未定值的变量符号表中的定值编号的属性以0表示。另外建立一四元式的符号表，为每个四元式的运算对象上都上都附加一个定值信息来指出该运算对象，这些信息也用四元式的编号表示。,再为每个四元式保存一个引用信息表示是否要为程序中的其它处引用而保留其值，其初值为false。当设表达式e是e的子表达式，在翻译是时形成了关于e的四元组时，其运算对象所关联的定值信息可从符号表中获得。将新产生的四元式和四元式符号表中现有的四元式比较，如果存在一个登记项为k的与新的四元组完全匹配的四元式，则说明其值与新的表达式的值完全相同，也就是新的四元式不必存放在四元式符号表中，用四元式符号表k的结果名代替e中的对

55、象，并对四元式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)进

56、入时，如图(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，

57、并将定值位置k与a相关联用-k表示。当生成一个四元组是，如果每个运算对象都是一个常量或是一个负的定值位置时，就可以实常量合并。 例:将上例中加入用合并常量算法 加入用合并常量算法后其结果，如图所示。,7.3.3 全局优化 要产生高效的代码，编译程序仅在基本块内优化是不够的。编译程序应把程序作为一整体来考虑，对各个基本块的信息进行数据流的分析从而达到优化的目的。全局优化和局部优化相比，全局优化需要更多的分析，以便确定优化的可行性。这里仅介绍全局子表达式的消除，包括公共表达式的消除和死代码的消除。 设有子表达式存在于程序的若干基本块中，记为SB = bi|bi是基本块。设子表达式存在于程序的一组基

58、本块中，且在某个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的最后一个语句转向基本

59、块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不再包括对表达式中的运算对象的赋值称子