1、编译原理第九章第九章 运行时存储空间组织运行时存储空间组织第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现第九章第九章 运行时存储空间组织运行时存储空间组织9.1 目标程序运行时的活动目标程序运行时的活动 n以以Pascal为例，假定程序由若干个过程组为例，假定程序由若干个过程组成成 过程（过程（procedure）定义定义一个过程的一个过程的活动活动指的是该过程的一次执行指的是该过程的一次执行 过
2、程过程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） function partit
3、ion(y, z:integer):integer;（9） var i:integer;（10） begin .（11） end;program sort procedure readarray function partition procedure quicksort（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 )（
4、19） end;（20） end;（21） begin（22） a0:=-9999; a10:=9999;（23） readarray;（24） quicksort(1, 9 )（25） end.program sort procedure readarray function partition procedure quicksort参数传递参数传递n过程是模块程序设计的主要手段，同时也过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言的主要途径。是节省程序代码和扩充语言的主要途径。n过程定义：过程定义：procedure add(x,y:integer; var z:intege
5、r) begin z：=x+y; end;n过程调用过程调用 add(a,b,c); 参数传递方式参数传递方式n传地址传地址n得结果得结果n传值传值n传名传名参数传递方式参数传递方式一一. . 传地址传地址n把实在参数的地址传递给相应的形式参数把实在参数的地址传递给相应的形式参数n方法：方法：调用段预先把实在参数的调用段预先把实在参数的地址地址传递到被调用段传递到被调用段可以拿到的地方可以拿到的地方；程序控制转入被调用段之后，被调用段首先把程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中实在参数的地址抄进自己相应的形式单元中；过程体对形式参数的引用域赋值被处理过程
6、体对形式参数的引用域赋值被处理成成对对形形式单元的间接访问式单元的间接访问。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的地址送到已知单元的地址送到已知单元j1和和j2中中 m:=j1; n:=j2; i:=m; m:= n; n:=i;参数传递方式参数传递方式二得结果二得结果n传地址的一种变形传地址的一种变形n方法：方法：每个形参对应两个形式单元，第一个形式单元每个形参对应两个形式单
7、元，第一个形式单元存放存放实参地址实参地址，第二个单元存放，第二个单元存放实参的值实参的值。在过程体中对形式参数的任何引用或赋值都看在过程体中对形式参数的任何引用或赋值都看作作对它的第二个单元的直接访问对它的第二个单元的直接访问。过程完成返回前把第二个单元的内容存放到第过程完成返回前把第二个单元的内容存放到第一个单元所指的实参单元中。一个单元所指的实参单元中。n有些有些Fortran采用这种方式；采用这种方式；参数传递方式参数传递方式三三传值传值n把实在参数的把实在参数的值传递给相应的形式参数值传递给相应的形式参数n方法：方法：调用段预先把实在参数的的值计算出来并放调用段预先把实在参数的的值计
8、算出来并放在被调用段可以拿到的地方；在被调用段可以拿到的地方；被调用段开始工作时，首先把实参的值抄入被调用段开始工作时，首先把实参的值抄入形式参数相应的单元；形式参数相应的单元；被调用段中，象引用局部数据一样引用形式被调用段中，象引用局部数据一样引用形式单元。单元。nPASCAL的值参数的值参数参数传递方式参数传递方式四四传名传名n过程调用的作用相当于把被调用段的过程过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实参。现的形式参数都替换成相应的实参。n方法：方法： 在进入被调用段之前不对实在参数预先进行计在
9、进入被调用段之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行计值（或计算地址）。因数时才逐次对它实行计值（或计算地址）。因此，通常把实在参数处理成一个子程序（称为此，通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形参数子程序），每当过程体中使用到相应的形式参数时就调用这个子程序。式参数时就调用这个子程序。PROGRAM EX var A:integer;PROCEDURE P(B:integer)var A:integer;BEGIN A:=0; B:=B+1; A:=A+B;END;BEG
10、IN 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,a); write(a);end传值传值:传地址传地址:得结果得结果:传名传名:542777传名传名procedure P(w,x,y,z);begin y := y*w; z := z+x;endbegin a := 5; b := 3; P(a+
11、b,a-b,a,a); write(a);endBEGIN a := 5; b := 3 a:= a*(a+b) ; a:= a+(a-b) ; write(a);END小结 传值、传址、得结果、传名第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现编译程序组织存储空间须考虑的问题：编译程序组织存储空间须考虑的问题：过程是否允许递归？过程是否允许递归？当控制从一个过程的活动返回时，对局部名当控制从一个
12、过程的活动返回时，对局部名称的值如何处理？称的值如何处理？过程是否允许引用非局部名称？过程是否允许引用非局部名称？过程调用时如何传递参数；过程是否可以做过程调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返回？为参数被传递和做为结果被返回？存储空间可否在程序控制下进行动态分配？存储空间可否在程序控制下进行动态分配？存储空间是否必须显式地释放？存储空间是否必须显式地释放？ 9.2 运行时存储器的划分运行时存储器的划分 n一个一个目标程序运行目标程序运行所需的存储空间包括所需的存储空间包括:存放存放目标代码目标代码的空间的空间存放存放数据项目数据项目的空间的空间存放程序运行的存放程序运行
13、的控制或连接数据控制或连接数据所需单元所需单元(控制控制栈栈)n一个程序在运行时刻的内存划分一个程序在运行时刻的内存划分:代码代码(Code)静态数据静态数据(Static Data)栈栈(Stack) 堆堆(Heap) 9.2.2 活动记录活动记录n活动记录：活动记录：为了为了管理过程在一次执行中所管理过程在一次执行中所需要的信息需要的信息所使用的所使用的一个连续的存储块一个连续的存储块。n假定假定语言的特点语言的特点为为:允许过程递归调用、允允许过程递归调用、允许过程含有可变数组，但过程定义不允许许过程含有可变数组，但过程定义不允许嵌套，如嵌套，如C语言语言。n采用栈式存储分配机制。采用栈
14、式存储分配机制。运行时，每当进运行时，每当进入一个过程就有一个相应的活动记录累筑入一个过程就有一个相应的活动记录累筑于于栈顶栈顶。此记录含有。此记录含有连接数据、形式单元、连接数据、形式单元、局部变量、局部数组的内情向量和临时工局部变量、局部数组的内情向量和临时工作单元作单元等。等。对任何对任何局部变量局部变量X的的引用可表示为引用可表示为变址访变址访问问: dxSP dx: 变量变量X相对于活相对于活动记录起点的地址，动记录起点的地址，在编译时可确定。在编译时可确定。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP 每
15、个过程的每个过程的活动记录内容活动记录内容(非嵌套语言非嵌套语言)q连接数据连接数据返回地址返回地址动态链动态链：指向调用该：指向调用该过程前的最新活动记过程前的最新活动记录地址的指针。录地址的指针。静态链：静态链：指向静态直指向静态直接外层最新活动记录接外层最新活动记录地址的指针，用来访地址的指针，用来访问非局部数据。问非局部数据。静态链静态链动态链动态链形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012返回地址返回地址TOP 每个过程的每个过程的活动记录内容活动记录内容(嵌套语言嵌套语言)q形式单元：形式单元：存放相存放相应的实在参数的地应的实在参数的地址或值。址
16、或值。q局部数据区局部数据区：局部：局部变量、内情向量、变量、内情向量、临时工作单元（如临时工作单元（如存放对表达式求值存放对表达式求值的结果）。的结果）。静态链静态链动态链动态链形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012返回地址返回地址TOP 每个过程的活动记录内容每个过程的活动记录内容n 静态分配策略静态分配策略(FORTRAN) 如果在编译时能确定数据空间的大小，则可采用静如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定出态分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。在运行时刻的存储空间中的位
17、置。n动态分配策略动态分配策略(PASCAL) 如果在编译时不能确定运行时数据空间的大小，如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程和动态则必须采用动态分配方法。允许递归过程和动态申请释放内存。申请释放内存。栈式动态分配：允许递归栈式动态分配：允许递归堆式动态分配：允许动态释放内存堆式动态分配：允许动态释放内存9.2.3 9.2.3 存储分配策略存储分配策略 PROGRAM MAIN integer X，YCOMMON /C/A，B ENDSUBROUTINE SUB1 real X，ZCOMMON /C/A1，B1 END9.3 静态存储管理静态存储管理(
18、FORTRAN)9.3 静态存储管理静态存储管理nFORTRAN程序的特点程序的特点：整个程序所需数据空间：整个程序所需数据空间的总量在编译时完全确定，每个数据名的地址可的总量在编译时完全确定，每个数据名的地址可以静态地进行分配。以静态地进行分配。n由于每个由于每个FORTRAN 程序段可以独立编译，运程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。行前由装入程序把各段连成可运行的整体。n按按数据区数据区组织存储组织存储:每个程序段定义一个每个程序段定义一个局部数据区局部数据区，用来存放程序，用来存放程序段中未出现在段中未出现在COMMON里的局部名的值。里的局部名的值。每个公用块
19、定义一个每个公用块定义一个公用数据区公用数据区，用来存放公用，用来存放公用块里各个名字的值。块里各个名字的值。n每个数据区有一个编号，地址分配时，在每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记其所属符号表中，对每个数据名登记其所属数据数据区编号区编号及在该区中的及在该区中的相对位置相对位置。n每个局部数据区的内容及存放次序每个局部数据区的内容及存放次序:寄存器保护区寄存器保护区返回地址返回地址形式单元形式单元临时变量临时变量数组数组简单变量简单变量01An考虑子程序段：考虑子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND地址地址名字名字N
20、AMENAME性质性质ATTRIBUTEATTRIBUTEDADAADDRADDRSWAPSWAP子程序，二目子程序，二目A A哑，实变量哑，实变量k ka aB B哑，实变量哑，实变量k ka+2a+2T T实变量实变量k ka+4a+4寄存器保护区寄存器保护区返回地址返回地址ATB01aa+2a+4第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现9.4 一个简单栈式存储分配一个简单栈式存储分配n
21、假定语言的特点为假定语言的特点为:允许过程递归调用、允允许过程递归调用、允许过程含有可变数组，但过程定义不允许许过程含有可变数组，但过程定义不允许嵌套，如嵌套，如C语言语言。n采用采用栈式存储分配栈式存储分配机制机制n活动记录：活动记录：运行时，每当进入一个过程就运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记有一个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。局部数组的内情向量和临时工作单元等。 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( )
22、 R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程R全局数据区全局数据区 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程R主程序主程序活动记录活动记录TOPSP全局数据区全局数据区 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的
23、活动记录的活动记录主程序主程序活动记录活动记录TOPSP全局数据区全局数据区 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录主程序主程序活动记录活动记录TOPR的活动记录的活动记录SP参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元全局数据区全局数据区 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的
24、数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录主程序主程序活动记录活动记录全局数据区全局数据区R的活动记录的活动记录TOPSPTOPSP 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录主程序主程序活动记录活动记录全局数据区全局数据区TOPSPTOPSP 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数
25、据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程R主程序主程序活动记录活动记录全局数据区全局数据区TOPSP 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程Rn每个过程的活动记录内容如图每个过程的活动记录内容如图:对任何局部变量对任何局部变量X的的引用可表示为变址访引用可表示为变址访问问: dxSP dx: 变量变量X相对于活相对于活动记录起点的地址，动记录起点的地址，在编译时可确定。在编译时
26、可确定。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP 9.4.1 C的活动记录的活动记录 n过程调用的语句过程调用的语句 P(T1,T2,Tn)n翻译成四元式序列翻译成四元式序列:par T1par T2 par Tncall P，n9.4.2 C的过程调用、过程进入、的过程调用、过程进入、数组空间分配和过程返回数组空间分配和过程返回 1) 每个每个par Ti(i=1,2,n)可直接翻译成如下指令可直接翻译成如下指令:(i+3)TOP:= Ti (传值传值)(i+3)TOP:=addr(Ti) (传地址传地址)2)
27、 call P，n 被翻译成被翻译成:1TOP:=SP (保护现行保护现行SP)3TOP:=n (传递参数个数传递参数个数)JSR P (转子指令转子指令)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元对于对于par和和call产生的目标代码如下产生的目标代码如下:TOP SP 调用过程的调用过程的活动记录活动记录形式单元形式单元老老SP参数个数参数个数3) 转进过程转进过程P后，首先应执行下述指令后，首先应执行下述指令:SP:=TOP+1 (定义新的定义新的SP)1SP:=返回地址返回地址 (保护返回地址保护返回地址)TOP:=TOP
28、+L (新新TOP) L：过程过程P的活动记录所需单元数，的活动记录所需单元数， 在编译时可确定。在编译时可确定。 参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元TOP 调用过程的活动记录调用过程的活动记录返回地址返回地址TOPSP4) 过程返回时，应执行下列指令过程返回时，应执行下列指令:TOP:=SP-1 (恢复调用前恢复调用前TOP)SP:=0SP (恢复调用前恢复调用前SP)X:=2TOP (把返回地址把返回地址取到取到X中中)UJ 0X (按按X返回返回)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量
29、局部变量老老SP临时单元临时单元调用过程的活动记录调用过程的活动记录TOPSPSPTOP4) 过程返回时，应执行下列指令过程返回时，应执行下列指令:TOP:=SP-1 (恢复调用前恢复调用前TOP)SP:=0SP (恢复调用前恢复调用前SP)X:=2TOP (把返回地址把返回地址取到取到X中中)UJ 0X (按按X返回返回)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元调用过程的活动记录调用过程的活动记录SPTOP小结小结n运行时存储器的划分运行时存储器的划分 活动记录（像活动记录（像c等允许递归的语言）等允许递归的语言） 局部数据区（
30、像局部数据区（像fortran等不含递归的语言）等不含递归的语言）n一个简单栈式存储分配一个简单栈式存储分配C的活动记录的活动记录C的过程调用、过程进入、数组空间分配和过的过程调用、过程进入、数组空间分配和过程返回程返回第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现9.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链
31、和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回9.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现n假定语言假定语言不仅允许过程的递归调用不仅允许过程的递归调用(和可变和可变数组数组)，而且，而且允许过程定义的嵌套允许过程定义的嵌套，如，如PASCAL，PL语言。语言。nPASCALPASCAL程序
32、本身可以看成是一个操作系程序本身可以看成是一个操作系统所调用的过程，统所调用的过程，过程可以嵌套和递归。过程可以嵌套和递归。一个一个PASCAL过程：过程：过程头；过程头；说明段（由一系列的说明语句组成）；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；执行体（由一系列的执行语句组成）；end9.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现作用域作用域：一个名字能被使用的区域范围：一个名字能被使用的区域范围称作这个名字的作用域。称作这个名字的作用域。允许同一个标识符在不同的过程中代表允许同一个标识符在不同的过程中代表不同的名字。不同的名字。名字作用域规则名字作
33、用域规则- 最近嵌套原则最近嵌套原则 n一个在子程序一个在子程序B1中说明的名字中说明的名字X只在只在B1中中有效（局部于有效（局部于B1）；）；n如果如果B2是是B1的一个内层子程序且的一个内层子程序且B2中对中对标识符标识符X没有新的说明，则原来的名字没有新的说明，则原来的名字X在在B2中仍然有效。中仍然有效。n如果如果B2对对X重新作了说明，那么，重新作了说明，那么，B2对对X的任何引用都是指重新说明过的这个的任何引用都是指重新说明过的这个X。program main var A, B : real; procedure P1 var B:boolean; begin end proce
34、dure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integr)嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回9.5.1 非局部名字的访问的实现非局部名字的访问的实现 n主程序的层次为主程序的层次为0；在；在i层中定义的过程，其层中定义的过程，其层次为层次为i+1;(层数，层数， 偏移量偏移量)n过程运行时，必须知道过程运行时，必
35、须知道其其所有外层过程的所有外层过程的当前活动记录的起始地址。当前活动记录的起始地址。 程序程序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-d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=
36、0;S;.end. P主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 RS的活动记录的活动记录主程序主程序P活动记录活动记录全局数据区全局数据区Q的活动记录的活动记录R的活动记录的活动记录R的活动记录的活动记录嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回一、静态链和活动记录一、静态链和活动记录 n静态链静态链：指向本过程：指向本过程的的直接外层直接外层过程的活过程的活动记录的起始地址，
37、动记录的起始地址，也称存取链。也称存取链。n动态链动态链：指向本过程：指向本过程的的调用过程调用过程的活动记的活动记录的起始地址，也称录的起始地址，也称控制链。控制链。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP012动态链动态链(老老SP)TOP 静态链静态链 程序程序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
38、=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 过程过程 R00返回地址返回地址102a3x4SP TOPq主程序主程序P参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP012动态链动态链(老老SP)TOP 静态链静态链00返回地址返回地址102a3x405返回地址返回地址6070(
39、形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P过程过程 S参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP012动态链动态链(老老SP)TOP 静态链静态链00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P过程过程 S？第第N层过程调用层过程调用第第 N+1层过程，如何层过程，如何确定被调用过程确定被调用过程(第第 N+1层层)过程的静态链？过程的静态链？A:调用过程调用过程(第第N层层过程过程)的最新活动记录的
40、最新活动记录的起始地址的起始地址.00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i16？第第N层过程调用层过程调用第第 N层过程，如何确层过程，如何确定被调用过程定被调用过程(第第 N层层)过程的静态链？过程的静态链？A:调用过程调用过程(第第N层层过程过程)的静态链的值。的静态链的值。00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静
41、态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v(形参形参)22c23d24SP TOP00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 R511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数
42、)20u(形参形参)21v(形参形参)22c23d241725返回地址返回地址2611272(形参个数形参个数)28u(形参形参)29v(形参形参)30c31d32TOPSP 00返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 Q511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v(形参形参)22c23d24TOPSP 1725返回地址返回地址260
43、271(形参个数形参个数)28b(形参形参)29i30？第第N层过程调用层过程调用第第 N-x层过程，如何层过程，如何确定被调用过程确定被调用过程(第第 N-x层层)过程的静态链？过程的静态链？A:沿着调用过程沿着调用过程(第第N层过程层过程)的静态链向的静态链向前走前走x步到达的活动步到达的活动记录的静态链的值。记录的静态链的值。嵌套过程语言的栈式实现嵌套过程语言的栈式实现第第N层过程调用第层过程调用第 N+1层：层：P2的静态链为调用过程的静态链为调用过程P1（第（第N层过程）的最新活动记录的起层过程）的最新活动记录的起始地址始地址第第N层过程调用第层过程调用第 N层：层：P2的的静态链为
44、调用过程静态链为调用过程P1（第（第N层层过程）的静态链的值过程）的静态链的值第第N层过程调用第层过程调用第 N-x层：层：P2的静态链为沿着调用过程的静态链为沿着调用过程P1的的静态链向前走静态链向前走x步到达的活动步到达的活动记录的静态链的值。记录的静态链的值。P0P2P1P0P1P2P0P1P2嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回二、嵌套层次显示表二、嵌套层次显示表displayn当进入一个
45、过程后，在建立其活动记录当进入一个过程后，在建立其活动记录区的同时建立一张嵌套层次显示表区的同时建立一张嵌套层次显示表diaplay，把把diaplay表作为活动记录的表作为活动记录的一部分。一部分。n令过程令过程R的外层为的外层为Q，Q的外层为主程序的外层为主程序为为P，则则过程过程R运行时的运行时的DISPLAY表内容表内容为：为：2R 的现行活动记录的现行活动记录的的地址地址(SP 的现值的现值)1Q 的最新活动记录的最新活动记录的地址的地址0P 的活动记录的活动记录的地址的地址PRQn问题：问题：当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建
46、立起自己的display表？表？P0P1P2P0P2P1P0P1P2n问题：问题：当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P1P2l2: P1的最新活动记的最新活动记录的起始地址录的起始地址P0的最新活动记的最新活动记录的起始地址录的起始地址P1的的display表表P0的最新活动记录的最新活动记录的起始地址的起始地址l2: P2的最新活动记的最新活动记录的起始地址录的起始地址P2的的display表表从从P1的的display表中自底而上地取过表中自底而上地取过l2个个单元（单元（l2为为P2的层数）再添上
47、进入的层数）再添上进入P2后后新建立的新建立的SP值就构成了值就构成了P2的的display表。表。 0l2-1 l2n问题：问题：当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P2P1l2-1: P1的最新活动的最新活动记录的起始地址记录的起始地址P0的最新活动记录的最新活动记录的起始地址的起始地址P1的的display表表P0的最新活动记录的最新活动记录的起始地址的起始地址P1的最新活动记录的最新活动记录的起始地址的起始地址P2的的display表表从从P1的的display表中自底而上地取过表中自底而上地取过
48、l2个个单元（单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后后新建立的新建立的SP值就构成了值就构成了P2的的display表。表。l2: P2的最新活动记的最新活动记录的起始地址录的起始地址l2-2l2-1n问题：问题：当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P1P2P1的最新活动记录的最新活动记录的起始地址的起始地址P0的最新活动记录的最新活动记录的起始地址的起始地址P1的的display表表P0的最新活动记录的最新活动记录的起始地址的起始地址P2的的display表表从从P1的的displ
49、ay表中自底而上地取过表中自底而上地取过l2个个单元（单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后后新建立的新建立的SP值就构成了值就构成了P2的的display表。表。l2: P2的最新活动的最新活动记录的起始地址记录的起始地址l2: P2的最新活动的最新活动记录的起始地址记录的起始地址n问题：问题：当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？答案：答案：从从P1的的display表中自底而上地取过表中自底而上地取过l2个个单元（单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后新建后新建
50、立的立的SP值就构成了值就构成了P2的的display表。表。F把把P1的的display表表（全局全局display表表）地址地址作为作为连接数据之一传送给连接数据之一传送给P2就能够建立就能够建立P2的的display表。表。P0P1P2P0P2P1P0P1P2n全局全局display：调用过程：调用过程的的display表地址表地址ndiaplay表在活动记录表在活动记录中中的相对地址的相对地址d在编译时能在编译时能完全确定。完全确定。n假定在现行过程中引用了假定在现行过程中引用了某层过程某层过程(令其层次为令其层次为k)的的X变量，那么，可用下面变量，那么，可用下面两条指令获得两条指令
