编译原理课件Chapter10.ppt

1 第十章目标程序运行时的存储组织 10 1概述10 2数据表示 略 10 3目标程序运行时的栈式存储组织10 4参数传递10 5堆式存储组织的讨论 略 2 10 1概述 任务 在目标代码生成之前 编译程序对目标程序的运行环境进行设计和数据空间进行分配 如通常存储空间的典型划分 目标代码区静态数据区StackHeap 3 数据空间的使用方法 存储分配策略 静态存储分配栈式动态存储分配堆式动态存储分配栈式存储分配方案基本思想 运行时每当进入一个过程 就在栈顶为该过程分配所需的数据空间 当一个过程工作完毕之后 它在栈顶的数据空间也将被释放 活动记录 活动记录 活动记录 运行栈 4 例如 voidmain voida voidb a b main a b Main的数据区 函数a的数据区 函数b的数据区 嵌套调用次序后进先出生存期限于本次调用自动释放 5 活动记录 是一个连续的存储区 用以存放一个过程的一次执行所需要的信息 表达式计算所需的临时变量局部数据寄存器 程序计数器 返回地址 保存实在参数的值或地址存放返回值保存调用者活动记录地址用于存取非局部名 访问链 控制链 返回值 实在参数 机器状态 局部变量 临时变量 6 10 3 1简单的栈式分配方案 程序结构特点 过程可递归调用 可含可变数据结构 但不允许嵌套定义 没有分程序结构 例 main main voidR R voidQ Q 7 TOP 始终指向已占用的栈顶单元 SP 总是指向当前执行过程活动记录的起点 8 9 10 3 2嵌套过程语言的栈式存储分配方案 1 主要特点 语言 一个过程可以引用包围它的任一外层过程所定义的标识符 如变量 数组或过程等 实现 一个过程可以引用它的任一外层过程的最新活动记录中的某些数据 10 2 关键技术 解决对非局部变量的引用 存取 也就是说 设法跟踪每个外层过程的最新活动记录AR的位置 3 跟踪办法 1 用静态链 存取链 如PL 0的SL 2 用DISPLAY表 11 目标代码解释执行时数据栈的布局 运行栈的存储分配 每个过程的AR有3个联系单元 SL 静态链 存取链 指向定义该过程的直接外过程 或主程序 运行时最新活动记录的基地址 DL 动态链 控制链 指向调用该过程前正在运行过程的数据段基地址 RA 返回地址 记录调用该过程时目标程序的断点 即调用过程指令的下一条指令的地址 局部变量中间结果 12 consta 10 varb c procedurep beginc b a end begin main read b whileb 0dobegincallp write 2 c read b endend main 0 jmp08转向主程序入口 1 jmp02转向过程p入口 2 int03过程p入口 为过程p开辟空间 3 lod13取变量b的值到栈顶 4 lit010取常数10到栈顶 5 opr02次栈顶与栈顶相加 6 sto14栈顶值送变量c中 7 opr00退栈并返回调用点 16 8 int05主程序入口开辟5个栈空间 9 opr016从命令行读入值置于栈顶 10 sto03将栈顶值存入变量b中 11 lod03将变量b的值取至栈顶 12 lit00将常数值0进栈 13 opr09次栈顶与栈顶是否不等 14 jpc024等时转 24 条件不满足转 15 cal02调用过程p 16 lit02常数值2进栈 17 lod04将变量c的值取至栈顶 18 opr04次栈顶与栈顶相乘 2 c 19 opr014栈顶值输出至屏幕 20 opr015换行 21 opr016从命令行读取值到栈顶 22 sto03栈顶值送变量b中 23 jmp011无条件转到循环入口 11 24 opr00结束退栈 13 目标代码的解释执行运行栈 M调用过程PS RADLSL b t t b P M 14 解决对非局部变量的引用 存取 用Display表 Display表 嵌套层次显示表当前执行过程的层次为K 主程序层为0层 它的Display表含有K 1个单元 依次存放着现行层 直接外层 定义外层 直至最外层的每一过程的最新活动记录的基地址 15 例 programsort procreadarray end readarray procexchange end exchange procquicksort procpartition end partition end quicksort end sort 程序结构图Sortreadarrayexchangequicksortpartition 16 用Display表的方案 1 sort 2 quicksort 3 partition 4 exchange d 1 2 d 0 sp display top 1 sort的活动记录 sp display top d 0 17 用Display表的方案 1 sort 2 quicksort 3 partition 4 exchange 3 d 2 sp sort的活动记录 quicksort的活动记录 partition的活动记录 top d 1 d 0 4 sp top d 0 d 1 18 DISPLAY表的维护和建立 当过程的层次为n 它的DISPLAY为n 1个值 一个过程被调用时 从调用过程的DISPLAY表中自下向上抄录n个SP值 再加上本层的SP值 全局DISPLAY地址 19 10 3 3分程序结构的存储分配方案 处理分程序结构存储分配方案的一种简单办法是 把分程序看成 无名无参过程 它在哪里定义就在哪里被调用 因此 可以把处理过程的存储办法应用到处理分程序中 但这种做法是极为低效的 1 每逢进入一个分程序 就照样建立连接数据和DISPLAY表 这是不必要的 2 当从内层分程序向外层转移时 可能同时要结束若干个分程序 20 按照过程处理办法 意味着必须一层一层地通过 返回 来恢复所要到达的那个分程序的数据区 但不能直接到达 例如 如果有一个从第5层分程序转出到达第1层分程序的标号L 虽然在第5层分程序工作时知道L所属的层数 我们极易从DISPLAY中获得第1层分程序的活动记录基址 SP 但是怎么知道第1层分程序进入时的TOP呢 唯一的办法是从5 4 3和2各层顺序退出 但这种办法是很浪费时间的 21 为了解决上述问题 可采取两种措施 第一 对每个过程或分程序都建立有自己的栈顶指示器TOP 代替原来仅有过程的栈顶指示器 每个TOP的值保存在各自活动记录中 这样 上述的第二个问题便可解决 第二 不把分程序看作 无参过程 每个分程序享用包围它的那个最近过程的DISPLAY 每个分程序都隶属于某个确定的过程 分程序的层次是相对于它所属的那个过程进行编号的 22 每个过程被当作是0层分程序 而过程体分程序 假定是一个分程序 当作是它所管辖的第1层分程序 这样 每个过程的活动记录所含的内容有 1 过程的TOP值 它指向过程活动记录的栈顶位置 2 连接数据 共四项 1 老SP值 2 返回地址 3 全局DISPAY地址 4 调用时的栈顶单元地址 老TOP 23 3 参数个数和形式单元4 DISPAY表 5 过程所辖的各分程序的局部数据单元 对于每个分程序来说 它们包括 1 分程序的TOP值 当进入分程序时它含现行栈顶地址 以后 用来定义栈的新高度 分程序的TOP值 2 分程序的局部变量 数组内情向量和临时工作单元 24 25 Z T O 26 DISPLAY DISPLAY 形式单元 m n 2 形式单元 m n 2 连 接 数 据 连接 数 据 A 的 TOP A 的 TOP c d c 数组 B 分配之后 d 进入分程序 B2 2 27 28 10 4参数传递 A 传值调用call by value过程调用时计算实参 将值存到活动记录形式参数绑定于活动记录的实在参数域例 C语言 Pascal语言的值参 29 传值的实现 1 形式参数当作过程的局部变量处理 即在被调过程的活动记录中开辟了形参的存储空间 这些存储位置即是我们所说的形式单元 用以存放实参 2 调用过程计算实参的值 并将其放在对应形式单元开辟的空间中 3 被调用过程执行时 就像使用局部变量一样使用这些形式单元 30 传值调用例题 voidinc2 intx x x voidmain inta 1 inc2 a 31 B 传地址调用call by address实际上 形参是实参的别名 alias 如果实在参数具有左值 则存放其左值到活动记录中 否则按传值处理表达式的左值 处于赋值符左侧时表示的存储地址表达式的右值 处于赋值符右侧时表示的值例 Pascal语言的变参 C C 语言的引用类型 32 传地址的实现 1实在参数是一个名字 或具有左值的表达式 a b c 传递左值2实在参数是无左值的表达式 计算值 放入一存储单元 传此存储单元地址3目标代码中 被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用 33 传地址调用例题 voidinc2 int x x x voidmain inta 1 inc2 34 C 传值结果调用call by result实际上 不把形参作为实参的别名在函数中复制和使用实参的值到形参 返回时 将形参的终值复制回实参例 Ada的传入 in 和传出 out 的参数机制 35 传值结果调用例题 voidp intx inty x y voidmain inta 1 p a a 传地址 a为3 传值结果 a为2不确定性 参数传递次序 36 d 传名字调用call by name即换名 将形参名字换成实参名字延迟赋值 delayedevaluation 太复杂 已被传地址取代 有些老师把 传地址 误以为 换名 采用的语言 ALGOL60例 voidp intx x 若调用p a i 结果是计算 a i 37 又例 inti inta 10 voidp intx i i 2 x a 2 3 voidmain i 1 a 1 1 a 2 2 p a i 结果 置a 2 为3 而a 1 不变 38 voidP intx inty intz y y 3 z z x voidmain inta 5 b 2 p a b a a printf d n a 若参数传递方法