北京外国语大学《编译原理》课件-第5章 运行环境

第5章运行环境北京外国语大学《编译原理》第5章运行环境过程的动态特性运行时数据空间的组织栈式动态分配本章小结第5章运行环境5.1

过程的动态特性5.1.1过程与活动过程的每一次运行(或执行)被称为一次活动(activation)。活动是一个动态的概念，除了设计为永不停机的过程(如操作系统

等)，或者是因设计错误而出现死循环的过程之外，任何过程的

活动均有有限的生存期(life

time)。第5章运行环境定义5.1活动的生存期是指从进入活动的第一条指令执行到离开此活动前的最后一条指令执行的这段时间，其中包括调用其它过程时其它活动的生存期。活动之间存在两种调用关系：如果活动A调用活动B，从B中退出后又调用活动C，B和C是被顺序调用的活动，显然被顺序调用的活动的生存期是不交的；如果活动A调用活动B，而活动B又调用活动C，B和C是被嵌套调用的关系。特别需要指出的是，活动的嵌套与过程的嵌套是两个截然不同的概念。第5章运行环境过程的嵌套实际上是过程定义的嵌套，是指在一个过程的定义中包含另外一个过程的定义，这是一个静态的概念，仅从读源程序就可以确定过程之间的嵌套定义关系。而活动的嵌套实际上是活动调用的嵌套或者活动生存期的嵌套，是指当一个活动正在执行时，又调用了另外的活动，这是一个动态的概念，它们的嵌套关系是由确定活动执行轨迹的条件(例如参数等)动

态确定的。第5章运行环境顺序执行的程序的最大特征是程序的执行在时间上是顺序的和排他的。即一个程序的运行轨迹由若干个顺序或嵌套的活动组成，并且在程序执行的任一瞬间，有且仅有一个活动正在活动。假想时间是一支笔，则任何一个顺序程序的执行过程(控制流)是一个“一笔画”，于是顺序程序运行时的控制流满足以下两点：①控制流是连续的；②过程间的控制流可以用树来表示。第5章运行环境定义5.2用来描绘控制进入和离开活动方式的树结构被称为活动树，在活动树中：①每个结点代表过程的一个活动；②根代表主程序的活动；③结点a是结点b的父亲，当且仅当控制流从a的活动进入b的活动；④结点a处于结点b的左边，当且仅当a的生存期先于b的生存期第5章运行环境活动树的实质是它反映了顺序执行程序的调用和时序关系，它把每个活动的生存期缩小到了一点。也就是说，如果我们关心的仅是活动之间的控制流和它们的生存期，而不关心活动究竟执行了多少时间的话，活动树是最好的表示形式。第5章运行环境例5.1阶乘函数的计算可以用下述程序test实现，首先调用get_line(n)得到一个整型数值，然后调用递归函数f(n)计算出n的阶乘，最后将结果输出。令n=4，则程序运行时活动的轨迹如图5.1(a)所示。其中纵向是时间轴，横向反映控制流，即调用与返回关系。如果忽略活动执行的时间，仅考虑控制流的流向，即将图5.1(a)各活动执行时间均压缩为一个点，且将其旋转90o0，则演变成为如图5.1(b)所示的活动树。树的边是双向的，既表示调用又表示返回。第5章运行环境图5.1顺序执行的程序的控制流(a)活动的调用关系与生存期；(b)仅反映控制流的活动树第5章运行环境procedure

test

isn

:

integer;procedure

f(n:integer)

return

integer

isbeginif

i<2

then

return

1;

else

return

n*f(n-1);

end

iend

f;beginget_line(n);

n:=f(n);

put_line(n);end

test;第5章运行环境例5.2考虑例4.14的快排序过程。如果忽略partition中对

exchange的调用，则对于某个初始数据，sort的活动树可能如图5.2(a)所示。其中的s、r、q、p分别是sort、readarray、quicksorpartition的缩写。图5.2(a)反映了活动的嵌套，而图4.11(a)反映了程的嵌套。第5章运行环境图5.2活动树与控制栈第5章运行环境5.1.2控制栈与活动记录一个完整程序执行的控制流，恰好是对它的活动树的一次深度优先遍历。根据顺序执行程序的控制流特性，活动树上各节点之间具有下述关系：①同一层次的活动生存期不交；②任一时刻，处在生存期的活动构成一条从根到某节点的路径；③路径上各节点生存期是嵌套的(后进先出)。第5章运行环境换句话说，任何时刻仅需要为所有处在生存期的活动提供它

们的活动场所，称为运行环境。根据上述的②和③，很显然，运行环境的最佳数据结构应该是一个栈，称为控制栈。而栈上的每个节点是每个活动的运行环境，称为活动记录(activation

record)。每个活动开始时，就为它分配一个活动记录，即将此活动记录分配在栈顶上。活动的整个生命期中活动记录一直存在，而当活动结束时，将它从当前栈顶取消。控制栈的栈顶一般由top指示，为了提高效率，top一般放在寄存器中。第5章运行环境活动记录中至少应该存放两类信息：①控制信息：用于控制活动的正确调用与返回和用于控制活动记录的正确切换；②访问信息：用于为当前活动提供对数据，如本地数据和非本地数据的访问。第5章运行环境例5.3图5.2(b)给出了快排序程序运行时的某个状态，从s开始，实线条所链接的活动构成了活动树上的一条路径，也是控制栈的一个状态，在当前状态下，栈中共有4个节点，分别是s、q(1,9)、q(1,3)、q(1,0)。这些活动均处在它们的生存期，但是只有栈顶的q(1,0)是正在活动的活动。第5章运行环境5.1.3名字的绑定定义5.3运行时为名字X分配存储空间S，这一过程称为绑定(binding)。绑定是名字X与存储空间S的结合。此处，名字X是一个对象，它既可以是数据对象，如变量，与之结合的是一个存储单元，也可以是操作对象，如过程，与之结合的是一段可执行的代码。本章的讨论仅限于X是一个数据对象。第5章运行环境现在有两个关于名字的问题：名字的声明与名字的绑定。它们都需要有对应的存储空间，而存储空间的对应方式，一个是静态的，一个是动态的。声明时我们关心的是声明的作用域，即当一个名字被引用时，在不同的作用域中与该名字的不同声明结合；绑定时我们关心的是绑定的生存期，即当一个名字在运行时被实际分配的存储单元，名字与存储单元结合的这段时间被称为绑定的生存期，显

然这个生存期应该和名字的生存期是一致的。表5.1静态与动态第5章运行环境在名字绑定的概念下，对一个变量的赋值，实际上是通过两步映射来实现的。源程序中的一个名字，需要经过名字的绑定将名字映射到一个实际的存储空间，然后经过赋值将此存储空间映射到一个实际的值。名字到存储空间的映射被称为“环境”，存

储空间到值的映射被称为“状态”。由于存储空间对应的是左值，而值对应的是右值，因此我们也可以说，环境将名字映射到左值，状态将左值映射到右值，或者说环境改变存储空间，状态改变值。同样，在名字绑定的概念下，对一个常量的赋值实质上就是直接将名字与一个具体的值绑定，或者说环境将名字映射到右值，或者说环境直接改变值。变量与常量的映射关系分别如图5.3(a)、(b)所示。由于表示常量的名字没有左值，因此，常量是不能通过赋值句被改变的。第5章运行环境例5.4对于赋值句x:=3.14，首先为x分配一个存储单元S，然后将3.14赋值给S。对于常量声明const

pi=3.14，直接将pi与3.14绑定，于是在程序运行的任何时刻，pi的值不能被改变。它们的映射关系分别如图5.3(c)、(d)所示。第5章运行环境图5.3变量与常量名字的映射(a)变量名字的映射；(b)常量名字的映射；(c)x:=3.14的映射；(d)pi=3.14的映射第5章运行环境在允许过程递归的情况下，当一个活动还没有执行完成时，可能又会进入同一过程的另一个活动。为了同时保存两个同一过程活动的运行环境，同一作用域中的一个名字在运行时可能会被分配多个存储空间，也就是说，同一作用域中的一个名字可以同时绑定到多个存储单元。例如图5.2(b)中同一个快排序过程的三个活动的活动记录q(1,9)、q(1,3)和q(1,0)均被放在控制栈中，相同参数在三个活动记录中有不同的存储空间用于存放不同的值，从而使得在快排序的递归调用中，能够通过实在参数的值进行正确的排序操作。因此，环境是一个一对多的映射。同样，由于一个存储单元可以存放不同的值，状态也是一个一对多的映射。第5章运行环境编译器怎样对存储空间进行组织和采用什么样的存储分配策略，很大程度上取决于程序设计语言中所采用的机制，如过程能否递归、过程能否嵌套、过程调用时参数如何传递、哪些实体可以作为参数和返回值、是否允许动态的为对象分配和撤销存储空间、存储空间是否必须显式地释放，等等。第5章运行环境5.2

运行时数据空间的组织5.2.1运行时内存的划分与数据空间的存储分配策略程序运行时，内存用来保存可执行代码和代码所操作的数据。可执行代码的大小在编译时可以静态确定，因此可以把它放在静

态数据区。而对于数据，可以有三种存储方式，对应三种组织形

式的数据区，它们分别是静态数据区、栈和堆。静态数据区用于

存放一对一的绑定且编译时就可确定存储空间大小的数据；栈用

于存放一对多的绑定且与活动同生存期的数据；堆用于存放与活

动生存期不一致且可以动态生成和撤消的数据，典型的如PASCAL

中new(p)和dispose(p)等。栈与堆的典型安排如图5.4所示，它们的增长空间是共享的。第5章运行环境图5.4内存空间划分第5章运行环境三种数据区对应着下述三种不同的分配策略，编译器具体实现时，根据语言机制的特性，可以采用三种方式的其中若干种。①静态分配策略：编译时安排所有数据对象的存储；②栈分配策略：按栈的方式管理运行时的存储；③堆分配策略：在运行时根据要求从堆数据区动态地分配和释放存储。第5章运行环境5.2.2静态与动态分配简介1．静态分配策略在静态分配中，名字在程序编译时与存储空间结合，运行时

不再改变，每次过程活动时，过程中的名字映射到同一存储单元。这种性质允许局部名字的值在活动停止后仍能保持，即当控制再次进入活动时，变量的值和控制上一次离开时相同。第5章运行环境采用静态分配策略的存储空间可以组织如下，编译器为每个模块分配一块连续的存储空间，根据模块中名字的类型确定它所需空间的大小。为了称呼上的统一，我们称每个模块的数据区为活动记录。由于每个活动记录的大小均是确定的，所以若干活动记录组成的连续存储空间的大小也是确定的。这一确定的空间在程序运行时一并装入内存，而不管各活动记录是否在某次特定的运行中被使用，程序运行时不再有对存储空间的分配。第5章运行环境静态数据区中变量的地址可以有两种表示方法。以图5.5中变

量X的地址Δx为例，它可以相对base寻址，也可以相对base

2寻址。事实上，由于数据的静态特性，所有的base

i相对于base的偏移量均是编译时可以确定的常量，因此两种表示方法没有实质性区别。但是，相对于base

i寻址的方法，可以将静态存储分配与栈式存储分配的方法统一起来，同时也有利于将各活动记录中的共享数据

提取出来进行统一处理。第5章运行环境图5.5静态存储分配第5章运行环境静态分配的特点，使得它所适用的程序设计语言在某些方面受到限制：①数据对象的大小和它在内存中位置的限制必须在编译时确定，如数组的大小不能是动态的；②不允许程序递归，因为一个过程的所有活动使用同样的名字绑定，即绑定是一对一的；③不允许动态生成数据，因为没有运行时的存储分配机制。第5章运行环境FORTRAN语言可以完全采用静态存储分配策略，因为FORTRAN满足上述限制。但是，FORTRAN中的等价片与公用区机制，使得分配比较复杂。允许分别编译的程序设计语言，分别编译模块中的数据定义模块(特别是全程引用的数据)，也可以采用静态分配策略，因为它们一般在整个程序运行的期间是被共享的。第5章运行环境2．栈分配策略栈分配策略是一种动态分配的策略，它的基础是活动的控制栈，所有与活动同生存期的数据均可以采用栈分配策略。当活动处在生存期时，相应的数据被分配，生存期结束后，数据被撤销。对于这样的数据，他们的分配与撤销实际上就是控制栈上活动记录的分配与撤销。活动记录被分配在栈数据区中，栈顶由统一的栈顶指针top指示。活动记录的大小如果是L，则活动开始时(确切讲应是开始前)，top增加L，活动结束后，top减少L。第5章运行环境对于静态分配策略分配的数据，栈分配策略均可进行分配。因为静态分配数据的特征是编译时可以确定大小，所以栈分配策略可以把这些静态可确定的数据在编译时就安排在栈的底部。而对于静态存储分配无法处理的递归程序调用问题和动态数组问题，均可以采用栈分配的策略来解决，因为递归调用的活动的活动记录的分配和撤销，可以在程序运行时(活动活动时)动态地添加到栈顶，或是从栈顶撤销；动态数组的存储空间大小，也可以根据保存在活动记录中的内情向量信息计算出来，然后动态地添加在当前的栈顶。第5章运行环境虽然栈分配策略是可以进行动态分配的，但是由于可以进行栈分配的数据必须与活动同生存期，所以它对程序设计语言的下述要求也无法满足：①当活动停止时，局部活动中名字的值必须保持(否则会出现悬空引用)；②在程序运行的任意时刻，可以随时生成或撤销的动态数据；③被调用者的活动比调用者的活得更长，此时，活动树不能正确描绘过程间的控制流。第5章运行环境3．堆分配策略堆分配策略是三种分配策略中最灵活的一种，它对程序设计语言几乎不做什么限制，可以采用静态分配策略或栈分配策略进行分配的数据，均可采用堆分配策略。同时，对于栈分配策略不能分配的数据，堆分配策略也可以进行分配。堆分配策略采用一个双向链表的结构，将所有可以被分配的自由空间链接在链表中，链表中的每个节点指示一个连续可用空间的信息，典型的如可用空间的起始和结束地址。节点的顺序应与可用空间的地址先后一致。第5章运行环境堆分配的思想并不复杂，当需要空间时，就在链表的节点中找到一块大小合适的区域，将区域中的部分或全部分给需要空间的对象，并将已分配的空间从链表的节点信息中删除，根据是全部还是部分分配，将节点从链中摘除或者修改节点可用空间信息。当空间需要释放时，首先在链表中进行查找，看是否释放的空间与某个(或某两个连续的)节点中的可用空间相邻：若与一个相邻，则修改当前链表中的节点可用信息；若与两个相连，则合并两个节点为一个节点，且修改节点中的可用空间信息；若不与任何可用空间相邻，则在链表的适当位置加入一个新的节点。第5章运行环境一开始，链表中仅有一个节点，它提供的是一个连续的可用空间的全部。随着程序的运行，各活动和动态分配的数据不断地从可用空间中获取存储空间，或者将释放的空间放回可用空间。经过一段时间之后，堆中可能包含交错出现的正在使用和已经释放的区域，使得到一定的时候，堆分配的可用存储空间变成若干个不连续的可用空间(如图5.6(a)、(b)所示)。如果存储空间的分配与撤销算法设计不合理，就会造成程序运行到一定的时刻，所有

可用的存储空间被分割成许许多多不连续的碎片，使得无法再进

行分配。因此堆分配的空间分配与撤销算法的核心思想之一，就

是使可用存储空间尽可能地保持连续。当然，算法的效率也是需

要考虑的问题之一。第5章运行环境图5.6堆分配(a)堆分配的存储空间；(b)堆分配的可用存储空间链第5章运行环境5.3

栈式动态分配5.3.1控制栈中的活动记录前边已经提到，控制栈中的活动记录的作用是为当前的活动提供运行环境，因此它既需要提供活动所操作的数据对象的存储空间，也需要提供适当的信息，以保证活动调用与返回时实现代码的正确转移和活动记录的正确切换，即活动记录中需要保存两类信息：控制信息与访问信息。活动记录的具体内容可如下：第5章运行环境图5.7活动记录的内容第5章运行环境①参数与返回地址：用于存放实参和返回地址，如果是函数，还应有返回值；②控制链：指向调用者活动记录的指针，用于当调用返回时，将当前栈顶正确切换到调用者的活动记录；如果是静态分配，该

项可以没有；③访问链：用于指示访问非本地数据；当过程不允许嵌套时，该项也可以没有；第5章运行环境④调用时需要保存的机器状态。如程序计数器，寄存器等，对于某特定的计算机，这些被保存信息是固定的；⑤过程内部声明的数据，如VAR

X，Y

:INTEGER等；⑥临时变量：源程序中不出现的、由编译器产生的变量，如表达式x+y+z计值时产生的T1，T2，…；指示当前活动记录的一般有两个指针，一个是当前的栈顶指针top，另一个是用于数据访问的sp。活动记录中的所有数据，均可以是相对于sp的偏移量。通常，top和sp分别放在两个寄存器中，并且让sp作为活动记录的代表。第5章运行环境例5.5回顾图5.2(b)控制栈的一个状态，当前栈中有4个活

动记录s、q(1,9)、q(1,3)、q(1,0)。从活动s开始，控制栈中的活动记录需要根据控制流的转变，经过一系列的变化，才能到达当前的状态。活动s刚开始时，栈中仅有s的活动记录。当s调用r之后，栈顶加入了r的活动记录。当控制从r退出，又进入q(1,9)时，首先需要在退出r时将r的活动记录从栈顶弹出，然后再将q(1,9)的活动记录压进栈。图5.8给出了控制流与控制栈的部分变化过程。第5章运行环境图5.8控制流与活动记录第5章运行环境5.3.2调用序列与返回序列实现控制流正确转移和活动记录正确切换的方法，是在过程发生调用和返回处加入适当的可执行代码：调用处加入的代码被称为调用序列(call

sequence)，返回处加入的代码称为返回序列(return

sequence)。以图5.9所示的源程序中过程A调用过程B为例，调用前的栈顶是A的活动记录，top(A)指向当前栈顶，A代码段中的变量i相对于sp(A)寻址(如：Δi[sp]:=Δi[sp]+1)。调用发生时，调用序列将B的活动记录加入到栈顶，使得栈顶指针改变为top(B)，而B中的变量j相对于sp(B)寻址(如：Δj[sp]:=Δj[sp]+1)。B运行结束返回时将当前栈顶的活动记录弹出，又恢复到调用前的top(A)和sp(A)。第5章运行环境图5.9过程的调用与返回第5章运行环境这一系列的控制流转移和栈顶活动记录的切换，由调用序列和返回序列来完成。一般来讲，调用序列和返回序列的内容既可以放在调用者中，也可以放在被调用者中。经验认为，能

让被调用者做的事情尽量不要让调用者做，因为在被调用者中只需要一个序列，而在调用者中每调用一次就需要一个序列。表5.2是一个可能的调用序列与返回序列的安排，其中图5.9的①和②形成调用序列，③和④形成返回序列。第5章运行环境表5.2调用序列与返回序列第5章运行环境5.3.3栈式分配中对非本地名字的访问如果过程不允许嵌套定义，则过程中只可能访问局部于过程的本地数据和全局的静态数据。全局数据可以放在静态数据区中(或者栈底)，而本地数据均可以放在过程的活动记录中，且相对于活动记录的sp寻址。如果过程允许嵌套定义，则过程中会访问到一些定义在其它过程中的数据，这些数据既不是本地数据，又不是全局数据。第5章运行环境对允许嵌套定义过程的语言进行栈式分配，需要考虑两个关键问题：①名字在不同的作用域内表示不同的数据对象；②如何通过当前的活动记录，访问非本地数据。第一个问题由名字的作用域规则解决(静态作用域＋最近嵌套)第二个问题通过引入访问链的方法解决。第5章运行环境1．访问链①它本身所在的位置可以作为本活动记录中数据寻址的基础，即活动记录的sp。②访问链的内容指向它直接外层过程的最新活动记录的访问链，即最新直接外层活动记录的sp。如果当前栈顶活动记录的过程p的

嵌套深度为np,则沿当前sp间接访问一次(习惯上称沿访问链追踪一次)，sp所到达活动记录的嵌套深度减1。沿访问链进行若干次追踪，则可到达任何嵌套深度小于np过程的活动记录。这实际上等价于可以沿访问链找到所有p的外层最新活动记录的sp，通过这些sp就可以访问任何p的非本地数据。第5章运行环境2．利用访问链访问非本地数据假定过程p的嵌套深度是np，在过程p中引用一个嵌套深度为na，且na≤np的变量a。设p和a的层次之差为x，即na+x=np，于是x=np-na。则a的存储可以按如下方法找到：①当控制在p中，p的一个活动记录肯定在栈顶。从栈顶的活动记录中追踪访问链np-na次。np-na

的值是静态作用域规则决定的，可以在编译时通过计算得到；第5章运行环境②追踪访问链np-na次后，找到a的声明所在过程的活动记录的访问链sp(a)。因此，过程p中变量a的地址计算需要两个信息：层次差np-na和偏移量Δa，它们均可以在编译时计算得到，因此可以将有序对：(np-na，Δa)(5.1)存放在符号表a的条目中，这些信息用于生成存取变量a的代码。第5章运行环境3．如何在调用序列中生成访问链建立访问链的代码是过程调用序列的一部分。假定嵌套深度是np的过程p调用嵌套深度为nx的过程x，则建立访问链分下边两种情况：①np＜nx的情况：因为被调用过程x比p嵌套得更深，根据作

用域规则，x肯定直接声明在p中。例如sort调用quicksort，quicksort调用partition等。此时，被调用过程x的访问链必须指向栈中刚好在它下面的调用过程p活动记录的访问链。第5章运行环境②np≥nx的情况：根据作用域规则，p和x具有公共外层，即静态包围p和x且嵌套深度为1，2，…，nx-1的过程。例如quicksort调用本身，partition调用exchange等。从调用过程追踪访问链np-

(nx+1)=np-nx+1次，到达静态包围x和p的最接近过程的最新活动记录。所到达的访问链就是被调用过程x必须指向的访问链。同样，np-nx+1

(5.2)可以在编译时计算。事实上，两种情况均可用统一的公式(5.2)计算，因为对于第一种情况，np-nx=-1，所以np-nx+1=0，即直接将当前的访问链地址填写进被调用者的访问链中，而无需追踪访问链。第5章运行环境例5.6再考察例4.14的快排序过程。假设当前控制栈的状态是：

s、q(1,9)、q(1,3)、p(1,3)、e(1,3)，其中，ns=1，nq=2，np=3，

ne=2，则从s开始，每个活动记录和访问链的建立过程如图5.10所示。图中简化的活动记录中cl和al分别表示控制链和访问链。左边的控制链反映了动态的调用关系(活动的嵌套)，右边的访问链反映了静态的嵌套关系(过程嵌套)。下述是部分访问链建立和利用访问链访问非本地数据的过程。①s调用q(1，9)时访问链的建立：当前控制栈如图5.10(a)所示根据公式(5.2)，ns–nq+1=1–2+1=0，直接令q(1，9)的访问链指向的访问链地址，形成图5.10(b)所示的访问链；第5章运行环境②p(1,3)调用e(1,3)时访问链的建立：当前控制栈如图5.10(d)所示，n–n

+1=3–2+1=2，从p(1,3)追踪访问链两次，到达s的访问链p

e于是形成图5.10(e)所示的访问链；③e(1,3)中访问变量x：根据有序对(5.1)的计算公式，追踪访问链n–n

=2–1=1次，到达s的访问链，利用此访问链对x进行寻址；e

x④p(1,3)中访问数组a：追踪访问链n–n

=3–1=2次，也同样到p

a达s的访问链，利用此访问链对a进行寻址。第5章运行环境图5.10活动记录中的控制链与访问链第5章运行环境4．利用显示表(display)快速访问非本地数据考察访问链的特点不难看出，对于任何一个深度为i的活动来

说，它可能访问的本地与非本地数据只能是嵌套深度不大于i的、

最新被调用的活动。例如在图5.10(d)中，当前的活动p(1,3)的嵌套深度是3，它除了可以访问本地的i和j之外，还可以沿访问链访问嵌套深度为2的最新活动q(1,3)中的k和v，以及嵌套深度为1的最

新活动s中的a和x。虽然栈中嵌套深度为2的活动有两个，但是在p(1,3)中可以访问的是最新的活动q(1,3)，而不是q(1,9)。换句话说在嵌套层次小于等于当前活动嵌套层次的活动中，每层仅有一个活动中的数据可以被当前的活动访问到。第5章运行环境为了加快对非本地数据的访问，我们可以考虑把访问链组织成一个栈，称为显示表(display)。显示表中的d[i]，存放的是嵌套深度为i的最新活动记录的访问链地址。因此，一个活动记录处在栈顶且深度为i的活动，可以通过显示表的内容直接访问任何一个它外层的非本地数据，而无需再沿访问链进行若干次追踪。假定过程p的嵌套深度是np，它引用一个嵌套深度为na(na≤np)的变量a，则a的活动记录的访问链地址可以在d[na]中找到，于是过程p中变量a的地址信息的有序对(5.1)可以简化为下述的(5.3)，它同样可以在编译时确定，并存放在符号表中。(na，Δa)(5.3)第5章运行环境5．生成与维护显示表在沿访问链追踪的访问模式中，访问链只需建立，无需撤销，因为活动记录的撤销自然也撤销了访问链。如果采用显示表方式，则当进入和退出活动时，均需对显示表进行维护。维护的方法是利用活动记录中的访问链。与前述访问链的方法不同，在显示表方案中，活动记录中的访问链已不是指向直接外层的最新活动记录，而是指向同层次的次新活动记录。第5章运行环境维护的过程被分别加入在对应的调用和返回序列中。一开始，显示表的初值被置为0，表示不指向任何活动记录的访问链。当一个嵌套深度为i的活动被调用时，调用序列在为它建立新的活动记录时，也对显示表进行如下修改：①将d[i]的值保存在新活动记录的访问链中，并且②置d[i]指向新的活动记录(置d[i]内容为新活动记录访问链地址)。当活动结束时，返回序列中恢复d[i]原来的值，即执行上述①的逆操作。第5章运行环境6．显示表的存储分配由于顺序执行程序的排他性特点，程序运行到任何一个时刻，只需一个显示表副本。为了提高访问速度，可以用一组寄存器来作为显示表的存储空间，寄存器的个数(即显示表的容量)就是程序设计语言允许过程嵌套的层次数。原理上，程序嵌套的深度是不应受到限制的，而寄存器资源是十分宝贵的，因此，也可以设立一块静态存储区作为显示表，在栈分配中，它可以被放在栈底。显示表的另外一种存储分配是，给显示表多个副本。栈顶每生成一个新的活动记录时，从旧栈顶的活动记录中复制两个活动的公共外层的显示表部分，而把当前活动记录的访问链地址作为显示表中的最新元素。第5章运行环境例5.7将图5.10中访问链改为显示表方案，则显示表建立的过程如图5.11(a)~(f)所示。读者可以根据上述方法，在活动返回的序列中将显示表和控制栈的内容从图5.11(f)恢复到图5.11(a)。第5章运行环境图5.11显示表的维护第5章运行环境5.3.4参数传递的实现根据上一章的分析，我们知道参数传递的主要区别在于传递的是左值还是右值，而且无论是哪种情况，均可按下述原则处理：①过程定义时形参被当作局部名看待，即在活动记录中为参数分配存储单元；②将调用时实参的左值或者右值放入形参单元；③根据传递的是左值还是右值确定过程中对形参单元的数据是间接访问还是直接访问。第5章运行环境此处我们仅考虑最简单的情况，即参数是简单变量，且传递的是右值(值调用)。对于4.9节中的过程调用call

sum(X+Y，Z)，当时生成了如下的中间代码：(k–3)

param

T(k–2)

param

Z(k–1)

call

2,

sum设sum的声明为：proc

sum(a,b:int)，则可具体处理如下。第5章运行环境1．设计含有参数存储单元的活动记录设计一个简化的活动记录，如图5.12(a)所示，其中访问链和控制链存放在连续的两个单元中，sp指向访问链的存储单元。当所处理的语言不需要访问链时，sp直接指向控制链。如果有n个参

数，则相对sp寻址的前n+1个单元分配给参数，从第n+2个单元开始分配给过程中声明的变量，最后是代码生成时引进的临时变量。对于一段完整的过程来讲，所有这些内容在编译时均是可以确定的，因此，过程活动记录的长度L是可确定的。这实际上给栈式

分配带来很大的方便：为新的活动记录分配存储空间就是将旧的top加上L形成新的栈顶。第5章运行环境图5.12活动记录与内容的填写(a)简化的活动记录；(b)参数传递；(c)调用前后活动记录的变化第5章运行环境2．调用序列中将实参的值放入对应的存储单元参数传递的过程在调用者的调用序列中实现，将call

2,sum扩充为一个调用序列，其中的参数传递代码可以如下，从而得到图5.12(b)所示的sum活动记录的参数的内容。(k–3)

param

T(k–2)

param

Z(k–1)

4[top]

:=

2(k)

5[top]

:=

–