《编译原理(第2版)第八章》由会员分享，可在线阅读，更多相关《编译原理(第2版)第八章（62页珍藏版）》请在金锄头文库上搜索。
1、第八章 目标程序运行时的 组织8.1 概述 8.2 数据表示 8.3 目标程序运行时的栈式存储组织 8.4 参数传递 8.5 堆式存储概述概述-代码生成解决语义gap高级语言支持的概念 Type value expression Variable procedure Function parameters目标机支持的概念bits bytes words Registers Stack address Routine(sub routine)概述代码生成前如何安排目标机资源 运行时组织的几个问题 数据表示-如何在目标机中表示每个源语言类型的值 表达式求值-如何组织表达式的计算 存储分配-如何组织
2、不同作用域变量的存储 过程实现-如何以例程实现过程，函数，参数传递概述任务：编译程序对目标程序运行时的组织（设 计运行环境和分配存储） 如 通常存储区布 局可为：目标代码区静态数据区Stackheap运行环境和存储分配 设计分析逻辑阶段：在目标代码生成前，作准备 实质： 关联（Binding） 将源程序的文本 程序运行动作的实现源文件中的名字N 运行时的存储S在语义学中，使用术语environment函数表示 env: NS (N到S的映射)决定运行管理复杂程度的因素源语言本身 1. 允许的数据类型的多少 2语言中允许的数据项是 静态确定动态确定 3程序结构 决定名字的作用域的规则和结构 A
3、段结构(Fortran) B 过程定义不嵌套，只允许过程递归调用 C 分程序结构 分程序嵌套 过程定义嵌套4存储类别的多少Global Static Local dynamic术语 静态：如果一个名字的性质通过说明语句 或隐或显规则而定义，则称这种性质是“ 静态”确定的。 动态：如果名字的性质只有在程序运行时 才能知道，则称这种性质为“动态”确定的 。 例 procedure A(m,n:integer); begin real z; array Bm:n; begin end; end;数据表示各种数据对象的存储分配数据对象的属性name 名字，名称type 类型location 内存地址v
4、alue 值component 成分数据表示简单变量：char: 1 byte integers: 2 or 4 bytes floats: 4 to 16 bytes booleans: 1 bit (but usually 1 byte) 指针：unsigned integers一维数组：一块连续的存储区 多维数组：一块连续的存储区，按行存放 结构（记录）：把所有域（field)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储 区，但方法（成员函数）不存在该对象里 指令：目标程序运行时的存储组织存储分配策略：简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储
5、分配方案堆式存储静态存储分配动态存储分配栈式 堆式术语-过程活动记录AR:为说明方便，假定源程序是由过程组成，运行时称作过程的激活。一个过程的一次执行所需要的信息使用一个连续的存储区来 管理，这个区 （块）叫做一个活动记录AR或 frame帧 一般这个段要记录： l 临时值，如计算表达式时的中间工作单元。 l 局部变量（数据） l 保存运行过程前的状态（返回地址，寄存器值） l 存取链（可选） 对于非局部量的引用。 l 控制链（可选） 指向调用者的活动记录，释放栈。 l 实参（形式单元） l 返回值（对函数）（有时可使用寄存器存放返回值）简单的栈式分配方案 程序结构特点:过程定义不嵌套，过程
6、可递归调用，含可变数组; 例: main 全局变量的说明 proc R end R; proc Q end Q; 主程序执行语句 end main嵌套过程语言的栈式 分配方案l主要特点： （语言）一个过程可以引用包围它的任 一外层过程所定义的标识符（如变量， 数组或过程等）。 （实现）一个过程执行时可以引用它的 任一外层过程的最新活动记录中的某些 数据。 关键技术：解决对非局部量的引用（存 取）。 设法跟踪每个外层过程的最新活动记录 AR的位置。 跟踪办法：1. 用静态链（如PL/0的SL）。2. 用嵌套层次显示表DISPLAY。const a=10; var b,c; procedure p
7、;beginc:=b+a;end; beginread(b);while b#0 dobegincall p;write(2*c);read(b);end end.( 0) jmp 0 8 转向主程序入口 ( 1) jmp 0 2 转向过程p入口 ( 2) int 0 3 过程p入口,为过程p开辟空间 ( 3) lod 1 3 取变量b的值到栈顶 ( 4) lit 0 10 取常数10到栈顶 ( 5) opr 0 2 次栈顶与栈顶相加 ( 6) sto 1 4 栈顶值送变量c中 ( 7) opr 0 0 退栈并返回调用点(16) ( 8) int 0 5 主程序入口开辟5个栈空间 ( 9) o
8、pr 0 16 从命令行读入值置于栈顶 (10) sto 0 3 将栈顶值存入变量b中 (11) lod 0 3 将变量b的值取至栈顶 (12) lit 0 0 将常数值0进栈 (13) opr 0 9 次栈顶与栈顶是否不等 (14) jpc 0 24 等时转(24)（条件不满足转） (15) cal 0 2 调用过程p (16) lit 0 2 常数值2进栈 (17) lod 0 4 将变量c的值取至栈顶 (18) opr 0 4 次栈顶与栈顶相乘(2*c) (19) opr 0 14 栈顶值输出至屏幕 (20) opr 0 15 换行 (21) opr 0 16 从命令行读取值到栈顶 (2
9、2) sto 0 3 栈顶值送变量b中 (23) jmp 0 11 无条件转到循环入口(11) (24) opr 0 0 结束退栈目标代码解释执行时数据栈的布 局（运行栈的存储分配） 每个过程的AR有 3个联系单元： SL： 静态链，指向定义该过程的直接外过程 （或主程序）运行时最新数据段的基地 址。 DL： 动态链，指向调用该过程前正在运行过 程的数据段基地址。 RA： 返回地址，记录调用该过程时目标程序 的断点，即调用过程指令的下一条指令的地 址。 局部变量 中间结果目标代码的解释执行 运行栈 S M调用过程PRADLSLb. . ttbPM解决对非局部量的引用（存取） 用Display表
10、Display表-嵌套层次显示表 当前激活过程的层次为K，它的Display表含有K+1个单元，依次 存放着现行层，直接外层直至最外层的每一过程的最新活动 记录的基地址用Display表的方案(1)主程序-(2)P-(3)Q-(4)RP 的 活动记录 主程序的 活动记录d1d0displaysptop主程序的 活动记录d0spdisplaytop（1）（2）用Display表的方案 主程序-P-Q-RR 的 活动记录 Q 的 活动记录P 的 活动记录 主程序的 活动记录Q 的 活动记录P 的 活动记录 主程序的 活动记录display d2 d1 d0d1 d0displaysptoptops
11、p（3）（4）DISPLAY表的维护和建立 不放在过程的活动记录中 放在过程的活动记录中 当过程的层次为n， 它的 display为n+1个 值。 一个过程被调用时， 从调用过程的 DISPLAY表中自下向 上抄录n个SP值，再加 上本层的SP值。 全局DISPLAY地址栈式存储组织review数据空间的存储管理：栈式存储分配 过程(函数)的活动记录：是一段连续的存储区，存放 过程(函数)的一次执行所需要的信息。 过程(函数)活动记录的内容：联系单元（静态链,动态 链和返回地址）、局部变量和临时变量 栈式存储分配的实现： 设置两个指针：栈顶指针Top和当前活动记录指针SP； 调用一个过程(函数
12、)前，先把过程(函数)的参数压入数据栈 ； 在数据栈中为过程(函数)的活动记录分配空间； 填写联系单元内容； 执行过程(函数)代码； 过程(函数)返回前，根据当前SP恢复Top指针，根据动态链 恢复SP为外层过程(函数)的活动记录起始地址，根据返回地 址得到下一条指令地址； 继续执行外层过程(函数)代码。过程的活动记录(AR)CPL0 临时工作单 位局部变量机器状态信息 存取链 控制链 实参 返回地址过程R的活动记 录 过程Q的活动 记录 过程P的活动记 录 主程序全局数 据区分程序结构 Procedure A(m,n); integer m,n;B1:begin real z; array
13、Bm:n; B2:begin real d, e; L3: 2end;B4:begin array C1:m; 1 B5:begin real e; L6: 5 4end;end;L8:end; 分程序结构的存储 分配方案处理分程序结构存储分配方案的一种 简单办法是，把分程序看成 “无名无参过 程”，它在哪里定义就在哪里被调用。因 此，可以把处理过程的存储办法应用到 处理分程序中。但这种做法是极为低效 的。一则，每逢进入 一个分程序，就照样建 立连接数据和DISPLAY表,这是不必要的 。 二则 ，当从内层分程序向外层转移时 ，可能同时要结束若干个分程序。按照过程处理办法，意味着必须一 层一层
14、地通过“返回” 来恢复所要到达 的那个分程序的数据区，但不能直接到 达。 例如：如果有一个从第5层分程序转出到 达第1层分程序的标号L，虽然在第5层 分程序工作时知道L所属的层数，我们 极易从DISPLAY中获得第1层分程序的 活动记录基址（SP），但是怎么知道第 1层分程序进入时的TOP呢？唯一的办 法是从 5,4,3和2各层顺序退出。但这种 办法是很浪费时间的。为了解决上述问题，可采取两种措施。第 一，对每个过程或分程序都建立有自己 的栈顶指示器TOP，代替原来仅有过程 的栈顶指示器, 每个TOP的值保存在各 自活动记录中。这样，上述的第二个问 题便可解决。第二，不把分程序看作“ 无参过程
15、”，每个分程序享用包围它的 那个最近过程的DISPLAY。每个分程 序都隶属于某个确定的过程，分程序的 层次是相对于它所属的那个过程进行编 号的。：每个过程被当作是0层分程序。而过程 体分程序（假定是一个分程序）当作是 它所管辖的第1层分程序。这样，每个过程的活动记录所含的内容有 ： 1.过程的TOP值，它指向过程活动记录的 栈顶位置。 2.连接数据，共四项： （1)老SP值； （2)返回地址；(3)全局DISPAY地址； （4)调用时的栈顶单元地址，老TOP。3. 参数个数和形式单元 4. DISPAY表。 5. 过程所辖的各分程序的局部数据单元 。 对于每个分程序来说，它们包括： （1)分程序的TOP值。当进入分程序时它 含现行栈顶地址，以后，用来定义栈的 新高度（分程序的TOP值）； （2)分程序的局部变量， 数组内情向量 和临时工作单元。参数传递(1)procedure exchangel(i,j:integer); (2) va
