1、 第6章 运行时存储空间组织6.1 静态存储分配静态存储分配 6.2 简单的栈式存储分配简单的栈式存储分配 6.3 嵌套过程语言的栈式实现嵌套过程语言的栈式实现 6.4 堆式动态存储分配堆式动态存储分配*6.5 参数传递补遗参数传递补遗 习题六习题六 6.1 静态存储分配静态存储分配如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址，存储空间的这种分配方法叫做静态分配。对FORTRAN语言来说，其特点是不允许过程有递归性，每个数据名所需的存储空间大小都是常量(即不允许含可变体积的数据，如可变数组)，并且所有
2、数据名的性质是完全确定的(不允许出现在运行时再动态确定其性质的名字这种情况)。这些特点确保整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。静态存储分配是一种最简单的存储管理。一般而言，适于静态存储分配的语言必须满足以下条件：(1)数组的上下界必须是常数；(2)过程调用不允许递归；(3)不允许采用动态的数据结构(即在程序运行过程中申请和释放的数据结构)。满足这些条件的语言除了FORTRAN之外，还有BASIC等语言。在这些语言中，编译程序可以完全确定程序中数据项所在的地址(通常为相对于各数据区起始地址的位移量)。由于过程调用不允许递归，因此数据项的存储地址
3、就与过程相联系。过程调用所使用的局部数据区可以直接安排在过程的目标代码之后，并把各数据项的存储地址填入相关的目标代码中，以便在过程运行时访问这个局部数据区。在此，不存在对存储区的再利用问题，目标程序执行时不必进行运行时的存储空间管理，过程的进入和退出变得极为简单。FORTRAN语言的静态存储管理特点是FORTRAN程序中的各程序段均可独立地进行编译。在编译过程中，给程序中的变量或数组分配存储单元的一般做法是：为每一个变量(或数组)确定一个有序的整数对；其中，第一个整数用来指示数据区(局部数据区或公用区)的编号，第二个整数则用来指明该变量(或数组)所对应的存储起始单元相对于其所在数据区起点的位移
4、(即相对于数据区起点的地址)，并将这一对整数填入符号表相应登记项的信息栏中。至于各数据区的起始地址在编译时可暂不确定，待各程序段全部编译完成之后，再由连接装配程序最终确定，并将各程序段的目标代码组装成一个完整的目标程序。一个FORTRAN程序段的局部数据区可由图61所示的项目组成。其中，隐参数是指过程调用时的连接信息(不在源程序中明显出现)，如调用时的返回地址、调用时寄存器的保护等；形式单元用来存放过程调用时形参与实参结合的实参地址或值。图61 一个FORTRAN程序段的局部数据区 6.2 简单的栈式存储分配简单的栈式存储分配我们首先考虑一种简单程序语言的实现，这种语言没有分程序结构，过程定义
5、不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。例如，C语言除不允许含有可变数组外，就是这样一种语言。C语言的程序结构如下：全局数据说明void main()main中的数据说明 void R()R中的数据说明void Q()Q中的数据说明 例如，下面计算n！的C语言程序就是一个递归调用的程序，它的执行过程可以用栈来实现：#include“stdio.h”long factorial(int n)if(n1)return(n*factorial(n1);elsereturn(1);void main()int num;doscanf(“%d”,&num);if(num=0&num=0)
6、;6.2.1 栈式存储分配与活动记录栈式存储分配与活动记录使用栈式存储分配法意味着程序运行时，每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶，此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等；在进入过程和执行过程的可执行语句之前，再把局部数组所需空间累筑于栈顶，从而形成过程工作时的完整数据区。注意，每个过程的活动记录的体积在编译时可以静态地确定。但由于允许含有可变数组，所以数组的大小只有在运行时才能知道。因数组区的大小不能预先获知，为了扩充方便，所以只能将数组区累筑于活动记录之上的当前栈顶。当一个过程工作完毕返回时，它在栈顶的数据区(包括活动记录和数组区)
7、也随即不复存在。对C语言来说，由于其不含可变数组，因而它的活动记录本身包含了局部数组的空间。图62和图63分别给出了C语言和含可变数组的某简单语言程序运行时的数据空间结构，即显示了主程序在调用了过程Q，Q又调用了过程R，且在R投入运行后的存储结构。SP指示器总是指向执行过程活动记录的起点，而TOP指示器则始终指向(已占用)栈顶单元。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端；在分配数组区之后(如果有的话)，TOP又改为指向数组区(从而是该过程整个数据区)的顶端。图62 C语言程序的存储组织 图63 含可变数组程序的存储组织 C的活动记录含有以下几个区段(如图64所示)：(1)连接
8、数据(两项)：老SP值(即前一活动记录的起始地址)和返回地址；(2)参数个数；(3)形式单元(存放实在参数的值或地址)；(4)过程的局部变量(简单变量)、数组的内情向量和临时工作单元。C语言不允许过程(函数)嵌套，也即不允许一个过程的定义出现在另一个过程的定义之内。因此，C语言的非局部变量仅能出现在源程序头，非局部变量可采用静态存储分配并在编译时确定它们的地址。图64 C过程的活动记录 由图64可知，过程的每一局部变量或形参在活动记录中的位置都是确定的；也就是说，这些变量或形参所分配的存储单元其地址都是相对于活动记录的基址SP的。因此，变量和形参运行时在栈上的绝对地址是：绝对地址=活动记录基址
9、(SP)+相对地址于是，对当前正在执行(即活动)的过程，其任何局部变量或形参X的引用均可表示为变址访问XSP。此处X代表X相对于活动记录基址的偏移量，这个偏移量(即相对数)在编译时可完全确定下来。过程的局部数组的内情向量的相对地址在编译时也同样可完全确定下来，一旦数据空间在过程里获得分配，对数组元素的引用也就容易用变址的方式进行访问。6.2.2 过程的执行过程的执行1过程调用过程调用的四元式序列为 par T1 par T2 par Tn call P,n 由于此时TOP指向被调用过程P之前的栈顶，而P的形式单元和活动记录起点之间的距离是确定的(等于3，参见图64)，因而由调用者过程给将要调用
10、的过程P的活动记录(正在形成中)的形式单元传递实参值或实参地址，即每个par Ti(i=1,2,n)可直接翻译成如下指令：(i+3)TOP=Ti /传递参数值 或 (i+3)TOP=addrTi /传递参数地址 而四元式call P,n则翻译成：1TOP=SP /保护现行SP 3TOP=n /传递参数个数 JSR P /转子指令，转向P过程的第一条指令 过程P调用之前，先构造出P的活动记录部分内容，如图65所示。图65 过程P调用前先构造P的活动记录部分内容 2过程进入转入过程P后，首先要做的工作是定义新活动记录的SP，保护返回地址和定义新活动记录的TOP值，即执行下述指令：SP=TOP+1
11、/定义新SP 1SP=返回地址 /保护返回地址 TOP=TOP+L /定义新TOP 其中，L是过程P的活动记录所需的单元数，这个数在编译时可静态地计算出来。对含可变数组(非C语言)的情况来说，因为过程可含可变数组且所有数组都分配在活动记录的顶上，所以紧接上述指令之后应是对数组进行存储分配的指令(如果含有局部数组)，这些指令是在翻译数组说明时产生的。对每个数组说明，相应的目标指令组将做以下几件工作：(1)计算各维的上、下限；(2)调用数组空间分配子程序，其参数是各维的上、下限和内情向量单元首地址。数组空间分配子程序计算并填好内情向量的所有信息，然后在TOP所指的位置之上留出数组所需的空间，并将T
12、OP调整为指向数组区的顶端。进入过程P后所做的工作如图66所示。图66 进入过程P后所做的工作示意 3过程返回C语言以及其它一些相似的语言含有return(E)形式的返回语句，其中E为表达式。假定E值已计算出来并存放在某临时单元T中，则此时即可将T值传送到某个特定的寄存器中(调用过程将从这个特定的寄存器中获得被调用过程P的结果)。剩下的工作就是恢复SP和TOP为进入过程P之前的原值(即指向调用过程的活动记录及工作空间)，并按返回地址实行无条件转移，即执行下述指令序列：TOP=SP1 /恢复调用过程的TOP值 SP=0SP /恢复调用过程的SP值 X=2TOP /将返回地址送X UJ 0X /无
13、条件转移，即按X的地址返回到调用过程 一个过程也可通过它的end语句(对C语言则是该过程(函数)体结束时的“”)自动返回。如果此过程是一个函数过程，则按上述办法传递结果值，否则仅直接执行上述返回指令序列。过程P的返回示意如图67所示。图67 过程P的返回示意 6.3 嵌套过程语言的栈式实现嵌套过程语言的栈式实现6.3.1 嵌套层次显示嵌套层次显示(DISPLAY)表和活动记录表和活动记录在讨论中，常常要用到过程定义的“嵌套层次”(简称层数)这个概念。我们始终假定主程序的层数为0，因此主程序称为第0层过程。如果过程Q是在层数为i的过程P内定义的，并且P是包围Q的最小过程，则Q的层数就为i+1。当
14、编译程序处理过程说明时，过程的层数将作为过程名的一个重要属性登记在符号表中。一种常用的跟踪每个外层过程最新活动记录位置的有效办法是，每进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次DISPLAY表。假定现在进入的过程层数为i，则它的DISPLAY表含有i+1个单元。此表本身是一个小栈，自顶而下每个单元依次存放着现行层、直接外层直至最外层(第0层，即主程序层)的每一层的最新活动记录的起始地址。例如，令过程R的外层为Q，Q的外层为主程序P，则过程R运行时的DISPLAY表内容如表6.1所示。表 6.1 过程 R 运行时的 DISPLAY 表 2 R 的现行活动记录的起始地址(SP 的现
15、行值)1 Q 的最新活动记录的起始地址 0 P 的活动记录的起始地址 由于过程定义是嵌套的，因而一个过程可以引用包围它的任一外层过程所定义的变量或数组。也就是说，运行时，一个过程Q可能引起它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有外层的最新活动记录的起始地址。由于允许递归和可变数组的存在，过程的活动记录位置（即使是相对位置）也往往是变迁的，因而必须设法跟踪每个外层过程的最新活动记录的位置（起始地址）。例如，下面的PASCAL程序其活动记录在栈中的示意如图6-8所示（调用顺序为：envabcbc）。图6-8 活动记录在栈中的示意 图69 活动记录结构 6.3
16、.2 嵌套过程的执行嵌套过程的执行1过程调用过程调用所做的工作与简单栈式存储分配大体相同，只是增加了一个连接数据，所以每个par Ti 相应的指令应改为 (i+4)TOP=Ti 或者 (i+4)TOP=addrTi call P,n所对应的指令应为1TOP=SP /保护现行SP 3TOP=SP+d /将直接外层的DISPLAY表起始地址作为P的全局DISPLAY表地址4TOP=n /传递参数个数 JSR P /转向P的第一条指令 2过程进入转入过程P后，首先执行和简单栈式存储分配相同的指令：SP=TOP+1 /定义新的SP 1SP=返回地址 /保护返回地址 TOP=TOP+L /定义新的TOP
17、其次，应按第三项连接数据所提供的全局DISPLAY表地址，自下而上地抄录k个单元内容(k为P的层次)，最后再添上新的SP值形成现行过程P的DISPLAY表(共k+1个单元)。其过程如图610所示。图610 过程P进入示意 3过程返回当过程P工作完毕要返回到调用段时，若return语句含有返回值或P是函数过程，则把已算好的值传送到某个特定的寄存器，然后执行：TOP=SP1 /恢复调用过程的TOP值 SP=0SP /恢复调用过程的SP值 X=2TOP /将返回地址送X UJ 0X /无条件转移，返回过程返回执行的指令与简单栈式存储分配的过程返回完全一样。6.3.3 访问非局部名的另一种实现方法访问
18、非局部名的另一种实现方法在允许嵌套的过程中，一个过程可以引用包围它的任一外层过程所定义的变量或数组；也即在运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据(这些数据视为过程Q的非局部量)。为了在活动记录中查找非局部名字所对应的存储空间，过程Q运行时必须知道它的所有外层过程的最新活动记录的地址。因为过程活动记录的位置(即使是相对位置)往往也因过程的递归而变迁，所以必须设法跟踪每个外层过程的最新活动记录的位置。跟踪的一种有效办法是采用嵌套层次显示(DISPLAY)表，其优点是访问非局部量的速度较快。在此，我们介绍另一种访问非局部名的方法存取链(也称静态链)方法。存取链方法引入
19、一个称为存取链的指针，该指针作为活动记录的一项指向直接外层的最新活动记录的地址，这就意味着在运行时栈中的每个数据区(活动记录)之间又拉出一条链，这个链称为存取链。注意，运行时栈中数据区之间原先就存在一条链，即每个活动记录中所保存的老SP值这一项，它是指向调用该过程(子过程)的那个过程(父过程)的最新活动记录的起点，由此向前形成了一条SP链。为了区别于存取链，称SP链为控制链(也称动态链)，它记录了在运行中过程之间相互调用的关系。注意，控制链是动态的，而存取链是静态的。控制链记录了当前时刻程序中各过程相互调用的情况；而存取链则始终记录着程序静态定义时该过程所有的直接外层(嵌套过程规定，内层过程只
20、允许调用其静态定义时的外层过程说明的变量和数组)。因此，存取链指出了一个过程的当前活动记录指向其直接定义的外层过程直至最外层的最新活动记录的起点。具有存取链的活动记录结构如图611所示。图611 具有存取链的活动记录结构 假定过程的嵌套关系如下：P:var a;Q(b);var i;R;var c,d;call R;S;var c,i;call Q;call S;程序中每个过程的静态结构(嵌套层次)是确定的，如嵌套深度为2的过程R引用了非局部量a和b，其嵌套深度分别为0和1。从R的活动记录开始，分别沿着20=2和21=1个存取链向前查找，则可找到包含这两个非局部量的活动记录。上述过程P调用S以
21、及S调用Q运行时栈的变化过程如图612(a)、(b)所示。由图612可以看出，指针SP总是指向当前正在执行过程的活动记录起点，控制链(老SP)则指向调用运行过程的父过程的活动记录起点。因此，当运行过程调用结束返回时，利用控制链老SP值可以得到调用前原父过程活动记录的起点。从程序的静态结构来看，P是S和Q的静态直接外层，因此，S和Q活动记录中的存取链均指向其直接外层P的活动记录起点。图612 过程调用时运行栈的变化(a)P调用S；(b)S调用Q 例6.1 某程序的结构如图613所示，其中A、B、C为过程名，请分别画出过程C调用A前后的栈顶活动记录。图613 例6.1的程序结构示意 解答 过程C调
22、用A前后的栈顶活动记录示意如图614所示。由图613可知，当过程C执行时，它可使用主程序、A、B和C过程所说明的变量，且其外层嵌套的过程活动记录起始地址由DISPLAY表指出。当C调用A而使过程A执行时，我们看到此时的DISPLAY表已变为两项，即主程序和A过程自身；也即此时A只可使用主程序和A过程所说明的变量。图614 例6.1的运行栈与活动记录示意 例6.2 在下面的PASCAL程序中，已经第二次(递归地)进入了f，请给出第三次进入f后的运行栈及DISPLAY表的示意图。PROGRAM test(input,output);VAR K:integer;FUNCTION f(n:intege
23、r):integer;BEGIN IF n=0 THEN f:=1 ELSE f:=n*f(n1)END;BEGIN K:=f(10);write(K)END.解答 第三次进入f后的运行栈及DISPLAY表的示意图如图614所示。由于静态嵌套层次只有两层，故每一次递归调用产生的DISPLAY表只有两项，一项是test的SP(即0)，另一项是当前活动记录的SPi(i=1,2,3)。图615 例6.2的运行栈及DISPLAY表示意图 6.4 堆式动态存储分配堆式动态存储分配6.4.1 堆式存储的概念堆式存储的概念如果一种程序语言允许数据对象能够自由地分配和释放，或者不仅有过程而且有进程(Proce
24、ss)这样的程序结构，那么由于空间的使用不一定遵循“先申请后释放”的原则，则栈式存储分配就不适用了。在这种情况下，通常使用一种称之为堆的动态存储分配方案。假定程序运行时有一个大的存储空间，需要时就从这个空间中借用一块，不用时再退还给它。由于借、还的时间先后不一，因而经过一段时间的运行后，这个大空间就必然被分割成如图616所示的许多小块，这些块有些正在使用，有些则是空闲的(未被使用)。图616 堆式存储分配示意 对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间的回收，由于返回堆的不用空间是按任意次序进行的，所以需要研究专门
25、的回收分配策略。在许多语言中都有显式的堆空间分配和回收语句或函数，如PASCAL语言中的new和dispose、C语言中的alloc和free以及C+语言中的new和delete。6.4.2 堆式存储管理的方法堆式存储管理的方法由于堆式分配方式和存储管理技术较为复杂，并且有效的堆管理是数据结构课程研究的问题，故我们只对堆式分配方式作简单的讨论。当运行程序要求一块体积为N的存储空间时应如何分配？从理论上讲，这时应从比N稍大一些的空闲块中取出N个单元予以分配，这种做法的目的是保持较大的空闲块以备将来之需。但这种方法实现起来难度较大，实际中采用的办法是：扫描空闲块链并在首次遇到的比N大的空闲块中取出
26、N个单元进行分配。如果找不到一块比N大的空闲块，但所有空闲块的总和却比N大，这时就需要用某种方法使这些空闲块拼接在一起，形成一个可分配的连续空间。如果所有空闲块的总和都不及N大，则需要采用更复杂的办法，如废品回收技术(即寻找那些运行程序已不使用但仍未释放的存储块或运行程序目前很少使用的存储块)，把这些存储块回收后再重新分配。可以采用多种策略进行堆式动态存储管理。在此，我们介绍一种使用可利用空间表进行动态分配的方法。可利用空间表是指将所有空闲块用一张表记录下来，表的结构可以是目录表，也可以是链表，其结构分别如图617(b)、(c)所示。图617 内存状态和可利用空间表(a)内存状态；(b)目录表
27、；(c)链表 使用可利用空间表进行动态存储分配的方法又可分为如下两种：(1)定长块的管理。最简单的堆式存储管理方法是采用定长块的管理方法，即将堆存储空间在初始化时就划分成大小相同的若干块，将各个块通过链表链接起来形成一个单向线性链表。由于各块大小相同，故分配时无需查找，只需将头指针所指的第一块分配给用户即可，然后头指针指向下一块。同样，当回收时，系统将待回收的存储块插入到表头即完成了该块的回收。(2)变长块的管理。变长块管理方法是一种常用的堆式存储管理方法，它可以根据实际需要来分配长度不同的空闲块；对空闲块的管理则可以采用图617(c)中的链表形式。系统开始时，存储空间是一完整空间，可利用空间
28、表中只有一个大小为整个存储空间的空闲块。在系统运行一段时间后，随着分配和回收的进行，可利用空间表中空闲块的大小和个数也随之改变。由于可利用空间表中的空闲块大小不同，因而存在着如何进行空闲块分配的问题。若可利用空间表存在多个大于所要求空间的空闲块，可采取以下三种方法之一进行存储分配：(1)首次满足法。从表头开始查找可利用空间表，将找到的第一个满足需要的空闲块或空闲块的一部分分配出去(当空闲块略大于所要求的空间时，则整块分配出去)，而其余部分仍作为一个空闲块留在表中。(2)最优满足法。系统扫描整个可利用空间表，从中找出一块不小于要求的最小空闲块予以分配。为了避免每次分配都要扫描整个表，通常将空闲块
29、按由小到大的顺序进行排列。这样，所找到的第一个大于或等于所需空间的空闲块即为所求，无须再扫描整个表。(3)最差满足法。系统将可利用空间表中最大的空闲块予以分配(当然也要求其不小于所需空间的大小)，这种方法应使空闲块按由大到小的顺序排列，此时表头的空闲块即为所求。最优满足法和最差满足法在回收时都需将待回收的空闲块插入到链表中适当的位置上去。以上三种方法各有所长。一般来说，最优满足法适用于请求分配的内存大小范围较广的系统；最差满足法适用于请求分配的内存大小范围较窄的系统；而首次满足法则适用于事先无法获知请求分配和回收情况的系统。从时间上来看，最优满足法无论分配与回收都需要查表，故最费时间；最差满足
30、法分配时无需查表，但回收时却需查表并根据回收空闲块的大小确定其在表中应插入的位置；而首次满足法在分配时需要查表，回收时直接插入到表头即可。对于已分配的存储块，可以采用不同的回收策略。有的程序语言干脆不做回收工作，直到内存空间用完为止；如果当空间用完时还有分配存储块的请求，就停止程序的运行。这样做的缺点是浪费空间，但如果系统具有海量虚存或堆中的多数数据是一分配就一直使用的情形，则这种方法也是可行的。如果程序语言有显式的分配命令，那么就可用显式的回收命令(如C语言中的free)来回收不用的空间。*6.5 参数传递补遗参数传递补遗定义和调用过程是程序语言的主要特征之一。过程是模块程序设计的主要手段，
31、同时也是节省程序代码和扩充语言能力的主要途径。PASCAL语言的设计者N.Wirth曾经说过：“在程序设计技巧中，过程是很少几种基本工具中的一种，掌握了这种工具，就能对程序员工作的质量和风格产生决定性的影响。”一个过程一旦定义后，就可以在别的地方调用它。调用与被调用(过程)两者之间的信息往来通过全局量或参数传递。例如，下面的C语言程序：#include“stdio.h”void showme(int a,int b,int c)printf(“a=%d,b=%d,c=%dn”,a,b,c);void main()int x=10,y=20,z=30;showme(z,y,x);就是一个含函数调
32、用的程序。其中a、b、c称为形式参数(简称形参)，而函数调用语句：showme(z,y,x)中的z、y、x则称为实在参数(简称实参)。实参甚至也可以是一个较复杂的表达式而不仅仅只是一个变量。实参和对应的形参在性质上应相容不悖。6.5.1 参数传递的方法参数传递的方法1传值传值是最简单的参数传递方法。所谓传值，就是计算出实在参数的值然后把它传给被调用过程相对应的形式参数，具体过程如下：(1)把形式参数当作过程的局部变量处理，即在被调用过程的活动记录中开辟形式参数的存储空间(即形式单元)。(2)调用过程计算出实在参数的值，并将该值放入为形式单元开辟的空间中。(3)被调用过程执行时就像使用局部变量一
33、样使用这些形式单元。传值的一个重要特点是对形式参数的任何运算都不影响调用过程的活动记录中实在参数的值，即参数传递后实在参数与对应的形式参数不再发生联系了。2传地址传地址所谓传地址，是指把实在参数的地址传递给相应的形式参数所对应的形式单元。如果实在参数是一个变量(包括下标变量)，则直接将该变量的地址传给相应的形式单元；如果实在参数是常数或表达式，则先计算其值并存放在某一临时单元中，然后将这个临时单元的地址传给相应的形式单元。被调用过程执行时，对形式参数的任何引用或赋值都被处理成对形式单元的间接访问，即按形式单元中存放的地址转到调用过程的活动记录中去访问实在参数。对形式参数的任何运算实际上都是对实
34、在参数的运算，而形式参数只不过起到辅助查找到实在参数的指针的作用。因此，当被调用过程工作完毕返回时，形式单元所指的实在参数单元就保留了运算的结果。3传名传名是高级语言ALGOL 60所定义的一种特殊的参数传递方式，其传递参数的方法如下：(1)过程调用的作用相当于把被调用过程的过程体复制到调用处(替换调用语句)，并将过程体中所有出现的形式参数在文字上替换成相应的实在参数。这种文字上的替换称为宏扩展(Marcro Expansion)。(2)被调用过程中的局部名如果与过程调用的实在参数名发生冲突，则在宏扩展前对被调用过程中的这些局部名重新命名以避免重名冲突。(3)为表现实在参数的整体性，必要时在替
35、换前把实在参数用括号括起来。传名这种参数传递方法因其操作过于复杂现在已很少采用。6.5.2 不同参数传递方法的比较不同参数传递方法的比较为了描述不同参数传递方法下程序的执行，我们将动态栈和活动记录结合起来简化为一种动态图。采用动态图的方法来对程序的执行进行描述时，记录主程序和过程(或函数)的调用、运行及撤消各个阶段的状态，以及程序运行期间所有变量和过程(或函数)中传值与传地址的变化过程。动态图规则如下：(1)动态图纵向描述主程序、过程或函数各层之间的调用关系，横向由左至右按执行的时间顺序记录主程序、过程(或函数)中各变量值的变化情况。(2)过程(或函数)的传值的形式参数均看作是带初值的局部变量
36、(也可用箭头来表示实在参数传给形式参数的指向)，其后，形式参数就作为局部变量参与过程(或函数)的操作。对于传地址方式，由于形式参数的作用就像指向实在参数的指针，故动态图中形式参数一律指向与其对应的实在参数变量(注意，两者位于动态图相邻的两层上；如果实在参数为表达式，则用一个临时变量来代表这个表达式)；此后，所有对形式参数的操作都是根据形式参数箭头所指对实参变量进行的。(3)主程序，过程(或函数)按运行中的调用关系由上向下分层，各层(相当于活动记录)说明的变量(包括形式参数)都依次列于该层首列，各变量值的变化情况按时间顺序记录在与该变量对应的同一行上。以下面的程序为例，对三种参数传递方法进行比较
37、：program parament;int A,B；procedure P(x,y,z);Y=Y+1;Z=Z+X A=2;B=3;P(A+B,A,A);print A (1)传值：用T代表A+B的临时变量，则对图618所示的动态图分析得A=2。(2)传地址：用T代表A+B的临时变量，则对图619所示的动态图分析得A=8。图618 传值时的动态图 图619 传地址时的动态图 (3)传名：由于传名时的过程调用就是把过程体抄到调用出现的地方，所以实际执行的程序为A=2;B=3;A=A+1;/形参Y换成A A=A+(A+B);/形参Z换成A，形参X换成(A+B)print A经分析得A=9。不同的参数
38、传递方法得到的结果不同，因此，如何选择参数传递的方法将影响语言的语义，这是编译程序在处理参数传递时应引起重视的问题。习习 题题 六六6.1 完成下列选择题：(1)分配目标程序数据空间的基本策略分为 。A栈式分配和堆式分配 B局部分配和整体分配 C静态分配和动态分配 D程序运行之前分配 (2)过程的DISPLAY表中记录了 。A.过程的连接数据 B.过程的嵌套层次C.过程的返回地址 D.过程的入口地址(3)过程P1调用P2时，连接数据不包含 。A.嵌套层次显示表 B.老SP值 C.返回地址 D.全局DISPLAY表地址 D.程序中允许有递归定义的过程,也允许有嵌套定义的过程 (7)两个不同过程的
39、活动，其生存期是_。A重叠且不嵌套 B不重叠却嵌套 C重叠且嵌套 D不重叠也不嵌套 (8)编译的动态存储分配含义是_。A在运行阶段对源程序中的各种变量、常量进行分配 B在编译阶段对源程序中的各种变量、常量进行分配 C在编译阶段对源程序中的各种变量、常量进行分配，在运行时这些各种变量、常量的地址可以根据需要修改 DAC都不是 6.2 何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？6.3 (1)写出实现一般递归过程的活动记录结构以及过程调用、过程进入与过程返回的指令；(2)对以return(表达式)形式(这个表达式本身是一个递归调用)返回函数值的特殊函数过程，给出不增加时间开销但能节省
40、存储空间的实现方法。假定语言中过程参数只有传值和传地址两种形式。为便于理解，举下例说明这种特殊的函数调用：int gcd(int p,int q)if(p%q=0)return q;else return gcd(q,p%q)6.4 有一程序如下：program ex;a:integer;procedure PP(x:integer);begin:x:=5;x:=a+1end;begina:=2;PP(a);write(a)end.试用图表示ex调用PP(a)前后活动记录的过程。6.5 类PASCAL结构(嵌套过程)的程序如下，该语言的编译器采用栈式动态存储分配策略管理目标程序数据空间：pro
41、gram Demo procedure A;procedure B;begin(*B*)if d then B else A;end;(*B*)begin(*A*)Bend;(*A*)begin(*Demo*)A end.(1)若过程调用序列为 DemoA；DemoAB；DemoABB；DemoABBA；请分别给出这四个时刻运行栈的布局和使用的DISPLAY表；(2)若该语言允许动态数组，编译程序应如何处置？如过程B有动态局部数组Rm:n，请给出B第1次激活时相应的数据空间的情况。6.6 下面程序的结果是120。但是如果把第5行的abs(1)改成1的话，则程序结果为1。试分析为什么会有两种不同的结果。int fact()static int i=5;if(i=0)return(1);else i=i1;return(i+abs(1)*fact();void main()printf(factor or 5=%dn,fact();
