运行时的存储组织及管理 编译器的应用模型 出错处理 语法分析程序 语义分析程序 目标代码生成程序 词法分析程序 中间代码生成程序 代码优化程序 表格管理 编译的前端 FrontEnd 编译的后端 BackEnd 运行时的存储组织及管理 概述存储组织运行时的存储分配策略静态存储分配动态存储分配对非局部名字的访问参数传递 运行时的存储组织及管理 计算环境运行时的环境计算目标代码当词法分析扫描得到标识符 并将它填入符号表的过程中需要给识别出来的标识符分配内存空间 源程序由一组过程按某种规则组成 过程的一次执行称作一次活动 在过程的语句序列执行之前 过程中访问的对象构成此过程的运行环境 由运行支持程序组织好 编译程序根据如何组织运行环境而生成目标代码 映射 源程序 运行时环境的作用 目标程序运行时所需存储空间的组织与管理以及源程序中变量存储空间的分配 有关源程序中的一些问题 问题的提出 如何构造运行程序的策略和方法过程活动树控制栈说明的作用域名字的绑定构造运行程序和源程序有关的一些问题 过程 源程序由一组过程组成 不同的程序设计语言 由过程构成源程序的方法不同 构成源程序的两个过程行文 要么是嵌套的 要么是不相交的 programsort input output vara array 0 10 ofinteger procedurereadarry vari integer beginfori 1to9doread a i end functionpartition y z integer integer vari j x v integer begin end procedurequicksort m n integer vari integer beginif n m thenbegini partition m n quicksort m i 1 quicksort i 1 n endendbegina 0 9999 a 10 9999 readarray quicksort 1 9 end 活动树 程序执行期间的控制流 程序执行的控制是连续的 在任何一步 控制都处于程序的某一点过程的每一次执行都是从过程体的开头开始 并最终把控制返回到紧接着该过程被调用点的后面 过程的一次活动 过程体的每一次执行 过程p的一次活动的生存期 在该过程体的执行中的第一步和最后一步之间的一序列步骤的执行时间 其中包括执行过程p所调用的过程的执行时间 以及这些过程所调用的过程的执行时间 如此等等 一个过程是递归的 如果同一过程的一次新的活动可以在前面活动结束以前开始 活动树 为什么过程的活动可以用树形结构描述 过程活动的特点 每当控制流从过程p的活动进入到过程q的活动中后 它将返回到过程p的同一次活动中 也就是说 如果a和b是两个过程活动 那么它们的生存期要么是不重叠的 要么是嵌套的 在树形结构中 节点间的关系就反映了过程之间的关系 父子关系 嵌套兄弟关系 先后 活动树 用一颗树来描绘控制进入和离开活动的途径 这祥的树称作活动树 每个节点代表过程的一个活动根节点代表主程序的活动当且仅当控制流从活动a进入活动b时 节点a是b的父节点当且仅当a的生存期先于b的生存期时 a节点处于b结点的左边一个结点代表一个唯一的活动 且每一个活动只有一个结点表示 当控制进入某一个活动时 可以直接说 控制在这个结点上 programsort input output vara array 0 10 ofinteger procedurereadarry vari integer beginfori 1to9doread a i end functionpartition y z integer integer vari j x v integer begin end procedurequicksort m n integer vari integer beginif n m thenbegini partition m n quicksort m i 1 quicksort i 1 n endendbegina 0 9999 a 10 9999 readarray quicksort 1 9 end s r q 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 控制栈 程序的控制流对应于从活动树根节点开始的深度优先遍历 从左至右 活动树表示了完整的程序控制的先后顺序 在真正运行过程中 活动树并不是真实存在的数据结构 在程序运行过程中 我们只需要保存那些活跃着的过程 控制栈控制栈的基本思想 当一个活动开始执行时 把代表这个活动的结点推进栈 当这个活动结束时 把代表这个活动的结点从栈中弹出 控制栈只能表示活动树的一部分 活动树只是逻辑上存在的 类似于语法分析树 栈和活动树的变化 s s r Sr q 1 9 Sq 1 9 p 1 9 Sq 1 9 p 1 9 q 1 3 Sq 1 9 q 1 3 p 1 3 Sq 1 9 q 1 3 p 1 3 q 1 0 Sq 1 9 q 1 3 q 1 0 q 2 3 Sq 1 9 q 1 3 q 2 3 控制栈 控制栈中的活动都是活跃的 当前控制进入的活动在栈顶 从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列 从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系 结论 扩充控制栈可用来实现如Pascal语言的栈式存储分配 控制栈中存储活动记录 声明的作用域 声明语句是把名字与名字的属性信息绑定在一起的语法结构 说明的作用域是一个说明起作用的范围 源程序行文 一个名字在源程序行文中可能有几处说明 语言的作用域规则规定了在语句序列中引用的一个名字是在何处说明的名字 编译时 处理说明时 把名字及其属性信息填写进符号表 处理引用时 查找这个名字的属性信息 符号表管理程序根据语言的作用域规则 返回其作用域中绑定的属性信息 名字与存储的绑定 名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程 环境把名字映射到一个存储单元上 状态把存储单元映射到那里所存放的值上 或者说 环境把一个名字映射为一个左值 而状态把一个左值映射为一个右值 名字与存储的绑定 名字 存储单元 值 存储分配 程序运行 环境 状态 l value r value 静态概念动态对应过程定义过程活动名字说明名字的绑定说明的作用域活动的生存期 存储组织 运行时刻内存的划分 假定编译器从操作系统得到一块存储区 运行时的存储空间要划分成块 生成的目标代码 数据对象 记录过程活动的控制栈对应的数据结构 目标代码 静态数据 栈 堆 1 编译后知道目标代码的大小 放入静态确定的区域中2 某些数据对象的长度也可以在编译时知道 也可以放在静态区域中 主程序中的数据 c FORTRAN3 栈 控制栈 Pascal c4 堆 开销比栈大 分配和释放方式 Pascal c 活动记录 把过程的一个活动所需要的信息组织成一块连续的存储单元 称为活动记录 一个活动所需要的信息的每个数据项有相同的生存期 因此 组织成一个活动记录是很自然的 对于pascal语言来说 运行过程中 当调用一个过程时 在栈顶构筑它的活动记录 当这个过程的活动执行完后 把它从栈顶弹出 活动记录 控制链 指向调用过程活动的活动记录 访问链 指向本活动要访问的非局部数据所在的活动记录 保存机器状态 调用过程活动在调用点的机器状态 包括计数器 各种寄存器的值 局部数据 过程中定义的局部量 临时变量 编译产生 返回值 实在参数 控制链 访问链 保存机器状态 局部数据 临时变量 编译时刻的局部数据的设计 PROCEDUREsub x y real VARi j integer a ARRAY 1 5 OFreal e f real BEGIN f e i j END 名字形类型偏移量 x形real1 y形real2 iint20 jint21 a array22 ereal27 freal28 符号表 中间代码 编译结束 知道每个过程的活动记录的长度 将其填写到相应的过程表中 运行时 调用哪个过程 就在运行栈顶 推进那个过程的活动记录 栈箭头加上活动记录长度 f e i j ijt1 et1t2 t2 f 运行时刻存储分配策略 分配策略是 静态分配 栈式分配 或称栈式动态分配 堆式分配 或称堆式动态分配 采用哪种分配策略是由源语言的语义决定的 静态存储分配 静态存储分配 在编译阶段由编译程序实现对存储空间的管理和为源程序中的变量分配存储的方法 静态存储分配的条件如果在编译时能够确定源程序中变量在运行时的数据空间大小 且运行时不改变 那么就可以采用静态存储分配方法 允许局部名字的值在过程停止活动后仍然保持 也就是当控制再次进入程序时 局部名字的值同控制上次离开时一样 还能用控制栈进行控制吗 静态存储分配的局限 在编译时刻知道数据目标的大小和它们在内存位置上的约束 不能递归调用过程 一个过程的两个活动的生存期不相交 一个过程的所有活动可以使用同一个活动记录 不能动态地建立数据结构 静态存储分配策略 CNSUME目标代码 PRDUCE目标代码 Char 50bufintnextcharc Char 80bufferintnext Cnsume活动记录 prduce活动记录 目标代码 静态数据 静态存储分配策略 由于每个变量所需空间的大小在编译时已知 因此可以用简单的方法给变量分配目标地址 开辟一数据区 首地址在加载时定 按编译顺序给每个模块分配存储空间 在模块内部按顺序给模块的变量分配存储 一般用相对地址 所占数据区的大小由变量类型决定 目标地址填入变量的符号表中 动态存储分配 在目标程序运行阶段由目标程序实现对存储空间的组织与管理 和为源程序中的变量分配存储的方法 特点编译时不能具体确定程序所需数据空间编译程序生成有关存储分配的目标代码实际上的分配要在目标程序运行时进行分程序结构 且允许递归调用的语言 栈式动态存储分配 栈式存储分配策略 基于控制栈的原理 存储空间被组织成栈 活动记录的推入和弹出分别对应于活动的开始和结束 与静态分配不同的是 在每次活动中把局部名字和新的存储单元绑定 在活动结束时 活动记录从栈中弹出 因而局部名字的存储空间也随之消失 分配策略 整个数据区为一个堆栈 当进入一个过程时 在栈顶为其分配一个数据区 退出时 撤消过程数据区 Thanksforyourtime Questions Answers