《存储空间组织-5节(节选).ppt》由会员分享，可在线阅读，更多相关《存储空间组织-5节(节选).ppt（40页珍藏版）》请在三一办公上搜索。
1、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:intege
2、r;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处：PSQR1R2,返回,pascal子程序的调用规定：任何子程序都不能调用主程序。任何子程序（包括主程序）可调用自己的直接内 层子程序，但不能调用隔层的内层子程序。(图1)子程序可以调用自己，以及它的任何一层外层
3、子 程序（不包括主程序）。（图2）,pascal子程序的调用规定：并列子程序中后说明的可以调用先说明的，而先 说明的不能调用后说明的（除非采用向前引用）。一个子程序可以调用所有与自己的某个外层子程 序并列的子程序（其说明先于这个外层子程序）。,8.5.2 非局部名字的访问的实现,1.实现方案：静态链活动记录中，加“静态链”，指向静态直接外层过程的最新活动记录的地址(有多次调用时,以最后一次为准)。,R2中:v:=(a+c)*(b-d)+i;要访问b,i(Q)，或a(P),必须知道外层过程的活动记录首址，即：SPQ，SPP,活动记录,PASCAL中，主程序无参数项，所以主程序的活动记录中没有形参
4、单元、形参个数。,活动记录格式,程序结构,活动记录格式,活动记录格式,活动记录格式,程序结构,老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
5、,调用顺序：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前
6、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=DP
7、0+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调用PP与P3的外层并列,若有过程：P，Q，R P调用Q，Q递归调用自己m次，Q调用R，则有：D
8、Q1=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(参数个
9、数)*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.引用各种数
10、据的方式 参数、局部量、临时单元、内情向量：设相对数=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（
11、返回地址）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 M1.n:integer;begin end;,
