编译原理,清华大学,第2版-第10章目标程序运行时的存储组织讲述.ppt

第10章 目标程序运行时的组织 教学要求：本章介绍目标程序运行时的存储组织方式，包括静态存储分配和动态存储分配。 要求掌握各种存储组织形式的基本方法。 教学重点：静态分配策略和动态分配策略的基本思想，嵌套过程语言栈式分配，活动记录、运行时栈的组织。 10.1 概述 从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配 数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织输入/输出所需的缓冲区。 存储管理复杂度取决于源语言本身，具体包括： 允许的数据类型的多少? 语言中允许的数据项是: 静态确定?动态确定? 程序决定名字的作用域的规则和结构 段结构? 过程定义不嵌套?只允许过程递归调用? 分程序结构: 分程序嵌套?过程定义嵌套? 2、存储分配策略： （1）静态存储分配——在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置。 注：1、程序结构特点：不允许递归调用，而且不含有可变数组。（如FORTRAN语言）。 2、基本策略:在编译时，根据各类数据所需的存储空间大小以及存储方式规定，在符号表中建立“名字-地址”对应关系，然后根据这些对应关系进行变量名的地址分配。 2)动态分配数据单元时一般使用栈，即栈式存储管理。 栈式: 简单的栈式分配方案 嵌套过程的栈式分配方案 分程序结构的存储分配方案 每个过程的活动记录内容(非嵌套语言) 每个过程的活动记录内容(嵌套语言) 每个过程的活动记录内容 活动记录的填写 1、 call P 被翻译成: 1[TOP]:=SP (保护现行SP) JSR P (转子指令) 2、转进过程P后，首先应执行下述指令: SP:=TOP+1 (定义新的SP) 1[SP]:=返回地址 (保护返回地址) TOP:=TOP+L (新TOP) L：过程P的活动记录所需单元数， 在编译时可确定。 3、 过程返回时，应执行下列指令: X:=2[TOP] (把返回地址取到X中) TOP:=SP-1 (恢复调用前TOP) SP:=0[SP] (恢复调用前SP) UJ X (按X返回) 10.2 栈式存储分配的实现 一、简单的栈式存储分配的实现 程序结构特点：没有分程序结构，过程定义不嵌套，过程可递归调用。 简单栈式分配方案：把存储区组织成一个栈，运行时每进入一个过程，就把它的活动记录压入栈，形成过程工作时的临时数据区，该过程结束时取消该数据区。 例: Main( ) { Main中的数据说明 } proc R( ) { R中的数据说明 } … proc Q( ) { Q中的数据说明 } 主程序→过程Q →过程R 二、嵌套过程语言的栈式分配的实现 1、程序结构特点：语言的定义允许嵌套，一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）（如PASCAL语言） 。 如何才能引用外层数据？ 2、关键：设法跟踪每个外层过程的必威体育精装版活动记录AR的位置。 跟踪办法： （1） 用静态链。 （2） 用DISPLAY表。 PASCAL PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 一个PASCAL过程： 过程头； 说明段（由一系列的说明语句组成）； begin 执行体（由一系列的执行语句组成）； end 作用域：一个名字能被使用的区域范围称作这个名字的作用域。 允许同一个标识符在不同的过程中代表不同的名字。 名字作用域规则--最近嵌套原则 一个在子程序B1中说明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。 program main var A, B : real; … procedure P1 var B:boolean; … begin … end procedure P2 var A:integer; … begin … end begin … end 非局部名字的访问的实现 主程序的层次为0；在i层中定义的过程，其层次为i+1; 过程运行时，必须知道其所有外层