编译原理基础(刘坚)第5章.ppt

《编译原理基础(刘坚)第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章运行环境5.1过程的动态特性5.2运行时数据空间的组织5.3栈式动态分配5.4本章小结5.1过程的动态特性5.1.1过程与活动过程的每一次运行(或执行)被称为一次活动(activation)。活动是一个动态的概念，除了设计为永不停机的过程(如操作系统等)，或者是因设计错误而出现死循环的过程之外，任何过程的活动均有有限的生存期(lifetime)。定义5.1活动的生存期是指从进入活动的第一条指令执行到离开此活动前的最后一条指令执行的这段时间，其中包括调用其它过程时其它活动的生存期。活动之间存在两种调用关

2、系：如果活动A调用活动B，从B中退出后又调用活动C，B和C是被顺序调用的活动，显然被顺序调用的活动的生存期是不交的；如果活动A调用活动B，而活动B又调用活动C，B和C是被嵌套调用的关系。特别需要指出的是，活动的嵌套与过程的嵌套是两个截然不同的概念。过程的嵌套实际上是过程定义的嵌套，是指在一个过程的定义中包含另外一个过程的定义，这是一个静态的概念，仅从读源程序就可以确定过程之间的嵌套定义关系。而活动的嵌套实际上是活动调用的嵌套或者活动生存期的嵌套，是指当一个活动正在执行时，又调用了另外的活动，这是一个动态的概

3、念，它们的嵌套关系是由确定活动执行轨迹的条件(例如参数等)动态确定的。顺序执行的程序的最大特征是程序的执行在时间上是顺序的和排他的。即一个程序的运行轨迹由若干个顺序或嵌套的活动组成，并且在程序执行的任一瞬间，有且仅有一个活动正在活动。假想时间是一支笔，则任何一个顺序程序的执行过程(控制流)是一个“一笔画”，于是顺序程序运行时的控制流满足以下两点：①控制流是连续的；②过程间的控制流可以用树来表示。定义5.2用来描绘控制进入和离开活动方式的树结构被称为活动树，在活动树中：①每个结点代表过程的一个活动；②根代表主

4、程序的活动；③结点a是结点b的父亲，当且仅当控制流从a的活动进入b的活动；④结点a处于结点b的左边，当且仅当a的生存期先于b的生存期。活动树的实质是它反映了顺序执行程序的调用和时序关系，它把每个活动的生存期缩小到了一点。也就是说，如果我们关心的仅是活动之间的控制流和它们的生存期，而不关心活动究竟执行了多少时间的话，活动树是最好的表示形式。例5.1阶乘函数的计算可以用下述程序test实现，首先调用get_line(n)得到一个整型数值，然后调用递归函数f(n)计算出n的阶乘，最后将结果输出。令n=4，则程序运

5、行时活动的轨迹如图5.1(a)所示。其中纵向是时间轴，横向反映控制流，即调用与返回关系。如果忽略活动执行的时间，仅考虑控制流的流向，即将图5.1(a)各活动执行时间均压缩为一个点，且将其旋转90o0，则演变成为如图5.1(b)所示的活动树。树的边是双向的，既表示调用又表示返回。图5.1顺序执行的程序的控制流(a)活动的调用关系与生存期；(b)仅反映控制流的活动树proceduretestisn:integer;proceduref(n:integer)returnintegerisbeginifi<2the

6、nreturn1;elsereturnn*f(n-1);endif;endf;beginget_line(n);n:=f(n);put_line(n);endtest;例5.2考虑例4.14的快排序过程。如果忽略partition中对exchange的调用，则对于某个初始数据，sort的活动树可能如图5.2(a)所示。其中的s、r、q、p分别是sort、readarray、quicksort和partition的缩写。图5.2(a)反映了活动的嵌套，而图4.11(a)反映了过程的嵌套。图5.2活动树与控制栈

7、5.1.2控制栈与活动记录一个完整程序执行的控制流，恰好是对它的活动树的一次深度优先遍历。根据顺序执行程序的控制流特性，活动树上各节点之间具有下述关系：①同一层次的活动生存期不交；②任一时刻，处在生存期的活动构成一条从根到某节点的路径；③路径上各节点生存期是嵌套的(后进先出)。换句话说，任何时刻仅需要为所有处在生存期的活动提供它们的活动场所，称为运行环境。根据上述的②和③，很显然，运行环境的最佳数据结构应该是一个栈，称为控制栈。而栈上的每个节点是每个活动的运行环境，称为活动记录(activationreco

8、rd)。每个活动开始时，就为它分配一个活动记录，即将此活动记录分配在栈顶上。活动的整个生命期中活动记录一直存在，而当活动结束时，将它从当前栈顶取消。控制栈的栈顶一般由top指示，为了提高效率，top一般放在寄存器中。活动记录中至少应该存放两类信息：①控制信息：用于控制活动的正确调用与返回和用于控制活动记录的正确切换；②访问信息：用于为当前活动提供对数据，如本地数据和非本地数据的访问。例5.3图5.2(b)给出了快