编译原理第五章运行环境

《编译原理第五章运行环境》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章运行环境源程序最终需要运行。因此需了解：与源程序等价的目标程序如何在内存中存放，为了程序的正确运行需要什么样的支持。不同的源语言结构，所需的运行环境和支持不同。本章仅以最简单的、基于过程的、顺序执行的程序为前提讨论，即源程序的基本结构是顺序执行的过程，过程与过程之间仅通过子程序调用的方式进行控制流的转移。讨论内容：静态的过程运行时具有什么样的动态特性；运行时需要什么样的环境支持（存储空间分配）；过程之间的调用与返回应如何实现等。15.1过程的动态特性5.1.1过程与活动<1>过程、活动、生存期过程（函数）的每一次运行称为一次活动（activation）。活动是

2、一个动态的概念，它有有限的生存期（lifetime）。定义5.1活动的生存期是指从进入活动的第一条指令开始执行到离开此活动前的最后一条指令执行结束的这段时间，其中包括调用其它过程时其它活动的生存期。■25.1.1过程与活动（续1）<2>活动之间的通信子程序调用：call/return，特点是有去必有回顺序调用：生存期不交嵌套调用：生存期嵌套，关系由活动执行轨迹的条件（例如参数等）动态确定容易混淆的概念：过程的并行定义和嵌套定义（作用域不交和嵌套）消息传递：send/receive，特点是可以有去无回。35.1.1过程与活动（续2）特点：程序的执行在时间上是顺序的和排

3、他的。即在程序执行的任一瞬间，有且仅有一个活动正在活动。假想时间是一支笔，则任何一个顺序执行程序的执行过程（控制流）是一个“一笔画”。控制流满足：①控制流是连续的；②过程间的控制流可以用树来表示。<3>顺序执行程序的控制流45.1.1过程与活动（续3）<4>活动树定义5.2描绘控制进入和离开活动方式的树结构被称为活动树，它具有下述性质：每个结点代表过程的一个活动；根代表主程序的活动；结点a是b的父亲，当且仅当控制流从a的活动进入b的活动；结点a处于b的左边，当且仅当a的生存期先于b的生存期。■通俗讲：结点a是b的父亲：a调用b结点a处于b的左边：先调用a后调用b55

4、.1.1过程与活动（续4）例5.1考虑快排序过程：programsort(input,output);procedurereadarray;functionpartition(y,z:integer):integer;procedurequicksort(m,n:integer);考虑sort的执行：时间缩为一个点，且翻转：i:=partition(y,z)的结果:65.1.1过程与活动（续5）活动树的实质是反映了顺序执行程序的调用和时序关系，它把每个活动的生存期缩小到了一点。例5.1快排序程序的一次执行的活动树：其中：s－sortr－readarrayq－quic

5、ksortp－partition30105208仅关心活动是否可正确执行，不关心活动执行了多长时间75.1.2控制栈与活动记录控制流与活动树的关系<1>程序控制流：对应活动树从根开始的一次深度优先遍历。<2>活动树上各节点之间具有下述关系：同一层次的活动生存期不交；任一时刻，处在生存期的活动构成一条从根到某节点的路径；路径上各节点生存期是嵌套的（后进先出）。8控制流与活动树的关系（续）<3>控制栈与活动记录控制栈：保存所有在生存期的活动(一条后进先出的路径)活动记录(activationrecord)：栈中的每个元素称为一个活动记录，为活动提供的活动场所。活动记录中

6、至少应该存放两类信息：控制信息：控制活动的正确调用与返回和控制活动记录的正确切换；访问信息：用于为当前活动提供对数据，如本地数据和非本地数据的访问。95.1.2控制栈与活动记录（续1）例5.2快排序程序运行时某状态的控制栈：控制栈中保存了任何时刻所有在生存期活动的活动记录105.1.3名字的绑定<1>名字的绑定定义5.3运行时为名字X分配存储空间S，这一过程称为绑定（binding）。■换句话说，绑定是名字X与存储空间S的结合。X是一个对象：既可以是数据对象，如变量，与之结合的是一个存储单元；也可以是操作对象，如过程，与之结合的是可执行的代码。我们的讨论仅限于X是一

7、个数据对象。115.1.3名字的绑定（续1）名字的声明与名字的绑定均需要有对应的存储空间，而存储空间的对应方式，一个是静态的，一个是动态的。声明时关心的是声明的作用域，即当一个名字被引用时，在不同的作用域中与该名字的不同声明结合；名字和作用域是静态的一对一关系。绑定时关心的是绑定的生存期，即当一个名字在运行时被实际分配的存储单元，名字与存储单元结合的这段时间被称为绑定的生存期，显然此生存期应该和名字的生存期一致。运行时名字与存储单元的结合可以是一对多的关系。静态动态过程的定义过程的活动名字的声明名字的绑定声明的作用域绑定的生存期符号表活动记录<2>静态与动态12