Ch8运行时存储空间组织

1、第八章第八章 运行时存储空间组织运行时存储空间组织8.1 目标程序运行时的活动目标程序运行时的活动 n以以Pascal为例，假定程序由若干个过程组成为例，假定程序由若干个过程组成 q过程（过程（procedure）定义定义q一个过程的一个过程的活动活动指的是该过程的一次执行指的是该过程的一次执行 q过程过程P一个一个活动的生存期活动的生存期，指的是从执行该过程体，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执第一步操作到最后一步操作之间的操作序，包括执行行P时调用其它过程花费的时间时调用其它过程花费的时间q过程可以是过程可以是递归递归的的（1） program sort(in

2、put, 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） function partition(y, z:integer):integer;（9） var i:integer;（10） begin .（11） end;program sort procedure readarray function partition(y procedure quicksort（12） proce

3、dure 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, 9 )（25） gram sort procedure readarray function partit

4、ion(y procedure quicksort参数传递参数传递n过程是模块程序设计的主要手段，同时也是节过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言的主要途径。省程序代码和扩充语言的主要途径。n过程定义：过程定义：procedure add(x,y:integer; var z:integer) begin z：=x+y; end;n过程调用过程调用 add(a,b,c); 参数传递方式参数传递方式一一. . 传地址传地址n把实在参数的地址传递给相应的形式参数把实在参数的地址传递给相应的形式参数n方法：方法：q调用段预先把实在参数的地址传递到被调用段可调用段预先把实在参数的

5、地址传递到被调用段可以拿到的地方以拿到的地方；q程序控制转入被调用段之后，被调用段首先把实程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中在参数的地址抄进自己相应的形式单元中；q过程体对形式参数的引用域赋值被处理过程体对形式参数的引用域赋值被处理成成对形式对形式单元的间接访问。单元的间接访问。nPASCAL的变量参数方式的变量参数方式procedure swap (var m:integer; var n: integer); var i:integer; begin i:=m; m:=n; n:=i; endq swap(a,b) 把把a,b的地址送到已知单元的

6、地址送到已知单元j1和和j2中中 m:=j1; n:=j2; i:=m; m:= n; n:=i;参数传递方式参数传递方式二得结果二得结果n传地址的一种变形传地址的一种变形n方法：方法：q每个形参对应两个形式单元，第一个形式单元存放每个形参对应两个形式单元，第一个形式单元存放实参地址，第二个单元存放实参的值。实参地址，第二个单元存放实参的值。q在过程体中对形式参数的任何引用或赋值都看作对在过程体中对形式参数的任何引用或赋值都看作对它的第二个单元的直接访问。它的第二个单元的直接访问。q过程完成返回前把第二个单元的内容存放到第一个过程完成返回前把第二个单元的内容存放到第一个单元所指的实参单元中。单

7、元所指的实参单元中。n有些有些Fortran采用这种方式；采用这种方式；参数传递方式参数传递方式三三传值传值n把实在参数的把实在参数的值值传递给相应的形式参数传递给相应的形式参数n方法：方法：q调用段预先把实在参数的的值计算出来并放在被调用段预先把实在参数的的值计算出来并放在被调用段可以拿到的地方调用段可以拿到的地方；q被调用段开始工作时，首先把实参的值抄入形式被调用段开始工作时，首先把实参的值抄入形式参数相应的单元参数相应的单元；q被调用段中，象引用局部数据一样引用形式单元。被调用段中，象引用局部数据一样引用形式单元。nPASCAL的值参数的值参数参数传递方式参数传递方式四四传名传名n过程调

8、用的作用相当于把被调用段的过程体过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实参。形式参数都替换成相应的实参。n方法：方法： q在进入被调用段的之前不对实在参数预先进行计在进入被调用段的之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参数值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行计值（或计算地址）。因此，时才逐次对它实行计值（或计算地址）。因此，通常把实在参数处理成一个子程序（称为参数子通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形式参数时程

9、序），每当过程体中使用到相应的形式参数时就调用这个子程序。就调用这个子程序。PROGRAM EX var A:integer;PROCEDURE 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);ENDBEGIN 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,

10、a); write(a);end传值传值:传地址传地址:得结果得结果:传名传名:542777n编译程序为了组织存储空间，必须考虑下面编译程序为了组织存储空间，必须考虑下面几个问题：几个问题：q过程是否允许递归？过程是否允许递归？q当控制从一个过程的活动返回时，对局部名称当控制从一个过程的活动返回时，对局部名称的值如何处理？的值如何处理？q过程是否允许引用非局部名称？过程是否允许引用非局部名称？q过程调用时如何传递参数；过程是否可以做为过程调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返回？参数被传递和做为结果被返回？q存储空间可否在程序控制下进行动态分配？存储空间可否在程序控制下进

11、行动态分配？q存储空间是否必须显式地释放？存储空间是否必须显式地释放？ 8.2 运行时存储器的划分运行时存储器的划分 n一个目标程序运行所需的存储空间包括一个目标程序运行所需的存储空间包括:q存放目标代码的空间存放目标代码的空间q存放数据项目的空间存放数据项目的空间q存放程序运行的控制或连接数据所需单元存放程序运行的控制或连接数据所需单元(控制栈控制栈)n一个程序在运行时刻的内存划分一个程序在运行时刻的内存划分:代码代码(Code)静态数据静态数据(Static Data)栈栈(Stack) 堆堆(Heap) 8.2.2 活动记录活动记录n假定语言的特点为假定语言的特点为:允许过程递归调用、允

12、许允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，过程含有可变数组，但过程定义不允许嵌套，如如C语言语言。n采用栈式存储分配机制采用栈式存储分配机制n活动记录：运行时，每当进入一个过程就有一活动记录：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记录含有连个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。情向量和临时工作单元等。对任何局部变量对任何局部变量X的的引用可表示为变址访引用可表示为变址访问问: dxSP dx: 变量变量X相对于活相对于活动记录起点的地址，动记录起

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

14、12返回地址返回地址TOP 每个过程的活动记录内容每个过程的活动记录内容(嵌套语言嵌套语言)q形式单元：存放相形式单元：存放相应的实在参数的地应的实在参数的地址或值。址或值。q局部数据区：局部局部数据区：局部变量、内情向量、变量、内情向量、临时工作单元（如临时工作单元（如存放对表达式求值存放对表达式求值的结果）。的结果）。静态链静态链动态链动态链形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012返回地址返回地址TOP 每个过程的活动记录内容每个过程的活动记录内容n 静态分配策略静态分配策略(FORTRAN) 如果在编译时能确定数据空间的大小，则可采用静态如果在编译时能

15、确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定出在运行分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。时刻的存储空间中的位置。n动态分配策略动态分配策略(PASCAL) 如果在编译时不能确定运行时数据空间的大小，则必如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程和动态申请释放须采用动态分配方法。允许递归过程和动态申请释放内存。内存。q栈式动态分配栈式动态分配q堆式动态分配堆式动态分配8.2.3 8.2.3 存储分配策略存储分配策略 PROGRAM MAIN integer X，YCOMMON /C/A，B ENDSU

16、BROUTINE SUB1 real X，ZCOMMON /C/A1，B1 END8.3 静态存储管理静态存储管理8.3 静态存储管理静态存储管理nFORTRAN程序的特点：整个程序所需数据空间的程序的特点：整个程序所需数据空间的总量在编译时完全确定，每个数据名的地址可以静总量在编译时完全确定，每个数据名的地址可以静态地进行分配。态地进行分配。n由于每个由于每个FORTRAN 程序段可以独立编译，运行前程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据由装入程序把各段连成可运行的整体。通常按数据区组织存储区组织存储:q每个程序段定义一个局部数据区，用来存放程序段中每个程序段

17、定义一个局部数据区，用来存放程序段中未出现在未出现在COMMON里的局部名的值。里的局部名的值。q每个公用块定义一个公用数据区，用来存放公用块里每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。各个名字的值。n每个数据区有一个编号，地址分配时，在符每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记其所属数据区编号表中，对每个数据名登记其所属数据区编号及在该区中的相对位置。号及在该区中的相对位置。n每个局部数据区的内容及存放次序每个局部数据区的内容及存放次序:寄存器保护区寄存器保护区返回地址返回地址形式单元形式单元临时变量临时变量数组数组简单变量简单变量01An考虑子程序段

18、：考虑子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND地地址址名名字字N NA AM ME E性性质质A AT TT TR RI IB BU UT TE ED DA A A AD DD DR RS SW WA AP P子子程程序序，二二目目A A哑哑，实实变变量量k ka aB B哑哑，实实变变量量k ka a+ +2 2T T实实变变量量k ka a+ +4 4寄存器保护区寄存器保护区返回地址返回地址ATB01a8.4 一个简单栈式存储分配一个简单栈式存储分配n假定语言的特点为假定语言的特点为:允许过程递归调用、允许允许过程递归调用、允许过程含有可变数组

19、，但过程定义不允许嵌套，过程含有可变数组，但过程定义不允许嵌套，如如C语言语言。n采用栈式存储分配机制采用栈式存储分配机制n活动记录：运行时，每当进入一个过程就有一活动记录：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记录含有连个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。情向量和临时工作单元等。 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过

20、程Q 过过程程RQ的活动记录的活动记录主程序主程序活动记录活动记录TOPR的活动记录的活动记录SP参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元全局数据区全局数据区n每个过程的活动记录内容如图每个过程的活动记录内容如图:对任何局部变量对任何局部变量X的的引用可表示为变址访引用可表示为变址访问问: dxSP dx: 变量变量X相对于活相对于活动记录起点的地址，动记录起点的地址，在编译时可确定。在编译时可确定。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP 8.4.

21、1 C的活动记录的活动记录 n过程调用的四元式序列过程调用的四元式序列:par T1par T2 par Tncall P，n8.4.2 C的过程调用、过程进入、的过程调用、过程进入、数组空间分配和过程返回数组空间分配和过程返回 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 (转子指令转子指令)参数个数参数个数返回地址返回地

22、址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元对于对于par和和call产生的目标代码如下产生的目标代码如下:TOP SP 调用过程的调用过程的活动记录活动记录形式单元形式单元老老SP参数个数参数个数3) 转进过程转进过程P后，首先应执行下述指令后，首先应执行下述指令:SP:=TOP+1 (定义新的定义新的SP)1SP:=返回地址返回地址 (保护返回地址保护返回地址)TOP:=TOP+L (新新TOP) L：过程过程P的活动记录所需单元数，的活动记录所需单元数， 在编译时可确定。在编译时可确定。 参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变

23、量局部变量老老SP临时单元临时单元TOP 调用过程的活动记录调用过程的活动记录返回地址返回地址TOPSP4) 过程返回时，应执行下列指令过程返回时，应执行下列指令:TOP:=SP-1 (恢复调用前恢复调用前TOP)SP:=0SP (恢复调用前恢复调用前SP)X:=2TOP (把返回地址把返回地址取到取到X中中)UJ 0X (按按X返回返回)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元调用过程的活动记录调用过程的活动记录TOPSPSPTOP8.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名

24、字的访问的实现q静态链和活动记录静态链和活动记录q嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现q静态链和活动记录静态链和活动记录q嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回8.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现n假定语言不仅允许过程的递归调用假定语言不仅允许过程的递归调用(和可变数和可变数组组)，而且允许过程定义的嵌套，如，而且允许过程定义的嵌套，如PASCAL，P

25、L语言。语言。nPASCALqPASCAL程序本身可以看成是一个操作系统所程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。调用的过程，过程可以嵌套和递归。q一个一个PASCAL过程：过程：过程头；过程头；说明段（由一系列的说明语句组成）；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；执行体（由一系列的执行语句组成）；end8.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现q作用域作用域：一个名字能被使用的区域范围称：一个名字能被使用的区域范围称作这个名字的作用域。作这个名字的作用域。q允许同一个标识符在不同的过程中代表不允许同一个标识符在不同的

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

27、B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integr)嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现q静态链和活动记录静态链和活动记录q嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回8.5.1 非局部名字的访问的实现非局部名字的访问的实现 n主程序的层次为主程序的层次为0；在；在i层中定义的过程，其层层中定义的过程，其层次为次为i+1;(层数，层

28、数， 偏移量偏移量)n过程运行时，必须知道过程运行时，必须知道其其所有外层过程的当前所有外层过程的当前活动记录的起始地址。活动记录的起始地址。嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现q静态链和活动记录静态链和活动记录q嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回图图9.15 程序程序program P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure R(u: integer; var v:

29、 integer);var c, d: integer;begin if u=1 then R(u+1, v).v:=(a+c)*(b-d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 过程过程 S 过过程程 Q 过程过程 R 过程过程 R一、静态链和活动记录一、静态链和活动记录 n静态链静态链：指向本过程的：指向本过程的直接外层过程的活动记直接外层过程的活动记录的起始地址，也称存录的起始地址，也称存取链。取链。n动态链动态链：指向本过

30、程的：指向本过程的调用过程的活动记录的调用过程的活动记录的起始地址，也称控制链。起始地址，也称控制链。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP012动态链动态链(老老SP)TOP 静态链静态链00返回地址返回地址102a3x4SP TOPq主程序主程序P00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P过程过程 S？第第N层过程调用层过程调用第第 N+1层过程，如何层过程，如何确定被调用过程确定被调用过程(第第 N+1层层)过程的静态链？过

31、程的静态链？A:调用过程调用过程(第第N层层过程过程)的最新活动记录的最新活动记录的起始地址的起始地址.00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i16？第第N层过程调用层过程调用第第 N层过程，如何确层过程，如何确定被调用过程定被调用过程(第第 N层层)过程的静态链？过程的静态链？A:调用过程调用过程(第第N层层过程过程)的静态链的值。的静态链的值。00返回地址返回地址102a3x405

32、返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v(形参形参)22c23d24SP TOP00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 R511返回地址返回地址120131(形参个数形参个数)14b(形参形

33、参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v(形参形参)22c23d241725返回地址返回地址2611272(形参个数形参个数)28u(形参形参)29v(形参形参)30c31d32TOPSP 00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 Q511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v

34、(形参形参)22c23d24TOPSP 1725返回地址返回地址260271(形参个数形参个数)28b(形参形参)29i30？第第N层过程调用层过程调用第第 N-x层过程，如何层过程，如何确定被调用过程确定被调用过程(第第 N-x层层)过程的静态链？过程的静态链？A:沿着调用过程沿着调用过程(第第N层过程层过程)的静态链的的静态链的向前走向前走x步到达的活步到达的活动记录的静态链的值。动记录的静态链的值。嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现q静态链和活动记录静态链和活动记录q嵌套层次显示表嵌套层次显示表displayn过程调用

35、、过程进入、过程返回过程调用、过程进入、过程返回二、嵌套层次显示表二、嵌套层次显示表displayn当进入一个过程后，在建立其活动记录区当进入一个过程后，在建立其活动记录区的同时建立一张嵌套层次显示表的同时建立一张嵌套层次显示表diaplay，把把diaplay表作为活动记录的一部分。表作为活动记录的一部分。n令过程令过程R的外层为的外层为Q，Q的外层为主程序为的外层为主程序为P，则过程则过程R运行时的运行时的DISPLAY表内容为：表内容为：2R 的的现现行行活活动动记记录录的的地地址址(SP 的的现现值值)1Q 的的最最新新活活动动记记录录的的地地址址0P 的的活活动动记记录录的的地地址址

36、n问题：问题：当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P1P2P0P2P1P0P1P2n问题：问题：当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P1P2l2: P1的最新活动记的最新活动记录的起始地址录的起始地址P0的最新活动记的最新活动记录的起始地址录的起始地址P1的的display表表P0的最新活动记录的最新活动记录的起始地址的起始地址l2: P2的最新活动记的最新活动记录的起始地址录的起始地址P2的的display表表从从

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

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

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

40、单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后新建后新建立的立的SP值就构成了值就构成了P2的的display表。表。F把把P1的的display表地址作为连接数据之一传送表地址作为连接数据之一传送给给P2就能够建立就能够建立P2的的display表。表。P0P1P2P0P2P1P0P1P2ndiaplay表在活动记录表在活动记录中中的相对地址的相对地址d在编译在编译时能完全确定。时能完全确定。n假定在现行过程中引假定在现行过程中引用了某层过程用了某层过程(令其层令其层次为次为k)的的X变量，那么，变量，那么，可用下面两条指令获可用下面两条指令获得得X的地址的地址: LD R1

41、(d+k)SP LD R2 dxR1嵌套过程语言活动记录嵌套过程语言活动记录参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP Display 表表全局全局Diaplay3d图图9.15 程序程序program P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure R(u: integer; var v: integer);var c, d: integer;begin if u=1 then R(u+1, v).v:=(a+c)*(b-

42、d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 过程过程 S 过过程程 Q 过程过程 R 过程过程 R00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参个数形参个数)809510主程序主程序过过程程 Sc11i12TOPSP 动态链动态链00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参个数形参个数)809510

43、主程序主程序P过程过程 S 过过程程 Qc11i12动态链动态链513返回地址返回地址149(全局全局display)151(形参个数形参个数)16b(形参形参)170181319i20TOPSP 00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参个数形参个数)809510主程序主程序P过程过程 S 过过程程 Q 过程过程 Rc11i12动态链动态链513返回地址返回地址149(全局全局display)151(形参个数形参个数)16b(形参形参)170181319i201321返回地址返回地址2218(全局全局display)232

44、(形参个数形参个数)24u(形参形参)25v(形参形参)2602713282129c30d31TOPSP 00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参个数形参个数)809510主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 Rc11i12动态链动态链513返回地址返回地址149(全局全局display)151(形参个数形参个数)16b(形参形参)170181319i201321返回地址返回地址2218(全局全局display)232(形参个数形参个数)24u(形参形参)25v(形参形参)2602713282

45、129c30d31TOPSP 2132返回地址返回地址3327(全局全局display)342(形参个数形参个数)35u(形参形参)36v(形参形参)3703813393240c41d42嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现q静态链和活动记录静态链和活动记录q嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量老老SPDisplay 表表全局全局Diaplay1. 每个每个par Ti

46、(i=1,2,n)可直接翻译成可直接翻译成如下指令如下指令:(i+4)TOP:= Ti (传值传值) (i+4)TOP:=addr(Ti ) (传地址传地址)过程调用、过程进入、过程返回过程调用、过程进入、过程返回TOPSP 调用过程的调用过程的活动记录活动记录形式单元形式单元参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量老老SPDisplay 表表全局全局Diaplay2. call P，n 被翻译成被翻译成:1TOP:=SP (保护现行保护现行SP)3TOP:=SP+d (传送现行传送现行display地址地址)4TOP:=n (传递参数个

47、数传递参数个数)JSR (转子指令转子指令)过程调用、过程进入、过程返回过程调用、过程进入、过程返回TOPSP 调用过程的调用过程的活动记录活动记录老老SP全局全局Diaplay参数个数参数个数3. 转进过程转进过程P后，首先后，首先定义新的定义新的SP和和TOP，保存返回地址。保存返回地址。4. 根据根据全局全局display建立现行过程的建立现行过程的display：从全局从全局display表中自底向表中自底向上地取上地取l个单元，在个单元，在添上进入添上进入P后新建立后新建立的的SP值就构成了值就构成了P的的display。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单

48、元内情向量内情向量局部变量局部变量老老SPDisplay 表表全局全局DiaplayTOPSP 调用过程的调用过程的活动记录活动记录返回地址返回地址Display 表表5. 过程返回时，执行下述指令过程返回时，执行下述指令: TOP:=SP-1SP:=0SPX:=2TOPUJ 0X参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量老老SPDisplay 表表全局全局DiaplayTOPSP 调用过程的调用过程的活动记录活动记录TOPSP 嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现q静态链

49、和活动记录静态链和活动记录q嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回三、上面两种方法的三、上面两种方法的折中折中PL编译程序编译程序建立一个总的运行时的建立一个总的运行时的diaplay表表(而不是每个而不是每个过程的活动记录中都有一个过程的活动记录中都有一个)，它记录正被调，它记录正被调用执行的过程及其所有外层过程的活动记录用执行的过程及其所有外层过程的活动记录的起始地址。通过这个的起始地址。通过这个diaplay访问数据。访问数据。在各过程活动记录之间保留一条在各过程活动记录之间保留一条静态链静态链SL，它主要用于由它主要用于由层次大层次大的过程调用的过程调用层次小层次小的过的过程后程后返回返回时，恢复调用前的时，恢复调用前的display内容。内容。(这这时，调用返回后，执行一条时，