《编译原理：第九章 运行时存储空间组织》由会员分享，可在线阅读，更多相关《编译原理：第九章 运行时存储空间组织（77页珍藏版）》请在金锄头文库上搜索。
1、编译原理,第九章 运行时存储空间组织,第九章 运行时存储空间组织,9.1 目标程序运行时的活动 以Pascal为例，假定程序由若干个过程组成 过程（procedure）定义 一个过程的活动指的是该过程的一次执行 过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间 过程可以是递归的,（1） program sort(input, output) （2） var a: array010 of integer; （3） procedure readarray; （4） var i: integer; （5） begin （6） for
2、 i:=1 to 9 do read(ai) （7） end; （8） function partition(y, z:integer):integer; （9） var i:integer; （10） begin （11） end;,program sortprocedure readarrayfunction partition(yprocedure quicksort,（12） procedure quicksort(m, n:integer); （13） var i:integer; （14） begin （15） if (nm) then begin （16） i:=partitio
3、n(m, n ); （17） quicksort(m, i-1 ); （18） quicksort(i+1, n ) （19） end; （20） end; （21） begin （22） a0:=-9999; a10:=9999; （23） readarray; （24） quicksort(1, 9 ) （25） end.,program sortprocedure readarrayfunction partition(yprocedure quicksort,参数传递,过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言的主要途径。 过程定义： procedure add(x,
4、y:integer; var z:integer)beginz：=x+y;end; 过程调用add(a,b,c);,参数传递方式,一. 传地址 把实在参数的地址传递给相应的形式参数 方法： 调用段预先把实在参数的地址传递到被调用段可以拿到的地方； 程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中； 过程体对形式参数的引用域赋值被处理成对形式单元的间接访问。 PASCAL的变量参数方式,procedure swap (var m:integer; var n: integer);var i:integer;begini:=m;m:=n;n:=i;end,swap(a
5、,b) 把a,b的地址送到已知单元j1和j2中 m:=j1; n:=j2; i:=m; m:= n; n:=i;,参数传递方式,二得结果 传地址的一种变形 方法： 每个形参对应两个形式单元，第一个形式单元存放实参地址，第二个单元存放实参的值。 在过程体中对形式参数的任何引用或赋值都看作对它的第二个单元的直接访问。 过程完成返回前把第二个单元的内容存放到第一个单元所指的实参单元中。 有些Fortran采用这种方式；,参数传递方式,三传值 把实在参数的值传递给相应的形式参数 方法： 调用段预先把实在参数的的值计算出来并放在被调用段可以拿到的地方； 被调用段开始工作时，首先把实参的值抄入形式参数相应
6、的单元； 被调用段中，象引用局部数据一样引用形式单元。 PASCAL的值参数,参数传递方式,四传名 过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实参。 方法： 在进入被调用段的之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行计值（或计算地址）。因此，通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形式参数时就调用这个子程序。,PROGRAM EXvar A:integer;PROCEDURE P(B:integer)var A:integer;BEGINA:=0;B:=B+1;A
7、:=A+B;END;,BEGINA :=2;TA:=0;A:= A +1;TA:=TA+ A;write(A); END,BEGINA:=2;P(A);write(A); END,例： procedure P(w,x,y,z); beginy := y*w;z := z+x; end begina := 5;b := 3;P(a+b,a-b,a,a); write(a); end,传值: 传地址: 得结果: 传名:,5 42 7 77,编译程序为了组织存储空间，必须考虑下面几个问题： 过程是否允许递归？ 当控制从一个过程的活动返回时，对局部名称的值如何处理？ 过程是否允许引用非局部名称？ 过程
8、调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返回？ 存储空间可否在程序控制下进行动态分配？ 存储空间是否必须显式地释放？,9.2 运行时存储器的划分,一个目标程序运行所需的存储空间包括: 存放目标代码的空间 存放数据项目的空间 存放程序运行的控制或连接数据所需单元(控制栈：跟踪过程活动),一个程序在运行时刻的内存划分:,代码(Code),静态数据 (Static Data),栈(Stack),堆(Heap),9.2.2 活动记录,假定语言的特点为:允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如C语言。 采用栈式存储分配机制 活动记录：运行时，每当进入一个过程就有
9、一个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。,对任何局部变量X的引用可表示为变址访问:dxSPdx: 变量X相对于活动记录起点的地址，在编译时可确定。,参数个数,返回地址,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,老SP,TOP,每个过程的活动记录内容(非嵌套语言),连接数据 返回地址 动态链：指向调用该过程前的最新活动记录地址的指针。 静态链：指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。,静态链,动态链,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,返回地址,TOP,每个过程的活动记录内
10、容(嵌套语言),形式单元：存放相应的实在参数的地址或值。 局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。,静态链,动态链,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,返回地址,TOP,每个过程的活动记录内容,静态分配策略(FORTRAN)如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。 动态分配策略(PASCAL)如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程和动态申请释放内存。 栈式动态分配 堆式动态分配,9.2.3 存储分配策略,PROGRAM MA
11、IN integer X，Y COMMON /C/A，B END SUBROUTINE SUB1 real X，Z COMMON /C/A1，B1 END,9.3 静态存储管理,9.3 静态存储管理,FORTRAN程序的特点：整个程序所需数据空间的总量在编译时完全确定，每个数据名的地址可以静态地进行分配。 由于每个FORTRAN 程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据区组织存储: 每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值。 每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。,每个数据区有一个编号，地址分配时，在符
12、号表中，对每个数据名登记其所属数据区编号及在该区中的相对位置。 每个局部数据区的内容及存放次序:,寄存器保护区,返回地址,形式单元,临时变量,数组,简单变量,0,1,A,考虑子程序段： SUBROUTINE SWAP(A,B) T=A A=B B=T RETURN END,寄存器保护区,返回地址,A,T,B,0,1,a,9.4 一个简单栈式存储分配,假定语言的特点为:允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如C语言。 采用栈式存储分配机制 活动记录：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工
13、作单元等。,全局数据说明 Main( ) Main中的数据说明 void R( ) R中的数据说明 void Q( ) Q中的数据说明 ,主程序过程Q 过程R,Q的活动记录,主程序活动记录,TOP,R的活动记录,SP,全局数据区,每个过程的活动记录内容如图:,对任何局部变量X的引用可表示为变址访问:dxSPdx: 变量X相对于活动记录起点的地址，在编译时可确定。,参数个数,返回地址,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,老SP,TOP,9.4.1 C的活动记录,过程调用的四元式序列:par T1par T2par Tncall P，n,9.4.2 C的过程调用、过程进入、数
14、组空间分配和过程返回,1) 每个par Ti(i=1,2,n)可直接翻译成如下指令:(i+3)TOP:= Ti (传值)(i+3)TOP:=addr(Ti) (传地址)2) call P，n 被翻译成: 1TOP:=SP (保护现行SP) 3TOP:=n (传递参数个数) JSR P (转子指令),对于par和call产生的目标代码如下:,形式单元,老SP,参数个数,3) 转进过程P后，首先应执行下述指令:SP:=TOP+1 (定义新的SP)1SP:=返回地址 (保护返回地址)TOP:=TOP+L (新TOP)L：过程P的活动记录所需单元数，在编译时可确定。,返回地址,TOP,SP,4) 过程
15、返回时，应执行下列指令:TOP:=SP-1 (恢复调用前TOP)SP:=0SP (恢复调用前SP)X:=2TOP (把返回地址取到X中)UJ 0X (按X返回),TOP,SP,SP,TOP,9.5 嵌套过程语言的栈式实现,PASCAL 非局部名字的访问的实现 静态链和活动记录 嵌套层次显示表display 过程调用、过程进入、过程返回,嵌套过程语言的栈式实现,PASCAL 非局部名字的访问的实现 静态链和活动记录 嵌套层次显示表display 过程调用、过程进入、过程返回,9.5 嵌套过程语言的栈式实现,假定语言不仅允许过程的递归调用(和可变数组)，而且允许过程定义的嵌套，如PASCAL，PL
16、语言。,PASCAL PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 一个PASCAL过程： 过程头； 说明段（由一系列的说明语句组成）； begin 执行体（由一系列的执行语句组成）； end,9.5 嵌套过程语言的栈式实现,作用域：一个名字能被使用的区域范围称作这个名字的作用域。 允许同一个标识符在不同的过程中代表不同的名字。 名字作用域规则-“最近嵌套原则“ 一个在子程序B1中说明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。,
