编译原理西安交通大学冯博琴8运行时空间组织2.0

《编译原理西安交通大学冯博琴8运行时空间组织2.0》由会员分享，可在线阅读，更多相关《编译原理西安交通大学冯博琴8运行时空间组织2.0（67页珍藏版）》请在金锄头文库上搜索。

1、第九章第九章 运行时空间组织运行时空间组织常见的分配策略：常见的分配策略：1 1，静态分配策略静态分配策略，适用于编译时能完全确定每个数据项存储，适用于编译时能完全确定每个数据项存储空间的位置情况，如空间的位置情况，如 FORTRANFORTRAN；2 2，动态分配策略动态分配策略，编译时不能完全确定数据项的性质，大小，编译时不能完全确定数据项的性质，大小等，如等，如 ALGOL, ALGOL, 它允许递归过程和可变数组，名字作用域和它允许递归过程和可变数组，名字作用域和生存期满足分程序结构所限定的作用范围，可采用生存期满足分程序结构所限定的作用范围，可采用栈式动态栈式动态分配策略分配策略（内

2、存先申请先释放）；当一种语言内存申请和释（内存先申请先释放）；当一种语言内存申请和释放不遵循先请后放时，一般的处理方法是：让运行程序持有放不遵循先请后放时，一般的处理方法是：让运行程序持有一个大存区（称为一个大存区（称为堆堆），凡申请者从堆中分给一块，凡释放），凡申请者从堆中分给一块，凡释放者归还给堆，叫做者归还给堆，叫做堆式动态分配策略堆式动态分配策略17.1 静态存储管理静态存储管理 - FORTRAN 存储分配存储分配FORTRAN FORTRAN 的特点：的特点：1 1，过程不允许递归；，过程不允许递归；2 2，每个数据名所需的存储空间是常数（无可变数组），每个数据名所需的存储空间是常

3、数（无可变数组）3 3，数据名的性质完全确定，数据名的性质完全确定FORTRAN FORTRAN 的的可调数组可调数组：不是可变数组，例子：不是可变数组，例子：子程序子程序：FUNCTION DIA ( A, N, L ) DIMENSION A ( L, L ) DIA = A ( 1, 1 ) DO 6 I = 2, N 6 DIA = DIA + A ( I, I ) RETURN END主程序主程序： DIMENSION X ( 50, 50 ), DIMENSION Y( 100, 100 ) P1 = DIA ( X, 10, 50 ) + DIA ( Y, 100,100)27.

4、1.1 数据区数据区一个 FORTRAN 程序：主程序子程序子程序COMPILER 分块编译目标程序1常数局部区目标程序2常数局部区目标程序3常数局部区有名公用区无名公用区LODER 分块连接3符号表：名字NAME性质ATTR地址DAADDRSWAP子，二目A哑，实变kaB哑，实变ka+2T实变ka+4子程序：子程序：SUBROTINE SWAP ( A, B )SUBROTINE SWAP ( A, B ) T = A T = A A = B A = B B = T B = T RETURN RETURN END END4分层分配方案分层分配方案1 1，将源表示成一个有层次的有向图，将源表示

5、成一个有层次的有向图2 2，从有向图的最低层开始，从有向图的最低层开始, , 往上逐层对程序块分配存储单元往上逐层对程序块分配存储单元20-301 18 83 32 24 46 67 75 511114 49 95 56 68 85 57 713-198-120-70-50-46-1415-18如果不重叠, 需要5555个单元现在只要3131个5关于区关于区 COMPILER 所作的工作所作的工作1 1，名字填符号表，名字填符号表2 2，分局部区号，分局部区号3 3，构造数据区的相应存储映象：，构造数据区的相应存储映象：局部区，公用块局部区，公用块局部数据区的内容局部数据区的内容临时变量，数组

6、，简单变量临时变量，数组，简单变量形式单元形式单元寄存器保护区寄存器保护区返回地址返回地址a6COMMON语句介绍语句介绍COMMON/COMMON/n n1 1/a/a1 1, ,a a2 2, ,a an n,/n,/n2 2/b/b1 1,b,b2 2, ,b bn n/ /R,X,Y,Z/ /R,X,Y,Z1, 格式格式公用区名变量名, 数组名, 数组说明符无名公用区2, 用途用途A, A, 不同程序块的变量之间建立联系不同程序块的变量之间建立联系主程序主程序: :COMMON Z1,Z2,AL,BE,GACOMMON Z1,Z2,AL,BE,GAREAD(11,1)AL,BE,GAR

7、EAD(11,1)AL,BE,GACALL QUADCALL QUAD子程序子程序: :SUBROUTINE QUADSUBROUTINE QUADCOMMON COMMON X1,X2,X1,X2, A,B,CA,B,C结果初值B, B, 节省单元节省单元,2,2块程序可以公用一个公用块块程序可以公用一个公用块, , 特别是数组特别是数组7组说明符数组名交换次序3, 使用使用A, A, COMMON A(2,3)COMMON A(2,3)B,B,DIMENSION A(2,3)DIMENSION A(2,3)COMMON ACOMMON AC,C,COMMON ACOMMON ADIMENS

8、ION A(2,3)DIMENSION A(2,3)87.1.2 公用语句处理公用语句处理用途：不同程序段之间共享数据用途：不同程序段之间共享数据COMMON /B1/A,B,CCOMMON /B1/A,B,CCOMMON /B1/E,F,GCOMMON /B1/E,F,GABCEFGB19处理方法处理方法COMMON / B1 / A, B, C ( 50 )DIMENSION A ( 10, 10 ), B ( 100 )COMPLEX A, B 当首次扫描到当首次扫描到 B1 的时候并不能立即确定每个公用元的相的时候并不能立即确定每个公用元的相对地址对地址 怎么办？怎么办？10NAMEC

9、MPCMP 和和 公用表名公用表名 COMLIST以 COMMON /B1/ A, B, CCOMMON /B1/ A, B, C 为例 引入引入 CMP CMP 后的符号表：后的符号表： COMLIST COMLIST 表：表： NAMELENGTHFTLT.123 B1区链完成的最后结果区链完成的最后结果 新段开始新段开始, FT,LT= 0查查COMLIST表无表无B1填填B1, B1.FT=B1.LT=null, length不变不变B1B1nullnullnullnull2 2 3 30 00 0 对对A(入口为入口为 1 ) 1 11 1 对对B(入口为入口为 2 ) 2 23 3

10、0 0ABC111，若块名，若块名 BLK1 未出现在未出现在 COMMLIST 中，则把它填入并形成中，则把它填入并形成它的空链（它的空链（FT 和和 LT 原来已经为原来已经为 NULL）2，把符号表中的，把符号表中的 NAM1 和和 NAM2 标志为属于公用区，并把他们标志为属于公用区，并把他们依次连接到依次连接到 BLK1 原链的末端。若原链为空则把原链的末端。若原链为空则把 NAM1 的入口的入口填到填到 FT 栏中。最后，调整栏中。最后，调整 LT 使它指向新链的末端。使它指向新链的末端。处理处理 COMMON /BLK1 /NAM1, NAM2的算法的算法127.1.3 7.1.

11、3 等价语句处理等价语句处理1, 1, 等价语句介绍等价语句介绍a, 格式:EQUIVALENCE(变量表1),(变量表2)b, 用途: 同一等价片中的变量共同存储单元 1) 节省: EQU(A,B,C,D) 变量A,B,C,D共同单元 2) 同一量定义不同名字13c,使用: 1) 数组等价 : DIMENSION A(2,3), B(4) EQU(A(1,2),B(1)2) 间接联系 : DIM A(2,3), B(4) EQU(A(1,2),C),(C,B(1)3) 不可矛盾 : DIM A(10) EQU(X, A(1), (X,A(3) DIM A(5), B(10) EQU(A(1)

12、, B(2)(A(3),B(3) A11 A21 A12 A22 A13 A23 B1 B2 B3 B4A1 A2 A3 A4 A5 A6 B2 B3 B4B1 B2 B3 B4 A11 A21 A12 A22 A13 A23 C B1 B2 B3 B4142, 2, 等价语句处理等价语句处理FORTRAN FORTRAN 的等价语句目的在于建立一个程序段中诸变量或数组之间的的等价语句目的在于建立一个程序段中诸变量或数组之间的存储空间的存储空间的一致性一致性 例例, , 处理等价语句：处理等价语句：EQUIVALENCE ( X, A( 2, 3 ),(I, J, A( 1, 2 ), K)1

13、,规则 :a, 对于简单变量 I,J 属一个等价片, 表示 I,J 占用同一单元b, 对于(X, A2,3),名表中无A2,3, 只有A,要指出 X 与 A 位置关系, 引入相对数-A11,相对 X 的地址. c, 对于同一个等价元 A11 在不同的片中出现, 表示这两片的等价元存储是相关的, 他们应予以合并, 原则是后一等价片按照第一片调整相对数.15数组数组数组数组 A(iA(i1 1, i, i2 2,i,in n) ) 的的的的足标足标足标足标 j j j j 的的的的计算公式计算公式计算公式计算公式：1，若等价元为简单变量，则足标为，若等价元为简单变量，则足标为 0；2，若等价元为数

14、组元素，则足标为，若等价元为数组元素，则足标为(di 为维长为维长) : ( i1 - 1) + d1 * ( i2 -1 ) + + di * *dn-1 * ( in 1 )2,语句为存储分配提供信息, 指出那些是等价片. 对它的处理需在名表中增加记号, 为此设栏目.引入 EQEQ -指出同一片的,下一个等价元的入口引入 OFFSET -指出他们的偏移量, OFFSET的计算需要引入足标j, 基准BASE3,算法 : 2 2 2 2 个工作变量个工作变量个工作变量个工作变量 ： P P 和和 BASEBASE P P 指示现行等价链首元在名表入口指示现行等价链首元在名表入口 BASEBAS

15、E 计算等价元相对数的基准计算等价元相对数的基准, , 若在本链中若在本链中, BASE = 0, , BASE = 0, 否则否则 BASE = BASE = 新链基新链基在老链基的相对数在老链基的相对数 z z 相对数相对数, z = BASE , z = BASE j*L (L j*L (L 所需字数所需字数) )164, 等价环的建立过程等价环的建立过程(具体做法具体做法)x0标识标识符符OFFSETEQ等价语句 EQUIVALENCE ( X, A( 2, 3 ),(I, J, A( 1, 2 ), K), 指针指针p指向等价环指向等价环首部首部, 这里没有画出这里没有画出.1, 第

16、第1片片, 第第1元元 x, x为基准为基准, 它相它相对自己的对自己的 z = 0, OFFSET = 0, 本链本链内内 BASE = 0名表工作名表工作: 自环自环.2, 第第2元元 A2,3, A1,1相对相对x的的 地址为地址为z = BASE j*L = -21 名表工作名表工作: A1,1 与与x 链接链接, A1,1 的的 OFFSET = z = -21.3, 第第2片片, 第第1元元I , I 为基准地址为基准地址, 本链内的本链内的 BASE = 0, 名表工作名表工作: 自环自环X0A-21-21I04, 第第2片片, 第第2元元J , z = BASE j*L= 0,

17、 名表工作名表工作: J 链入链入 I, OFFSET =0I0J J05, A1,2, A1,2由于第一片的由于第一片的A2,3, 已经在第一片中占有一席之地已经在第一片中占有一席之地, 现在由于与现在由于与I,J 等价等价, 它将把它将把I, J 带入第一等价片中合并带入第一等价片中合并, 关键之一关键之一是是老环中老环中 I, J 的相对的相对数的计算数的计算. A1,2以以I 为基准为基准, A1,1 相对于相对于I 的相对数为的相对数为 Z = BASE j*L = -10a, 当把新环中的等价元当把新环中的等价元I, J链入到原环时链入到原环时, 新环的相对数都要调整新环的相对数都

18、要调整:z = z原原+D, 其中其中 D = (A的老相对数的老相对数 - 21) (A的新相对数的新相对数-10)b, 合并环合并环, 新环指针新环指针 p c, 基准改变基准改变, BASE = BASE + D = -11, 现行等价链的基准要搬到老链来看现行等价链的基准要搬到老链来看6, 第第2片片, 第第3元元K , K 首变首变, z = BASE j*L= -11 OFFSET, K与与I 等价等价, 应与应与I 有相同的有相同的 z 插入链中插入链中, 由由 p 指出指出A-21X0J J-11-11I-11-11X0J-11K K-11-11I-11A-21加入加入 EQ

19、和和 OFFSET 栏之后的符号表栏之后的符号表（等价语句（等价语句 EQUIVALENCE ( X, A( 2, 3 ),(I, J, A( 1, 2 ), K)EQUIVALENCE ( X, A( 2, 3 ),(I, J, A( 1, 2 ), K)）NAMEOFFSETEQI-11J-11K-11X0A-2112345环：环：环：环：X X X XA A A AI I I IK K K KJ J J JX X X X1 15 52 24 43 318 算法算法BEGIN 把符号表中所有 EQ 栏置为 null /初始化WHILE 存在未处理的等价片 DOBEGIN /* 开始处理新等

20、价片 */P := null ; BASE := 0 ;WHILE 现行片中尚有未处理的等价元 DOBEGIN 取出下一个等价元 X , 假定它在符号表的 入口为 N, 计算出 X 的足标 j ; IF X 为“双实型” 或者 “复型” THEN L := 2 ELSE L := 1; z := BASE j * L ; IF EQ N = null BEGIN IF P = null THEN19 P := N ; ELSE EQ N := EQ P ; EQ P := N; OFFSET N := z;END ELSE BEGIN D := OFFSET N z;BASE := BASE

21、+ D;IF P = null THEN P := N ELSEBEGIN Q := P;LOOP: IF Q = N THENIF D != 0 THEN ERROR （等价冲突）ELSE GOTO NXELE;OFFSET Q := OFFSET Q + D;Q1 := Q; Q := EQ Q ;IF Q != P THEN GOTO LOOP;MERGE:20 EQ Q1 := EQ N ; EQ N := P;END OF MERGING; END;NXELE; END OF THE INNER WHILE;END OF THE OUTER WHILE;END217.1.47.1.4

22、7.1.47.1.4 地址分配地址分配地址分配地址分配对于所有说明性语句处理后，即类型信息等以及对于所有说明性语句处理后，即类型信息等以及EQ,OFFSET,EQ,OFFSET,在名表建立，在名表建立，COMLISTCOMLIST建立之后，可以对变量，数组名进行建立之后，可以对变量，数组名进行分配地址，即填分配地址，即填DA,ADDR,DA,ADDR,对于易碎的个体，地址分配无什么要求，但对于易碎的个体，地址分配无什么要求，但COMMON COMMON 的公共的公共块块B1B1要求其成员必须要求其成员必须保持其顺序保持其顺序，而，而EQUIVALENCEEQUIVALENCE中的等价中的等价片

23、元必须使片元必须使等价元共享存储等价元共享存储。等价片和公共块谁先处理？决。等价片和公共块谁先处理？决定于前者的处理定于前者的处理不要给后者的处理设置障碍不要给后者的处理设置障碍。先等价，后公。先等价，后公共，问题更多。先公共，后等价比较容易处理，只有一点限共，问题更多。先公共，后等价比较容易处理，只有一点限制（制（冒头冒头），所以我们先处理公共语句的块），所以我们先处理公共语句的块. .先分配先分配先分配先分配COMMONCOMMONCOMMONCOMMON的原因的原因的原因的原因COMMON A1,B,C,A,DCOMMON A1,B,C,A,DCOMMON A1,B,C,A,DCOMMO

24、N A1,B,C,A,DDEMENSION A(10,10)DEMENSION A(10,10)DEMENSION A(10,10)DEMENSION A(10,10)EQUIVALANCE(I,J,AEQUIVALANCE(I,J,AEQUIVALANCE(I,J,AEQUIVALANCE(I,J,A1,21,21,21,2,K) (X, A,K) (X, A,K) (X, A,K) (X, A2,32,32,32,3) ) ) )1,1,1,1,公用块中公用元分配公用块中公用元分配公用块中公用元分配公用块中公用元分配LENFTLT无无名名14NAMEATTCMPOFFSETEQDAADDR

25、1A122B33C54D5A4-1096I077J058K069X118KXA1BCA1,1A1,2A2,3A10,10DA1.EQ = NULL, 非等价元,即可分配地址a, a后移 size(A1)B,C 同理123104410314141425公共区长度:S = MAX(fi-f1+size(Ni), i 从1到m这时候的局部区长度len = a + S 分配到数组 A, A1,2 A2,3 为等价元等价片中其他元的地址为ADDR( NI )=a + (fI fA), 当前a=4a等价片内部是一个整体,不论片中哪一个元作为公共元出现,内部相对队形不变,但是遇到不同的元,在公共块中等价片的

26、位置要变化,若先遇到I,那么A1,1 就要跑到A1之前,可能出现冒头,这是错误.使用EQ链和OFFSET(NI)可以计算出ADDR(NI),因此各NI的地址可填,剩下2个问题:1,D分到哪里?2,公共区长度如何算?D应该分配到公共区之后,故ADDR(D) = a + S = 4 + 100 = 104公用区冒头一例公用区冒头一例: :A1BCIJKA1,2A10,1A9,1A8,1A1,1A2,2A2,3A10,10D冒头冒头!24公用区地址分配算法公用区地址分配算法公用区地址分配算法公用区地址分配算法a: a: 地址计数器地址计数器; len: ; len: 长度计数器长度计数器; d ;

27、d 公用区编号公用区编号FOR COMLIST 中每个中每个 FT 不为不为 null 的项的项 i , DOBEGIN a := 0; len := 0; d := i + 127; N := FT i ; WHILE N != null DOBEGIN IF DA N != 0 THEN IF DA N != d OR ADDR N != a THEN ERROR (冲突冲突) ELSE IF EQ N = null THEN DA N := d; ADDR N := a ELSE BEGIN N1 := N; f := OFFSET N ; REPEAT a1 := a + ( OFFS

28、ET N1 - f); IF a1 0 THEN ERROR (冒头冒头); IF DA N1 != 0 AND ( DA N1 != d OR ADDR N1 != a1)THEN ERROR (非法等价非法等价); ELSE BEGINDA N1 := d; ADDR N1 := a1 ;len := MAX ( len, a1 + size( N1 );N1 := EQ ( N1 ) ;ENDUNTIL N1 = NEND;a := a + size N ;len := MAX ( len, a ); REPEATN := CMP N ;END OF WHILE;LENGTH i :=

29、MAX ( LENGTH i , len );FT i := null; LT i := null ;END OF FOR LOOP;2,2,局部区地址分配局部区地址分配局部区地址分配局部区地址分配例子例子: DIMENSION A(10,10), B(4) REAL Y EQUIVALANCE(X, A EQUIVALANCE(X, A2,32,3 ), ), REAL Z REAL ZYA1,1A2,1A2,3A2,3Za假定假定 f2 最小最小,N2 的地址为的地址为 a其他其他, ADDR(Ni)=a + (fi f2), 特别地特别地, 对对X有有 f1 = 0, f2 = -21

30、ADDR(N1)=a + (f1 f2)= a + 21N1 X f1N2 A f2Nm fmY 已经分配已经分配Xf1=0f2 = -21算法算法: :1, 1, 环内求环内求 Min offset(NMin offset(Ni i) = f;) = f;2, 2, 环内每个元环内每个元 Ni Ni 做做 DA DA 栏为现行程序区号栏为现行程序区号ADDRADDR栏栏 = a + offset(N= a + offset(Ni i) - f) - f局部区长度局部区长度: :len = MAX(len, (offset(Nlen = MAX(len, (offset(Ni i)-f) +

31、size(N)-f) + size(Ni i););3, 3, 处理完本等价环后地址移动处理完本等价环后地址移动: : a = a + lena = a + len为改等价环后地变量指出分配地址为改等价环后地变量指出分配地址3,3,3,3,临时变量的地址分配临时变量的地址分配临时变量的地址分配临时变量的地址分配临时变量的临时变量的作用域不相交作用域不相交, ,则可以公用一个存储单元则可以公用一个存储单元大部分临时变量名用来存放表达式的中间结果大部分临时变量名用来存放表达式的中间结果, ,这类变量这类变量名有一个特点名有一个特点, ,它们均只被定值一次它们均只被定值一次, ,被引用一次被引用一次

32、. .它们的它们的作用域是作用域是层次嵌套层次嵌套的的 - - 栈栈例子例子: :对赋值语句对赋值语句 X := A * B X := A * B X := A * B X := A * B C * D + E * F C * D + E * F C * D + E * F C * D + E * F产生的临时变量的处理产生的临时变量的处理产生的临时变量的处理产生的临时变量的处理四元式四元式四元式四元式地址地址地址地址临时变量名临时变量名临时变量名临时变量名( 1 ) * A B T1( 1 ) * A B T1T1T1a a( 2 ) * C D T2( 2 ) * C D T2T2T2a+

33、1a+1( 3 ) - ( 3 ) - T1 T2T1 T2 T3 T3( 4 ) * E F T4( 4 ) * E F T4( 5 ) + ( 5 ) + T3 T4T3 T4 T5 T5( 6 ) := T5 X( 6 ) := T5 XT3T3T4T4T5T5a aa+1a+1a aT1, T2 T1, T2 不再使用不再使用不再使用不再使用它们的存储单元可它们的存储单元可它们的存储单元可它们的存储单元可以回收以回收以回收以回收T3, T4 T3, T4 不再使用不再使用不再使用不再使用它们的存储单元可它们的存储单元可它们的存储单元可它们的存储单元可以回收以回收以回收以回收最后只是用了

34、一最后只是用了一最后只是用了一最后只是用了一个单元个单元个单元个单元 : a: a“代真代真代真代真”后的四元式序列后的四元式序列后的四元式序列后的四元式序列(1) * A B $a(1) * A B $a四元式四元式四元式四元式K(K(K(K(初始值为初始值为初始值为初始值为 a)a)a)a)(2) * C D $(a+1) (2) * C D $(a+1) (3) - (3) - $a $(a+1)$a $(a+1) $a $a (4) * E F $(a+1) (4) * E F $(a+1) (5) + (5) + $a $(a+1)$a $(a+1) $a $a(6) := $a x

35、 (6) := $a x a + 1a + 1a + 2a + 2a + 1a + 1a + 2a + 2a + 1a + 1a aa, a + 1 a, a + 1 存储单存储单存储单存储单元不再使用元不再使用元不再使用元不再使用可以回收可以回收可以回收可以回收a, a + 1 a, a + 1 存储单存储单存储单存储单元不再使用元不再使用元不再使用元不再使用可以回收可以回收可以回收可以回收最后只使用了单最后只使用了单最后只使用了单最后只使用了单元元元元 a a7.2 7.2 7.2 7.2 动态存储分配动态存储分配动态存储分配动态存储分配 - - - - 简单栈式简单栈式简单栈式简单栈式特

36、点特点特点特点: : 1, 1, 没有分程序结构没有分程序结构没有分程序结构没有分程序结构; ;2, 2, 过程定义不允许嵌套过程定义不允许嵌套过程定义不允许嵌套过程定义不允许嵌套; ;3, 3, 允许过程递归调用允许过程递归调用允许过程递归调用允许过程递归调用; ;4, 4, 允许过程含有可变数组允许过程含有可变数组允许过程含有可变数组允许过程含有可变数组;( ;(但不允许全局可变数组但不允许全局可变数组但不允许全局可变数组但不允许全局可变数组) )主程序全局数据区主程序全局数据区Q Q 的活动记录的活动记录Q Q 的数组区的数组区R R 的活动记录的活动记录R R 的数组区的数组区调调用用

37、方方向向C C C C 语言程序的存储组织语言程序的存储组织语言程序的存储组织语言程序的存储组织TOPTOPSPSP主程序调主程序调主程序调主程序调用用用用 QQSPSPTOPTOP分配数组分配数组分配数组分配数组区完成区完成区完成区完成主程序调主程序调主程序调主程序调用用用用 R R分配数组分配数组分配数组分配数组区完成区完成区完成区完成最最最最终终终终情情情情形形形形7.2.17.2.17.2.17.2.1 C C C C 过程的活动记录过程的活动记录过程的活动记录过程的活动记录临时临时临时临时工作工作工作工作单单单单元元元元内情向量内情向量内情向量内情向量简单变简单变简单变简单变量量量量

38、形式形式形式形式单单单单元元元元参数个数参数个数参数个数参数个数返回地址返回地址返回地址返回地址老老老老SPSP2 21 10 0TOPTOPSPSPC 的过程调用，过程进入，数组空间分配和过程返回的过程调用，过程进入，数组空间分配和过程返回过程调用的四元式序列过程调用的四元式序列过程调用的四元式序列过程调用的四元式序列par Tpar T1 1par Tpar T2 2. . . .par par T Tn ncall P, ncall P, n每个每个每个每个 par par par par 翻译成翻译成翻译成翻译成(i + 3)TOP := T(i + 3)TOP := T(i + 3)

39、TOP := T(i + 3)TOP := Ti i i i 或者或者(i + 3)TOP := (i + 3)TOP := addr(Taddr(Ti i) )其中其中:x SP :x SP 表示变址访问表示变址访问地址地址 x + SPx + SP36call P, ncall P, ncall P, ncall P, n翻译成翻译成翻译成翻译成1 TOP := SP1 TOP := SP1 TOP := SP1 TOP := SP ( ( ( (保护现行保护现行保护现行保护现行SP)SP)SP)SP)3 TOP := n3 TOP := n3 TOP := n3 TOP := n ( (

40、 ( (传送参数个数传送参数个数传送参数个数传送参数个数) ) ) )JSR PJSR PJSR PJSR P ( ( ( (转子指令，转向转子指令，转向转子指令，转向转子指令，转向 P P P P 的第一条指令的第一条指令的第一条指令的第一条指令) ) ) )接着执行接着执行接着执行接着执行SP := TOP + 1 SP := TOP + 1 SP := TOP + 1 SP := TOP + 1 ( ( ( (定义新定义新定义新定义新SP)SP)SP)SP)1SP:= 1SP:= 1SP:= 1SP:= 返回地址返回地址返回地址返回地址 ( ( ( (保护返回地址保护返回地址保护返回地址

41、保护返回地址) ) ) )TOPTOPTOPTOP := TOP + L := TOP + L := TOP + L := TOP + L ( ( ( (定义新定义新定义新定义新TOP)TOP)TOP)TOP)对数组处理对数组处理对数组处理对数组处理1 1 1 1，计算各维上下限，计算各维上下限，计算各维上下限，计算各维上下限2 2 2 2，调用数组空间分配子程序，调用数组空间分配子程序，调用数组空间分配子程序，调用数组空间分配子程序37E E E E 已在已在已在已在 T T T T 中中中中return return return return (E)(E)(E)(E)T T T T 送寄

42、存器送寄存器送寄存器送寄存器（等待调用段取走）（等待调用段取走）（等待调用段取走）（等待调用段取走）接着执行恢复工作接着执行恢复工作接着执行恢复工作接着执行恢复工作TOP := SP TOP := SP TOP := SP TOP := SP 1 1 1 1SP := 0SPSP := 0SPSP := 0SPSP := 0SPX := 2TOPX := 2TOPX := 2TOPX := 2TOPUJ 0XUJ 0XUJ 0XUJ 0X 另另另另: : : :过程通过过程通过过程通过过程通过 end end end end 自动返回的方法：自动返回的方法：自动返回的方法：自动返回的方法：如果

43、过程是函数过程，则按同样的办法传送结果值，否则直接执行如果过程是函数过程，则按同样的办法传送结果值，否则直接执行如果过程是函数过程，则按同样的办法传送结果值，否则直接执行如果过程是函数过程，则按同样的办法传送结果值，否则直接执行上述返回指令上述返回指令上述返回指令上述返回指令387.3 嵌套过程语言的栈式实现嵌套过程语言的栈式实现重点重点：嵌套层次的概念和处理方法：嵌套层次的概念和处理方法7.3.1 嵌套层次显示表嵌套层次显示表 DISPLAY 和活动纪录和活动纪录要求：要求：过程过程 Q 运行时必须知道它的运行时必须知道它的所有所有外层过程的最新活动纪录的地址外层过程的最新活动纪录的地址做法

44、：做法：设法跟踪每个外层过程的最新活动纪录的位置设法跟踪每个外层过程的最新活动纪录的位置例子：过程例子：过程 R 的外层为的外层为 Q, Q 的外层为主程序的外层为主程序 P, 则则 R 运行时的运行时的DISPLAY 表为：表为： R R 的现行活动纪录的地址（的现行活动纪录的地址（SP SP 现行值）现行值） Q Q 的的最新最新活动纪录的地址活动纪录的地址 P P 的活动纪录的地址的活动纪录的地址39 引入引入 DISPLAY 表以后的活动纪录表以后的活动纪录临时变量临时变量临时变量临时变量内情向量内情向量内情向量内情向量简单变量简单变量简单变量简单变量DISPLAYDISPLAY形式单

45、元形式单元形式单元形式单元参数个数参数个数参数个数参数个数全局全局全局全局 DISPLAYDISPLAY返回地址返回地址返回地址返回地址老老老老 SPSPTOPSPD D 个个个个单单单单元元元元40 活动纪录表：活动纪录表： ARPROC P PROC P PROC P PROC P PyPyPyPyPROC Q PROC Q PROC Q PROC Q QxQxQxQxPROC RPROC RPROC RPROC R. . . . . . .引用引用引用引用 PyPyPyPy, , , , QxQxQxQx. . . .call Rcall Rcall Rcall Rcall Qcall

46、Qcall Qcall Q( ( ( ( Py,QxPy,QxPy,QxPy,Qx 为参数为参数为参数为参数 ) ) ) )临时变量，内情向量临时变量，内情向量临时变量，内情向量临时变量，内情向量简单变量简单变量简单变量简单变量SPSP2 2SPSP1 1SPSP0 0形式单元形式单元形式单元形式单元mm全局全局全局全局DISPLAYDISPLAY返回地址返回地址返回地址返回地址老老老老SPSPData SectionData SectionQxQx , ,内情内情内情内情QQP P形参形参形参形参n n全局全局全局全局DISPLAYDISPLAY返回地址返回地址返回地址返回地址老老老老SPS

47、Pd + l l l lR R R Rl l l lQ Q Q Ql l l lR R R Rd d d d 个单元个单元个单元个单元ARARARARR R R Rd d d d 个单元个单元个单元个单元SP2SP1.241建立建立 DISPLAY 的方法的方法SPSPSPSP0 0 0 01.0 1.0 1.0 1.0 层层层层 (P)(P)(P)(P)SPSPSPSP1.11.11.11.1SPSPSPSP0 0 0 02.1 2.1 2.1 2.1 层层层层 (Q(Q(Q(Q第一次调用第一次调用第一次调用第一次调用) ) ) )SPSPSPSP1.21.21.21.2SPSPSPSP0

48、0 0 02.2 2.2 2.2 2.2 层层层层 (Q(Q(Q(Q递归调用递归调用递归调用递归调用) ) ) )SPSPSPSP2 2 2 2SPSPSPSP1.21.21.21.2SPSPSPSP0 0 0 03.1 3.1 3.1 3.1 层层层层 (R)(R)(R)(R)DISPLAY 的结构的结构1 1 1 1，表项和层次有关，底层若从，表项和层次有关，底层若从，表项和层次有关，底层若从，表项和层次有关，底层若从 0 0 0 0 层开始，表项层开始，表项层开始，表项层开始，表项 = = = = 层次层次层次层次+1+1+1+12 2 2 2，与调用层有关，与调用层有关，与调用层有关，

49、与调用层有关本层本层本层本层 SPSPSPSP调用层调用层调用层调用层D D D D表表表表不考虑递归：不考虑递归：不考虑递归：不考虑递归：本层本层本层本层 SPSPSPSP调用层调用层调用层调用层D D D D表表表表-1-1-1-1 考虑递归：考虑递归：考虑递归：考虑递归：42DISPLAY 的建立方法（从的建立方法（从Q2 调用调用 R）进入新过程时进入新过程时1，应把它的外层的，应把它的外层的 D 表地址作为连接数据传过来，若进表地址作为连接数据传过来，若进R, 应把应把d SP1.2 传到传到 ARR 的全局的全局 D 表表;2,进入进入 R 时，根据时，根据 SP1.2 从从 Q

50、的活动纪录中截取的活动纪录中截取 d SP1.2 (d + lR) SP1.2 (l 为层数为层数)， 再添加进入再添加进入 R 时新建立的时新建立的 SP243现行过程中引用了某一外层过程（层数为现行过程中引用了某一外层过程（层数为k）获得）获得 X 值的方法值的方法LD R1, ( d + k ) SP LD R1, ( d + k ) SP ( (获得第获得第获得第获得第 k k 层过程的最新活动纪录层过程的最新活动纪录层过程的最新活动纪录层过程的最新活动纪录) )LD R2, X R1 LD R2, X R1 ( (把把把把 X X 的值传送到的值传送到的值传送到的值传送到 R2)R2

51、)当过程当过程 P1 调用过程调用过程 P2 而进入了而进入了 P2 后，后，P2 建立建立自己的自己的DISPLAY 的方法的方法1，若，若 P2 是一个是一个真实过程，真实过程，2 种情形种情形P1P2CALL P2P0P2P1CALL P2做法：做法：只需要把只需要把 P1 的的 DISPLAY 地址作为地址作为连接数据之一传给连接数据之一传给 P2, WHY?442, 若若 P2 是形式参数，连接数据包含是形式参数，连接数据包含 3 项项1 1，老，老，老，老 SP SP 值；值；值；值；2 2，返回地址；，返回地址；，返回地址；，返回地址；3 3，全局，全局，全局，全局 DISPLA

52、Y DISPLAY 地址地址地址地址 （P1 P1 的的的的 DISPLAY DISPLAY 地址）地址）地址）地址）457.3.2 过程调用，过程进入过程调用，过程进入与前述与前述与前述与前述 C C C C 语言的方法大体相同，但是由于增设了一个连接数据，所以语言的方法大体相同，但是由于增设了一个连接数据，所以语言的方法大体相同，但是由于增设了一个连接数据，所以语言的方法大体相同，但是由于增设了一个连接数据，所以每个每个每个每个 par Ti par Ti par Ti par Ti 相应的指令改为：相应的指令改为：相应的指令改为：相应的指令改为：( i + 4) TOP := Ti;(

53、i + 4) TOP := Ti; 或者或者( i + 4) TOP := ADDR( Ti )( i + 4) TOP := ADDR( Ti )call P, ncall P, n翻译成翻译成翻译成翻译成1 TOP := SP;1 TOP := SP;3 TOP := SP + d;3 TOP := SP + d;4 top := n;4 top := n;JSR PJSR P接下来接下来 定义新的定义新的定义新的定义新的 SP , TOPSP , TOP； 保护返回地址保护返回地址保护返回地址保护返回地址46接下来接下来 按第三项连接数据所提供的全局按第三项连接数据所提供的全局按第三项连

54、接数据所提供的全局按第三项连接数据所提供的全局 DISPLAY DISPLAY 的地址，的地址，的地址，的地址，自低向上抄录自低向上抄录自低向上抄录自低向上抄录 l l 个单元的内容（个单元的内容（个单元的内容（个单元的内容（l l 为为为为P P 的层数），再添的层数），再添的层数），再添的层数），再添上新的上新的上新的上新的 SP SP 以形成以形成以形成以形成新的新的新的新的DISPLAY ( l + 1 DISPLAY ( l + 1 个单元个单元个单元个单元) )P P 返回返回TOP := SP -1 ;TOP := SP -1 ;SP := 0 SP;SP := 0 SP;X :

55、= 2 TOP;X := 2 TOP;UJ 0 X;UJ 0 X;477.3.3 参数传递参数传递如果实参是一个简单变量，数组元素或者临时变量，则根据传地址如果实参是一个简单变量，数组元素或者临时变量，则根据传地址或者传值对或者传值对 par T 的解释是正确的；如果实参为数组，过程或者标的解释是正确的；如果实参为数组，过程或者标号，号，par T 的作用都是传地址，而且在传地址之前要做别的工作。的作用都是传地址，而且在传地址之前要做别的工作。 1, par T, T 为数组为数组若要求运行时对形若要求运行时对形-实数组的维数一致性和体积相容性进行动态检实数组的维数一致性和体积相容性进行动态检

56、查，则应传送查，则应传送 T 的的内情向量内情向量；否则，只传送；否则，只传送 T 的的首地址首地址。2, par T, T 为过程为过程例子：假定例子：假定 过程过程 P 把过程把过程 T 作为实参传递给过程作为实参传递给过程 Q，随后，随后，Q 又通又通过引用相应的形式参数调用过引用相应的形式参数调用 T 48调用关系调用关系P PT TQQ(z(z(z(z) ) ) )Call ZCall ZCall Q(T)Call Q(T)49P 和和 T 仅有的两种关系仅有的两种关系1, P 1, P 的的的的 DISPLAY DISPLAY 正好就是正好就是正好就是正好就是 T T 的直接外层的

57、的直接外层的的直接外层的的直接外层的 DISPLAY :DISPLAY :P PT T2, P 2, P 的的的的 DISPLAY DISPLAY 包含了包含了包含了包含了 T T 的直接外层的的直接外层的的直接外层的的直接外层的 DISPLAY :DISPLAY :P PT T不论何种情况，假定不论何种情况，假定不论何种情况，假定不论何种情况，假定 T T 的层数为的层数为的层数为的层数为 l l，那么，那么，那么，那么，T T 的的的的 DISPLAY DISPLAY 是由是由是由是由 P P 的的的的 DISPLAY DISPLAY 的的的的前前前前 l l 个单元个单元个单元个单元的的

58、的的内容和内容和内容和内容和 SP SP 的现行值组成的现行值组成的现行值组成的现行值组成50目的：使得过程目的：使得过程 T 工作时能知道工作时能知道 P 的的 DISPLAY方法：在方法：在 P 把把 T 作为实参传送给作为实参传送给 Q 的时候，把的时候，把 P 自身的自身的DISPLAY 地址也传过去地址也传过去过程过程过程过程 P P 中的中的中的中的 par Tpar T的作用：建立下面两个相继临时单元的值的作用：建立下面两个相继临时单元的值的作用：建立下面两个相继临时单元的值的作用：建立下面两个相继临时单元的值B1 : B1 : 过程过程过程过程 T T 的入口地址；的入口地址；

59、的入口地址；的入口地址；B2 : B2 : 现行的现行的现行的现行的 DISPLAY DISPLAY 地址地址地址地址 （DpDp）然后，把第一临时单元然后，把第一临时单元然后，把第一临时单元然后，把第一临时单元 B1 B1 的地址传送给的地址传送给的地址传送给的地址传送给 Q (Q (执行执行执行执行 (i + 4) TOP := ADDR(B1) (i + 4) TOP := ADDR(B1) 假定后来执行到假定后来执行到假定后来执行到假定后来执行到 CALL Z, m Z CALL Z, m Z 为形式参数为形式参数为形式参数为形式参数 ，含有，含有，含有，含有B1B1的地址。的地址。的

60、地址。的地址。Z: B1Z: B1地址地址DpDpB1B1B2B2过程过程过程过程 T TT T Q Q P P B2作为全局DISPLAY传给T513，par T, T 为标号为标号, 形如：形如：P PGOTO z;GOTO z;CALL Q(T)CALL Q(T)T: T: Q(zQ(z) )52假定标号假定标号 T 是在过程是在过程 P0 中定义的（中定义的（P0是是P自身或某一外层），自身或某一外层），P 中中 par T ( T 为标号为标号)的功能为建立如下的功能为建立如下 2 个临时单元：个临时单元：第一临时单元第一临时单元B1: 标号标号 T 的地址；的地址；第二临时单元第二

61、临时单元B2：P0 的活动记录地址的活动记录地址B1 Q（B1地址给地址给Q）执行到执行到 GOTO z ( z 已经含有已经含有 B1 地址地址)53逐级恢复逐级恢复SP 和和 TOP 到到 SP 指向指向 P0 的活动纪录的活动纪录（栈不动，（栈不动，SP 动）动）B2 := ( l l + d ) SP （取得（取得 P0 的活动纪录地址）的活动纪录地址）其中，其中，l l 为为 P0 的层数，的层数，d 为为 DISPLAY 的相对地址的相对地址Z : B1Z : B1P0P0T1B1: T 的地址，送的地址，送 D DP P : : l l l ld dSPQQP PP0P0B2:

62、P0 的活动地址的活动地址 547.4 ALGOL 的实现的实现ALGOL 的特点：的特点：1，分程序，分程序 分程序的分程序的嵌套性嵌套性2，参数换名，参数换名分程序和过程的分程序和过程的区别和联系区别和联系：相同：都可以引用外层变量相同：都可以引用外层变量不同：不同：过程有名字，都有变量说明，流程和书面写法不相同，可以单独运行过程有名字，都有变量说明，流程和书面写法不相同，可以单独运行分程序没有名字，流程和书面写法相同，不能单独运行分程序没有名字，流程和书面写法相同，不能单独运行557.4.1 分程序结构分程序结构一种可能的处理方法一种可能的处理方法把分程序看作把分程序看作把分程序看作把分

63、程序看作“ “无参数过程无参数过程无参数过程无参数过程” ”，在哪里定义就在哪里被调用，在哪里定义就在哪里被调用，在哪里定义就在哪里被调用，在哪里定义就在哪里被调用引入的引入的 问题问题1 1，每次进入一个分程序都要建立连接数据和，每次进入一个分程序都要建立连接数据和，每次进入一个分程序都要建立连接数据和，每次进入一个分程序都要建立连接数据和 DISPLAYDISPLAY；2 2，分程序返回时必须从各层依次退出（一次退出可以获得目标层活动纪录，分程序返回时必须从各层依次退出（一次退出可以获得目标层活动纪录，分程序返回时必须从各层依次退出（一次退出可以获得目标层活动纪录，分程序返回时必须从各层依

64、次退出（一次退出可以获得目标层活动纪录地址，但是无法知道目标层的地址，但是无法知道目标层的地址，但是无法知道目标层的地址，但是无法知道目标层的 TOPTOP，因为，因为，因为，因为 TOP TOP 是共有的）是共有的）是共有的）是共有的）56解决办法解决办法1 1，TOP TOP 私有化，每一个过程和每一个分程序都保有一个私有化，每一个过程和每一个分程序都保有一个私有化，每一个过程和每一个分程序都保有一个私有化，每一个过程和每一个分程序都保有一个 TOPTOP；2 2，分程序不作为无参数过程调用处理，分程序不作为无参数过程调用处理，分程序不作为无参数过程调用处理，分程序不作为无参数过程调用处理

65、例子例子 新的活动纪录新的活动纪录1 1Procedure A ( m, n ); integer m, n ;Procedure A ( m, n ); integer m, n ;B1: begin real z ; array B m : n ;B1: begin real z ; array B m : n ;B2: begin real d, e;B2: begin real d, e; L3: L3: end; end;B4: begin array C 1 : m ;B4: begin array C 1 : m ;B5: begin real e;B5: begin real

66、e;L6:L6:end;end;end;end;L8: end;L8: end;2 24 45 557变量变量 e 变量变量 e 和和 dB5 的的 TOP数组数组 C 的内情向量的内情向量B4 的的 TOPB2 的的 TOP数组数组 B 的内情向量的内情向量变量变量 zB1 的的 TOPDISPLAY形式单元形式单元 m, n参数个数：参数个数： 2调用时候的栈顶地址调用时候的栈顶地址 （老（老 TOP）全局全局 DISPLAY 地址地址返回地址返回地址老老 SP过程的过程的 TOP, 指向活动纪录顶部指向活动纪录顶部Procedure A 的活动纪录的活动纪录SPSPK KD D6 65

67、54 43 32 21 10 058DISPLAYDISPLAY形式单元形式单元形式单元形式单元m, nm, n2 2连接数据连接数据连接数据连接数据A A 的的的的TOPTOP。B B 的内情向量的内情向量的内情向量的内情向量z zB1 B1 的的的的TOPTOP7.4.2 分程序的进入和退出分程序的进入和退出 以以 procedure 为例为例数组数组数组数组 B B数组数组数组数组 C C 到达标号到达标号到达标号到达标号 B1 B1 处处处处 进入分程序进入分程序进入分程序进入分程序 B1 B1 数组数组数组数组 B B 分配之后分配之后分配之后分配之后 进入分程序进入分程序进入分程序

68、进入分程序 B2 B2 进入分程序进入分程序进入分程序进入分程序 B4 B4 分配数组分配数组分配数组分配数组 C C 之后之后之后之后 进入分程序进入分程序进入分程序进入分程序 B5 B5 e ed dB2 B2 的的的的 TOPTOPC C 的的的的内情向量内情向量内情向量内情向量B4 B4 的的的的 TOPTOPe eB5 B5 的的的的TOPTOP597.4.3 过程调用，进入和返回过程调用，进入和返回一个例子：一个例子：过程过程 Q 中的某一个分程序中的某一个分程序 B 里调用了过程里调用了过程 PB: B: Proc Q ( x1, x2, , Proc Q ( x1, x2, ,

69、 xnxn ) )BeginBeginZ, A ( 1: n )Z, A ( 1: n )Call P, m;Call P, m;endend60语句语句 Call P, m 的执行过程的执行过程: B 的的 TOP 送变址器送变址器 X : X := B.TOP 建立未来的建立未来的 P 的连接数据和实现转子的连接数据和实现转子 : 2 X := SP 4 X := SP + d 5 X := X 6 X := mJSR P 进入进入 P 后立即执行：后立即执行：SP := X +10 SP := X + L （L 是过程是过程 P 的活动纪录长度）的活动纪录长度）2 SP := 返回地址返

70、回地址61P 出口的动作：出口的动作： X := 2 SP SP := 1 SP UJ 0 X 形参mX ( 老 TOP)SPQ + d返回地址（到分程序）老的 SPQX + lp Q.TOPA 数组A 的内情向量zB.TOPDISPLAY 表形参单元变参个数 n全局 D 表返回地址老 SPQ 的 TOP d d建立建立建立建立 P P 的的的的 DISPLAY DISPLAY 表的方法：表的方法：表的方法：表的方法：根据根据根据根据 3 SP (3 SP (即：即：即：即：4 X ) 4 X ) 中所指的全中所指的全中所指的全中所指的全局局局局 D D 表表表表 ( Q ( Q 的的的的 D

71、ISPLAY)DISPLAY)从从从从 Q Q 的的的的 AR AR 中取出中取出中取出中取出 D D 表表表表, , 再加上再加上再加上再加上过程过程过程过程 P P 的层数的层数的层数的层数 l lP P ，送到形参单元之上，形成本过程，送到形参单元之上，形成本过程，送到形参单元之上，形成本过程，送到形参单元之上，形成本过程（P P）的）的）的）的DISPLAY.DISPLAY.送送送送 X X627.4.4 参数子程序参数子程序ALGOL 的换名形式参数对应的实参的处理方法：的换名形式参数对应的实参的处理方法：子程序子程序，俗称，俗称thunkthunk处理办法：处理办法：处理办法：处理

72、办法：1 1，若实参是简单变量或者下标变量，若实参是简单变量或者下标变量，若实参是简单变量或者下标变量，若实参是简单变量或者下标变量，thunkthunk 直接计算该变量的直接计算该变量的直接计算该变量的直接计算该变量的地址；地址；地址；地址；2 2，若实参是一个其他表达式，若实参是一个其他表达式，若实参是一个其他表达式，若实参是一个其他表达式， thunkthunk 的任务是计算此表达式的任务是计算此表达式的任务是计算此表达式的任务是计算此表达式的值并把它存放在某个确定的工作单元中，然后回送此单元的的值并把它存放在某个确定的工作单元中，然后回送此单元的的值并把它存放在某个确定的工作单元中，然

73、后回送此单元的的值并把它存放在某个确定的工作单元中，然后回送此单元的地址。地址。地址。地址。63例子例子过程过程过程过程 P P 中的某个分程序中的某个分程序中的某个分程序中的某个分程序 B B 内通过语句内通过语句内通过语句内通过语句 Q ( E ) Q ( E ) 调用了过程调用了过程调用了过程调用了过程 Q ,Q ,此处实参此处实参此处实参此处实参 E E 是一个表达式。过程是一个表达式。过程是一个表达式。过程是一个表达式。过程 Q Q 中的某一个分程序中的某一个分程序中的某一个分程序中的某一个分程序 B1 B1 对对对对 Q Q 的形式参数的形式参数的形式参数的形式参数 Z Z 的的的

74、的引用意味着对引用意味着对引用意味着对引用意味着对 E E 的的的的 thunkthunk 调用调用调用调用Proc PProc PB:B:Q ( E )Q ( E )Proc Q ( Z )Proc Q ( Z )B1:B1:Z Z64注意：注意：注意：注意：1 1，B1 B1 对对对对 Q Q 的形式参数的形式参数的形式参数的形式参数 Z Z 的引用意味着对的引用意味着对的引用意味着对的引用意味着对 E E 的的的的 thunkthunk 的调用，的调用，的调用，的调用，这个这个这个这个 thunkthunk 必须工作在必须工作在必须工作在必须工作在 P P 的环境中；的环境中；的环境中；

75、的环境中；2 2，如果参数表达式，如果参数表达式，如果参数表达式，如果参数表达式 E E 中含有函数调用，会改写栈中中含有函数调用，会改写栈中中含有函数调用，会改写栈中中含有函数调用，会改写栈中 B.TOP B.TOP 所所所所指位置以上的部分，所以必须预先把指位置以上的部分，所以必须预先把指位置以上的部分，所以必须预先把指位置以上的部分，所以必须预先把 B B 的的的的 TOP TOP 值暂时改称指值暂时改称指值暂时改称指值暂时改称指向栈的最高位置（向栈的最高位置（向栈的最高位置（向栈的最高位置（B1.TOPB1.TOP），以保护他们（实际上就是），以保护他们（实际上就是），以保护他们（实际

76、上就是），以保护他们（实际上就是 Q Q 的的的的数据区）不被破坏数据区）不被破坏数据区）不被破坏数据区）不被破坏 。（具体解释见后面的图示）。（具体解释见后面的图示）。（具体解释见后面的图示）。（具体解释见后面的图示）654 4，JSR Z /* JSR Z /* 间接转子，进入间接转子，进入间接转子，进入间接转子，进入 thunkthunk */ */1 1，2 X := 2 X := 返回地址；返回地址；返回地址；返回地址；进入进入 thunk 后的执行后的执行2 2，3 X := B.TOP ( 3 X := B.TOP ( thunkthunk 所在的所在的所在的所在的 B )B )

77、；3 3，B.TOP := X +3 B.TOP := X +3 ； /* /*指向现行栈顶的最高位置指向现行栈顶的最高位置指向现行栈顶的最高位置指向现行栈顶的最高位置 * */ /4 4，进行，进行，进行，进行 thunkthunk 的工作；的工作；的工作；的工作；5 5，X := B.TOP - 3 X := B.TOP - 3 ； 6 6，SP := 1 X SP := 1 X ； /* /* 恢复恢复恢复恢复 SP*/SP*/7 7，B.TOP := 3 X B.TOP := 3 X ； /* /* 恢复恢复恢复恢复 B.TOP */B.TOP */8 8，X := 2 X X :=

78、2 X ； 9 9，UJ 0 X UJ 0 X ； /* /* 返回返回返回返回 Q */Q */在栈顶在栈顶在栈顶在栈顶之上的之上的之上的之上的动作动作动作动作具体的动作具体的动作 （Z 中含有中含有thunk 的入口地址）的入口地址）1 1，X := B1.TOP; /* X := B1.TOP; /* 现行栈顶地址送变址器现行栈顶地址送变址器现行栈顶地址送变址器现行栈顶地址送变址器 X */X */2 2，1 X := SP; /* 1 X := SP; /* 保护保护保护保护 SP */SP */3 3，SP := 1 SP /* SP := 1 SP /* 把把把把 SP SP 变成

79、指向调用段变成指向调用段变成指向调用段变成指向调用段 P P 的活动纪录的活动纪录的活动纪录的活动纪录 * */ /在栈顶之上的动作在栈顶之上的动作在栈顶之上的动作在栈顶之上的动作栈的活动情况栈的活动情况栈的活动情况栈的活动情况B1.TOPB1.TOPSPSPP PQ.TOPQ.TOPSP=SPSP=SPQQSP=SPSP=SPP P. .P.TOPP.TOP返回地址返回地址返回地址返回地址B.TOPB.TOPX XSPSPQQB.TOPB.TOPX := X := 返回地址返回地址返回地址返回地址解释一下：解释一下：解释一下：解释一下：现行现行现行现行 SP SP 是是是是 Q Q 的的的的

80、 SP = SPSP = SPQ, Q, SPSPQQ + 1 + 1 中的内容中的内容中的内容中的内容 1 SP1 SPQQ 是是是是 P P的活动记录地址（老的活动记录地址（老的活动记录地址（老的活动记录地址（老 SPSP），把它送），把它送），把它送），把它送 SP, SP, 得到得到得到得到SPSPP P66参考文献参考文献参考文献参考文献1 1，Kenneth Kenneth C.LoudenC.Louden, ,冯博琴译，冯博琴译，编译原理与实践编译原理与实践，机械工业，机械工业出版社，出版社，P267-P296;P267-P296;2,2,严尉敏，严尉敏，数据结构与算法数据结构与

81、算法，清华大学出版社，动态存储管理，清华大学出版社，动态存储管理 部分。部分。3 3，RandellRandell 和和 Russell1964Russell1964，Algol60Algol60基于栈的环境；基于栈的环境；4 4，Johnson Johnson 和和 Ritchie1981, C Ritchie1981, C 编译器活动记录组织和调用序列；编译器活动记录组织和调用序列；5 5，Fraser Fraser 和和 Hanson1995Hanson1995，编译时堆结构设计；，编译时堆结构设计；6 6，Wilson1992Wilson1992，Cohen1981Cohen1981，垃圾回收。，垃圾回收。