哈工大编译原理第7章.ppt

1 第七章运行时刻环境 2 序7 1源语言中的一些问题7 2存储组织7 3运行时刻存储分配策略7 4非局部名字的访问7 5符号表 3 序计算环境运行时的环境计算目标代码 映射 源程序 源程序中的名字 常量 变量 目标机存储空间 它受命于源程序的执行语义 源程序由一组过程按某种规则组成 过程的一次执行称作一次活动 4 在过程的语句序列执行之前 过程中访问的对象构成此过程的运行环境 由运行支持程序组织好 PROCEDUREsub x y real VARi j integer a ARRAY 1 5 OFreal e f real BEGIN f e i j END 5 f 符号表 名字形类型偏移量 活动记录布局 老SP sp 0 x形real3 返回地址 sp 1 y形real4 2 sp 2 sp 3 sp 5 iint5 i sp 9 jint9 j sp 13 a array13 a sp 53 e ereal53 sp 61 freal61 sp 4 x y t1 t2 t3 sp 62 sp 63 sp 64 6 中间代码 ijt1 sp 20 sp 21 sp 29 et1t2 sp 27 sp 29 sp 30 itort2 t3itor sp 30 sp 31 t3 f sp 31 sp 28 确定活动记录中局部数据的地址 假设sp标记一个活动记录的开始的位置 dx表示x的地址相对于sp的偏移量 那么 x在过程的目标代码中的地址可写成dx sp 7 7 1有关源程序中的一些问题目的 构造运行程序的策略和方法1 1过程1 2活动树1 3控制栈1 4说明的作用域1 5名字的绑定1 6参数传递1 7构造运行程序和源程序有关的一些问题 8 1 1过程 构成源程序的两个过程行文 源程序由一组过程组成 不同的程序设计语言 由过程构成源程序的方法不同 要么是嵌套的 要么是平行的 9 1 2活动树 程序执行期间的控制流 1 程序执行的控制是顺序的 2 过程的每一次执行都是从过程体的开头开始 并最终把控制返回到紧接着该过程被调用点的后面 10 一个过程p的一次活动的生存期 main P 其中包括执行过程p所调用的过程的执行时间 以及这些过程所调用的过程的执行时间 如此等等 在该过程体第一步到最后一步之间的语句的执行时间 p 11 这种活动生存期的嵌套性质可以通过在每一个过程中插入两个打印语句来加以跟踪 2 如果a和b是两个过程活动 那么它们的生存期要么是并列的 要么是嵌套的 控制流的特点 1 每当控制流从过程p的活动进入到过程q的活动中后 它将返回到过程p的同一次活动中 12 programsort input output vara array 0 10 ofinteger procedurereadarray vari integer begin end functionpartition y z integer integer vari j x v integer begin end procedurequicksort m n integer vari integer beginend end begin end 程序见P254页 13 执行开始enterreadarrayleavereadarrayenterquicksort 1 9 enterpartition 1 9 leavepartition l 9 enterquicksort 1 3 leavequicksort 1 3 enterquicksort 5 9 leavequicksort 5 9 leavequicksort 1 9 执行结束 这是递归调用 14 递归 一个过程是递归的 如果同一过程的一次新的活动可以在前面活动结束以前开始 活动树 在一棵活动树中 2 根结点代表主程序的活动 3 代表a的结点是b结点的父结点当且仅当控制从活动a进入活动b 4 结点a在结点b的左边当且仅当a的生存期发生在b的生存期之前 用一颗树来描绘控制进入和离开活动的途径 这样的树称作活动树 1 每一个结点代表一个过程的活动 15 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 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 8 q 9 9 16 结论 且每一个活动只有一个结点表示 当控制进入某一个活动时 可以直接说 控制在这个结点上 一个结点代表一个唯一的活动 17 1 3控制栈 因此 用一个栈保存过程活动的生存踪迹 程序执行的控制流对应于从根开始 按先根次序遍历活动树 当一个活动开始执行时 把代表这个活动的结点推进栈 当这个活动结束时 把代表这个活动的结点从栈中弹出 18 例2栈和活动树的变化 栈 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 19 结点序列 s q 1 9 q l 3 q 2 3 控制栈中的活动都是活跃的 从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系 从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的节点 当前控制进入的活动在栈顶 20 结论 扩充控制栈可用来实现如Pascal语言的栈式存储分配 进入一个活动 在栈顶建立这个活动所使用的存储空间 这个活动结束 从栈顶弹出其使用的存储空间 21 一个名字在源程序行文中可能有几处说明 语言的作用域规则规定了 1 说明把名字与名字的属性信息绑定在一起 1 4说明的作用域 2 说明的作用域是一个说明起作用的范围 源程序行文 如 局部变量 全局变量 Inta 10 在语句序列中引用的一个名字是在何处说明的名字 22 3 编译时 处理说明语句时 把名字及其属性信息填写进符号表 add id entry id vul 处理引用名字时 查找这个名字的属性信息 lookup id 符号表管理程序根据语言的作用域规则 使lookup id 返回id的作用域中绑定的属性信息 23 可以说 函数environment把一个名字映射为一个l value 左 值 1 5名字与存储的绑定 引进两个函数 environment和state environment把名字映射到一个存储单元上 state把存储单元映射到那里所存放的值上 而函数state把一个l value 左 值 映射为一个r value 右 值 如下图所示 名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程 24 名字 存储单元 值 存储分配 程序运行 environment state l value r value 图 从名字到值的两个阶段映射 25 静态概念动态对应过程定义过程活动名字说明名字的绑定说明的作用域活动的生存期 1 6参数传递 实在参数和形式参数结合的方法 传值调用 call by value 引用调用 call by reference 复制恢复 copy restore 传名调用 call by name 27 1 7提出的问题 编译程序组织存储分配所采用策略和方法主要取决于对源程序中下面的问题的回答 1 过程可以是递归的吗 2 当控制从过程的一次活动返回时 局部名的值将发生什么变化 3 一个过程可以访问非局部名吗 4 当调用过程时参数是怎样传递的 28 上面的问题对运行时的存贮分配有很大的影响 5 过程可以作为参数被传递吗 6 过程可以作为结果被返回吗 7 可以在程序控制下进行动态存储分配吗 8 显式的存储重新分配 指撤除分配后的分配 是必须的吗 我们将在后面章节里 对以上问题进行讨论并介绍与之相应的存贮分配策略 29 7 2存储组织 2 1运行时刻内存的划分 运行时刻的存储空间必须划分成块 用来存放 1 生成的目标代码 2 数据目标 3 用于保存过程活动踪迹的一个控制栈 30 目标代码 静态数据 栈 堆 1 编译后知道目标代码的大小 存储空间划分的各部分 2 Pascal c Fortran 3 栈 Pascal c 4 堆 Pascal c 31 2 2活动记录 对于pascal语言来说 运行过程中 当调用一个过程时 在栈顶构筑它的活动记录 一个活动所需要的信息的每个数据项有相同的生存期 因此 组织成一个活动记录是很自然的 当这个过程的活动执行完后 把它从栈顶弹出 把过程的一个活动所需要的信息组织成一块连续的存储单元 称为活动记录 32 源语言不同 实现方法不同 组成活动记录的域不同 常见语言的活动记录如后图所示 33 返回值 实在参数 控制链 访问链 保存机器状态 局部变量 临时变量 临时变量 编译产生 保存机器状态 调用过程的活动在调用点的机器状态 包括计数器 各种寄存器的值 局部数据 过程中定义的局部量 访问链 指向本活动要访问的非局部数据所在的活动记录 控制链 指向主调过程的活动记录的首地址 形式单元 内情向量 连接数据 局部数据 sp top 34 2 3编译时刻的局部数据的设计局部数据域是编译时刻在编译过程中分配的 例如 PROCEDUREsub x y real VARi j integer a ARRAY 1 5 OFreal e f real BEGIN f e i j END 名字所需的存贮空间的数量是由它的类型确定的 多字节对象存放于连续的字节中 以第一个字节的地址作为该对象的地址 35 f 符号表 名字形类型偏移量 活动记录布局 老SP sp 0 x形real3 返回地址 sp 1 y形real4 2 sp 2 sp 3 sp 5 iint5 i sp 9 jint9 j sp 13 a array13 a sp 53 e ereal53 sp 61 freal61 sp 4 x y t1 t2 t3 sp 62 sp 63 sp 64 36 中间代码 ijt1 sp 5 sp 9 sp 62 et1t2 sp 53 sp 62 sp 63 itort2 t3itor sp 63 sp 64 t3 f sp 64 sp 61 确定活动记录中局部数据的地址 假设sp标记一个活动记录的开始的位置 dx表示x的地址相对于sp的偏移量 那么 x在过程的目标代码中的地址可写成dx sp 37 编译结束 知道每个过程的活动记录的长度 将其填写到相应的过程表中 运行时 调用哪个过程 就在运行栈顶 推进那个过程的活动记录 栈箭头加上活动记录长度 38 7 3运行时刻存储分配策略 3 1静态存储分配 FORTRAN3 2栈式存储分配 C PASCAL3 3堆式存储分配 C PASCAL 采用哪种分配策略是由源语言的语义决定的 39 3 1静态存储分配 局部名字的值在过程活动停止后仍保留下来 且这种绑定在运行时刻不再发生变化 在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置 40 限制 1 在编译时刻知道数据目标的大小和它们在内存位置上约束 2 不能递归调用过程 一个过程的两个活动的生存期不相交 一个过程的所有活动可以使用同一个活动记录 3 不能动态地建立数据结构 41 1 PROGRAMCNSUME 2 CHARACTER 50BUF 3 INTEGERNEXT 4 CHARACTERC PRDUCE 5 DATANEXT 1 BUF 6 C PRDUCE 7 BUF NEXT NEXT C 8 NEXT NEXT 1 9 IF C NE GOTO6 10 WRITE A BUF 11 END 42 12 CHARACTERFUNCTIONPRDUCE 13 CHARACTER 80BUFFER 14 INTEGERNEXT 15 SAVEBUFFER NEXT 16 DATANEXT 81 17 IF NEXT GT 80 THEN 18 READ A BUFFER 19 NEXT 1 20 ENDIF 21 PRDUCE BUFFER NEXT NEXT 22 NEXT NEXT 1 23 END一个Fortran77程序 43 CNSUME目标代码 PRDUCE目标代码 Char 50bufintnextcharc Char 80bufferintnext Cnsume活动记录 prduce活动记录 目标代码 静态数据 44 与静态分配不同的是 基于控制栈的原理 3 2栈式存储分配 活动记录的推人和弹出 存储空间被组织成栈 分别对应于活动的开始和结束 在每次活动中把局部名字和新的存储单元绑定 在活动结束时 活动记录从栈中弹出 因而局部名字的存储空间也随之消失 45 图6 11表明当控制流通过图的活动树时 活动记录被推入或弹出运行时刻的栈中的情况 设寄存器top标记栈顶 46 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 p 5 9 q 5 5 q 7 9 p 7 9 q 7 7 图6 3一棵活动树 q 9 9 47 s Sa array top r ri integer top top q 1 9 q 1 9 i integer top p 1 9 p 1 9 i integer top top q 1 3 q 1 3 i integer top 图6 11栈式分配活动记录在栈中的变化 48 3 2 1简单栈式存贮分配 条件 C满足上述条件 C程序结构 全局数据说明Main Main数据说明 VoidR R数据说明 VoidQ Q数据说明 不允许嵌套定义 允许递归调用 49 假设调用顺序为 对于全局数据 main的活动记录 全局数据区 Q的活动记录 R的活动记录 top sp 是可以静态确定的 因此在编译时就可确定这些非局部数据的存贮分配 main Q R 则程序运行时存贮组织为 50 C的活动记录 有四个项目 1 连接数据老SP 主调过程活动记录首址返回地址 2 参数个数 3 形参单元 4 过程的局部变量 数组内情向量和临时工作单元 51 C的活动记录 老SP 返回地址 参数个数n 形式单元 简单变量 内情向量 临时工作单元 SP TOP 变量和形参运行时的绝对地址是 绝对地址 活动记录首地址 相对地址 2 0 1 2 i 2 sp 或 i 3 top 54 52 目标代码 调用序列 完成任务 C的过程调用 1 调用者对实在参数求值 过程语句p e1 e2 en 过程进入 数组空间分配 和过程返回时刻的存贮管理 并把它们传送给被调用过程的活动记录的参数域 53 4 被调用者初始化其局部数据并开始执行 3 被调用者存放寄存器值和其它状态信息 2 调用者在被调用者的活动记录中存放返回地址和老sp之值 之后调用者改变TOP的值 54 过程调用四元式 Part1 PartnCallp n Par和call产生的目标代码 Parti 因为形式单元与活动记录首地址之间的距离是确定的 为 i 3 top ti 传值 i 3 top addr ti 传地址 此工作由主调过程完成 具体实现方法 51 55 四元式callp n应翻译成 top sp 保护现行 top n 传送参数个数 jsrp 转向 的第一条指令 转入 后 建立自己的新的活动记录 SP top 11 sp 返回地址top top L L为 的活动记录所需单元数 56 返回序列 return目标代码完成的任务是 1 被调用者将返回值放入临近主调者的活动记录的地方 2 利用状态域中的信息 被调用者恢复sp和其它寄存器 并且按返回地址转移到调用者的代码之中 3 调用者复制返回值到自己的活动记录中 57 返回语句 return E E为返回值 放在临时单元 中 接下来恢复调用现场 top sp 1sp 0 sp x 2 top Uj0 x 首先 将 送入特定寄存器 58 任务的划分 根据源语言 目标机器和操作系统等具体情况而定 上述任务 由运行支持子程序完成 可视为虚机指令 59 Programp Vara x integerBegina 0 S end ProcedureQ b integer Vari integer Begin R 1 x end ProcedureR u integer varv integer Varc d integer BeginIfu 1thenR u 1 v v a c b d end ProcedureSVarc i integer Begina 1 Q c end 1 2 2 3 3 2 2嵌套过程语言的栈式实现 60 嵌套深度 主程序为1 过程S和R都引用了最外层过程说明的a 一 非局部名字的访问的实现 局部变量和形参可以用上节的方法处理 非局部名字的访问所要解决的问题就是 过程Q引用了最外层过程说明的x 而R又引用了其直接说明的变量b 如何找到所有外层过程活动记录的地址 61 常用跟踪外层过程最新活动记录的方法有两种 访问链 1 访问链和活动记录 访问链为活动记录的一个域 控制链 老SP 返回地址 访问链 形参个数 形参单元 临时单元内情向量简单变量 SP TOP 和显示表 Display表 它是从一个过程当前活动记录 指向其直接外层的最新活动记录 的一个指针 62 从P开始执行 过程P调用S 4x3a201返回地址00 Top Sp 过程P的活动记录 ic0 形参个数 70 访问链 6返回地址50 控制链 过程S的活动记录 Top Sp 63 16i15b 形参 141 形参个数 130 访问链 12返回地址115 控制链 过程S调用Q时 过程Q的活动记录 Top Sp 控 24d23c22v 形参 21u 形参 202 形参个数 1911 访问链 18返回地址1711 控制链 过程Q调用R 过程R的活动记录 Top Sp 64 过程R递归调用R 32d31c30v 形参 29u 形参 282 形参个数 2711 访问链 26返回地址2517 控制链 过程R的活动记录 Top Sp 65 2 嵌套层次显示表 display 和活动记录 嵌套层次显示表 display 是一个指针数组 假设当前运行的过程的层数为i 当前运行过程为R 则D表内容为 3R的活动记录首地址2Q的活动记录首地址1P的活动记录首地址 数组的元素指向现行层 直接外层 直至最外层 1层 的最新活动记录的首地址 则嵌套层次显示表 display 含有i个单无 66 由一个非局部变量说明所在的静态层数和相对活动记录的相对地址 活动记录结构 临时变量内情向量简单变量Display形参单元形参个数全局display返回地址控制链 老SP 就可得到绝对地址 绝对地址 display 静态层数 相对地址 top d321sp 0 67 假定在现行过程中引用了某一外层k的变量x 如何建立D表 则获得x的值的指令如下 LDR1 d k SP LDR2 X R1 P1调用P2的嵌套可能为如下两种情况 68 假定P2的嵌套深度为k2 对应于 a 情况 P1的嵌套深度为k2 1 P1的D表长度为k2 1P2的D表长度为k2 此时的D表内容为 P1的D表 P2自已的SP 69 对应于 b 情况 P1的嵌套深度也为k2 此时的D表内容为 P1的D表的前k2 1项 P2自已的SP P1 P2的D表长度都为k2 70 只需从P1的D表中自底向上取k2 1个单元 因此只需把P1的D表地址作为连接数据传给P2即可 只要知道主调过程P1的D表 就可以建立P2的D表 再填上P2自己的SP值 就构成了P2的D表 连接数据变为 老SP返回地址全局D表地址 当P1调用P2时 综合以上两种情况 71 4x3a20 D表 1返回地址00 Top Sp 过程P的活动记录 过程P中调用S时的分析栈及D表内容 12i11c105 S的0D表 0 形参个数 72 全局D表 6返回地址50 控制链 Top Sp 过程S的活动记录 72 1913 Q的180D表 17b 形参 161 形参个数 159 全局D表 14返回地址135 控制链 过程Q的活动记录 过程S中调用Q时的分析栈及Q表内容 Top Sp 30dc2820 R的2713260D表 25v 形参 24u 形参 232 形参个数 2218 全局D表 21返回地址2013 控制链 过程Q中调用R时的分析栈及R表内容 Top Sp 过程R的活动记录 73 过程R中递归调用R时的分析栈及R表内容 过程R的活动记录 41d40c3931 R的3813370D表 36v 形参 35u 形参 342 形参个数 3318 全局D表 32返回地址3113 控制链 Top Sp 74 3 2 3可变长度的数据 源程序的例子PROCEDUREexam l m n integer VARa array 1 l ofreal b array 1 m ofreal c array 1 n ofreal BEGIN END 75 编译时 不知a b c的大小 仅对每个数组设置一个指针 76 Controllink a b c sp top Arraya Arrayb Arrayc top P的活动记录 P的动态数组 图6 13动态分配的数组 77 3 3堆式存储分配 通常使用一种称之为堆的动态存贮分配方案 适应上述的存贮需求 1 局部名的值在活动结束时必须被保存 2 被调用者的活动生存期超过调用者 3 new p dispose p 用活动树不能够正确描绘这种语言的过程之间的控制流 78 堆是一片足够大的存贮空间 每当需要时 就从这片空间中分配一块 用完时 再归还给堆 79 存贮映象 XWYZ WXYz 80 存在的问题 1 如何分配 2 如何解决碎片问题 3 空闲块不够分配 81 堆式动态存贮分配的实现 一 定长块管理 将堆空间划分成等长的若干块 按照相邻的顺序把所有的块链成一个链表 指针available指向第一块 分配时每次都分配指针availa