《编译原理第六章运行时存储空间的组织和管理.》由会员分享，可在线阅读，更多相关《编译原理第六章运行时存储空间的组织和管理.（110页珍藏版）》请在金锄头文库上搜索。
1、第六章 运行时存储空间的组织和管理 术语 过程的活动 过程的一次执行称为过程的一次活动 活动记录 过程的活动需要可执行代码和存放所需信息的存储空间, 后者称为活动记录 本章内容 讨论一个活动记录中的数据布局 程序执行过程中，所有活动记录的组织方式 第六章 运行时存储空间的组织和管理 影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配 存储块是否必须显式地释放 6.1 局部存储分配 6.1.1 过程 语言概念： 过程定义、过程调
2、用、形式参数、实在参 数、活动的生存期 6.1 局部存储分配 6.1.2 名字的作用域和绑定 1、名字的作用域 一个声明起作用的程序部分称为该声明的作 用域 6.1 局部存储分配 2、环境和状态 环境把名字映射到左值，而状态把左值映射 到右值（即名字到值有两步映射） 赋值改变状态，但不改变环境 过程调用改变环境 如果环境将名字x映射到存储单元s，则说x被 绑定到s 名字存储单元 状态 值 环境 6.1 局部存储分配 3、静态概念和动态概念的对应 静 态态 概 念 动动 态态 对对 应应 过过程的定义义 过过程的活动动 6.1 局部存储分配 3、静态概念和动态概念的对应 静 态态 概 念 动动
3、态态 对对 应应 过过程的定义义 过过程的活动动 名字的声明 名字的绑绑定 6.1 局部存储分配 3、静态概念和动态概念的对应 静 态态 概 念 动动 态态 对对 应应 过过程的定义义 过过程的活动动 名字的声明 名字的绑绑定 声明的作用域 绑绑定的生存期 6.1 局部存储分配 6.1.3 活动记录 活动记录的常见布局 返 回 值 临 时 数 据 参 数 控 制 链 访 问 链 机 器 状 态 局 部 数 据 6.1 局部存储分配 6.1.4 局部数据的布局 字节是可编址内存的最小单位 一个过程所声明的局部变量，按这些变量声明时出 现的次序，在局部数据域中依次分配空间 局部数据的地址可以用相对
4、于某个位置的地址来表 示 数据对象的存储布局还有一个对齐问题 6.1 局部存储分配 例 在SPARC/Solaris工作站上下面两个结构体的 size分别是24和16，为什么不一样？ typedef struct _atypedef struct _b char c1; char c1; long i; char c2; char c2; long i; double f; double f; a; b; 对齐：char : 1, long : 4, double : 8 6.1 局部存储分配 例 在SPARC/Solaris工作站上下面两个结构体的 size分别是24和16，为什么不一样？
5、typedef struct _atypedef struct _b char c1;0 char c1;0 long i;4 char c2; 1 char c2;8 long i; 4 double f;16 double f; 8 a; b; 对齐：char : 1, long : 4, double : 8 6.1 局部存储分配 例 在X86/Linux机器的结果和SPARC/Solaris工作 站不一样，是20和16。 typedef struct _atypedef struct _b char c1;0 char c1;0 long i;4 char c2; 1 char c2;
6、8 long i; 4 double f;12 double f; 8 a; b; 对齐：char : 1, long : 4, double : 4 6.1 局部存储分配 6.1.5 程序块 本身含有局部变量声明的语句 可以嵌套 最接近的嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重叠分配 6.1 局部存储分配 main() / 例 / / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 /
7、 int b = 3; / end of B3 / / end of B1 / / end of B0 / 声 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2 int b = 3; B3 a0 b0 b1 a2, b3 重叠分配存储单元 6.2 全局栈式存储分配 本节介绍 描述过程的目标代码怎样访问绑定到局部名字的存 储单元 介绍三种分配策略 静态分配策略 栈式分配策略 堆式分配策略 6.2 全局栈式存储分配 6.2.1 运行时内存的划分 代 码 静 态 数 据 堆 栈 6.2 全局栈式存储分配 1
8、、静态分配 名字在程序被编译时绑定到存储单元，不需 要运行时的任何支持 绑定的生存期是程序的整个运行期间 6.2 全局栈式存储分配 2、静态分配给语言带来限制 递归过程不被允许 数据对象的长度和它在内存中位置的限制， 必须是在编译时可以知道的 数据结构不能动态建立 6.2 全局栈式存储分配 例 C程序的外部变量、静态局部变量以及程 序中出现的常量都可以静态分配 声明在函数外面 外部变量 静态分配 静态外部变量 静态分配 声明在函数里面 静态局部变量 也是静态分配 自动变量 不能静态分配 6.2 全局栈式存储分配 6.2.2 活动树和运行栈 1、活动树 用树来描绘控制进入和离开活动的方式 m q
9、(1,9)r p(1,9) q(1,3) q(1,0) p(1,3)q(2,3) q(2,1) q(3,3)p(2,3) q(5,9) q(5,5) p(5,9)q(7,9) q(7,7) q(9,9)p(7,9) 6.2 全局栈式存储分配 活动树的特点 每个结点代表某过程的一个活动 根结点代表主程序的活动 结点a是结点b的父结点，当且仅当控制流从a的 活动进入b的活动 结点a处于结点b的左边，当且仅当a的生存期先 于b的生存期 6.2 全局栈式存储分配 当前活跃着的过程活动可以保存在一个栈中 例 控制栈的内容：m, q (1, 9), q (1, 3), q (2, 3) m q(1,9)r
10、 p(1,9) q(1,3) q(1,0) p(1,3)q(2,3) q(2,1) q(3,3)p(2,3) q(5,9) q(5,5) p(5,9)q(7,9) q(7,7) q(9,9)p(7,9) 6.2 全局栈式存储分配 2、运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录） 6.2 全局栈式存储分配 2、运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录） m a : array m 6.2 全局栈式存储分配 2、运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录） m int i r a : array m
11、r 6.2 全局栈式存储分配 2、运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录） m q(1,9)r m int i q (1, 9) a : array int m, n 6.2 全局栈式存储分配 2、运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录） m q(1,9)r p(1,9) q(1,3) q(1,0) p(1,3) q (1, 9) m int i a : array int m, n int m, n int i q (1, 3) 6.2 全局栈式存储分配 6.2.3 调用序列 过程调用序列 过程调用时执行的分配活动记录、
12、把信息填入域中的代码 过程返回序列 过程返回时执行的恢复机器状态，释放活动记录，使调用过 程能够继续执行的代码 6.2 全局栈式存储分配 即使是同一种语言，过程调用序列、返回序列和活 动记录中各域的排放次序，也会因实现而异 设计这些序列和活动记录的原则 调用者和被调用者交流的数据放在 活动记录开始处，并尽可能靠近调用 者的活动记录 固定长度的项放在活动记录中间。 在编译时不能及时知道大小的项目 放在活动记录末端 返 回 值 临 时 数 据 参 数 控 制 链 访 问 链 机 器 状 态 局 部 数 据 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 返回值和参数 top_sp bas
13、e_sp 临时数据局部数据 控制链 和保存的机器状态 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (1) p计算实参，依 次放入栈顶，并在 栈顶留出放返回值 的空间。top_sp的 值在此过程中被改 变 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (2) p把返回地址和 当前base_sp的值 存入q的活动记录 中，建立q的访问 链，增加base_sp 的值 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 控制链
14、和返回地址 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (3) q保存寄存器的 值和其它机器状态 信息 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 控制链 和保存的机器状态 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (4) q根据局部数据 域和临时数据域的 大小增加top_sp的 值，初始化它的局 部数据，并开始执 行过程体 临时数据局部数据 返回值和参数 返回值和参数 控制链 和保存的机器状态 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 6.2 全局栈式存储分配 调用者p和被调用者q之间的任务划分 被调用者q的责任 调用者p的责任 调用者p的 活动记录 被调用者q 的活动记录 临时数据局部数据 返回值和参数 返回值和参数 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 6.2 全局栈式存储分配 2、过程p调用过程q的返回序列 临时数据局部数据 返回值和参数 返回值和参数 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 6.2 全局栈式存储分配 2、过程p调用过程q的返回序列 临时数据局部数据 返回值和参数
