8-第八章存储空间组织-5节(节选).ppt
§8.5 嵌套过程语言的栈式存储分配 （PASCAL语言）,§8.5.1 语言特性： .过程允许递归调用； .可变数组； .过程嵌套定义； (内层过程可引用外层过程定义的名字),层数：过程定义的嵌套层次； 约定：主程序的层数=0；,P中定义: Q,R， 若P的层数=n, 则：Q的层数=n+1；R的层数=n+1； 称：P 是 Q，R 的直接外层过程， Q,R 是P的内层过程 Q,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)+i; L处 end; R begin R(1,x); ; end; Q procedure S; var c,i:integer; begin a:=1; Q(c); end; S begin a:=0; S; end; P,主程序,0层,1层,2层,1层,名字的作用域,a, x,b, i,u,v, c,d,c,i,值参 变参,L处： PS QR1R2,返回,pascal子程序的调用规定： 任何子程序都不能调用主程序。 任何子程序（包括主程序）可调用自己的直接内 层子程序，但不能调用隔层的内层子程序。(图1) 子程序可以调用自己，以及它的任何一层外层子 程序（不包括主程序）。（图2）,pascal子程序的调用规定： 并列子程序中后说明的可以调用先说明的，而先 说明的不能调用后说明的（除非采用向前引用）。 一个子程序可以调用所有与自己的某个外层子程 序并列的子程序（其说明先于这个外层子程序）。,§8.5.2 非局部名字的访问的实现,1.实现方案：静态链 活动记录中，加“静态链”，指向静态直接外层过程的最新活动记录的地址(有多次调用时,以最后一次为准)。,R2中: v:=(a+c)*(b-d)+i; 要访问b,i(Q)，或a(P),必须知道外层过程的活动记录首址，即：SPQ ，SPP,活动记录,PASCAL中，主程序无参数项，所以主程序的活动记录中没有形参单元、形参个数。,活动记录格式,程序结构,活动记录格式,活动记录格式,活动记录格式,程序结构,老SP：调用本过程时，调 用者的SP;(动态链) 静态链：本过程直接外层 过程的最新SP；,调用顺序： PSQR1R2,访问b(Q): =SPQ=4SPQ 访问a(P): =SPQ=SPP=3SPP 缺点：访问速度慢。,程序结构,2.实现方案：DISPLAY表（嵌套层次显示表）,.引入DISPLAY表 设过程P,层数nP, D表有：nP+1项,调用顺序： PSQR1R2,名字地址= DISPLAY静态层数 + 相对数 访问b(Q): =DISPLAY1+相对数 = 相对数SPQ 访问a(P): =DISPLAY0+相对数 = 相对数SPP,调用顺序： PSQR1R2,. 活动记录格式： 其中：*为新增项 全局DISPLAY：指向调用者的 DISPLAY表的位置； DISPLAY表：本过程的嵌套层 次显示表； 主程序没有:参数项， 全局DISPLAY。, 过程的层数是静态确定的， D表的大小是静态确定的（=层数+1）。 又 过程的形参单元的数目在编译时是可以确定的， D表的相对地址d也是静态确定的。,返回,a)子程序可调用自己的直接内层子程序 则层数： nP = nP1 +1 P的D表中，共有nP+1项， P的直接外层是P1， “P的D表前nP项”与“P1的D表”相同,. 构造DISPLAY表 PASCAL的过程调用，有4种情况：,即：DP = DP1 + SPP = DP1前nP项 + SPP = 调用者D表的前nP项+SPP,全局DISPLAY: 指向调用者的 D表的位置,P1调用P P是P1的 直接内层,b) 子程序可以调用自己， 以及它的任何一层外层子程序 P的D表中，共有nP+1项， P是P2的外层， “P的D表前nP项” 与“P2的D表前nP项”相同,即：DP = DP2前nP项 + SPP = 调用者D表的前nP项+SPP,全局DISPLAY: 指向调用者的 D表的位置,c)并列子程序中后说明的调用先说明的 层数： nP = nP1 = nP0 +1 P的直接外层是P0， P的D表前nP项 与 P0的D表 相同， 即：DP=DP0+SPP 同理，P1的D表前nP1项 与 P0的D表 相同， 即：DP1=DP0+SPP1 DP = DP0+SPP = DP1前nP项+SPP = 调用者D表的前nP项+SPP,全局DISPLAY： 指向调用者的 D表的位置；,P1调用P P1、P并列,d) 子程序调用与自己的某个外层 子程序并列的子程序 P的D表中，共有nP+1项， 其中前nP项与 P0的D表 相同， 即：DP=DP0+SPP 又 P0也是也是P3的直接外层， P3的D表的前nP项 与 P0的D表相同 DP = DP0+SPP = DP3前nP项+SPP = 调用者D表的前nP项+SPP,全局DISPLAY： 指向调用者的 D表的位置；,P3调用P P与P3的外层并列,若有过程：P ，Q ，R P调用Q ， Q递归调用自己m次， Q调用R， 则有： DQ1 = DP前nQ项+SPQ1 DQ2 = DQ1前nQ项+SPQ2 = DP前nQ项+SPQ2 DQm = DQm-1前nQ项+SPQm = DP前nQ项+SPQm DQm+1 = DQm前nQ项+SPQm+1 = DP前nQ项+SPQm+1 DR = DQm+1前nR项+SPR,活动记录格式,主程序没有,Q活动记录,活动记录格式,活动记录格式,R活动记录,活动记录格式,S活动记录,返回,§8.5.3 主要处理工作 1. 过程调用 (红色标注),对：Par Ti ( i=1n ), (i+4)TOP:=AddrTi (传地址) 或：(i+4)TOP:=Ti (传值) 对：Call P, n * 1TOP:=SP （保护工作环境） * 4TOP:= n (参数个数) * 3TOP:=全局DISPLAY=SP+d * JSR P (转子),PSQR1R2,返回,2.过程进入(蓝色标注),.建立新工作环境 .保护返回地址 具体工作： * SP:=TOP+1 (新SP) * 1SP=返回地址 * TOP:=TOP+L (新TOP) ( L：活动记录大小，静态确定) * 建立本过程的D表,若层数=n, 从全局display地址开始，向 上n个单元的内容 抄录到现 行活动记录的DISPLAY表中， 再添上当前SP，形成D表。,返回,3.数组分配空间 对可变数组，计算每维的上限、下限、维长， 填入内情向量； 将TOP+1填入数组内情向量的a处(起始地址)； 设数组大小=M， TOP:=TOP+M ； 4. 引用各种数据的方式 参数、局部量、临时单元、内情向量： 设相对数=x，以SP为变址器访问：xSP, 数组元素 * 从内情向量查出a，C，维长等，计算出相对数x； * 变址访问 xa 非局部量： 设：相对数=x， 所在层数=k， D表的相对数=d，（dSP：活动记录起始地址） LD R1, (d+k)SP (第k层过程的最新活动记录的SP) LD R2, xR1 (取出值传送到R2),5.过程返回 （与C相同）,中间代码： proc 过程名 过程体 return (m) endproc,过程返回 * 由return引起 * 过程结束自然返回, 过程返回值存入特定位置 恢复老的工作环境 TOP:=SP-1 SP:=0SP 按返回地址转移 X:=2TOP （返回地址） UJ 0X （无条件转移）,示例程序,活动记录,调用： PS,过程调用,过程进入,返回,调用： PSQ,示例程序,活动记录,返回,过程调用,过程进入,调用： PSQR1,示例程序,活动记录,过程调用,过程进入,调用： PSQR1R2,调用： PSQR1R2,访问b(Q): 相对数x=4，Q层数 k=1， 现行D表相对SP d=6, 当前SP=32， LD R1 ，(6+1)SP /*R1=13*/ LD R2 ，4R1 /*取出b*/,Q数据区,命令：LD R1, (d+k)SP LD R2, xR1,调用： PSQR1R2,访问a(P): 相对数x=3，P层数 k=0， 现行D表相对SP d=6, 当前SP=32， LD R1 ，(6+0)SP /*R1=0 */ LD R2 ，3R1 /*取出a*/,P数据区,命令：LD R1, (d+k)SP LD R2, xR1,作业： P268 第 4 题 函数F中，增加一个动态数组，即： FUNCTION F(n:integer):integer; var M1n : integer; begin end;,
