3 变量访问环境 临时变量区 变量访问环境 机器状态 返回值 Size InitOff 过程层数 top 堆区空间 栈区空间 静态区空间

Presentation on theme: "3 变量访问环境 临时变量区 变量访问环境 机器状态 返回值 Size InitOff 过程层数 top 堆区空间 栈区空间 静态区空间"— Presentation transcript:

1 3 变量访问环境 临时变量区 变量访问环境 机器状态 返回值 Size InitOff 过程层数 top 堆区空间 栈区空间 静态区空间
3 变量访问环境 局部变量区 临时变量区 形参变量区 变量访问环境 过程层数 动态链指针 sp 返回地址 top 机器状态 返回值 Size 库代码空间 目标代码空间 静态区空间 堆区空间 栈区空间 高地址 低地址 InitOff

2 3.1 变量访问环境概述 声明链：声明链是过程名的序列，序列的头是主程序名M。具体定义如下： （M）是过程声明链；
3.1 变量访问环境概述 声明链：声明链是过程名的序列，序列的头是主程序名M。具体定义如下： （M）是过程声明链； 若（M，…，P）是声明链，且P中有过程Q的声明，则（M，…，P，Q）也是过程声明链。 用DeclareChain（Q）= （M，…，P，Q）表示声明链。 若Q的层数为N(最外层为0层)，则其声明链的长度为N+1； 对于任一过程Q，它的声明链是唯一的，并且在Q中出现的变量，其声明一定在DeclareChain（Q）中的过程内。

3 活跃活动记录 一个过程S在动态链中可有多个AR，但其中只有最新AR(S )是可访问的，称此AR(S)为S的活跃活动记录，并记为LiveAR(S)，简写为LAR(S)。 例：假设有当前调用链是（M, P1, P2, Q1, R1, R2, R3 ) 则当前动态链为： [AR(M),AR(P1),AR(P2),AR(Q1),AR(R1),AR(R2),AR(R3)] 活跃活动记录LAR为： LAR( M ) = AR(M) LAR( P ) = AR(P2) LAR( Q ) = AR(Q1) LAR( R ) = AR(R3)

4 声明链和变量访问环境 (当前)变量访问环境:Q的声明链中的每个过程的活跃活动记录构成的链称为Q的变量访问环境，记为：
VarVisitEnv(LAR(Q)) = [LAR(M), … , LAR(P), LAR(Q)] 例：（M,P,Q,R)为R的声明链，假设有当前调用链是（M,P1,P2,Q1,R1,R2,R3 ) 则当前动态链为： [AR(M),AR(P1),AR(P2),AR(Q1),AR(R1),AR(R2),AR(R3)] R3的当前变量访问环境: VarVisitEnv(LAR(R) )=[AR(M), AR(P2),AR(Q1),AR(R3)]

5 非局部变量访问的实现 假设Q的变量访问环境: VarVisitEnv（LAR（Q）） = [LAR（M）,…，LAR（P），LAR（Q）]
在Q中有变量XQ，YM，ZP，它们分别定义在过程Q、M和P中，则它们的存储单元地址可表示如下（其中<LAR（Q）>表示LAR（Q）的始地址，其它类似）： addr( XQ )= <LAR（Q）> + OffsetX addr( YM ）= <LAR（M）> + OffsetY addr ( ZP ）= <LAR（P）> + Offsez 结论: 对于每个AR，只要知道了它的变量访问环境VarVisitEnv（AR），即可实现包括非局部变量在内的所有变量的访问。

6 如何计算当前过程的变量访问环境 PROC P; PROC Q;
情况2 PROC Q; Begin … end … … PROC P; Q End 情况1 情况3 情况4 PROC P; … … Begin P End PROC P; … … PROC Q Begin End Begin Q End PROC Q; … … PROC P; Begin Q End Begin End 结论：新调用的当前过程Q(层数为N)的声明链可以通过复制主调过程的声明链前N-1层的信息再加上自己求得。 情况1： P调用P ： P层数等于P层数N. 情况3： P调用Q ,P层数(N-1)小于Q层数(N). DeclaChain(P)= (M，P1, P2,…,PN-2,PN-1) DeclaChain(Q)=(M，P1, P2,…,PN-2, PN-1 , Q) 情况4：P调用Q,P层数大于Q层数(N). DeclaChain(P)= (M，P1, P2,…,PN-1,Q，…，P) DeclaChain(Q)=(M，P1, P2,…,PN-1, Q) 情况2： P调用Q,P层数等于Q层数N. DeclaChain(P)= (M，P1, P2,…,PN-1,P) DeclaChain(Q)=( M，P1, P2,…,PN-1,Q)

7 如何计算当前过程的变量访问环境 定理： VarVisitEnv(LAR(Q)) =VarVisitEnv(LAR(P))N AR(Q)
设Q的调用链DynamicChain(Q)= [AR(M),…,AR(P),AR(Q)], 即P调用Q，切Q的层数为N，则有Q的变量访问环境： VarVisitEnv(LAR(Q)) =VarVisitEnv(LAR(P))N AR(Q) 注意：因为过程层数有0开始，所以Q的前N-1层变量访问信息在主调过程P的变量访问环境的前N个中。 结论：变量Q访问环境可由先行过程P的变量访问环境求得。

8 变量访问环境的实现方法 Display表方法 局部表法 全局表法 静态链方法

9 3.2 局部Display表方法 局部化Display表方法：对于每个AR求出其变量访问环境，并把它的起始地址以地址表的形式(Display表）保存在AR中。因为每个AR都自带Display表，称这种方法为局部化Display表方法。

10 Display表的求法 NewAR.Display= CurrentAR.Display的前Nnewsp； … …
[ar0,ar1,…,arN-1,newsp] Display表 … … newsp 动态链指针 sp … … Display表 [ar0,ar1,…,arN-1,…] … … sp 动态链指针

11 局部Display表时变量的访问 绝对地址=CurrentAR.Display[静态层数]+ 相对地址
对一个变量X(L, off)，地址为： addr(X)=CurrentAR.Display[L]+ off 可用下面两条变址指令获得X的值： LOAD R1,(InitOff+L)[sp] LOAD R2, Off[R1]

12 例1：有过程M,Q,R,S，其中level(M)=0;level(Q)=1;level(R)=1;level(S)= 2，
并且CallChain（S）= （M，Q，R，S）。 假设当前过程S有变量XS、YR和ZM，其中下标名表示变量被定义的过程名 则上述三个变量的地址分别如下： addr( XS ) = sp + offsetx= (sp + InitOff)[2] + offsetx addr( YR ) = (sp + InitOff)[1] + offsety addr( ZM ) = (sp + InitOff)[ 0 ] + offsetz (2, offsetx) (1, offsety) (0, offsetz) AR(S) AR(Q) ..... ar1 AR(R) AR(M) ar0 ..... X单元 Z单元 Y单元 ar0 ar1 ar0 ar2 ar0 ..... sp ar0 ar2 Display表 nil ar2 ..... InitOff sp

13 3.3 静态链的方法 原Display表部分变成一个单元，称为静态链单元，存放静态链指针，指向直接外层（上一层）的最新活动记录的始地址。这就使得运行时栈上的活动记录之间又拉出一条链，称为静态链。

14 Level(M)=0, Level(G)=1, Level(H)=2,Level(R)=3,Level(S)=3
AR0(M) AR1(G) AR2(H) AR3(R) AR4(S) nil sp nil ar0 ar1 ar2 ar3 ar4 AR0(M).Display =[ ar0 ] AR1(G).Display =[ ar0, ar1 ] AR2(H).Display =[ ar0, ar1 , ar2 ] AR3(R).Display =[ ar0, ar1, ar2, ar3] AR4(S).Display =[ ar0, ar1, ar2, ar4] 虚线为静态链指针 实线为动态链指针

15 其中Indir(sp,k)表示sp回退k次的地址。
静态链指针的确定 Level(M)=0, Level(G)=1, Level(H)=2,Level(R)=3,Level(S)=3 CurrentAR NewAR AR0(M) AR1(G) AR2(H) AR3(R) AR4(S) nil sp nil ar0 ar1 ar2 ar4 ar3 若 k= CurrentAR.level-（ NewAR.level -1） ，则 NewAR.StaticChainPointer=Indir(sp,k) 其中Indir(sp,k)表示sp回退k次的地址。

16 k= CurrentAR.level-LX addr(X)= Indir(sp,k)+OffSetx
使用静态链时变量的访问 CurrentAR(P) ……. sp Indir(sp,k) 局部变量X(LX, OffSetx)的访问 X的地址： k= CurrentAR.level-LX addr(X)= Indir(sp,k)+OffSetx

17 答： (1) AR1(p):Null AR2(Q):AR1 AR3(P):null AR4(R):AR3 (2)AR3
例：设有如下含有嵌套定义的类C程序， int P(){ int y,z,x int Q(){ int y ; Q的函数体; } int R(){ int x; int y; x=x+y+z; } P的函数体; } void main(){ 主函数体;} 若有调用链(main, P, Q, P, R)，则运行时5个活动记录见图。 请回答，AR1~AR4的静态链指针分别指向哪一个活动记录？语句x=x+y+z中使用的z在哪一个活动记录中。 答： (1) AR1(p):Null AR2(Q):AR1 AR3(P):null AR4(R):AR3 (2)AR3

18 3.4 全局Display表 系统保留一个Display表，其长度为过程的最大嵌套层数。每层保留当前层活跃活动记录的首地址。
当层数为j的过程Q被调用时，只可能改变j层的LAR首地址： 将原j层地址D[j]的内容保存到NewAR(Q)中： NewAR(Q).ResumeAddr = D[j]; 改写D[j]的内容：D[j]=NewAR(Q)的地址； 当退出Q时：恢复原来D[j]的内容： D[j] = CurrentAR.ResumeAddr 局部变量X(L,off,indir/dir)的访问 X的地址： addr(X)= D[L]+off

19     过程P1 过程 Q2 过程 R2 过程 S3 过程 T3 …… Z(3,offz) ars arT 全局Display
proc P;（设P层数为1） proc Q; （Q层数为2） begin R end proc R; （R层数为2） proc S;（S层数为3） begin T end proc T; (T层数为3) begin X(1,offx) … Y(2,offy) … Z(3,offz)… end begin S end begin Q end Z(3,offz) ………………………… ars AR(T) 动态链（控制链）指针 arT ←sp ………………………… 全局Display AR(S) …… 动态链（控制链）指针 arS Y(2,offy) ………………………… arQ AR(R) 动态链（控制链）指针 arR ………………………… arT arS D(3) AR(Q) 动态链（控制链）指针 arR arQ arQ D(2) X(1,offx) ………………………… AR(P) arP D(1) 动态链（控制链）指针 arp D(0)

20     主程序P 过程 Q 过程 R 过程 S 过程 T …… proc P;（设P层数为1） proc Q; Q层数为2
begin R end proc R; R层数为2 proc S; S层数为3 begin T end proc T; T层数为3 begin … end begin S end begin Q end ………………………… ars AR(T) 动态链（控制链）指针 arT ………………………… 全局Display表 AR(S) …… 动态链（控制链）指针 arS ………………………… arQ AR(R) 动态链（控制链）指针 arR ………………………… arT arS D(3) AR(Q) 动态链（控制链）指针 arQ arR arQ D(2) ………………………… AR(P) arP D(1) arp D(0)

21 总结 Display表方法是用表结构表示变量访问环境。 局部Display表的产生需要花时间，但返回时不需要为恢复变量访问环境做任何事情。

22 总结 静态链方法是用链表表示变量访问环境 静态链方法实际上是一种共享化的局部Display表方法。其主要优点同全局Display表方法是能节省存储单元。产生需要花时间，但返回时不需要为恢复变量访问环境做任何事情。 具体采用哪种方法，取决于机器条件：如果寄存器较少，则使用Display表方法可能合适些；如果机器能提供较好的间接操作，则可选用静态链方法。

23 4 地址分配原则回顾 值引用的形参按照类型大小分配 地址引用的形参分配1 局部变量按照类型长度分配 临时变量分配1
函数和过程作为形参分2个单元，其中1个是实参的入口地址，另一个是先行的display表地址 分配原则，对于值引用的形参，我们还是按照类型的长度分，~~ 地址引用的给她分配1个 都是要存实参的地址，不管实参是什么（都解释） 局部变量的分配就是按照类型的长度来分，临时变量我们一般分1个，特别说明以函数或者过程作为形参，我们一般分配两个单元，一个是实参的入口地址，另外一个是先行的display表的地址，后面我们要讲嵌套型语言进行地址计算的时候要用。 看一个例子（）这些我们前面都讲过，现在看看例子来回忆一遍。复习

24 抽象地址的变化规律 I.处理声明部分: 处理前可用的 处理内容 处理后可用的 抽象地址 抽象地址
处理前可用的 处理内容 处理后可用的 抽象地址 抽象地址 （ℓ，off）  LabelDec  （ℓ，off） （ℓ，off）  ConstDec  （ℓ，off） （ℓ，off）  TypeDec  （ℓ，off） （ℓ，off）  Var id:T  （ℓ，off+nT） （ℓ，off）  ProcDec  （ℓ，off） （ℓ，off）  FuncDec  （ℓ，off）

25 (ℓ，off）  Proc p()  （ℓ+1，off1） (ℓ，off）  Func f():T  （ℓ+1，off1）
II.处理完函数首部: 处理前可用的 处理内容 处理后可用的 抽象地址 抽象地址 (ℓ，off）  Proc p()  （ℓ+1，off1） (ℓ，off）  Func f():T  （ℓ+1，off1） (ℓ，off）  Proc P()  （ℓ，off+2）(形式过程) (ℓ，off）  Func F():T  （ℓ，off+2）(形式函数) 注：小写字母的标识符表示实在标识符，大写字母的标识符则表示形参标识符。nT 表示类型T的长度，off1表示处理完形参部分（实在过程首部）时的偏移值。

26 (ℓ，off） Var ID:T （ℓ，off+1）C语言：T *ID
III. 处理形式参数: (ℓ，off） Var ID:T （ℓ，off+1）C语言：T *ID (ℓ，off） ID:T （ℓ， off+ nT ） C语言：T ID IV.处理过程名及左括号之后: (ℓ，off） Proc p( （ℓ+1，d） (ℓ，off） Func f( （ℓ+1，d） (ℓ，off） Proc P( （ℓ+1，d） (ℓ，off） Fucn F( （ℓ+1，d） 注：小写字母的标识符表示实在标识符，大写字母的标识符则表示形参标识符。nT 表示类型T的长度，off1表示处理完形参部分（实在过程首部）时的偏移值, d为第一个形参的可用起始地址偏移。

27 抽象地址分配的实例: （ℓ，10）Label 100，200; （ℓ，10） Const pai=3.14;
Type arr=array[1..10]of integer; Var x:integer; （ℓ，11） a:array[1..5]of integer; （ℓ，16） Function f（ （ℓ+1，d） Var x:real; （ℓ+1，d+1） a:arr; （ℓ+1，d+11） Var c:arr; （ℓ+1，d+12） Procedure G（）; （ℓ+1，d+14 ） Function F（）:real （ℓ+1， d+16 ） ）:real; （ℓ+1， d+16 =off1） Begin ……end;

28 习题：假设当前层数为L，可用偏移为off0，试写出各个程序点的层数和偏移的变化情况。(d为第一个形参的可用区距)
①typedef at = int a[10][10]； typedef bt = struct {int number; at score;}； ②at x,y; ③int f （at a, ④at* b, ⑤float x） { ⑥bt m; ⑦int n; ………… }⑧ void g（） {⑨ int l; ………… } （ℓ，off0 ） （ℓ，off0 ） （ℓ，off0+200 ） （ℓ+1，d+100 ） （ℓ+1，d+101 ） （ℓ+1，d+103 ） （ℓ+1，d+204） （ℓ，off0+200 ） （ℓ+1，d） （ℓ，off0+200 ）

29 例子 内存 fac A R 临时变量 #define n 5 int sum = 0; int fac(int i)
{ if i=0 return 1; if i<0 return -1; return (i*fac(i-1)); } void main () { sum = fac(n); i: 4 gp sp …… fac A R 临时变 量 i: 5 gp …… main A R 临时变 量 gp …… sum : gp Code area (代码区) pc 内存

30 习题：对于下面的C语言程序，画出程序运行时第二次递归进入函数f后的运行时栈的内容是什么？ 要求：1 详细刻画各活动记录数据信息包含的变量及其值； 2 管理信息的详细内容可以不用给出。
int g(int s) { s=s+10; return s; } int f(int n) if(n<=0) return 1; else return n*f(n-1); void main() int k=1; k=g(20); k=f(10);

31 习题：对于下面的C语言程序，画出程序运行时第二次递归进入函数f后的运行时栈的内容是什么？ 要求：1 详细刻画各活动记录数据信息包含的变量及其值； 2 管理信息的详细内容可以不用给出。
int g(int s) { s=s+10; return s; } int f(int n) if(n<=0) return 1; else return n*f(n-1); void main() int k=1; k=g(20); k=f(10);