编译原理,清华大学,第2版-第10章目标程序运行时的存储组织

1、第第1010章章 目标程序运行时的组织目标程序运行时的组织 教学要求：本章介绍目标程序运行时的教学要求：本章介绍目标程序运行时的存储组织方式，包括静态存储分配和动存储组织方式，包括静态存储分配和动态存储分配。态存储分配。 要求掌握各种存储组织形要求掌握各种存储组织形式的基本方法。式的基本方法。 教学重点：静态分配策略和动态分配策教学重点：静态分配策略和动态分配策略的基本思想，嵌套过程语言栈式分配，略的基本思想，嵌套过程语言栈式分配，活动记录、运行时栈的组织。活动记录、运行时栈的组织。 10.1 10.1 概述概述 从逻辑上看，代码生成前，编译程序必须从逻辑上看，代码生成前，编译程序必须进行目标

2、程序运行环境的设计和数据空间进行目标程序运行环境的设计和数据空间的分配的分配 数据空间包括：用户定义的各种类型的数数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织单元，调用过程时所需的连接单元，组织输入输入/ /输出所需的缓冲区。输出所需的缓冲区。存储管理复杂度取决于源语言本身，具体包括：存储管理复杂度取决于源语言本身，具体包括：允许的数据类型的多少允许的数据类型的多少? ?语言中允许的数据项是语言中允许的数据项是: : 静态确

3、定静态确定? ?动态确定动态确定? ?程序决定名字的作用域的规则和结构程序决定名字的作用域的规则和结构段结构段结构? ?过程定义不嵌套过程定义不嵌套? ?只允许过程递归调用只允许过程递归调用? ?分程序结构分程序结构: : 分程序嵌套分程序嵌套? ?过程定义嵌套过程定义嵌套? ? 目标代码区目标代码区 静态数据区静态数据区 Stack heap目标代码区用以存放目标代码，这是目标代码区用以存放目标代码，这是固定长度的，即编译时能确定的。固定长度的，即编译时能确定的。静态数据区用以存放编译时能确定所静态数据区用以存放编译时能确定所占用空间的数据。占用空间的数据。堆堆/栈用于存放可变数据以及管理过

4、栈用于存放可变数据以及管理过程活动的控制信息。程活动的控制信息。三种数据区对应着下述三种不同的分配策略三种数据区对应着下述三种不同的分配策略在编译时能确定在编译时能确定目标程序运行中所需的全部数据空间的大目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置数据空间，确定每个数据对象的存储位置对任何局部变量对任何局部变量X X的引的引用可表示为变址访问用可表示为变址访问: : dxSP dxSP dx: dx: 变量变量X X相对于活相对于活动记录起点的地址，动记录起点的地址，在编译时可确定。在编译时可确

5、定。SP 012TOP 每个过程的活动记录内容每个过程的活动记录内容( (非嵌套语言非嵌套语言) )临时单临时单元元内情向内情向量量局部变局部变量量形式单形式单元元参数个参数个数数动态链动态链返回地返回地址址q连接数据连接数据返回地址返回地址动态链：指向调用该动态链：指向调用该过程的最新活动记录过程的最新活动记录地址的指针。地址的指针。静态链：指向直接外静态链：指向直接外层最新活动记录地址层最新活动记录地址的指针，用来访问非的指针，用来访问非局部数据。局部数据。SP 012TOP 每个过程的活动记录内容每个过程的活动记录内容( (嵌套语言嵌套语言) )临时单临时单元元内情向内情向量量局部变局部

6、变量量形式单形式单元元静态链静态链动态链动态链返回地返回地址址q形式单元：存放相形式单元：存放相应的实参的地址或应的实参的地址或值。值。q局部数据区：局部局部数据区：局部变量、内情向量、变量、内情向量、临时工作单元（如临时工作单元（如存放对表达式求值存放对表达式求值的结果）。的结果）。SP 012TOP 每个过程的活动记录内容每个过程的活动记录内容临时单元临时单元内情向量内情向量局部变量局部变量形式单元形式单元静态链静态链动态链动态链返回地址返回地址 1 1、 call P call P 被翻译成被翻译成: :11TOP:=SP (TOP:=SP (保护现行保护现行SP)SP)JSR P (J

7、SR P (转子指令转子指令) )参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元活动记录的填写活动记录的填写TOP SP 调用过程的调用过程的活动记录活动记录老老SP2 2、转进过程、转进过程P P后，首先应执行下述指令后，首先应执行下述指令: :SP:=TOP+1 (SP:=TOP+1 (定义新的定义新的SP)SP)1SP:=1SP:=返回地址返回地址 ( (保护返回地址保护返回地址) )TOP:=TOP+L (TOP:=TOP+L (新新TOP)TOP) L L：过程过程P P的活动记录所需单元数，的活动记录所需单元数， 在编译时可

8、确定。在编译时可确定。 参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元TOP 调用过程的活动记录调用过程的活动记录返回地址返回地址TOPSP3 3、 过程返回时，应执行下列指令过程返回时，应执行下列指令: :X:=2TOP (X:=2TOP (把返回地址取到把返回地址取到X X中中) ) TOP:=SP-1 (TOP:=SP-1 (恢复调用前恢复调用前TOP)TOP)SP:=0SP (SP:=0SP (恢复调用前恢复调用前SP)SP)UJ X (UJ X (按按X X返回返回) )参数个数参数个数返回地址返回地址形式单元形式单元内情向量

9、内情向量局部变量局部变量老老SP临时单元临时单元调用过程的活动记录调用过程的活动记录TOPSPSPTOP 例例:Main( ) Main中的数据说明中的数据说明 proc R( ) R中的数据说明中的数据说明 proc Q( ) Q中的数据说明中的数据说明 主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录TOPR的活动记录的活动记录SP主程序活动记录主程序活动记录全局数据区全局数据区 R R的数组区的数组区 R R的活动记录的活动记录 Q Q的活动记录的活动记录 主程序全局主程序全局 数据区数据区分配了数组区之后的运行栈分配了数组区之后的运行栈TOPSP PASCALPASCALPAS

10、CALPASCAL程序本身可以看成是一个操作程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和系统所调用的过程，过程可以嵌套和递归。递归。一个一个PASCALPASCAL过程：过程：过程头；过程头；说明段（由一系列的说明语句组成）；说明段（由一系列的说明语句组成）；beginbegin执行体（由一系列的执行语句组成）；执行体（由一系列的执行语句组成）；endend作用域作用域：一个名字能被使用的区域范围：一个名字能被使用的区域范围称作这个名字的作用域。称作这个名字的作用域。允许同一个标识符在不同的过程中代表允许同一个标识符在不同的过程中代表不同的名字。不同的名字。名字作用域规则名字作用

11、域规则- 最近嵌套原则最近嵌套原则 一个在子程序一个在子程序B1B1中说明的名字中说明的名字X X只在只在B1B1中有效（局部于中有效（局部于B1B1）；）； 如果如果B2B2是是B1B1的一个内层子程序且的一个内层子程序且B2B2中中对标识符对标识符X X没有新的说明，则原来的没有新的说明，则原来的名字名字X X在在B2B2中仍然有效。如果中仍然有效。如果B2B2对对X X重重新作了说明，那么，新作了说明，那么，B2B2对对X X的任何引的任何引用都是指重新说明过的这个用都是指重新说明过的这个X X。program main var A, B : real; procedure P1 var

12、 B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integr) 非局部名字的访问的实现非局部名字的访问的实现 主程序的层次为主程序的层次为0 0；在；在i i层中定义的过程，层中定义的过程，其层次为其层次为i+1;i+1; 过程运行时，必须知道其所有外层过程的过程运行时，必须知道其所有外层过程的当前活动记录的起始地址。当前活动记录的起始地址。main p1 p2 p3 p4 main过过程程定定义义的的嵌嵌套套执执行行顺顺序序p2p4p3p3mainmain活动

13、记活动记录录P3P3活动记录活动记录存取链存取链( (静静态链态链) )控制链控制链( (动动态链态链) )P3P3活动记录活动记录存取链存取链( (静静态链态链) )控制链控制链( (动动态链态链) )P4P4活动记录活动记录存取链存取链( (静静态链态链) )控制链控制链( (动动态链态链) )P2P2活动记录活动记录存取链存取链( (静静态链态链) )控制链控制链( (动动态链态链) )program P; var x,y: integer; . procedure P1; var i,j:integer; . procedure P11(a,b:integer); . begin .

14、end; begin . call P11(i,j); . end; procedure P2; var s,t:integer; . procedure P21; begin . end; begin . call P1 . end; begin . call P2; . end.012x3y4RA567s8t9152主程序主程序P过程过程 P2过程过程 P1过程过程 P11DisplayP的的活动活动记录记录P2的的活动活动记录记录RA101112i13j142P1的的活动活动记录记录RA151617a18b19P11的活的活动记动记录录3例：例：program main(i,0); 程序

15、结构图程序结构图 proc R(c,d); R end /*R*/ proc P (a); 主主 proc Q (b); P Q call R R(x,y); end /*Q*/ call Q Q(z); call P end /*P*/ call R P（W）；）； R（U，V）；）； end /*main*/用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R主程序的主程序的活动记录活动记录 d0spdisplaytop（1） P P的的活动记录活动记录主程序的主程序的活动记录活动记录 d1d0displaysptop（2）用用Display表的方案表的方案(

16、1)主程序主程序-(2)P-(3)Q-(4)RQ Q的的活动记录活动记录 P P的的活动记录活动记录主程序的主程序的活动记录活动记录 displayd2d1d0sptop（3）R R的的活动记录活动记录 Q Q的的活动记录活动记录 P P的的活动记录活动记录主程序的主程序的活动记录活动记录 d1d0 displaytopsp（4） d DISPLAY d DISPLAY 4 4 形式单元形式单元 3 3 参数个数参数个数 2 2 全局全局DISPLAYDISPLAY地址地址 1 1 返回地址返回地址 0 0 老老SPSP堆：堆：通常是一片连续的足够大的存储区，当需要通常是一片连续的足够大的存储

17、区，当需要时，就从堆中分配一小块存储区；用完就及时退时，就从堆中分配一小块存储区；用完就及时退还给堆。还给堆。注：注：在高级语言中有些数据存储空间的请求与释在高级语言中有些数据存储空间的请求与释放不再遵循后进先出的原则，而且是全局性的。放不再遵循后进先出的原则，而且是全局性的。为此，需要让运行程序持有一块专用的全局存储为此，需要让运行程序持有一块专用的全局存储空间来满足这些数据的存储要求。这种存储空间空间来满足这些数据的存储要求。这种存储空间就是堆。就是堆。 10.4 10.4 参数传递参数传递(1)procedure exchangel(i,j:integer);(1)procedure e

18、xchangel(i,j:integer);(2) var x:integer;(2) var x:integer;(3) begin;(3) begin;(4) x:=ai; ai:=aj; aj:=x(4) x:=ai; ai:=aj; aj:=x(5) end;(5) end; 带有非局部变量和形参的带有非局部变量和形参的PASCALPASCAL过程过程非局变量非局变量aiai和和ajaj的值进行交换，的值进行交换，i,ji,j为为形参形参传值的实现传值的实现 1.1.形式参数当作过程的局部变量处理，形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参即在被调过程的活动记录

19、中开辟了形参的存储空间，这些存储位置即是我们所的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。说的形式单元（用以存放实参）。 2.2.调用过程计算实参的值，并将其放在调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。对应形式单元开辟的空间中。 3.3.被调用过程执行时，就像使用局部变被调用过程执行时，就像使用局部变量一样使用这些形式单元。量一样使用这些形式单元。 (1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x,y:integer);(4) var temp:int

20、eger;(5) begin (6) temp:=x;(7) x:=y;(8) y:=temp(9) end;(10)begin(11) a:=1; b:=2;(12) swap(a,b);(13) writeln(a=,a);writeln(b=,b)(14)end. 带有过程带有过程swap的的PASCAL程序程序传地址的实现传地址的实现 把实在参数的地址传递给相应的形参，即把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：传递给被调用过程相应的形参：1.1.实在参数是一个名字，或具有左值的表达式实在

21、参数是一个名字，或具有左值的表达式-传递左值传递左值2.2.实在参数是无左值的表达式实在参数是无左值的表达式-计算值，放计算值，放入一存储单元，传此存储单元地址入一存储单元，传此存储单元地址3.3.目标代码中，被调用过程对形参的引用变成目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用对传递给被调用过程的指针的间接引用 (1)swap(x,y)(1)swap(x,y)(2)int (2)int * *x,x,* *y;y;(3) int temp;(3) int temp;(4)temp=(4)temp=* *x; x; * *x=x=* *y; y; * *y=temp

22、;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 (9) printf(“a is now %d,b is now %dn”,a,b);%dn”,a,b); 在一个值调用过程中使用指针的在一个值调用过程中使用指针的C C程序程序, ,在在C C程序中无传地址所以用指针实现。程序中无传地址所以用指针实现。 (1)program param(input,output); (2)procedure b(function h(n:in