编译原理_第9章.ppt

第九章 运行时存储空间组织 在程序的执行过程中，程序中数据的存取是通 过与之对应的存储单元来进行的 标识符对应的内存地址都是由编译程序在编译时 或由其生成的目标程序运行时进行分配 程序中使用的存储单元都由标识符来表示 第九章 运行时存储空间组织 9.1 目标程序运行时的活动（略） 9.2 运行时存储器的划分 9.3 静态存储分配（略） 9.4 简单的栈式存储分配 9.5 嵌套过程语言的栈式实现 9.6 堆式动态存储分配 9.2 运行时存储器的划分 一、运行时存储器的划分 1.编译器需要在存储区保护的对象 （1）目标代码编译时可确定，故可放在一个静态确定的区域 （2）数据对象部分数据对象的大小在编译时可确定，故也可 放在一个静态确定的区域 （3）跟踪过程活动的控制栈 目标代码 静态数据 栈 ↓ ↑ 堆 2.栈和堆 A.栈：用扩充的栈来管理过程的活动，当发生过程调用时， 中断当前活动的执行，激活新被调用过程的活动， 并把包含在这个活动生存期中的数据对象以及该活 动有关的其它信息存入栈中当控制从调用返回时， 将所占存储空间弹出栈顶同时，被中断的活动恢 复执行 B.堆（heap）——存放动态数据，大小可随程序的运 行而改变。

9.2 运行时存储器的划分 二、活动记录 1.活动记录：为了管理过程在一次执行中所需要的信息，使 用一个连续的存储块，该连续的存储块叫活动记录 当过程调用时，产生一个过程的新的活动，用一个活动记录表 示该活动的相关信息，并将其压入栈 当过程返回时，将该活动记录从栈中弹出 9.2 运行时存储器的划分 2.活动记录的内容 （1）连接数据 SP指向现行过程的活动记录在栈里的起始位置 返回地址 动态链—指向调用该过程前的最新活动记录地址的指针 静态链—指向静态直接外层最新活动记录地址的指针， 用来访问非局部数据. （2）形式单元——存放相应的实在参数的地址或值 （3）局部数据区 局部变量——简单变量 内情向量——局部数据的内情向量，即数组元素 临时工作单元——存放对表达式求值的结果 9.2 运行时存储器的划分 9.2 运行时存储器的划分 三、存储分配策略 1.静态存储分配策略 在编译时对所有数据对象分配固定的存储单元，且 在运行时始终保持不变 2.栈式动态分配策略 在运行时把存储器作为一个栈进行管理，运行时，每当调 用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦 退出，它所占空间就予以释放。

3.堆式动态分配策略 在运行时把存储器组织成堆结构，以便用户关于存储空 间的申请与归还（回收），凡申请者从堆中分给一块，凡释放 者退回给堆. 9.4 简单的栈式存储分配 1.前提：假设程序语言无分程序结构，过程定义不允 许嵌套，但允许过程的递归调用 例如：C 语言 2.过程：运行时 每当进入一个过程 ——即一个新的活动开始，就把其它活动记录压入栈（置 于栈顶），从而形成过程工作时的数据区. 当活动结束 ——即过程退出时，再把其活动记录弹出栈，这样，它在 栈顶上的数据区也随即不复存在. 3.举例 （1）主程序调用过程Q，而Q又调用R， 在R进入运行后的存储结构. 9.4 简单的栈式存储分配 R的活动记录 Q的活动记录 Main的活动记录 全局数据 SP TOP 静态分配 3.举例 （2）主程序调用过程Q，Q递归调用自己，在Q过程 第二次进入运行后的存储结构. 9.4 简单的栈式存储分配 Q2的活动记录 Q1的活动记录 Main的活动记录 全局数据 9.4 简单的栈式存储分配 3.举例 （3）主程序先调用过程Q，然后主程序调用R，且过 程Q不调用Q和R. R的活动记录 Main的活动记 录 全局数据 4.指示器SP——总是指向现行过程活动记录的 起点，用于访问局部数据. 指示器TOP——始终指向（已占用）栈顶单元. 9.4 简单的栈式存储分配 一、C的活动记录 1.C的活动记录的项目 （1）连接数据——A.老SP值: 即前一活动记录的地址 B.返回地址 （2）参数个数 （3）形式单元——存放实在参数的值或地址 （4）过程的局部变量——数组内情向量 ——临时工作单元 临时工作单元 内情向量 简单变量 形式单元 参数个数 返回地址 老SP TOP SP 9.4 简单的栈式存储分配 2.（1）不允许过程嵌套——非局部量仅能出现在源程 序头，可采用静态存储分配，编译时可确定其地址 （2）局部变量或形参在活动记录中的位置确定 即对它们都分配了存储单元，其地址是相对于活动记录 的基地址SP的 绝对地址=活动记录基地址+相对地址 变址访问X[SP] X——代表相对数，即相对于活动记录起点的地址，编译 时可完全确定下来. 9.4 简单的栈式存储分配 二、C的过程调用,过程进入、数组空间分配 和过程返回 已知过程调用的四元式序列为：par T1 … par Tn call P,n 9.4 简单的栈式存储分配 C语言过程调用与返回 Par Ti(i+3)[TOP] := Ti （传值 ） 或 (i+3)[TOP] := addr(Ti)（传地址） Call P,n1[TOP] := SP 3 [TOP] := n JSR P (转P) SP := TOP+1 1[SP] := 返回地址 TOP := TOP + 活动单元数 Return(E)TOP := SP－1 SP := 0[SP] X := 2[TOP] UJ 0[x] /* UJ:无条件转移*/ 9.5 嵌套过程语言的栈式实现 前提：假定允许过程定义嵌套，如Pascal语言， 但去掉Pascal中的“文件。

程序举例：——课本P258 图9.15 一、非局部名字的访问的实现 9.5 嵌套过程语言的栈式实现 1.静态链和活动记录 A.静态链——活动记录的一个域，从一个过程的当前活 动记录指向其静态直接外层的最新活动记录 动态链——活动记录一个域，从一个过程的当前活动记录 指向调用该过程前正在运行的过程的最新的活 动记录的基地址 B.活动记录结构——P259 图9.16 C.程序运行时栈的变化过程—— 举例： i b(形参) 1(形参个数) 0 返回地址 5 i c 0 0 返回地址 0 x a 0 返回地址 0 i c 0(形参个数) 0 返回地址 0 x a 0 返回地址 0 过程S中调 用Q时 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 SP TOP TOP SP 10 9 8 7 6 5 4 3 2 1 0 过程P中 调用S时 d c v(形参) u(形参) 2(形参个数) 11 返回地址 11 i b(形参) 1(形参个数) 0 返回地址 5 i c 0 0 返回地址 0 x a 0 返回地址 0 TOP SP 12 11 10 9 8 7 6 5 4 3 2 1 0 24 23 22 21 20 19 18 17 16 15 14 13 过程Q中调用R时 d c v u 2 11 返回地址 17 d c v(形参) u(形参) 2(形参个数) 11 返回地址 11 i b(形参) 1(形参个数) 0 返回地址 5 i c 0 0 返回地址 0 x a 0 返回地址 0 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 SP TOP 过程R中递归调用R 静态链:通过其值可以找到当前过程/活动可以引用的“非 局部变量”的过程的活动记录的基址，从而找到 要 引用的“非局部变量”。

9.5 嵌套过程语言的栈式实现 动态链:通过其值可以找到当前过程/活动结束后，需要返回的 上一层活动记录的基址SP D.含义： 2.嵌套层次显示表（display）和活动记录 2R的现行活动记录地址（SP的现行值） 1Q的最新活动记录的地址 0P的活动记里的地址 9.5 嵌套过程语言的栈式实现 A.嵌套层次显示表：每进入一个过程后，在建立它的 活动区的同时建立该表 B.表的内容： 举例：令过程R的外层为Q，Q的外层为P，则R运行时display 表为： C.“非局部量”地址的确定： 绝对地址= display[静态层数]+相对地址 D.活动记录结构: P261 图9.18 E.程序运行时栈的变化过程— P262-263 图9.19 TOP a 3 2 1 SP 0 临时单元 内情向量 简单变量 display 形参单元 参数个数 全局Display 返回地址 老SP(动态链) 9.5 嵌套过程语言的栈式实现 9.5 嵌套过程语言的栈式实现 F.静态链方法与显示表方法的比较： 通过显示表访问非局部量要比沿着静态链访问非局部 量的速度快 原因：因为通过显示表的一个域，可以确定任意外层活 动记录的指针，再沿着这个指针便可以找到处于 外层活动记录的非局部量。

9.5 嵌套过程语言的栈式实现 1.par T T——为数组 （1）或者传递数组T的首地址 （2）或者传递数组T的内情向量地址 2.Par TT——为过程 假设：过程P把过程T作为在世在参数传递过程Q，随 后，Q又通过引用相应的形式参数调用T 3.Par T T——为标号 二.参数传递的实现 ⇒ ⇒ 在进入T之后，为了建立T自己的display ，T必须知道它直接 外层的display 又P的display 或者正好就是这个外层的display， 或者包含了这个外层display 而由于T的层数是已知的 ⇒ ⇒ 只要知道P的display，T就可以用它来建立自己的display 即假定T的层数为1，则T的display乃是由P的display的前1个单元的 内容和SP的现行值所组成 ⇒ ⇒ 为了使得过程T工作时能够知道过程P的display，必须在P把T作为实 参传递给Q的时候把P自身的display地址也传过去 即：过程P中的par T的作用可刻画为建立如下所示的两个相继临时单元： 第一个临时单元B1：过程T的入口地址； 第二个临时单元B2：现行的display地址 然后执行（i+1）[TOP]:=addr(B1)把第一临时单元B1的地址传给Q 9.5 嵌套过程语言的栈式实现 2.Par TT——为过程 假定过程Q现在执行到调用语句call Z, m Z—形式参数，形式单元Z中已含有上述B1的地址 ⇒ ⇒ 故B1的内容将用来作为转子指令的目的地址 （即转进过程T） B2的内容将作为“全局display地址” （第三项连接数据）传送给T 9.5 嵌套过程语言的栈式实现 2.Par TT——为过程 9.6 堆式动态存储分配 1.堆式动态存储分配使用的情况 （1）允许用户自由地申请数据空间和退还空间 （2）不仅有过程而且有进程的程序结构 即空间的使用未必服从“先请后还，后请先还”的原则 例如：Pascal语言中的标准过程new-dispose 2.该种分配方法必须考虑的几个主要问题 （1）当运行程序要求一块体积为N的空间时，应该分配哪一块 给它？ （2）如果运行程序要求一块体积为N的空间，但所有空闲块的 总和也不够N，那该怎么办？ 一、堆式动态存储分配的实现 1.定长块管理 （1）实现方法： （2）优点： 占用占用占用空闲空闲空闲 占用空闲占用空闲空闲空闲 available available 9.6 堆式动态存储分配 2.变长块管理 （1）实现方法 （2）实现的非配策略 A.首次满足法 B.最有满足法 C.最差满足法 （3）3种分配策略的比较 A.适用情况 B.时间比较 9.6 堆式动态存储分配 二、隐式存储回收 1.隐式存储回收的要求： 用户程序和支持运行的回收子程序并行工作. 原因:回收子程序需要知道分配给用户程序的存储块 何时不再使用. 2.存储块格式： 块长度 访问计数标记 指针 用户使用空间 9.6 堆式动态存储分配 3.回收过程 （1）标记阶段：对已分配的块跟踪程序中各指针的访问路 径，若。