编译原理第九章课件

编译原理（第二版）郑洪编著第9章运行时存储空间管理程序运行时的存储环境1静态存储分配2基于栈的运行时存储器管理3参数传递机制49.1程序运行时的存储环境一个可执行程序所使用的存储空间被分为两个区间，一是代码区，存放程序的操作指令；二是数据区，存放程序所使用或产生的数据。动态分配数据区的方法有很多种，最典型的情况是将数据区以栈的形式管理。存放动态数据的另一种数据结构被称为堆（heep）。代码存储区示意9.2静态存储分配静态存储分配是指在编译阶段就能计算出一个程序在运行时所需的全部存储空间的大小，并能够安排好目标程序运行时的全部数据空间，最终为每个数据的存储单元确定地址。在完全静态存储分配的环境下，不仅全局变量，所有的变量都是静态分配存储地址。【例9.1】下面的程序是一个FORTRAN77程序，由主过程P和一个附加过程Q组成。PROGRAMPCOMMONMAXSINTEGERMAXSREALT(10),XX=1.0MAXS=10READ*,T(1),T(2),T(3)CALLQ(T,3,X)

SUBROUTINEQ(A,S,Y)COMMONMAXSINTEGERMAXS,SREALA(S),Y,XINTEGERKX=0.0DO10K=1,SIZEX=X+A(K)*A(K)CONTINUEY=SQRT(X/S)RETURNEND9.3基于栈的运行时存储器管理9.3.1简单的栈式存储管理所有的函数之间只存在调用关系，不存在定义关系。研究一个程序在运行时函数的调用顺序有一个工具，称为“活动树”，每个活动记录或调用都成为该树的一个结点，每个结点的子结点又表示一次调用。【例9.2】利用Euclid算法的简单递归实现计算两个非负整数的最大公约数，C代码如下：#include〈stdio.h〉intx,y;intgcd(intu,intv){if(v==0)returnu;elsereturngcd(v,u%v);}main(){scanf(%d,&x,&y);printf("%d\n",gcd(x,y,);return0;}运行时的活动树函数返回时的操作相对简单，大致如下：①将SP的内容复制到TOP，这意味着当前活动记录所占有的空间将重新分配。②将SP指针的内容复制到SP中，因为SP指针的内容是上一个活动记录的首地址，此时当前的活动记录被删除了，消失了。③弹出返回地址。在恢复了原来的活动记录并获得返回地址后，程序就可以转移到调用程序的返回点了。g(2)活动记录的运行过程第3次调用g时的栈数据区的活动记录情况及其对应的活动树9.3.2过程可局部定义的栈式存储管理如果一个语言允许在过程的内部再定义过程，即程序中并非所有的过程都是全局的。【例9.4】考虑以下PASCAL程序：programRefprocedurep;varn:minteger;procedureq;beginend;(*q*)procedurer(n:integer)beginq;end;(*r*)begin(*p*)n:=1;r(2);end(*p*);begin(*main*)p;end;显然，在这段程序中，n不是全局的变量，它是在过程p中定义的。它可以被在p中定义的过程q和过程r引用。对于q或r而言，n又不是局部的，因为在q或r里没有n的定义，所以若在q或r

里引用n，就称为非局部非全局引用。由于过程定义是嵌套的，一个过程可以引用包围它的任一外层过程所定义的变量（按标准静态作用域规则）。问题的关键是程序运行如何获得被引用的变量地址。引用时采用“SP＋偏移量”的寻址方式。1．静态链解决这个问题的第一个方法也称“实现静态作用域”，是将一个称为静态链（也称访问链）的额外信息添加到每个活动记录中。静态链的指针指向离本活动记录最近的直接外层过程的记录。静态链的指针指向离本活动记录最近的直接外层过程的记录【例9.5】programchainprocedurep;varx:integer;procedureq;procedurer；beginx:=2；…if…thenpend(*r*)beginr;end(*q*)beginq;end(*p*)begin(*main*)p;程序第一次对r调用后的栈数据区用静态链表示的嵌套层关系在实用的栈式存储管理应用中，往往把Display表插入在活动记录中。例如，可以把它放在“返回地址”单元的上面，并用Display表取代静态链来访问非局部变量。因此上述例子中的栈结构可用图来表示。9.4参数传递机制9.4.1值传递将实际参数作为函数中要使用的数值直接复制到活动记录中的形式参数区。形式参数在函数中等同于变量，引入实际参数如同为变量赋值。【例9.6】下述程序在过程调用时使用值传递。programmain(input,output)vara,b:integer;procedurep(x,y,z)beginy:=y+1;z:=z+x;end;{p}begina:=2;b:=3;p(a+b,a,a):printa;end9.4.2地址传递地址传递也称引用传递，是把实际参数单元的地址复制到形式参数单元内。【例9.7】再次使用例9.6的程序，参数传递方法为地址传递。programmain(input,output)vara,b:integer;procedurep(x,y,z)beginy:=y+1;z:=z+x;end;{p}begina:=2;b:=3;p(a+b,a,a):printa;end过程p调用初始时数据区的状态过程p调用结束时数据区的状态过程p调用初始时数据区的状态过程p调用结束时数据区的状态9.4.4名字传递生成一个处理实际参数的子程序（称参数子程序）。当被调用过程使用到相应的参数时就调用这个子程序。例如在下述C代码中：inti;inta[10];voidp(intx){++i;++x;}main(){i=1;a[1]=1;a[2]=2;p(a[i]);return0;}当main()程序调用p(a[i])时，i=1。如果采用名字传递机制，p函数执行++i之后，对参数的引用就不是a[1]，而是a[2]，所以这段代码执行的结果是将a[2]设置为3，而不是将a[1]设置为2。但若采用地址传递机制，则参数x在函数调用时即被存入a[1]的地址，此后无论改变与否都不会重新计算x的地址。再考虑前述例子：programmain(input,output)vara,b:integer;procedurep(x,y,z)beginy:=y+1;z:=z+x;end;{p}b