编译原理课件09-运行时存储空间组织.ppt

《编译原理课件09-运行时存储空间组织.ppt》由会员分享，可在线阅读，更多相关《编译原理课件09-运行时存储空间组织.ppt（53页珍藏版）》请在三一办公上搜索。

1、第九章 运行时存储空间组织,9.1 目标程序运行时的活动 以Pascal为例，假定程序由若干个过程组成 过程（procedure）定义一个过程的活动指的是该过程的一次执行 过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间过程可以是递归的,（1）program sort(input,output)（2）var a:array0.10 of integer;（3）procedure readarray;（4）var i:integer;（5）begin（6）for i:=1 to 9 do read(ai)（7）end;（8）fu

2、nction partition(y,z:integer):integer;（9）var i:integer;（10）begin.（11）end;,（12）procedure quicksort(m,n:integer);（13）var i:integer;（14）begin（15）if(nm)then begin（16）i:=partition(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,

3、9)（25）end.,9.1.2 参数传递,过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言的主要途径。过程定义：procedure add(x,y:integer;var z:integer)begin z：=x+y;end;过程调用 add(a,b,c);,参数传递方式,一.传地址把实在参数的地址传递给相应的形式参数方法：调用段预先把实在参数的地址传递到被调用段可以拿到的地方；程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中；过程体对形式参数的引用域赋值被处理成对形式单元的间接访问。PASCAL的变量参数方式,procedure swap(var

4、m:integer;var n:integer);var i:integer;begin i:=m;m:=n;n:=i;end,swap(a,b)把a,b的地址送到已知单元j1和j2中m:=j1;n:=j2;i:=m;m:=n;n:=i;,参数传递方式,二得结果传地址的一种变形方法：每个形参对应两个形式单元，第一个形式单元存放实参地址，第二个单元存放实参的值。在过程体中对形式参数的任何引用或赋值都看作对它的第二个单元的直接访问。过程完成返回前把第二个单元的内容存放到第一个单元所指的实参单元中。有些Fortran采用这种方式；,参数传递方式,三传值把实在参数的值传递给相应的形式参数方法：调用段预

5、先把实在参数的的值计算出来并放在被调用段可以拿到的地方；被调用段开始工作时，首先把实参的值抄入形式参数相应的单元；被调用段中，象引用局部数据一样引用形式单元。PASCAL的值参数,参数传递方式,四传名过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实参。方法：在进入被调用段的之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行计值（或计算地址）。因此，通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形式参数时就调用这个子程序。,PROGRAM EX var A:integer;PROCE

6、DURE P(B:integer)var A:integer;BEGIN A:=0;B:=B+1;A:=A+B;END;,BEGIN A:=2;TA:=0;A:=A+1;TA:=TA+A;write(A);END,BEGIN A:=2;P(A);write(A);END,例：procedure P(w,x,y,z);begin y:=y*w;z:=z+x;endbegin a:=5;b:=3;P(a+b,a-b,a,a);write(a);end,传值:5传地址:42得结果:7传名:77,编译程序为了组织存储空间，必须考虑下面几个问题：过程是否允许递归？当控制从一个过程的活动返回时，对局部名称

7、的值如何处理？过程是否允许引用非局部名称？过程调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返回？存储空间可否在程序控制下进行动态分配？存储空间是否必须显式地释放？,9.2 运行时存储器的划分,一个目标程序运行所需的存储空间包括:存放目标代码的空间存放数据项目的空间存放程序运行的控制或连接数据所需单元(跟踪过程活动的控制栈),一个程序在运行时刻的内存划分:,代码(Code),静态数据(Static Data),栈(Stack),堆(Heap),9.2.2 活动记录,活动记录(连续存储块,用于管理过程)：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记录含有连接数据、形

8、式单元、局部变量、局部数组的内情向量和临时工作单元等。活动记录采用栈式存储分配机制。,对任何局部变量X的引用可表示为变址访问:dxSP dx:变量X相对于活动记录起点的地址，在编译时可确定。,参数个数,返回地址,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,老SP,TOP,每个过程的活动记录内容如图:,连接数据返回地址动态链：指向调用该过程前的最新活动记录地址的指针。静态链：指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。,静态链,动态链,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,返回地址,TOP,每个过程的活动记录内容,形式单元：存放相应的实在参数的地

9、址或值。局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。,静态链,动态链,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,返回地址,TOP,每个过程的活动记录内容,静态分配策略(FORTRAN)如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。动态分配策略(PASCAL)如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程和动态申请释放内存。栈式动态分配堆式动态分配,9.2.3 存储分配策略,9.3静态存储管理,FORTRAN程序的特点：整个程序所需数据空间的总量在编

10、译时完全确定，每个数据名的地址可以静态地进行分配。由于每个FORTRAN 程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据区组织存储:每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值。每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。,每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记其所属数据区编号及在该区中的相对位置。每个局部数据区的内容及存放次序:,寄存器保护区,返回地址,形式单元,临时变量,数组,简单变量,0,1,A,考虑子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND,寄

11、存器保护区,返回地址,A,T,B,0,1,a,9.4 一个简单栈式存储分配,假定语言的特点为:允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如C语言。采用栈式存储分配机制活动记录：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。,全局数据说明Main()Main中的数据说明 void R()R中的数据说明void Q()Q中的数据说明,主程序过程Q 过程R,Q的活动记录,主程序活动记录,TOP,R的活动记录,SP,全局数据区,每个过程的活动记录内容如图:,对任何局部变量X的引用可表示为变址访问

12、:dxSP dx:变量X相对于活动记录起点的地址，在编译时可确定。,参数个数,返回地址,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,老SP,TOP,9.4.1 C的活动记录,9.5 嵌套过程语言的栈式实现,假定语言不仅允许过程的递归调用(和可变数组)，而且允许过程定义的嵌套，如PASCAL，PL语言。,PASCALPASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。一个PASCAL过程：过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；end,9.5 嵌套过程语言的栈式实现,作用域：一个名字能被使用的区域范围称作这个名字

13、的作用域。允许同一个标识符在不同的过程中代表不同的名字。名字作用域规则-最近嵌套原则一个在子程序B1中说明的名字X只在B1中有效（局部于B1）；如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。,program main var A,B:real;procedure P1 var B:boolean;begin end procedure P2 var A:integer;begin endbegin end,A(real),B(real),B(bool),A(integr)

14、,嵌套过程语言的栈式实现,PASCAL非局部名字的访问的实现静态链和活动记录嵌套层次显示表display,非局部名字的访问的实现,主程序的层次为0；在i层中定义的过程，其层次为i+1;过程运行时，必须知道包围其所有外层过程的最新活动记录的起始地址。,嵌套过程语言的栈式实现,PASCAL非局部名字的访问的实现静态链和活动记录嵌套层次显示表display,一、静态链和活动记录 静态链：指向本过程的直接外层过程的活动记录的起始地址，也称存取链。动态链：指向本过程的调用过程的活动记录的起始地址，也称控制链。,参数个数,返回地址,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,动态链(老SP)

15、,TOP,静态链,SP,TOP,主程序P,SP,TOP,动态链,静态链,主程序P过程 S,？第N层过程调用第 N+1层过程，如何确定被调用过程(第 N+1层)过程的静态链？,A:调用过程(第N层过程)的最新活动记录的起始地址.SL(N+1)=SP(N),SP,TOP,动态链,静态链,主程序P 过程 S 过程 Q,？第N层过程调用第 N层过程，如何确定被调用过程(第 N层)过程的静态链？,A:SL(N+1)=SL(N),动态链,静态链,主程序P 过程 S 过程 Q 过程 R,SP,TOP,动态链,静态链,主程序P 过程 S 过程 Q 过程 R 过程 R,TOP,SP,动态链,静态链,主程序P 过

16、程 S 过程 Q 过程 R 过程 Q,TOP,SP,？第N层过程调用第 N-x层过程，如何确定被调用过程(第 N-x层)过程的静态链？,A:沿着调用过程(第N层过程)的静态链的向前走x步到达的活动记录的静态链的值。,嵌套过程语言的栈式实现,PASCAL非局部名字的访问的实现静态链和活动记录嵌套层次显示表display,二、嵌套层次显示表display当进入一个过程后，在建立其活动记录区的同时建立一张嵌套层次显示表diaplay，把diaplay表作为活动记录的一部分。,令过程R的外层为Q，Q的外层为主程序为P，则过程R运行时的DISPLAY表内容为：,非局部量的绝对地址=display静态层数

17、+相对地址,问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？,问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？,l2:P1的最新活动记录的起始地址,P0的最新活动记录的起始地址,P1的display表,P0的最新活动记录的起始地址,l2:P2的最新活动记录的起始地址,P2的display表,从P1的display表中自底而上地取过l2个单元（l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。,问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？,l2-1:P1的最新活

18、动记录的起始地址,P0的最新活动记录的起始地址,P1的display表,P0的最新活动记录的起始地址,P1的最新活动记录的起始地址,P2的display表,从P1的display表中自底而上地取过l2个单元（l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。,l2:P2的最新活动记录的起始地址,问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？,P1的最新活动记录的起始地址,P0的最新活动记录的起始地址,P1的display表,P0的最新活动记录的起始地址,P2的display表,从P1的display表中自底而上地取过l2个单元（

19、l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。,l2:P2的最新活动记录的起始地址,l2:P2的最新活动记录的起始地址,问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？,答案：从P1的display表中自底而上地取过l2个单元（l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。把P1的display表地址作为连接数据之一传送给P2就能够建立P2的display表。,diaplay表在活动记录中的相对地址d在编译时能完全确定。假定在现行过程中引用了某层过程(令其层次为k)的X变量，那么，可用下面两条指令获得X的地址:LD R1(d+k)SPLD R2 dxR1,嵌套过程语言活动记录,参数个数,返回地址,形式单元,临时单元,内情向量,局部变量,SP 0,1,2,老SP,TOP,Display 表,全局Diaplay,3,d,主程序P 过程 S,TOP,SP,动态链,主程序P过程 S 过程 Q,动态链,TOP,SP,主程序P过程 S 过程 Q 过程 R,动态链,TOP,SP,主程序P 过程 S 过程 Q 过程 R 过程 R,动态链,TOP,SP,作业,P2694 P2709,练习,P2695,