当前位置：文档之家 › 编译原理 第7章 运行时刻环境

编译原理 第7章 运行时刻环境

  • 格式：ppt
  • 大小：1.09 MB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

运行环境-编译原理-07-(二)

运行环境-编译原理-07-(二)
第七章 运行环境
标识符与数据目标的关系
变量名
── 数据存储Biblioteka 元地址 ── 程序段地址过程名、函数名
相关问题
变量和过程的作用域 过程调用的实现方法
7.1 绑定的完成
何时进行空间分配：
全局变量：程序装入时 局部变量：进入过程或分程序时
变量名的绑定
静态绑定：编译时指定（相对地址）
说明语句或函数定义的语义处理
分析参数的类型、分配地址 统计参数和返回值的空间需求
表格管理
完成过程名的属性登录
过程调用的实现
1)
在过程 f 中调用过程 g 时
a.
f 对实在参数求值，将结果存入 g 的 活动记录参数域
b.
在 g 的活动记录中存放返回地址和当 前栈顶指针 按照活动记录的大小，上移栈顶指针 从 g 的入口开始执行
作用
绑定的完成、空间分配、 特殊语法现象、语义合法性检查
符号表的功能
建立表项
以标识符为关键字
属性的设置与引用
类型、作用域、存储类别、地址等
符号表的实现
实现方法：
线性表、排序表、散列表（哈希）
特殊问题
结构成员、函数参数、分程序结构
性能
优先考虑查找的效率
试分析以下 C 程序的运行结果 float x, y; char buf[32]; 思考题 main( ) { int i; char *p = &x + 20; for( i = 0; i < 32; i++ ) buf[ i ] = ‘a’ + i; while( *++p != ‘x’ ) putchar( *p ); }

编译原理-运行环境

编译原理-运行环境
将生成的代码输出到目标文件或内存中，供运行环境执行。
03
运行环境概述
操作系统
操作系统是计算机系统的核心软件，负责管理硬 件资源、提供软件运行环境以及执行用户任务。
操作系统的主要功能包括进程管理、内存管理、 文件系统和设备驱动等。
常见的操作系统有Windows、Linux和macOS等。
内存管理
寄存器分配
编译器通过合理地分配寄存器，减少 内存访问次数，提高程序的执行效率。
指令选择
编译器根据目标平台的指令集和特性， 选择最优的指令集来执行程序，以提 高程序的执行效率。
内存管理优化
内存布局优化
编译器可以通过优化内存布局，将相关数据和函数放在一起，减少 内存访问的开销。
内存访问优化
编译器可以通过优化内存访问，减少内存访问次数，提高程序的执 行效率。常见的优化技术包括缓存优化、预取技术等。
保护等。
03
常见的文件系统有FAT32、NTFS和ext4等。
进程与线程管理
进程是操作系统中一个独立运行的程序实例，具有独立的内存空间和系统 资源。
线程是进程中的一个执行单元，共享进程的资源，实现并发执行。
进程与线程管理的主要任务包括进程创建、进程终止、进程切换和线程调 度等。
04
运行环境与编译原理的关系
01 内存管理是操作系统的重要组成部分，负责分配 和回收内存资源。
02 内存管理的主要任务包括内存分配、内存回收、 内存保护和内存扩充等。
03 内存管理算法有静态分配、动态分配和垃圾回收 等。
件系统
01
文件系统是操作系统中用于管理文件存储和访问的机
制。
02
文件系统的主要功能包括文件存储、文件访问和文件

编译原理7 运行环境

编译原理7 运行环境

d + lR
PROC P PROC Q PROC R
. .引用 Py, Qx
Py Qx
ARR
SP2 SP1 SP0 形式单元 m 全局DISPLAY
lR
d 个单元
返回地址
SP2
老SP Data Section Qx ,内情
.
call call R Q
SP1.2
Q P 形参 n 全局DISPLAY
lQ
TOP 16
主程序P
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
过程 S 过程 Q
SP
i b(形参) 1(形参个数) 0 返回地址 5 i c 0(形参个数) 0 返回地址 0 x a 0 返回地址 0
？第N层过程调用
第 N层过程，如何确 定被调用过程(第 N层) 过程的静态链？
，该函数所需的存储空间动态地分配于栈顶，函 数返回时，释放所占用的空间。
7
Ch6 运行环境
6.1 关于程序运行环境与存储组织
堆式动态存储分配
在内存中开辟一个称为堆的存储区，程序
运行每当需要（申请）时就按照某种分配原则
在堆的自由区(可占用区)中，分配能满足其需
要的存储空间给它，使用后需要释放操作，再
23 22 21 20 19 18 SP 17
d c v(形参) u(形参) 2(形参个数) 11 返回地址 11
动态链
静态链
31
主程序P
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
过程 S 过程 Q 过程 R 过程 R
TOP 32
31 30 29 28 27 26 SP 25 24 23 22 21 20 19 18 17

编译原理之运行时刻环境

编译原理之运行时刻环境

编译原理之运行时刻环境编译原理是计算机科学中的重要课程，它研究的是将高级语言代码翻译成机器语言的过程。

在编译过程中，除了词法分析、语法分析、语义分析等步骤外，运行时刻环境也是一个非常重要的概念。

本文将介绍编译原理里的运行时刻环境。

什么是运行时刻环境运行时刻环境是指在程序运行过程中支持程序执行的一系列运行时数据结构和服务。

在编译原理中，运行时刻环境通常包含以下几个重要组成部分：1.堆栈（Stack）：存储函数调用和局部变量的内存空间。

每个函数调用都会在堆栈上创建一个称为帧的数据结构，用来保存函数参数、局部变量和返回地址等信息。

2.堆（Heap）：存储动态分配的内存对象，比如使用new关键字创建的对象会在堆上分配内存。

3.全局数据区（Global Data Area）：存储程序运行过程中始终存在的全局变量和静态变量。

4.常量池（Constant Pool）：存储程序中使用的常量值，比如字符串、数字等。

5.代码区（Code Area）：存储程序的指令集，包括函数的二进制代码等。

运行时刻环境的作用运行时刻环境在程序执行过程中起着至关重要的作用，它主要负责以下几个方面的功能：1.内存管理：运行时刻环境负责内存的分配和释放，保证程序运行时能够动态地分配和释放内存，避免内存泄漏和空指针引用等问题。

2.异常处理：处理程序运行过程中出现的异常情况，比如空指针异常、数组越界异常等，保证程序的稳定性和可靠性。

3.类型检查：在程序运行过程中对数据的类型进行检查，避免类型不匹配导致的错误。

4.动态链接：在程序运行过程中对函数调用进行动态链接，确保程序可以正常调用外部库中的函数。

5.运行时优化：运行时刻环境还可以对程序进行一些优化，比如函数内联、循环展开等，提高程序的执行效率。

运行时刻环境的实现方式不同的编程语言和编译器实现了不同的运行时刻环境，下面以几种常见的实现方式为例进行介绍：JVMJVM（Java Virtual Machine）是Java平台的关键组成部分，它定义了一套独立于硬件平台的指令集架构，并提供了一套丰富的库函数。

编译原理课件Chapter-7

编译原理课件Chapter-7
INTEGER X;
(2)
CALL M2( IND + 1 );
END M1;
M2: PBLOCK( INTEGER J );
高层（内层）模块可以引用低层（外层） 模块中的变量，例如在M1中可引用外层模块中 定义的变量 Y。
在 M1 中引用Y时，可通过其 display 区找 到程序块 1 的活动记录基地址，加上 Y 在该数 据区的相对地址就可以求得 y 的绝对地址。
abp
(a) 进入模块1
1 BBLOCK; 2 REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X;
CALL M2( IND + 1 );
3 END M1; M24: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2;
（h）当最外层模块执行完，运行栈恢复到进入模块时 的情况，运行栈空。
main的数据 （空） 进入main函数的情况 OS
abp(0) → （空） 1
BBLOCK; 2 REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X;
CALL M2( IND + 1 );
3 END M1; M24: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2;
CALL M1( X / Y )
END
1 X, Y, NAME
2 M1: (IND); X;

编译原理运行时环境

编译原理运行时环境

machunyan
编译原理运行时环境
对名字的访问：（续）
fp mOffset=+8
高端地址
m:2 返回地址
控制链 y:1
mOffset yOffset 低端地址
yOffset=-4
machunyan
编译原理运行时环境
对名字的访问：（续）
例：考虑下面的C过程
对f调用的活动记录为：
Viod f(int x,char c)
编译原理运行时环境
2020/12/13
编译原理运行时环境
第7章 运行时环境(存储空间)(续)
o 存储分配是在运行阶段进行的，但编译程序在 编译阶段要为其设计好存储组织形式，并将这 种组织形式通过生成的目标代码体现出来。 (举例说明：函数调用分析.txt)
o 目标代码运行时，存储空间的组织称为目标代 码的运行时环境。
主调函数的控 制链(main.ebp)
栈底 栈顶
c:3
machunyan
编译原理运行时环境
7.3 基于栈的运行时环境（续）
当一个函数被调用时，在栈顶为该函数分配 所需的数据空间(过程活动记录)如下：
1) 将实参的值压入在该函数对应的新活动记录中。 2) 将被调函数执行完毕后的返回地址压入在新的活动记录中。 3) 完成到被调用的过程代码一个转移。 4) 将主调函数的fp作为控制链压入到新的活动记录中。 5) 改变fp以使其指向新的活动记录(将sp复制到fp中) 6) 将该函数的局部变量和局部临时变量压入到新的活动记录中。
放的数据结构 n 过程不可递归调用
machunyan
编译原理运行时环境
7.2 完全静态的运行时环境（续）
整个程序 存储器如 右所示：

编译 第7章 运行时环境

编译 第7章 运行时环境
–
堆管理和完全动态运行时环境
– 堆管理使用 分配操作和释放操作处理指针 分配和重新分配, 这是管理堆的手工方法， 分配和重新分配 这是管理堆的手工方法， 因为程序员必须编写出分配和释放存储器 的明确的调用 – 在一种需要完全动态的运行时环境的语言 中，堆必须自动管理
7.3 参数传递机制
过程活动记录
允许递归调用 – 每一个调用都重新分配局部变量
–
Program main; 全局变量定义; 全局变量定义 Procedure R; … End(R); Procedure Q; … End(Q); 主程序执行体 End.(main)
若主程序调用Q， 递归调用自己 递归调用自己， 若主程序调用 ，Q递归调用自己，在Q 第二次进入运行后的存储结构为： 第二次进入运行后的存储结构为：
i:=5; k[i]:=6; SWAP(i, k[i]);
① 参数传递(add_i 表示 i的地址 参数传递 的地址) 的地址 调用者的数据区 add_i add_K[i] 5 6 被调用者的数据区 add_n add_m add_j ② 过程代码执行后“j:=n;n:=m;m:=j” 过程代码执行后“ 调用者的数据区 add_i add_K[i] 6 5 被调用者的数据区 add_n add_i add_m add_k[i] add_j 结果 :i=6，k[5]=5 ,参数发生改变 ， 参数发生改变 5 add_i add_K[i]
代码区 全局变量数据区 全局 静态区 全局/静态区 Main的数据 的数据 Q的数据 的数据 Q的数据 的数据 栈区
3. 完全动态运行时环境
完全动态运行时环境
数据空间在执行时可以任意次地分配与回收。 数据空间在执行时可以任意次地分配与回收。 活动数据仅在对它们所有的引用都消失了才 再重新分配 – 完全动态运行时环境比基于栈的运行环境要 复杂许多， 复杂许多，因为它包含了要在执行时跟踪引 用，以及在执行时任意次地找寻和重新分配 存储器的不可访问区域（这种处理称为垃圾 存储器的不可访问区域（这种处理称为垃圾 回收） 回收）

编译原理第7章

编译原理第7章
② a．若NODE(B)是以常数叶结点，则转步骤②c，否则转步骤③a。
b．若NODE(B)和NODE(C)都是以常数叶结点，则转步骤②d，否则转步 骤③b。
c．执行OP B(即合并已知量)，令得到的新常数为P。若NODE(B)是处理当 前四元式时新建立的结点，则应予以删除；若NODE(P)=null，则建立以常 数P为标记的结点n，置 NODE(P)=n，转步骤④。
(a)构造前
(1) (=, 3.14, _, T1) (2) (=, 6.28, _, T2) (3) (=, 6.28, _, T4) (4) (+, R, r, T3) (5) (=, T3, _, T5) (6) (*, 6.28, T3, A) (7) (=, A, _, T6) (8) (_, R, r, T7) (9) (=, T5, T7, B)
(1) (:=, 3.14, _, T1) (2) (*, 2, T1, T2) (3) (+, R, r, T3) (4) (*, T2, T3, A) (5) (:=, A, _, B) (6) (*, 2, T1, T4) (7) (+, R, r, T5) (8) (*, T4, T5, T6) (9) (-, R, r, T7) (10) (*, T5, T7, B)
k=1;
if(k<5)
(×)
s=s+k;
else s=s-k;
基本块的划分算法
①确定各基本块的入口，其原则是 a．程序的第一条语句。 b．控制语句所转向的语句。 c．紧跟在条件转移语句之后的语句。
②对每一个入口语句，确定其所属的基本块。它是由该入 口语句到下一个入口语句(不包括下一个入口语句)，或到一个 转移语句(包括该转移语句)，或到一个停语句(包括该停语句) 之间的语句序列组成的。

《编译原理》教学大纲

《编译原理》教学大纲

《编译原理》教学大纲大纲说明课程代码： 3225003总学时： 64 学时（讲课 48 学时，实验16 学时）总学分： 4课程类别：学科基础课适用专业 : 计算机科学与技术（专业）预修要求： C 语言程序设计、 C++ 程序设计、数据结构课程的性质、任务及地位：《编译原理》是计算机科学与技术专业的一门重要基础课。

通过对该课程的学习，使学生掌握编译过程中的相关原理和编译技术，让学生能初步进行编译程序的开发和维护，同时促进提高学生开发软件的能力。

教学目的与基本要求：本课程的目的，通过向学生讲述编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，使学生既掌握编译技术理论的基础与基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。

本课程理论性较强。

因授课对象为工科学生，所以在强调编译系统的构造原理和实现方法的同时，为培养学生的实际工作能力，通过上机实践进一步加深学生对课堂教学内容的理解。

目的是要使学生牢固掌握相关的基本理论和基本方法，并能初步利用上述理论和方法解决简单实际问题。

教学方法和教学手段的建议：在教学方法上，贯彻理论联系实际、“精讲、多练”的原则，进行案例式、启发式的教学，对于一些实际性较强的问题要多采用课堂讨论等方式，以提高学生的思辨能力和学习的主动性；引导学生读书、理解、体悟、运用相结合；提高学生的学习兴趣与热情，培养与发挥学生的提出、分析及解决问题的能力。

教学手段：运用多媒体教学手段 +黑板 +上机实验的手段。

采取课堂讲授、课堂讨论、课后练习与自学等形式。

大纲的使用说明：大纲对课程性质、目的等作简单说明，同时列出各章节要学习的知识点、重点、难点，便于教学时教授重点的安排和学生自学安排。

大纲正文第一章引论学时： 4 学时（讲课 4 学时，实验 0 学时）了解编译的概念；理解编译程序的各组成部分及功能。

本章讲授要点：介绍程序设计语言与编译程序间的关系，主要内容包括：各级程序设计语言的定义、源程序的执行、编译程序的构造、编译程序的分类、形式语言理论与编译实现技术的联系。

编译原理-第七章解析资料

编译原理-第七章解析资料

中间代码 中间 中间代码 生成器 代码 优化器
静态语义检查和中间代码生成器的位置
2018/10/26
TJNU-COCIE-WJW
5
第七章 语义分析和中间代码产生
中间语言 7.2 说明语句 7.3 赋值语句的翻译 7.4 分情况语句 7.5 回填技术 7.6 类型检查
7.1
2018/10/26 TJNU-COCIE-WJW 6
TJNU-COCIE-WJW 28
2018/10/26
例子：语句a:=b*-c+b*-c 的三元式表示
op arg1 arg2
(0) (1) (2) (3) (4) (5)
uminus * uminus * + Assign
c b c b
(1)
(0) (2) (3) (4)
a
2018/10/26
TJNU-COCIE-WJW
例：x
+ y * z翻译成 t1 := y * z t2 := x + t1
TJNU-COCIE-WJW 16
2018/10/26
1.一般形式（续）
三地址代码是AST或DAG的线性化表示

DAG图对应的三地址代码可能比相应的AST
对应的三地址代码要优化，因为可以复用中 间结果
2018/10/26
29
注意： 有些三地址语句要多个三元式表示 例子： x[i] := y op arg1 arg2 (0) [ ]= x i (1) := (0) y
y := x[i] op arg1 (0) =[ ] x (1) := y arg2 i (0)
2018/10/26
TJNU-COCIE-WJW

ch07--运行环境

ch07--运行环境

Wensheng Li BUPT @ 2008

数据对象：
–每个过程的活动记录的位置及大小 –记录中每一个名字所占用的存储空间的位置及大小 –数据在运行时刻的地址可以填入到目标代码中
18/71
静态存储分配策略对源语言的限制


数据对象的大小和它们在内存中的位置必须在编译 时都能够确定 不允许过程递归调用
Wensheng Li BUPT @ 2008

过程引用：过程名出现在一个可执行语句中 参数：
–形参、实参
5/71
活动

活动
–一个过程的每次执行称为它的一次活动 –如果一个过程在执行中，则称它的这次活动是活着的

过程与活动
–过程是一个静态概念，活动是一个动态概念 –过程与活动之间可以是1:1、1:m的关系 –递归过程，同一时刻可能有若干个活动是活着的 –每个活动都有自己独立的存储空间/数据空间
Wensheng Li BUPT @ 2008
P
P
P
P有3个活着的活动
P有1个活着的活动
P有2执行时,过程之间的控制流
– 是连续的 – 过程的每一次执行都是从过程体的起点开始，最后控制返回到直接 跟随本次调用点的位置。

活动的生存期
– 过程体的执行中，第一步和最后一步之间的一系列步骤的执行时间 – 过程P的一次活动的生存期，包括执行过程P所调用的过程的时间， 以及这些过程所调用的过程的时间 – 如果a和b是过程的活动，那么它们的生存期要么是不重叠，要么是 嵌套的。 a a b a b b
局部数据的安排
–局部数据区是在编译过程中检查声明语句时安排的 –长度可变的数据对象，放在该区域之外
Wensheng Li BUPT @ 2008

编译原理演示文稿7

编译原理演示文稿7

例:设有类Pascal程序段 program example(input,output);
type student=record no:integer; name:array[1..10] of char; score:integer end;
weekday=(sun,mon,tue,wed,thu,fri,sat); var st:array[1..50] of student;
name :array[1..20] of char; next:link end; 的无类型结构树或无环 有向图相等即可。检查类型等价也分成静态检查和动态检查。 由编译程序能完成的类型检查叫做静态类型检查；由目标程 序运行时所作的类型检查就称为动态类型检查。一般地，如 果要在生成的目标代码中完成类型检查，则目标代中不但要 保存数据的值，而且还保存该数据的类型，则可完工成相应 的动态类型检查。因算法语言的类型检查多数是静态的类型 检查，在这里仅介绍了静态的类型检查。
7.1.4 控制结构 一种程序设计语言的控制结构是该语言在程序运行期间
用于改变控制流的语言特征集合。它包括有条件控制转移， 条件执行、循环控制、过程序调用、转移和出口。编译程序 在翻译时必须保证源程序不能违法控制结构的语义。如 Pascal中只能从循环体内转向循环体外、C语言中不能从一 个函数转向另一个函数、BASIC中不能在循环体内修改循环 变量的值，而C没有这种限制。 例:错误的控制结构 begin
定义7.1 数据类型是对该类型数据（变量或常量）的取值是 否合法以及对该类型据的运算是否合法的一种说明。
实现和完成数据类型的合法性检查，它包括以下任务：
(1) 检查运算符作用在运算对象上的合法性，这一合法性保 证了该运算能产生正确的运算结果。

编译原理与技术-运行环境

编译原理与技术-运行环境

18
e.g.2 栈式存储分配
过程g被调用时，活动记录栈的（大致）内容
返回地址 old bp a : 1000 返回地址 old bp a : 100 返回地址 bp sp
2012-6-6 《编译原理与技术》－运行环境 19
main程序的AR
函数h的AR
old bp a : 10
函数g的AR
e.g.3 有参函数的活动记录
main() { int a = 0 ; int b =0; //local VAR of main { int b = 1 ; // block 1 { int a = 2 ; printf(“%d %d\n”,a,b);//block 2 } { int b = 3 ; printf(“%d %d\n”,a,b);//block 3 } printf(“%d %d\n”,a,b); } printf(“%d %d\n”,a,b); }
机器状态 局部数据 临时区
d1、d2谁正谁负？
bp
偏移d2
地址： bp+d2
9
2012-6-6
《编译原理与技术》－运行环境
静态存储分配
－ 全局变量的存储绑定、AR均在编译时确定 且在整个程序执行中保持。 － 不支持： 1）动态数据结构 2）过程递归调用 － 实现静态分配的语言： （早期）FORTRAN
2012-6-6
《编译原理与技术》－运行环境
10
e.g.1 FORTRAN静态存储分配
CALL sub CALL sub END SUBROUTINE sub DATA I/10 第一次调用前 机器状态 WRITE(*.*) I I （ 10 ） I = 100 END 第一次调用后 机器状态 第一次调用sub，输出10

第七章运行时刻环境

第七章运行时刻环境
何激活的。
第七章运行时刻环境
非局部数据的访问（嵌套声明过程）
• PASCAL中，如果过程A的声明中包含了过程B的声 明，那么B可以使用在A中声明的变量。
• 当B的代码运行时，如果它使用的是A中的变量。那 么这个变量指向运行栈中最上层的同名变量。
• 但是，我们不能通过嵌套层次直接得到A的活动记录 的相对位置。必须通过访问链访问
• 程序运行的所有过程活动可以用树表示
• 每个结点对应于一个过程活动 • 根结点对应于main过程的活动 • 过程p的某次活动对应的结点所有子结点：此次
活动所调用的各个过程活动（从左向右，表示调用 的先后顺序）。
第七章运行时刻环境
活动树的例子（1）
• 程序：P277，图7-2 • 过程调用（返回）序列和活动
树的前序（后序）遍历对应 • 假定当前活动对应结点N，那
么所有尚未结束的活动对应于 N及其祖先结点。
第七章运行时刻环境
活动记录
• 过程调用和返回由控制 栈进行管理
• 每个活跃的活动对应于 栈中的一个活动记录
• 活动记录按照活动的开 始时间，从栈底到栈顶 排列
第七章运行时刻环境
运行时刻栈的例子
• a[11]为全局变量 • main没有局部变量 • r有局部变量i • q的局部变量i，和
• 指针d[i]指向栈中最高的、嵌套深度为i的活动记录。 • 如果程序p中访问嵌套深度为i的过程q中声明的变量x，
那么d[i]直接指向相应的（必然是q的）活动记录
• 注意：i在编译时刻已知
• 显示表的维护
• 调d[n用p]设过置程为p时当，前在活p动的记活录动。记录中保存d[np]的值，并将 • 从p返回时，恢复d[np]的值。
• 目标程序的代码放置在代码区 • 静态区、堆区、栈区分别放置不
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
37
存储管理器

基本功能


分配：为每个内存请求分配一段连续的、适当大 小的堆空间。首先从空闲的堆空间分配；如果不 行则从操作系统中获取内存、增加堆空间。 回收：把被回收的空间返回空闲空间缓冲池，以 满足其他的分配。

评价存储管理器的特性：



空间效率：是程序需要的堆空间最小，即减小碎 片 程序效率：充分运用内存系统的层次，提高效率 低开销：使分配/收回内存的操作尽可能高效

用访问链访问数据时，如果嵌套深度大，则 访问的效率差。 显示表：使用数组d为每个嵌套深度保留一个 指针


显示表的维护

指针d[i]指向最高的深度为i的的活动记录。 如果程序p中访问深度为i的过程q的变量x，那么 d[i]直接指向相应的q活动记录；
调用过程p时，在p的活动记录中保留d[np]的值， 并将d[np]设置为当前活动记录。 从p返回时，恢复d[np]的值。
25

Return sequence

调用代码序列的例子
26
7.3.4栈中的 变长数据



如果数据对象 的生命期局限 于过程活动的 生命期，就可 以分配在运行 时刻栈中。 top指向实际的 栈顶 top_sp用于寻 找顶层记录的 定长字段
27
7.4 非局部数据的访问（无嵌套过程）

没有嵌套过程时的数据访问

调用这计算实在参数的值 将返回地址和原top_sp存放到被调用者的活动记 录中。调用者增加top_sp的值（越过了局部数据、 临时变量、被调用者的参数、机器状态字段） 被调用者保存寄存器值和其他状态字段 被调用者初始化局部数据、开始运行。 被调用者将返回值放到和参数相邻的位置 恢复top_sp和寄存器，跳转到返回地址。

程序运行的所有过程活动可以用树表示

13
活动树的例子（1）


程序：P277，图7-2 过程调用（返回）序 列和活动树的前序 （后序）遍历对应 假定当前活动对应结 点N，那么所有尚未 结束的结点对应于N 及其祖先结点。
14
活动树的例子（1）
m r p(1,9) q(1,9) q(1,3) q(5,9) p(5,9) q(5,5) q(7,9) p(7,9) q(7,7) q(9,9)
28
7.4.1非局部数据的访问（无嵌套过程）



PASCAL中，如果过程A 的声明中包含了过程B的 声明，那么B可以使用在A 中声明的变量。 当B的代码运行时，如果 它使用的是A中的变量。 那么这个变量指向运行栈 中最上层的同名变量。 但是，我们不能通过嵌套 层次直接得到A的活动记 录的相对位置。
void A() {
int void { } void C();
}
x,y; B() int b; x = b+y;
C(){B();}
当A调用C，C又调用B时:
B的活动记录
C的活动记录
A的活动记录
29
7.4.2 嵌套深度

嵌套深度是正文概念，可以根据源程序静 态地确定 不内嵌于任何其他过程中的过程，嵌套 深度为1 嵌套在深度为i的过程中的过程，深度 为i+1.
3
7.1 概述


为什么要使用数据区 程序运行时各种数据必须放在内存中， 便于访问和使用。 数据区的管理 内存永远不能满足需要； 必须找到存贮的数据； 按照程序单位（过程、函数）分配和 管理数据区。
4
7.1 概述

1. 2.
数据区存贮的内容
变量和常数（用户自己定义） 临时单元：源程序中没有，编译程序在生成 中间代码时建立和使用。 形式单元：存放过程或函数间传递的参数； 返回地址：返回主调程序的入口。 保护区：保存主调程序的寄存器内容，恢复 现场。 数据访问控制信息

分配方式 在符号表中按照对象属性顺序分配 数据区，从而建立一个数据映像，运 行时按照此映像分配实际的内存数据 区。
10
7.2 静态存贮分配
符号表如下，DA栏表示数据区编号，ADDR栏是 相对地址 NAME 入 VA TYPE KIND DA ADDR 位 长 口 L 置 度 01 0 4 integer 简变 K a 02 4 1 integer 简变 K a+4 03 5 1 integer 简变 K a+8 ┋
11
7.3 栈式分配

内容： 活动树 活动记录 调用代码序列 栈中的变长数据
12
7.3.1 活动树

过程调用（过程活动）在时间上总是嵌套的：

后调用的先返回 因此可以用栈式分配来处理过程活动所需要的 内存空间。 每个结点对应于一个过程活动 根结点对应于main过程的活动 过程p的某次活动对应的结点的子结点对应于 此次活动调用的各个过程活动（从左向右，表 示调用的先后顺序）。
30
深度为1 sort 深度为2 readArray， exchange， quicksort 深度为3 partition
31
7.4.3 访问链


访问链被用于访问非局部的数据 如果过程p在声明时嵌套在过程q的声明中， 那么p的活动记录中的访问链指向最上层的 q的活动记录。 从栈顶活动记录开始，访问链形成了一个 链路，嵌套深度逐一递减。
17
指向调用者的 活动记录 用来访问存于其 它活动记录中的 非局部数据
运行时刻栈的例子

a[11]为全局变量 main没有局部变量 r有局部变量I q的局部变量i，和参 数m,n。
18
运行时刻栈的例子
运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录）
m a : array
23
调用/返回代码序列的要求

数据方面

能够把参数正确地传递给被调用者 能够把返回值传递给调用者 能够正确转到被调用者的代码的开始位置 能够正确转会调用者的调用位置（的下一条指 令）
24

控制方面


调用代码序列和活动记录的布局相关
调用代码序列的例子

Calling sequence

15
p(1,3) q(1,0) q(2,3)
p(2,3) q(2,1) q(3,3)
7.3.2 活动记录


过程调用和返回由控制栈进行管理 每个活跃的活动对应于栈中的一个活动 记录 活动记录按照活动的开始时间，从栈底 到栈顶排列
16
一般的活动记录的布局
实参 返 回 值 可选的控制链 可选的访问链 保存的机器状态 局部数据 临时数据
35
显示表的例子
q(1,9)调用q(1,3) 时，q的深度为2
q(1,3)调用p， p的深度为3
q调用e，e存贮分配


含义 在编译时无法确定数据区的大小，在过 程的入口处也确定不了数据区的大小， 因此无法使用静态或栈式分配方法。 条件 有static类型、指针类型和表单(form)等 变量。



调用代码序列(calling sequence)为活动记录 分配空间，填写记录中的信息； 返回代码序列(return sequence)恢复及其状 态，是调用者继续运行。 调用代码序列会分割到调用者和被调用者 中。


根据源语言、目标机器、操作系统的限制，可 以有不同的分割方案 把代码尽可能放在被调用者中。
第7 章 运行时刻环境
1
概 述 静态存储管理 栈式存储管理 堆式存储管理
2
7.1 概述

运行时刻环境

为数据分配安排存储位置 确定访问变量时使用的机制 过程之间的连接 参数传递 和操作系统、输入输出设备相关的其它接口

目的
编译程序除了要关心目标代码生成问题外， 还必须要考虑程序运行时使用的数据区域的管理 问题。
5
3. 4. 5.
6.
7.1 概述

主题

存储管理：栈分配、堆管理、垃圾回收 对变量、数据的访问 本章核心问题
如何访问到数据
6
1）存储分配的典型方式


目标程序的代码放置在代码 区 静态区、堆区、栈区分别放 置不同类型生命期的数据值， 即数据区
7
2）静态和动态存储分配

静态分配




编译器在编译时刻就可以做出存储分配决 定，不需要考虑程序运行时刻的情形 不存在可变长的数组、可变长的字符串、 指针； 不存在函数或过程的嵌套和递归。 全局变量
32
7.4.3 访问链

设深度为np的过程p访问变量x，而变量x在 深度为nq的过程中声明，那么


从当前活动记录出发，沿访问链前进np-nq 次找到的活动记录中的x就是要找的变量位 置 x相对于活动记录的偏移量在编译时刻已知 np-nq在编译时刻已知；
33
访问链的例子
34
7.4.4 显示表
m r q(1,9)
21
运行时刻栈的例子
运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录） m a : array q (1, 9) k: integer m r q(1,9)
p(1,9) q(1,3) p(1,3) q(1,0)
22
q (1, 3)
k: integer
7.3.3 调用代码序列
38

堆空间的分配及管理


固定长分块法：将堆空间分成大小相同的块，使用链 表连接各个单元；适用于类型单一或长度一致的数据 类型。 可变长分块法：将堆空间分成长度不同的块。