第九章 运行时存储空间组织 http://sei.nudt.edu.cn/cp 网上教学系统: 070606302: 编译原理 第九章 运行时存储空间组织 http://sei.nudt.edu.cn/cp 网上教学系统: 070606302: 编译原理

第九章 运行时存储空间组织 9.1 目标程序运行时的活动 以Pascal为例，假定程序由若干个过程组成 过程（procedure）定义 第九章 运行时存储空间组织 9.1 目标程序运行时的活动 以Pascal为例，假定程序由若干个过程组成 过程（procedure）定义 一个过程的活动指的是该过程的一次执行 过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间 过程可以是递归的 国防科技大学计算机系602教研室

（1） program sort(input, output) （2） var a: array[0..10] of integer; （3） procedure readarray; （4） var i: integer; （5） begin （6） for i:=1 to 9 do read(a[i]) （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 国防科技大学计算机系602教研室

（12） procedure quicksort(m, n:integer); （13） var i:integer; （14） begin （15） if (n>m) then begin （16） i:=partition(m, n ); （17） quicksort(m, i-1 ); （18） quicksort(i+1, n ) （19） end; （20） end; （21） begin （22） a[0]:=-9999; a[10]:=9999; （23） readarray; （24） quicksort(1, 9 ) （25） end. program sort procedure readarray function partition(y procedure quicksort 国防科技大学计算机系602教研室

参数传递 过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言的主要途径。 过程定义： 过程调用 procedure add(x,y:integer; var z:integer) begin z：=x+y; end; 过程调用 add(a,b,c); 国防科技大学计算机系602教研室

参数传递方式 一. 传地址 把实在参数的地址传递给相应的形式参数 方法： PASCAL的变量参数方式 调用段预先把实在参数的地址传递到被调用段可以拿到的地方； 程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中； 过程体对形式参数的引用域赋值被处理成对形式单元的间接访问。 PASCAL的变量参数方式 国防科技大学计算机系602教研室

swap(a,b) 把a,b的地址送到已知单元j1和j2中 m:=j1; n:=j2; i:=m↑; m↑:= n↑; n↑:=i; procedure swap (var 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; 国防科技大学计算机系602教研室

参数传递方式 二．得结果 传地址的一种变形 方法： 有些Fortran采用这种方式； 每个形参对应两个形式单元，第一个形式单元存放实参地址，第二个单元存放实参的值。 在过程体中对形式参数的任何引用或赋值都看作对它的第二个单元的直接访问。 过程完成返回前把第二个单元的内容存放到第一个单元所指的实参单元中。 有些Fortran采用这种方式； 国防科技大学计算机系602教研室

参数传递方式 三．传值 把实在参数的值传递给相应的形式参数 方法： PASCAL的值参数 调用段预先把实在参数的的值计算出来并放在被调用段可以拿到的地方； 被调用段开始工作时，首先把实参的值抄入形式参数相应的单元； 被调用段中，象引用局部数据一样引用形式单元。 PASCAL的值参数 国防科技大学计算机系602教研室

参数传递方式 四．传名 过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实参。 方法： 在进入被调用段的之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行计值（或计算地址）。因此，通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形式参数时就调用这个子程序。 国防科技大学计算机系602教研室

BEGIN A :=2; TA:=0; write(A); END PROGRAM EX … var A:integer; PROCEDURE P(B: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 国防科技大学计算机系602教研室

例： … procedure P(w,x,y,z); begin y := y*w; z := z+x; end a := 5; P(a+b,a-b,a,a); write(a); 传值: 传地址: 得结果: 传名: 5 42 7 77 国防科技大学计算机系602教研室

编译程序为了组织存储空间，必须考虑下面几个问题： 过程是否允许递归？ 当控制从一个过程的活动返回时，对局部名称的值如何处理？ 过程是否允许引用非局部名称？ 过程调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返回？ 存储空间可否在程序控制下进行动态分配？ 存储空间是否必须显式地释放？ 国防科技大学计算机系602教研室

9.2 运行时存储器的划分 一个目标程序运行所需的存储空间包括: 存放目标代码的空间 存放数据项目的空间 9.2 运行时存储器的划分 一个目标程序运行所需的存储空间包括: 存放目标代码的空间 存放数据项目的空间 存放程序运行的控制或连接数据所需单元(控制栈) 国防科技大学计算机系602教研室

一个程序在运行时刻的内存划分: 代码(Code) 静态数据 (Static Data) 栈(Stack)   堆(Heap) 国防科技大学计算机系602教研室

9.2.2 活动记录 假定语言的特点为:允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如C语言。 采用栈式存储分配机制 活动记录：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。 国防科技大学计算机系602教研室

每个过程的活动记录内容(非嵌套语言) 对任何局部变量X的引用可表示为变址访问: dx[SP] TOP 临时单元 对任何局部变量X的引用可表示为变址访问: dx[SP] dx: 变量X相对于活动记录起点的地址，在编译时可确定。 内情向量 局部变量 形式单元 参数个数 2 1 返回地址 SP 0 老SP 国防科技大学计算机系602教研室

每个过程的活动记录内容(嵌套语言) 连接数据 TOP 临时单元 返回地址 动态链：指向调用该过程前的最新活动记录地址的指针。 内情向量 静态链：指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。 TOP 临时单元 内情向量 局部变量 形式单元 静态链 2 1 动态链 SP 0 返回地址 国防科技大学计算机系602教研室

每个过程的活动记录内容 形式单元：存放相应的实在参数的地址或值。 局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。 TOP 临时单元 形式单元：存放相应的实在参数的地址或值。 局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。 内情向量 局部变量 形式单元 静态链 2 1 动态链 SP 0 返回地址 国防科技大学计算机系602教研室

9.2.3 存储分配策略 静态分配策略(FORTRAN) 9.2.3 存储分配策略 静态分配策略(FORTRAN) 如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。 动态分配策略(PASCAL) 如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程和动态申请释放内存。 栈式动态分配 堆式动态分配 国防科技大学计算机系602教研室

9.3 静态存储管理 PROGRAM MAIN … integer X，Y COMMON /C/A，B END 9.3 静态存储管理 PROGRAM MAIN … integer X，Y COMMON /C/A，B END SUBROUTINE SUB1 real X，Z COMMON /C/A1，B1 国防科技大学计算机系602教研室

9.3 静态存储管理 FORTRAN程序的特点：整个程序所需数据空间的总量在编译时完全确定，每个数据名的地址可以静态地进行分配。 9.3 静态存储管理 FORTRAN程序的特点：整个程序所需数据空间的总量在编译时完全确定，每个数据名的地址可以静态地进行分配。 由于每个FORTRAN 程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据区组织存储: 每个程序段定义一个局部数据区，用来存放程序 段中未出现在COMMON里的局部名的值。 每个公用块定义一个公用数据区，用来存放公用 块里各个名字的值。 国防科技大学计算机系602教研室

每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记其所属数据区编号及在该区中的相对位置。 每个局部数据区的内容及存放次序: 临时变量 数组 简单变量 形式单元 A 寄存器保护区 1 返回地址 国防科技大学计算机系602教研室

考虑子程序段： SUBROUTINE SWAP(A,B) T=A A=B B=T RETURN END T B A a 寄存器保护区 1 返回地址 国防科技大学计算机系602教研室

9.4 一个简单栈式存储分配 假定语言的特点为:允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如C语言。 9.4 一个简单栈式存储分配 假定语言的特点为:允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如C语言。 采用栈式存储分配机制 活动记录：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。 国防科技大学计算机系602教研室

主程序→过程Q →过程R 全局数据说明 Main( ) { Main中的数据说明 } void R( ) R中的数据说明 TOP 临时单元 … void Q( ) Q中的数据说明 主程序→过程Q →过程R TOP 参数个数 返回地址 形式单元 内情向量 局部变量 老SP 临时单元 R的活动记录 SP Q的活动记录 主程序活动记录 全局数据区 国防科技大学计算机系602教研室

9.4.1 C的活动记录 每个过程的活动记录内容如图: 对任何局部变量X的引用可表示为变址访问: dx[SP] TOP 临时单元 对任何局部变量X的引用可表示为变址访问: dx[SP] dx: 变量X相对于活动记录起点的地址，在编译时可确定。 内情向量 局部变量 形式单元 参数个数 2 1 返回地址 SP 0 老SP 国防科技大学计算机系602教研室

9.4.2 C的过程调用、过程进入、数组空间分配和过程返回 过程调用的四元式序列: par T1 par T2 … par Tn call P，n 国防科技大学计算机系602教研室

对于par和call产生的目标代码如下: 1) 每个par Ti(i=1,2,…n)可直接翻译成如下指令: (i+3)[TOP]:= Ti (传值) (i+3)[TOP]:=addr(Ti) (传地址) 2) call P，n 被翻译成: 1[TOP]:=SP (保护现行SP) 3[TOP]:=n (传递参数个数) JSR P (转子指令) 参数个数 返回地址 形式单元 内情向量 局部变量 老SP 临时单元 形式单元 参数个数 老SP TOP SP  调用过程的 活动记录 国防科技大学计算机系602教研室

3) 转进过程P后，首先应执行下述指令: SP:=TOP+1 (定义新的SP) 1[SP]:=返回地址 (保护返回地址) TOP:=TOP+L (新TOP) L：过程P的活动记录所需单元数， 在编译时可确定。 TOP 参数个数 返回地址 形式单元 内情向量 局部变量 老SP 临时单元 返回地址 SP 国防科技大学计算机系602教研室 TOP 调用过程的活动记录

4) 过程返回时，应执行下列指令: TOP:=SP-1 (恢复调用前TOP) SP:=0[SP] (恢复调用前SP) X:=2[TOP] (把返回地址取到X中) UJ 0[X] (按X返回) TOP 参数个数 返回地址 形式单元 内情向量 局部变量 老SP 临时单元 SP TOP 国防科技大学计算机系602教研室 调用过程的活动记录 SP

9.5 嵌套过程语言的栈式实现 PASCAL 非局部名字的访问的实现 过程调用、过程进入、过程返回 静态链和活动记录 嵌套层次显示表display 过程调用、过程进入、过程返回 国防科技大学计算机系602教研室

嵌套过程语言的栈式实现 PASCAL 非局部名字的访问的实现 过程调用、过程进入、过程返回 静态链和活动记录 嵌套层次显示表display 国防科技大学计算机系602教研室

9.5 嵌套过程语言的栈式实现 假定语言不仅允许过程的递归调用(和可变数组)，而且允许过程定义的嵌套，如PASCAL，PL语言。 9.5 嵌套过程语言的栈式实现 假定语言不仅允许过程的递归调用(和可变数组)，而且允许过程定义的嵌套，如PASCAL，PL语言。 国防科技大学计算机系602教研室

9.5 嵌套过程语言的栈式实现 PASCAL PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 9.5 嵌套过程语言的栈式实现 PASCAL PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 一个PASCAL过程： 过程头； 说明段（由一系列的说明语句组成）； begin 执行体（由一系列的执行语句组成）； end 国防科技大学计算机系602教研室

作用域：一个名字能被使用的区域范围称作这个名字的作用域。 允许同一个标识符在不同的过程中代表不同的名字。 名字作用域规则--"最近嵌套原则" 一个在子程序B1中说明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一个内层子程序且B2中对 标识符X没有新的说明，则原来的名字X在 B2中仍然有效。如果B2对X重新作了说明， 那么，B2对X的任何引用都是指重新说明 过的这个X。 国防科技大学计算机系602教研室

A(real) B(real) B(bool) A(integr) program main var A, B : real; … procedure P1 var B:boolean; begin end procedure P2 var A:integer; 国防科技大学计算机系602教研室

嵌套过程语言的栈式实现 PASCAL 非局部名字的访问的实现 过程调用、过程进入、过程返回 静态链和活动记录 嵌套层次显示表display 国防科技大学计算机系602教研室

9.5.1 非局部名字的访问的实现 主程序的层次为0；在i层中定义的过程，其层次为i+1; (层数， 偏移量) 9.5.1 非局部名字的访问的实现 主程序的层次为0；在i层中定义的过程，其层次为i+1; (层数， 偏移量) 过程运行时，必须知道其所有外层过程的当前活动记录的起始地址。 国防科技大学计算机系602教研室

嵌套过程语言的栈式实现 PASCAL 非局部名字的访问的实现 过程调用、过程进入、过程返回 静态链和活动记录 嵌套层次显示表display 国防科技大学计算机系602教研室

图9.15 程序 主程序P 过程 S 过程 Q 过程 R 过程 R 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 {R} R(1,x); end {Q} 图9.15 程序 主程序P 过程 S 过程 Q 过程 R 过程 R procedure S; var c, i:integer; begin a:=1; Q(c); ...... end {S} a:=0; S; end. {P} 国防科技大学计算机系602教研室

静态链：指向本过程 的直接外层过程的活 动记录的起始地址， 也称存取链。 一、静态链和活动记录 静态链：指向本过程 的直接外层过程的活 动记录的起始地址， 也称存取链。 动态链：指向本过程 的调用过程的活动记 录的起始地址，也称 控制链。 TOP 临时单元 内情向量 局部变量 形式单元 参数个数 静态链 2 1 返回地址 SP0 动态链(老SP) 国防科技大学计算机系602教研室

主程序P TOP x 4 a 3 2 返回地址 1 SP  国防科技大学计算机系602教研室

？第N层过程调用第 N+1层过程，如何确定被调用过程(第 N+1层)过程的静态链？ 主程序P过程 S ？第N层过程调用第 N+1层过程，如何确定被调用过程(第 N+1层)过程的静态链？ TOP i 10 c 9 0(形参个数) 8 7 返回地址 6 SP  5 N -> N+1 SL(N+1) = SP(N) x 4 A:调用过程(第N层过程)的最新活动记录的起始地址. a 3 2 返回地址 1 动态链 静态链 国防科技大学计算机系602教研室

？第N层过程调用第 N层过程，如何确定被调用过程(第 N层)过程的静态链？ 主程序P 过程 S 过程 Q TOP i 16 b(形参) 15 ？第N层过程调用第 N层过程，如何确定被调用过程(第 N层)过程的静态链？ 1(形参个数) 14 13 返回地址 12 SP  5 11 i 10 c 9 0(形参个数) 8 7 N -> N SL(N+1) = SL(N) 返回地址 6 A:调用过程(第N层过程)的静态链的值。 5 x 4 a 3 2 返回地址 1 国防科技大学计算机系602教研室 动态链 静态链

主程序P 过程 S 过程 Q 过程 R TOP SP  动态链 静态链 i 16 b(形参) 15 1(形参个数) 14 13 13 返回地址 12 5 11 i 10 c 9 0(形参个数) 8 7 TOP d 24 返回地址 6 c 23 5 v(形参) 22 x 4 u(形参) 21 a 3 2(形参个数) 20 2 11 19 返回地址 1 返回地址 18 SP  11 17 国防科技大学计算机系602教研室 动态链 静态链

主程序P 过程 S 过程 Q 过程 R 过程 R i 16 b(形参) 15 TOP d 32 1(形参个数) 14 c 31 13 v(形参) 30 返回地址 12 u(形参) 29 5 11 2(形参个数) 28 i 10 11 27 c 9 返回地址 26 0(形参个数) 8 SP  17 25 7 d 24 N+1 -> N 返回地址 6 c 23 5 v(形参) 22 x 4 u(形参) 21 a 3 2(形参个数) 20 2 11 19 返回地址 1 返回地址 18 11 17 国防科技大学计算机系602教研室 动态链 静态链

主程序P 过程 S 过程 Q 过程 R 过程 Q A:沿着调用过程(第N层过程)的静态链的向前走x步到达的活动记录的静态链的值。 ？第N层过程调用第 N-x层过程，如何确定被调用过程(第 N-x层)过程的静态链？ i 16 b(形参) 15 1(形参个数) 14 13 TOP i 30 返回地址 12 b(形参) 29 5 11 1(形参个数) 28 i 10 27 c 9 返回地址 26 0(形参个数) 8 SP  17 25 7 d 24 N+1 -> N 返回地址 6 c 23 5 v(形参) 22 x 4 u(形参) 21 a 3 2(形参个数) 20 2 11 19 返回地址 1 返回地址 18 11 17 国防科技大学计算机系602教研室 动态链 静态链

嵌套过程语言的栈式实现 PASCAL 非局部名字的访问的实现 过程调用、过程进入、过程返回 静态链和活动记录 嵌套层次显示表display 国防科技大学计算机系602教研室

当进入一个过程后，在建立其活动记录 区的同时建立一张嵌套层次显示表 diaplay，把diaplay表作为活动记录的 一部分。 二、嵌套层次显示表display 当进入一个过程后，在建立其活动记录 区的同时建立一张嵌套层次显示表 diaplay，把diaplay表作为活动记录的 一部分。 N+1 -> N SL(N+1) = SL(N) 国防科技大学计算机系602教研室

令过程R的外层为Q，Q的外层为主程序为P，则过程R运行时的DISPLAY表内容为： 国防科技大学计算机系602教研室

问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？ 国防科技大学计算机系602教研室

问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？ 从P1的display表中自底而上地取过l2个单元（l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。 l2: P1的最新活动记 录的起始地址 l2: P2的最新活动记 录的起始地址 P0的最新活动记 录的起始地址 P0的最新活动记录 的起始地址 …… …… P1的display表 P2的display表 国防科技大学计算机系602教研室

问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？ 从P1的display表中自底而上地取过l2个单元（l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。 l2: P2的最新活动记 录的起始地址 l2-1: P1的最新活动 记录的起始地址 P1的最新活动记录 的起始地址 P0的最新活动记录 的起始地址 P0的最新活动记录 的起始地址 …… …… P1的display表 P2的display表 国防科技大学计算机系602教研室

问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？ 从P1的display表中自底而上地取过l2个单元（l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。 P1的最新活动记录 的起始地址 l2: P2的最新活动 记录的起始地址 l2: P2的最新活动 记录的起始地址 P0的最新活动记录 的起始地址 P0的最新活动记录 的起始地址 …… …… P1的display表 P2的display表 国防科技大学计算机系602教研室

问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？ 答案：从P1的display表中自底而上地取过l2个单元（l2为P2的层数）再添上进入P2后新建立的SP值就构成了P2的display表。 把P1的display表地址作为连接数据之一传送给P2就能够建立P2的display表。 国防科技大学计算机系602教研室

diaplay表在活动记录中的相对地址d在编译时能完全确定。 嵌套过程语言活动记录 diaplay表在活动记录中的相对地址d在编译时能完全确定。 假定在现行过程中引用了某层过程(令其层次为k)的X变量，那么，可用下面两条指令获得X的地址: LD R1 (d+k)[SP] LD R2 dx[R1] TOP 临时单元 内情向量 局部变量 d Display 表 … 形式单元 3 参数个数 2 全局Diaplay 1 返回地址 SP 0 老SP 国防科技大学计算机系602教研室

图9.15 程序 主程序P 过程 S 过程 Q 过程 R 过程 R 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 {R} R(1,x); end {Q} 图9.15 程序 主程序P 过程 S 过程 Q 过程 R 过程 R procedure S; var c, i:integer; begin a:=1; Q(c); ...... end {S} a:=0; S; end. {P} 国防科技大学计算机系602教研室

主程序过程 S TOP SP  动态链 i 12 c 11 5 10 9 0(形参个数) 8 2(全局display) 7 返回地址 9 0(形参个数) 8 2(全局display) 7 返回地址 6 SP  5 x 4 a 3 0(display) 2 返回地址 1 动态链 国防科技大学计算机系602教研室

主程序P过程 S 过程 Q TOP SP  动态链 i 20 13 19 18 b(形参) 17 1(形参个数) 16 18 b(形参) 17 1(形参个数) 16 9(全局display) 15 返回地址 14 SP  5 13 i 12 c 11 5 10 9 0(形参个数) 8 2(全局display) 7 返回地址 6 5 x 4 a 3 0(display) 2 返回地址 1 国防科技大学计算机系602教研室 动态链

主程序P过程 S 过程 Q 过程 R TOP SP  动态链 i 20 13 19 18 b(形参) 17 1(形参个数) 16 18 b(形参) 17 1(形参个数) 16 9(全局display) 15 返回地址 14 5 13 i 12 c 11 TOP d 31 5 10 c 30 9 21 29 0(形参个数) 8 13 28 2(全局display) 7 27 返回地址 6 v(形参) 26 5 u(形参) 25 x 4 2(形参个数) 24 a 3 18(全局display) 23 0(display) 2 返回地址 22 SP  返回地址 1 13 21 国防科技大学计算机系602教研室 动态链

主程序P 过程 S 过程 Q 过程 R 过程 R TOP d 42 i 20 c 41 13 19 32 40 18 13 39 b(形参) 17 38 1(形参个数) 16 v(形参) 37 9(全局display) 15 u(形参) 36 返回地址 14 2(形参个数) 35 5 13 27(全局display) 34 i 12 返回地址 33 SP  c 11 21 32 5 10 d 31 9 c 30 0(形参个数) 8 21 29 2(全局display) 7 13 28 返回地址 6 27 5 v(形参) 26 x 4 u(形参) 25 a 3 2(形参个数) 24 0(display) 2 18(全局display) 23 返回地址 1 返回地址 22 国防科技大学计算机系602教研室 动态链 13 21

嵌套过程语言的栈式实现 PASCAL 非局部名字的访问的实现 过程调用、过程进入、过程返回 静态链和活动记录 嵌套层次显示表display 国防科技大学计算机系602教研室

过程调用、过程进入、过程返回 1. 每个par Ti(i=1,2,…n)可直接翻译成如下指令: 参数个数 返回地址 形式单元 临时单元 内情向量 局部变量 老SP Display 表 全局Diaplay 过程调用、过程进入、过程返回 1. 每个par Ti(i=1,2,…n)可直接翻译成如下指令: (i+4)[TOP]:= Ti (传值) (i+4)[TOP]:=addr(Ti ) (传地址) 形式单元 TOP 调用过程的 活动记录 SP  …… 国防科技大学计算机系602教研室

过程调用、过程进入、过程返回 2. call P，n 被翻译成: 1[TOP]:=SP (保护现行SP) 参数个数 返回地址 形式单元 临时单元 内情向量 局部变量 老SP Display 表 全局Diaplay 过程调用、过程进入、过程返回 2. call P，n 被翻译成: 1[TOP]:=SP (保护现行SP) 3[TOP]:=SP+d (传送现行display地址) 4[TOP]:=n (传递参数个数) JSR (转子指令) 参数个数 全局Diaplay 老SP TOP 调用过程的 活动记录 SP  …… 国防科技大学计算机系602教研室

3. 转进过程P后，首先定义新的SP和TOP，保存返回地址。 参数个数 返回地址 形式单元 临时单元 内情向量 局部变量 老SP Display 表 全局Diaplay 3. 转进过程P后，首先定义新的SP和TOP，保存返回地址。 4. 根据"全局display"建立现行过程的display：从全局display表中自底向上地取l个单元，在添上进入P后新建立的SP值就构成了P的display。 Display 表 返回地址 SP  调用过程的 活动记录 …… 国防科技大学计算机系602教研室

5. 过程返回时，执行下述指令: TOP:=SP-1 SP:=0[SP] X:=2[TOP] UJ 0[X] 临时单元 内情向量 局部变量 参数个数 返回地址 形式单元 临时单元 内情向量 局部变量 老SP Display 表 全局Diaplay 5. 过程返回时，执行下述指令: TOP:=SP-1 SP:=0[SP] X:=2[TOP] UJ 0[X] SP  TOP 调用过程的 活动记录 SP  …… 国防科技大学计算机系602教研室

嵌套过程语言的栈式实现 PASCAL 非局部名字的访问的实现 过程调用、过程进入、过程返回 静态链和活动记录 嵌套层次显示表display 国防科技大学计算机系602教研室

三、上面两种方法的"折中"——PL编译程序 建立一个总的运行时的diaplay表(而不是每个过程的活动记录中都有一个)，它记录正被调用执行的过程及其所有外层过程的活动记录的起始地址。通过这个diaplay访问数据。 在各过程活动记录之间保留一条"静态链 SL"，它主要用于由层次大的过程调用层 次小的过程后返回时，恢复调用前的 display内容。(这时，调用返回后，执行 一条UDIS指令) 国防科技大学计算机系602教研室

PL中每个过程的活动 记录结构: 1) 简单局部变量 2) 连接数据 返回地址RA 动态链DL，指向过程调用者的活动记录起始地址 静态链SL, 指向过程的直接外层过程活动记录起始地址 TOP 局部变量 数组 3 形式单元 2 动态链指针DL 1 静态链指针SL SP 0 返回地址RA 国防科技大学计算机系602教研室

procedure P11(a,b:integer); begin end; call P11(i,j); var s,t:integer; program P; var x,y: integer; ... procedure P1; var i,j:integer; procedure P11(a,b:integer); begin end; call P11(i,j); procedure P2; var s,t:integer; ... procedure P21; begin end; call P1 call P2; end. 国防科技大学计算机系602教研室

主程序P 过程 P2 过程 P1 过程 P11 Display P11的活动记录 P1的活动记录 P2的活动记录 P的活动记录 b 19 P11的活动记录 a 18 DL(10) 17 SL(10) 16 RA 15 j 14 P1的活动记录 i 13 DL(5) 12 SL(0) 11 RA 10 15 3 t 9 P2的活动记录 10 2 5 2 s 8 DL(0) 7 1 SL(0) 6 RA 5 Display y 4 P的活动记录 x 3 2 1 国防科技大学计算机系602教研室

主程序P 过程 P2 过程 P1 过程 P11 Display P11的活动记录 P1的活动记录 P2的活动记录 P的活动记录 b 19 P11的活动记录 主程序P 过程 P2 过程 P1 过程 P11 a 18 DL(10) 17 SL(10) 16 RA 15 j 14 P1的活动记录 i 13 DL(5) 12 SL(0) 11 15 3 RA 10 t 9 P2的活动记录 5 2 10 2 s 8 DL(0) 7 1 SL(0) 6 RA 5 Display y 4 P的活动记录 x 3 2 1 国防科技大学计算机系602教研室

procedure P11(a,b:integer); begin end; call P11(i,j); procedure P2; program P; var x,y: integer; ... procedure P1; var i,j:integer; procedure P11(a,b:integer); begin end; call P11(i,j); procedure P2; var s,t:integer; procedure P21; var u,v:integer; ... begin call P1 end; call P21 call P2; end. 国防科技大学计算机系602教研室

主程序P 过程 P2 过程 P21 过程 P1 Display P1的活动记录 P21的活动记录 P2的活动记录 P的活动记录 j 19 P1的活动记录 i 18 DL(10) 17 SL(0) 16 RA 15 v 14 P21的活动记录 u 13 DL(5) 12 SL(5) 11 RA 10 10 3 t 9 P2的活动记录 5 2 15 2 s 8 DL(0) 7 1 SL(0) 6 RA 5 Display y 4 P的活动记录 x 3 2 1 国防科技大学计算机系602教研室

主程序P 过程 P2 过程 P21 过程 P1 Display udis:begin h1:=a;h2:=l;h3:=base; repeat display[h1]:=h3;h1:=h1-1; h3:=s[h3+2] until h1=h2 end; 由层次大的过程调用层次小的过程后返回时，要根据“静态链SL”恢复调用前的display内容(通过执行UDIS指令实现) j 19 P1的活动记录 主程序P 过程 P2 过程 P21 过程 P1 i 18 DL(10) 17 SL(0) 16 h3:=s[h3+1] RA 15 v 14 P21的活动记录 u 13 DL(5) 12 SL(0) 11 10 3 RA 10 t 9 P2的活动记录 5 2 15 2 s 8 DL(0) 7 1 SL(0) 6 RA 5 Display y 4 P的活动记录 x 3 2 1 国防科技大学计算机系602教研室

作业 P270–9 国防科技大学计算机系602教研室