第十章第十章 存储组织存储组织10.1 概述概述10.2 数据空间的管理数据空间的管理10.3 栈式动态存储分配的实现栈式动态存储分配的实现10.4 参数传递参数传递10.5 跟过程相关的语义分析跟过程相关的语义分析110.1 概述概述操操作作系系统统分分配配给给目目标标程程序运行所需的序运行所需的内存空间内存空间此此内内存存空空间间的的具具体体使使用用由由编编译译程程序序在在语语义义分分析析阶段确定阶段确定此此内内存存空空间间分分为为两两大大部部分：代码段、数据段分：代码段、数据段数据段包括数据段包括（P231P231）210.2 数据空间的使用方法数据空间的使用方法存储分配策略：存储分配策略： 静态存储分配静态存储分配 栈式动态存储分配栈式动态存储分配 堆式动态存储分配堆式动态存储分配3静态存储分配静态存储分配特点特点编译时刻确定存储位置编译时刻确定存储位置编译时刻确定存储位置编译时刻确定存储位置访问效率高访问效率高访问效率高访问效率高主要用途主要用途子程序的目标代码段子程序的目标代码段子程序的目标代码段子程序的目标代码段全局数据目标（全局变量）全局数据目标（全局变量）全局数据目标（全局变量）全局数据目标（全局变量）10.2 10.2 数据空间的使用方法数据空间的使用方法数据空间的使用方法数据空间的使用方法4栈式存储分配栈式存储分配把程序看作由多个把程序看作由多个过程过程（子程序、函数等）组成（子程序、函数等）组成每进入一个每进入一个过程过程，在栈顶，在栈顶为它分配所需的数据空间；为它分配所需的数据空间；当一个当一个过程过程工作完毕之后，工作完毕之后，相应的数据空间将被释放。相应的数据空间将被释放。运行栈图示运行栈图示10.2 10.2 数据空间的使用方法数据空间的使用方法数据空间的使用方法数据空间的使用方法过程过程1 1过程过程2 2过程过程3 3过程过程0 05堆式存储分配堆式存储分配用于动态数据结构用于动态数据结构存储空间的动态分配和释放存储空间的动态分配和释放实现方法：实现方法： 将将内内存存空空间间分分为为若若干干块块，根根据据用用户户要要求求分配分配无无法法满满足足时时，调调用用无无用用单单元元收收集集程程序序将将被释放的块收集起来重新分配被释放的块收集起来重新分配10.2 10.2 数据空间的使用方法数据空间的使用方法数据空间的使用方法数据空间的使用方法6对过程的语义处理对过程的语义处理过程说明的翻译过程说明的翻译计算实在参数、返回值的空间计算实在参数、返回值的空间计算实在参数、返回值的空间计算实在参数、返回值的空间过程体的翻译过程体的翻译计算局部变量、临时变量的空间计算局部变量、临时变量的空间计算局部变量、临时变量的空间计算局部变量、临时变量的空间10.3 栈式动态存储分配的实现栈式动态存储分配的实现过程的过程的活动记录活动记录AR（ Activation Record ）一段连续的存储区，用以存放过一段连续的存储区，用以存放过程的程的一次执行一次执行所需的信息。所需的信息。7程序由过程组成程序由过程组成，当过程当过程被激活被激活时时，在运行栈，在运行栈的栈顶设置相应的的栈顶设置相应的AR：临时值：例临时值：例如计算表达式时的中间工作单元。如计算表达式时的中间工作单元。局部变量局部变量（数据）（数据）保存运行过程前的状态（程序计数器，寄存保存运行过程前的状态（程序计数器，寄存器值器值）存取链存取链（可选）：（可选）：对于非局部量的引用。对于非局部量的引用。控制链控制链(老老SP)（可选）：可选）：指向调用者的指向调用者的AR。实参（形式单元）实参（形式单元）返回值（对函数），有时可使用寄存器存放返回值（对函数），有时可使用寄存器存放返回值返回值返回地址：保存该被调过程返回后的地址返回地址：保存该被调过程返回后的地址8 简单语言的分配方案简单语言的分配方案语言的结构特点：语言的结构特点：过程可递归调用过程可递归调用不允许不允许嵌套定义嵌套定义没有分程序结构没有分程序结构允许可变数组允许可变数组(P234 图图10.7；见右例见右例)例例: main 全局变量的说明全局变量的说明 proc R end R; proc Q end Q;主程序执行语句主程序执行语句 end main10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现9MainMainQQR RMainMainQQQQR R的活动记录的活动记录的活动记录的活动记录QQ的活动记录的活动记录的活动记录的活动记录主程序全局主程序全局主程序全局主程序全局数据区数据区数据区数据区TOPTOPSPSPSPSPSPSPTOPTOPQQ的活动记录的活动记录的活动记录的活动记录SPSPQQ的活动记录的活动记录的活动记录的活动记录主程序全局主程序全局主程序全局主程序全局数据区数据区数据区数据区SPSPSPSP10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现QQ之之之之ARAR全局数全局数全局数全局数据区据区据区据区TOPTOPSPSPR R 之之之之ARAR全局数全局数全局数全局数据区据区据区据区MainMainQQR R退出退出退出退出MainMain10R R的活动记录的活动记录的活动记录的活动记录QQ的活动记录的活动记录的活动记录的活动记录主程序全局主程序全局主程序全局主程序全局数据区数据区数据区数据区TOPTOPSPSPR R的数组区的数组区的数组区的数组区10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现临时工作单元临时工作单元临时工作单元临时工作单元 局部简单变量局部简单变量局部简单变量局部简单变量局部数组的内情向量局部数组的内情向量局部数组的内情向量局部数组的内情向量 调用前的状态调用前的状态调用前的状态调用前的状态 实参和参数个数实参和参数个数实参和参数个数实参和参数个数控制链控制链控制链控制链（老（老（老（老SP SP ）TOPTOPSPSP返回地址返回地址返回地址返回地址老老老老SPSP：指向调用者的指向调用者的指向调用者的指向调用者的ARARARAR起始位置起始位置起始位置起始位置R的活动记录的活动记录假如假如R含有可变数组含有可变数组11例（例（P236图图10.11）sortvar a;readarray;a;exchange;quicksort;partition;a;exchange;quicksort;嵌套过程语言的分配方案嵌套过程语言的分配方案语言主要特点语言主要特点：一个过程可以引用包围它一个过程可以引用包围它的的任一外层任一外层过程所定义的过程所定义的标识符（如变量，数组或标识符（如变量，数组或过程等）。过程等）。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现过程过程过程过程0 01 1 2 2问题问题问题问题：如何引用非局部标识符如何引用非局部标识符如何引用非局部标识符如何引用非局部标识符？实现方法：实现方法：一个过程可以引用它的一个过程可以引用它的任一任一外层外层过程的最新过程的最新AR中的某中的某些数据。些数据。12关键技术：关键技术：解决对非局部变量的引用解决对非局部变量的引用( (存取存取) )也就是说，设法跟踪每个也就是说，设法跟踪每个外层过程外层过程的最新活动的最新活动记录记录ARAR的位置。的位置。跟踪办法：跟踪办法： 1. 1. 存取链。存取链。 2. DISPLAY 2. DISPLAY表。表。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现13指向指向定义定义该过程的该过程的直接外层过程直接外层过程（或主（或主程序）运行时程序）运行时最新最新活动记录的基地址。活动记录的基地址。（例如：（例如：PL/0 ）注意注意与与控制链控制链（又名（又名动态链动态链 SP）相区别）相区别：控制链指向控制链指向调用者调用者的的AR，存取链指向存取链指向定义者定义者的的AR。两链的指向位置有可能相同，也可能不同。两链的指向位置有可能相同，也可能不同。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现存取链（存取链（SL） ，又名：静态链又名：静态链(PL/0)P237P237图图图图10.1310.13、图、图、图、图10.14 10.14 、图、图、图、图10.1510.1514嵌套层次显示表（嵌套层次显示表（Display表）表）display是一个指针是一个指针数组数组d，自顶向下，每，自顶向下，每个单元依次存放现行层、直接外层个单元依次存放现行层、直接外层直至最外层（直至最外层（0层）的每一层过程的最新层）的每一层过程的最新活动记录的基地址。活动记录的基地址。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现d 0 存存 第第0层层d 1 1d 2 2d n n SP0 SP1 SP2d 0d 1d 2display15 0 0老老老老SPSPSPSP1 1 返回地址返回地址返回地址返回地址2 2全局全局全局全局DISPLAYDISPLAYDISPLAYDISPLAY地址地址地址地址3 3 参数个数参数个数参数个数参数个数 4 4形式单元形式单元形式单元形式单元. . . . d d displaydisplay . . . .简单变量简单变量简单变量简单变量 数组内情向量数组内情向量数组内情向量数组内情向量 临时变量临时变量临时变量临时变量v 当过程的层次为当过程的层次为n，它的它的 display为为n+1个个值。值。v 一个过程被调用时，一个过程被调用时，从调用过程的从调用过程的display表中自下向上抄录表中自下向上抄录n个个SP值，再加上本层的值，再加上本层的SP值。值。v全局全局display地址地址10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现各个过程的各个过程的display存存放在自己的放在自己的AR中中1610.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现17用用Display表的方案表的方案(1)主程序-(2)P-(3)Q-(4)R主程序的主程序的活动记录活动记录 d0spdisplaytop（1）P的活动的活动 记录记录主程序的主程序的活动记录活动记录 d1d0displaysptop（2）10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现18用用Display表的方案表的方案 主程序-(2)P-(3)Q-(4)RR的活动的活动 记录记录 Q的活动的活动 记录记录P的活动的活动 记录记录主程序的主程序的活动记录活动记录 d1d0 displaytopsp（3）（4）Q的活动的活动 记录记录P的活动的活动 记录记录主程序的主程序的活动记录活动记录 displayd2d1d0sptop10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现19分程序结构分程序结构Procedure A(m,n); integer m,n;Procedure A(m,n); integer m,n; B B1 1: :begin real z; array Bm:n; begin real z; array Bm:n; B B2 2:begin real d, e;:begin real d, e; L L3 3: : end; end; B B4 4:begin array C1:m; :begin array C1:m; B B5 5:begin real e; :begin real e; L L6 6: : end; end; end; end; L L8 8:end; :end; 10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现20分程序结构的存储分配方案分程序结构的存储分配方案方法之一：方法之一：把分程序看成把分程序看成“无名无参过无名无参过 程程”，它，它在哪里定义就在哪里被调用。因此，可以把在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。处理过程的存储办法应用到处理分程序中。但极为低效：但极为低效： 1）每逢进入一个分程序，就照样建立连接）每逢进入一个分程序，就照样建立连接数据和数据和DISPLAY表表,这是不必要的。这是不必要的。 2）对于多层嵌套的分程序，当从内层分程）对于多层嵌套的分程序，当从内层分程序向外层转移时，可能要同时结束若干层分序向外层转移时，可能要同时结束若干层分程序。程序。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现21按照过程处理办法，意味着必须一层一层按照过程处理办法，意味着必须一层一层地通过地通过“返回返回” 来恢复所要到达的那个分来恢复所要到达的那个分程序的数据区，但不能直接到达。程序的数据区，但不能直接到达。 例如：如果有一个从第例如：如果有一个从第5层分程序转层分程序转出到达第出到达第1层分程序的标号层分程序的标号L，虽然在第，虽然在第5层分程序工作时知道层分程序工作时知道L所属的层数，我们所属的层数，我们极易从极易从display中获得第中获得第1层分程序的活层分程序的活动记录基址（动记录基址（SP），但是怎么知道第），但是怎么知道第1层分程序进入时的层分程序进入时的TOP呢？唯一的办法呢？唯一的办法是从是从 5,4,3和和2各层顺序退出。但这种办各层顺序退出。但这种办法是很浪费时间的。法是很浪费时间的。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现22为了解决上述问题，可采取两种措施：为了解决上述问题，可采取两种措施：第一，对每个过程或分程序都建立有自己第一，对每个过程或分程序都建立有自己的栈顶指示器的栈顶指示器TOP，代替原来仅有过程，代替原来仅有过程的栈顶指示器的栈顶指示器, 每个每个TOP的值保存在各自的值保存在各自活动记录中。这样，上述的第二个问题活动记录中。这样，上述的第二个问题便可解决。便可解决。第二，第二，不把不把分程序看作分程序看作“无参过程无参过程”，每个，每个分程序享用包围它的那个分程序享用包围它的那个最近过程最近过程的的display。每个分程序都隶属于某个确定。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的过程，分程序的层次是相对于它所属的那个过程进行编号的。的那个过程进行编号的。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现23：每个过程被当作是每个过程被当作是0层分程序。而过程体分程层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的序（假定是一个分程序）当作是它所管辖的第第1层分程序。层分程序。这样，每个过程的活动记录所含的内容有：这样，每个过程的活动记录所含的内容有：1.过程的过程的TOP值，它指向过程活动记录的栈顶值，它指向过程活动记录的栈顶位置。位置。2.连接数据，共四项：连接数据，共四项： (1)老老SP值；值； (2)返回地址；返回地址； (3)全局全局display地址；地址； (4)调用时的栈顶单元地址，老调用时的栈顶单元地址，老TOP。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现243. 参数个数和形式单元参数个数和形式单元 4. display表。表。5.过程所辖的过程所辖的各分程序各分程序的局部数据单元，的局部数据单元， 对于每个分程序来说，它们包括：对于每个分程序来说，它们包括：6.（1）分程序的）分程序的TOP值。当进入分程序值。当进入分程序时它含现行栈顶地址，以后，用来定义时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的栈的新高度（分程序的TOP值）；值）；（2）分程序的局部变量，）分程序的局部变量， 数组内情向量数组内情向量和临时工作单元。和临时工作单元。10.3 10.3 栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现栈式动态存储分配的实现2526 27数组B数组BedB2的TOPB的内情向量B的内情向量zzB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A 的 TOPA 的 TOP(c)(d)(c)数组B分配之后；（ d ）进入分程序282910.4 过程调用的参数传递过程调用的参数传递(1) procedure exchangel(i,j:integer);(2) var x:integer;(3) begin;(4) x:=ai; ai:=aj; aj:=x(5) end;带有非局部变量和形参的带有非局部变量和形参的带有非局部变量和形参的带有非局部变量和形参的PASCALPASCAL过程过程过程过程非局变量非局变量非局变量非局变量aiai和和和和ajaj的值进行交换，的值进行交换，的值进行交换，的值进行交换，i,ji,j为形参（在这里为形参（在这里为形参（在这里为形参（在这里是是是是传值传值传值传值）30(1) program reference(input,output);(1) program reference(input,output);(2) var a,b:integer;(2) var a,b:integer;(3) procedure swap(var x,y:integer);(3) procedure swap(var x,y:integer);(4) var temp:integer;(4) var temp:integer;(5) begin (5) begin (6) temp:=x;(6) temp:=x;(7) x:=y;(7) x:=y;(8) y:=temp(8) y:=temp(9) end;(9) end;(10) begin /*reference*/(10) begin /*reference*/(11) a:=1; b:=2;(11) a:=1; b:=2;(12) (12) swap(a,b);swap(a,b);(13) writeln(a=,a);writeln(b=,b)(13) writeln(a=,a);writeln(b=,b)(14) end. /*swap*/(14) end. /*swap*/10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递过过过过程程程程参参参参数数数数以以以以传传传传地地地地址址址址方方方方式式式式被被被被调调调调用用用用的的的的P PA AS SC CA AL L程程程程序序序序31传地址传地址（变量参数）（变量参数）例如：过程例如：过程 swap(var x,y:integer); swap(a,b）；（）；（ a,b为调用时的实参为调用时的实参 ） 调用结果调用结果a,b的值的值被改变被改变。传值传值（值调用）（值调用）例如：过程例如：过程 swap(x,y:integer);特点是对形式参数的任何运算不影响实参的值。特点是对形式参数的任何运算不影响实参的值。swap(a,b）；）；其结果：其结果： a,b调用前的值调用前的值不改变不改变。10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递32传值的实现传值的实现1.形式参数当作过程的局部变量处理，即在被形式参数当作过程的局部变量处理，即在被调过程的调过程的活动记录活动记录中开辟形参的存储空间，中开辟形参的存储空间，这些存储位置即是我们所说的这些存储位置即是我们所说的形式单元形式单元（用（用以存放实参）。以存放实参）。2.调用过程计算实参的值，并将其放在对应形调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。式单元开辟的空间中。3.被调用过程执行时，就像使用局部变量一样被调用过程执行时，就像使用局部变量一样使用这些形式单元。使用这些形式单元。10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递33procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 调用调用swap(a,b) 过程将不会影响过程将不会影响a和和b的值。的值。 其结果等价于执行下列运算：其结果等价于执行下列运算： x :=a； y :=b； temp :=x； x :=y； y :=temp10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递34传地址的实现传地址的实现把实参的地址传递给相应的形参，即调用过程把实参的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的把一个指向实参的存储地址的指针指针传递给被传递给被调用过程相应的调用过程相应的形参形参：1 1、实参是一个名字，或具有左值的表达式、实参是一个名字，或具有左值的表达式传递左值传递左值2 2、实在参数是无左值的表达式、实在参数是无左值的表达式计算值，放计算值，放入到一存储单元，传此存储单元地址入到一存储单元，传此存储单元地址3 3、目标代码中，被调用过程对形参的引用变成、目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用对传递给被调用过程的指针的间接引用10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递35procedure swap(var x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 调用调用swap(i,ai) 其结果等价于执行下列运算：其结果等价于执行下列运算：1.把把 i和和ai的地址分别放到的地址分别放到x和和y相应的单元相应的单元a1,a2 2.( temp :=x；)temp的内容置为的内容置为a1所指单元中所指单元中存的内容存的内容3.(x :=y;) a1所指单元的内容置为所指单元的内容置为a2所指单元值所指单元值4.( y :=temp) a2所指单元的内容置为所指单元的内容置为temp的值的值10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递36(1)swap(x,y)(1)swap(x,y)(2)int *x,*y;(2)int *x,*y;(3) int temp;(3) int temp;(4) temp=*x; *x=*y; *y=temp;(4) temp=*x; *x=*y; *y=temp;(5)(5)(6)main( )(6)main( )(7) int a=1,b=2;(7) int a=1,b=2;(8) swap(&a,&b);(8) swap(&a,&b);(9) printf(“a is now %d,b is now %dn”,a,b);(9) printf(“a is now %d,b is now %dn”,a,b);(10)(10) 在一个值调用过程中使用指针的在一个值调用过程中使用指针的在一个值调用过程中使用指针的在一个值调用过程中使用指针的C C程序在程序在程序在程序在C C程序程序程序程序中无传地址所以用指针实现。中无传地址所以用指针实现。中无传地址所以用指针实现。中无传地址所以用指针实现。10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递37值结果传递值结果传递 除了未建立真正的别名之外，这个机制得到的结果与引用传递类似：在过除了未建立真正的别名之外，这个机制得到的结果与引用传递类似：在过除了未建立真正的别名之外，这个机制得到的结果与引用传递类似：在过除了未建立真正的别名之外，这个机制得到的结果与引用传递类似：在过程程程程中中中中复复复复制制制制和和和和使使使使用用用用自自自自变变变变量量量量的的的的值值值值，然然然然后后后后当当当当过过过过程程程程退退退退出出出出时时时时，再再再再将将将将参参参参数数数数的的的的最最最最终终终终值值值值复复复复制制制制回回回回自自自自变变变变量量量量的的的的地地地地址址址址。因因因因此此此此，这这这这个个个个方方方方法法法法有有有有时时时时也也也也被被被被称称称称为为为为复复复复制制制制进进进进，复复复复制制制制出出出出，或或或或复复复复制制制制存储。存储。存储。存储。值值值值结结结结果果果果传传传传递递递递与与与与引引引引用用用用传传传传递递递递的的的的唯唯唯唯一一一一区区区区别别别别在在在在于于于于别别别别名名名名的的的的表表表表现现现现不不不不同同同同。例例例例如如如如，在在在在以以以以下下下下的的的的代代代代码中（码中（码中（码中（C C语法）：语法）：语法）：语法）：void p (int x, int y)void p (int x, int y)+x;+x;+y;+y; main()main()int a=1;int a=1;p(a,a);p(a,a);return 0;return 0; 在调用在调用在调用在调用p p之后，若使用了地址传递，则之后，若使用了地址传递，则之后，若使用了地址传递，则之后，若使用了地址传递，则a a的值为的值为的值为的值为3 3；若使用了值结果传递则；若使用了值结果传递则；若使用了值结果传递则；若使用了值结果传递则a a的值为的值为的值为的值为2 2。10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递38名字传递名字传递这这是是传传递递机机制制中中最最复复杂杂的的参参数数了了。由由于于名名字字传传递递的的思思想想是是直直到到在在被被调调用用的的程程序序真真正正使使用用了了自自变变量量（作作为为一一个个参参数数）之之后后才才对对这这个个自自变变量量赋赋值值 ， 所所 以以 它它 还还 称称 作作 延延 尽尽 赋赋 值值 （ delayed evaluation）。因因此此，自自变变量量的的名名称称或或是是它它在在调调用用点点上上的的结结构构表表示示取取代代了了它它对对应应的的参参数数的的名名字。例如在代码字。例如在代码 void p (int x) +x;中，若做了一个如中，若做了一个如p(ai)的调用时，其结果是的调用时，其结果是计算计算+(ai)。因此，若在。因此，若在p中使用中使用x之前改变之前改变i，那么它的结果就与在引用传递或在值结果传，那么它的结果就与在引用传递或在值结果传递中的不同递中的不同 10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递39int i;int i;int a 10;int a 10;void p (int x)void p (int x) +i; +i; +x; +x; main ()main () i=1; i=1; a1=1; a1=1; a2=2; a2=2; p(ai); p(ai); return 0; return 0; 对对对对p p的调用的结果是将的调用的结果是将的调用的结果是将的调用的结果是将a2a2设置为设置为设置为设置为3 3并保持并保持并保持并保持a1a1不变。不变。不变。不变。10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递40名字传递的解释如下：在调用点上的自变名字传递的解释如下：在调用点上的自变量的文本被看作是它自己右边的函数，生量的文本被看作是它自己右边的函数，生当在被用的过程的代码中到达相应的参数当在被用的过程的代码中到达相应的参数名时，就要计算它。我们总是在调用程序名时，就要计算它。我们总是在调用程序的环境中计算自变，而总是在过程的定义的环境中计算自变，而总是在过程的定义环境中执行过程。环境中执行过程。10.4 10.4 过程调用的参数传递过程调用的参数传递过程调用的参数传递过程调用的参数传递41一、过程说明语句的翻译；一、过程说明语句的翻译；一、过程说明语句的翻译；一、过程说明语句的翻译；说明语句或函数定义的语义处理说明语句或函数定义的语义处理说明语句或函数定义的语义处理说明语句或函数定义的语义处理分析参数的类型、分配地址分析参数的类型、分配地址分析参数的类型、分配地址分析参数的类型、分配地址统计参数和返回值的空间需求统计参数和返回值的空间需求统计参数和返回值的空间需求统计参数和返回值的空间需求表格管理表格管理表格管理表格管理完成过程名的属性登录完成过程名的属性登录完成过程名的属性登录完成过程名的属性登录二、过程调用的翻译；二、过程调用的翻译；二、过程调用的翻译；二、过程调用的翻译；建立建立建立建立ARAR、DisplayDisplay表等表等表等表等10.5 跟过程相关的语义分析跟过程相关的语义分析42过程调用的语义翻译过程调用的语义翻译11 在过程在过程 P1中调用过程中调用过程P2 时时a. P1 对对实实在在参参数数求求值值，将将结结果果存存入入P2的的活活动记录参数域动记录参数域b. 在在P2的的活活动动记记录录中中存存放放返返回回地地址址和和当当前前栈顶指针栈顶指针c. 按照活动记录的大小，上移栈顶指针按照活动记录的大小，上移栈顶指针d. 从从P2的入口开始执行的入口开始执行e. P2存放寄存器值和其它状态信息存放寄存器值和其它状态信息f. 执行执行P2的定义体的定义体10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析4322从过程从过程P2P2返回时返回时a.a. P2 P2在返回值域中保存返回值在返回值域中保存返回值b.b. 恢复原栈顶指针和其它寄存器恢复原栈顶指针和其它寄存器c.c. 按按返返回回地地址址转转移移，直直接接使使用用返返回回值进行计算值进行计算10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析44过程调用的代码过程调用的代码参数传递参数传递 param x完成完成 11 a.调用调用 call f完成完成 11 b. c. d.函数入口函数入口完成完成 11 e.过程出口过程出口 return x完成完成 22 a. b. c.10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析45A A1 , E过程调用表达式的翻译方案过程调用表达式的翻译方案 S.code := A.code | S.code := A.code | gen(callid.entry,A.num) gen(callid.entry,A.num) A.num := 1; A.num := 1; A.code := E.code | A.code := E.code | gen(param E.place) gen(param E.place) A.num := A1.num+1; A.num := A1.num+1; A.code := A1.code |E.code| A.code := A1.code |E.code| gen(param E.place) gen(param E.place) 产生式产生式语义规则语义规则S id ( A );A E10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析46例：函数调用例：函数调用 f (3+a, 6) 的翻译的翻译3 + a6生成的目标代码生成的目标代码: t1 := 3 + a param t1 param 6 call f , 2 /*参数个数为参数个数为2 */10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析47过程调用的四元式序列过程调用的四元式序列 S call id() ,E E par T1 par T2 par Tn call id,n10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析48过程调用的四元式序列过程调用的四元式序列S call id() for 队列队列.q的每一项的每一项P do gen(par,-,-,p);n:=n+1; gen(call,-,-,entry(id) 1,E 把把E.place排在排在.q的末端；的末端； E10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析49(1) program param(input,output);(2) procedure b(function h(n:integer):integer);(3) begin writeln(h(2) endb;(4) procedure c;(5) var m:integer;(6) function f(n:integer):integr;(7) begin f:=m+n endf;(8) begin m := 0; b(f) end c;(9) begin(10) c(11)end. 过程作为参数传递过程作为参数传递10.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析5010.5 10.5 跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析跟过程相关的语义分析51堆式动态存储分配以下不讲52堆式动态存储分配堆变量堆空间的管理策略减少碎片的技术空间的释放53C+的堆变量Int*Ptr;Ptr=newint(5)；Int*ptr=newint10DeleteptrDeleteptr堆变量是可以在程序运行时根据需要随时创建或删除的变量54C+的堆对象#includeClassMyclassPublic:Myclass();Myclass(intk,intj);voidSet(int,int)m=k;n=j;Myclass();Private:intm,n;Myclass:Myclass()Set(0,0);CoutDefaultendl;Myclass:Myclass(intk,intj)Set(k,j);Cout“m=“mendl;Myclass:Myclass()Cout“Destructor”endl;55使用new和delete的示例#includeIntmain()Cout“one”endl;Myclass*ptr1=newMyclass;Deleteptr1;Cout“two”endl;Ptr1=newMyclass(5,10);Deleteptr1;Return0;oneDefaltDestructortwom=5Destructor56堆式动态存储分配ConstintArraySize=24;/defaultsizeClassIntArrayPublic:/operationsperformedonarraysIntArray(intsz=ArraySize);IntArray(constIntArray&);IntArray()deleteia;IntArray&operator=(constIntArray&);int&operator(int);intgetSize()returnsize;protected:/internaldatarepresentationintsize;int*ia;IntArray()函数的实现，引入新的运算符newIntArray:IntArray（intsz)size=sz;/allocateanintegerarrayofsize/andsetiatopointtoitia=newintsize;/initializearrayfor(inti=0;is.next=memptr=mem;memptr-s.usedsize=1;memptr-s.freesize=MEMSIZE-1;for(p=memptr;(p-s.next!=memptr)&(p-s.freesizes.next);if(p-s.freesizenunits)returnNULL;/*noblockbigenough*/newp=p+p-s.usedsize;newp-s.usedsize=nunits;newp-s.freesize=p-s.freesize-nunits;70newp-s.next=p-s.next;p-s.freesize=0;p-s.next=newp;memptr=newp;return(void*)(newp+1);void free (void *ap)Header*bp,*p,*prev;bp=(Header*)ap1;for(prev=memptr,p=memptr-s.next;(p!=bp)&(p!=memptr);prev=p,p=p-s.next);if(p!=bp)return;/*corruptedlist,donothing*/prev-s.freesize+=p-s.usedsize+p-s.freesize;prev-s.next=p-s.next;memptr=prev;71堆的自动管理-隐式存储回收在一种需要完全动态的运行时环境的语言（OO语言，函数式语言Lisp,ML)中，堆也必须类似地自动管理。自动存储器管理涉及到了前面分配的但不再使用的存储器的回收，可能是在它被分配的很久以后，而没有明确的对free的调用。这个过程称作垃圾回收（grabagecollection）。72垃圾回收垃圾回收程序-寻找可被引用的所有存储器并释所有未引用的存储器。在存储块不再引用时，无论是直接还是通过指针间接的引用，识别这些存储块是一项比维护堆存储的列表复杂得多的任务。方法-对malloc的调用失败，激活垃圾回收程序垃圾回收算法markandsweep73隐式存储回收markandsweep算法隐式存储回收要求用户程序和支持运行的回收子程序并行工作，因为回收程序需要知道分配给用户程序的存储块何时不再使用。为了实现并行工作，在存储块中要设置回收子程序访问的信息。存储块格式：块长度访问计数标记指针用户使用空间74回收过程分为两个阶段。（1）第一个阶段为标记阶段，对已分配的块跟踪程序中各指针的访问路径。如果某个块被访问过，就给这个块加一个标记。（2）第二个阶段为回收阶段，所有未加标记的存储块回收到一起，并插入空闲块链表中，然后消除在存储块中所加的全部标记。75面向对象的语言中的动态存储器面向对象的语言中的动态存储器面向对象的语言在运行时环境中要求特殊的机制以完成其增添的特性：对象、方法、继承以及动态联编。面向对象语言在对运行时方面的要求差异很大。Smalltalk要求与LISP相似的完全动态环境C则保持C的基于栈的环境76实现对象实现对象的一个简单机制是，初始化代码将所有当前的继承特征（和方法）直接地复制到记录结构中（将方法当作代码指针）。但这样做极浪费空间。另外一种方法是在执行时将类结构的一个完整的描述保存在每个点的存储器中，并由超类指针维护继承性（有时这也称作继承图（inheritancegraph）。接着同用于它的实例变量的域一起，每个对象保持一个指向其定义类的指针，通过这个类就可找到所有（局部和继承的）的方法。此时，只记录一次方法指针（在类结构中），而且对于每个对象并不将其复制到存储器中。由于是通过类继承的搜索来找到这个机制的，所以该机制还实现继承性与动态联编。其缺在于：虽然实例变量具有可预测的偏移量（正如在标准环境中的局部变量一样），方法却没有，而且它们必须由带有查询功能的符号表结构中的名字维护。这是对于诸如Smalltalk的高度动态语言的合理的结构，因为类结构可以在执行中改变。77C+中选择的方法将整个类结构保存在环境中，计算出每个类的可用方法的代码指针列表，并将其作为一个虚拟函数表（virtualfunctiontable）而存放在（静态）存储器。它的优点在于：可做出安排以使每个方法都有一个可预测的偏移量，而且也不再需要用一系列表查询遍历类的层次结构。现在每个对象都包括了一个指向相应的虚拟函数表而不是类结构的指针（当然，这个指针的位置必须也有可预测的偏移量）。78