《哈工大编译原理》由会员分享，可在线阅读，更多相关《哈工大编译原理（91页珍藏版）》请在金锄头文库上搜索。
1、第七章 运行时刻环境1序7.1 源语言中的一些问题7.2 存储组织7.3 运行时刻存储分配策略7.4 非局部名字的访问7.5 符号表2序计算环境 运行时的环境计算 目标代码映射源程序源程序中的名字（常量，变量）目标机 存储空间。它受命于源程序的执行语义。源程序由一组过程按某种规则组成。过程的一次执行称作一次活动.3在过程的语句序列执行之前，过程中 访问的对象构成此过程的运行环境，由运 行支持程序组织好。 PROCEDURE sub(x,y:real);VAR i ,j:integer;a:ARRAY1.5 OF real;e, f : real;BEGINf :=e+i*j;END;4f符号表
2、名字 形 类型 偏移量活动记录布局=老SP (sp,0)x 形 real 3返回地址(sp,1)y 形 real 42(sp,2)(sp,3)(sp,5)i int 5i (sp,9) j int 9 j(sp,13)a array 13a(sp,53) ee real 53(sp,61)f real 61(sp,4)xyt1t2t3(sp,62)(sp,63)(sp,64)5中间代码* i j t1 * (sp ,20) (sp ,21) (sp ,29) + e t1 t2 + (sp ,27) (sp ,29) (sp ,30) itor t2 t3 itor (sp ,30) (sp
3、,31):= t3 f := (sp ,31) (sp ,28)确定活动记录中局部数据的地址：假设 sp标记一个活动记录的开始的位置， dx表 示x的地址相对于sp的偏移量。那么， x在 过程的目标代码中的地址可写成dx（sp）67.1 有关源程序中的一些问题目的： 构造运行程序的策略和方法 1.1 过程 1.2 活动树 1.3 控制栈 1.4 说明的作用域 1.5 名字的绑定 1.6 参数传递 1.7 构造运行程序和源程序有关的一些问题 71.1 过程构成源程序的两个过程行文，源程序由一组过程组成，不同的程序设计 语言，由过程构成源程序的方法不同。 要么是嵌套 的，要么是平行的。81.2 活
4、动树程序执行期间的控制流： 1程序执行的控制是顺序的； 2过程的每一次执行都是从过程体 的开头开始，并最终把控制返回到紧接 着该过程被调用点的后面。9一个过程p的一次活动的生存期: main P其中包括执行过程p所调用的过程的 执行时间，以及这些过程所调用的过程 的执行时间，如此等等。在该过程体第一步到最后一步之间 的语句的执行时间。p10这种活动生存期的嵌套性质可以通过 在每一个过程中插入两个打印语句来加以 跟踪。2、 如果a和b是两个过程活动，那么它们 的生存期要么是并列的,要么是嵌套的。 控制流的特点： 1、 每当控制流从过程p的活动进入到过程 q的活动中后，它将返回到过程p的同一次 活
5、动中。11program sort（input，output）； var a ： array0.10 of integer； procedure readarray； var i ： integer； begin end； function partition （y ，z ： integer ）:integer； var i，j ，x，v： integer； begin end; procedure quicksort（m，n ： integer）； var i ： integer； begin end end； begin end.程序见P254页12执行开始enter readarray
6、leave readarray enter quicksort（1，9） enter partition（1，9） leave partition（l，9） enter quicksort（1，3） . leave quicksort（1，3) enter quicksort（5，9） . leave quicksort（5，9） leave quicksort（1，9） 执行结束这是递归调用13递归：一个过程是递归的，如果同一过程 的一次新的活动可以在前面活动结束以前 开始。活动树： 在一棵活动树中： 2. 根结点代表主程序的活动; 3. 代表a的结点是b结点的父结点当且仅当 控制从活动a进
7、入活动b; 4. 结点a在结点b的左边当且仅当a的生存 期发生在b的生存期之前用一颗树来描绘控制进入和离开 活动的途径。这样的树称作活动树。1. 每一个结点代表一个过程的活动; 14srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)p(2,3)q(2,1)q(3,3)q(5,9)p(5,9)q(5,5) q(7,9)p(7,9)q(7,7)一棵活动树假设 I=4假设 I=1假设 I=1假设 I=2假设 I=6假设 I=8假设 I=8q(9,9)15结论:且每一个活动只有一个结点表示; 当控制进入某一个活动时， 可以直接说，控制在这个结点上。一个结点代表一个唯一的活动，
8、161.3 控制栈因此，用 一个栈保存过程活动的生存踪迹;程序执行的控制流对应于从根开始 ，按先根次序遍历活动树.当一个 活动开始执行时， 把代表这个活动的结点 推进栈；当这个活动结束时，把代表这个 活动的结点从栈中弹出。17例2 栈和活动树的变化栈s srS rq(1,9)S q(1.9)p(1,9) S q(1.9) p(1,9)q(1,3)S q(1.9) q(1,3)p(1,3) S q(1.9) q(1,3) p(1,3)q(1,0)S q(1.9) q(1,3) q(1,0)q(2,3)S q(1.9) q(1,3) q(2,3)18结点序列： s,q（1，9），q（l，3），q（
9、2，3 ）控制栈中的活动都是活跃的，从栈底活动到栈顶活动的活动序列表示了 活动的生存期的嵌套关系。从栈顶活动到栈底 活动的活动序列是从活动树上当前结点通 向根的路径上的节点当前控制 进入的活动在栈顶；19结论：扩充控制栈可用来实现如Pascal语言 的栈式存储分配，进入一个活动，在栈顶 建立这个活动所使用的存储空间；这个活 动结束，从栈顶弹出其使用的存储空间。20一个名字在源程序行文中可能有几处说 明，语言的作用域规则规定了：1 .说明把名字与名字的属性信息绑定在一 起。1.4 说明的作用域2 . 说明的作用域是一个说明起作用的范 围 （源程序行文）。 如：局部变量、全 局变量Int a10;
10、在语句序列中引用的一个名字是在 何处说明的名字。 213 . 编译时,处理说明语句时,把名字及其属 性信息填写进符号表(add(id.entry,id.vul); 处理引用 名字时，查找这个名字的属性信 息（lookup(id),符号表管理程序根据语 言 的 作用域规则，使 lookup(id)返回id的作 用域中绑定的属性信息。22可以说，函数environment把一个名字映 射为一个l-value（左-值）,1.5名字与存储的绑定引进两个函数，environment和state。 environment把名字映射到一个存储单元 上； state把存储单元映射到那里所存放的 值上。而函数s
11、tate把 一个l-value（左-值）映射为一个r-value（ 右-值）。如下图所示。名字与存储单元的绑定是指把源程序中的 数据名字映射到目标机存储单元的过程。23名字存储单元值存储分配程序运行environmentstatel-valuer-value图：从名字到值的两个阶段映射24静态概念 动态对应过程定义 过程活动名字说明 名字的绑定说明的作用域 活动的生存期251.6 参数传递 实在参数和形式参数结合的方法： 传值调用（call-by-value） 引用调用（call-by-reference） 复制恢复（copy-restore） 传名调用（call-by-name）261.7
12、提出的问题 编译程序组织存储分配所采用策略 和方法主要取决于对源程序中下面的问 题的回答。1过程可以是递归的吗？ 2当控制从过程的一次活动返回时，局 部名的值将发生什么 变化? 3一个过程可以访问非局部名吗？ 4当调用过程时参数是怎样传递的？27上面的问题对运行时的存贮分配有很大 的影响，5过程可以作为参数被传递吗？ 6过程可以作为结果被返回吗？7. 可以在程序控制下进行动态存储分配 吗？8. 显式的存储重新分配（指撤除分配后 的分配）是必须的吗？ 我们将在后面章节里，对以上问题 进行讨论并介绍与之相应的存贮分配策略287.2 存储组织2.1 运行时刻内存的划分 运行时刻的存储空间必须划分成块
13、， 用来存放:1. 生成的目标代码; 2. 数据目标; 3. 用于保存过程活动踪迹的一个控制 栈。29目标代码静态数据栈堆1. 编译后知道目标 代码的大小。存储空间划分的各部分：2. Pascal, c , Fortran3. 栈:Pascal,c4. 堆: Pascal,c302.2 活动记录对于pascal语言来说，运行过程中， 当调用一个过程时，在栈顶构筑它的活动 记录；一个活动所需要的信息的每个数据项 有相同的生存期，因此，组织成一个活动 记录是很自然的。当这个过程的活动执行完后，把它 从栈顶弹出。把过程的一个活动所需要的信息组织 成一块连续的存储单元，称为活动记录。31源语言不同，实
14、现方法不同，组成活动记 录的域不同。常见语言的活动记录如后图 所示。32返回值实在参数控制链访问链保存机器状态局部变量 临时变量临时变量：编译产生。保存机器状态：调用过 程的活动在调用点的机 器状态，包括计数器， 各种寄存器的值。 局部数据：过程中定义 的 局部量。访问链：指向本活动要 访问的非局部数据所在 的活动记录.控制链:指向主调过程 的活动记录的首地址。 形式单元内情向量连 接 数 据局 部 数 据sptop332.3 编译时刻的局部数据的设计局部数据域是编译时刻在编译过程中 分配的。例如：PROCEDURE sub(x,y:real);VAR i ,j:integer;a:ARRAY1.5 OF real;e, f : real;BEGINf :=e+i*j;END;名字所需的存 贮空间的数量 是由它的类型 确定的
