编译原理第9章.ppt

《编译原理第9章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九章程序运行期间的存储空间组织本节内容与要点运行时存储空间的划分活动记录概念存储空间分配策略1、静态存储分配2、动态存储分配简单栈式存储分配嵌套过程语言的栈式分配典型范例解析运行时存储空间的划分编译程序为了使它编译后得到的目标程序能够运行，要从操作系统中获得一块存储空间。对这块提供运行的空间应该进行划分以便存放：生成的目标代码、数据对象和跟踪过程活动的控制栈。目标代码的大小在编译时可以确定，所以编译程序可以把它放在一个静态确定的区域。有一些数据对象的大小在编译时也能确定，因此它们也可以放在静态确定的区域。运行时存储空间的划分（续）目标代码静态数据栈↓↑堆返回活动记录为了管理过程

2、在一次执行中所需要的信息，使用一个连续的存储块，这样的一个连续存储块称为活动记录（ActivationRecord）。当过程调用时，产生一个过程的新的活动，用一个活动记录表示该活动的相关信息，并将其压入栈。当过程返回（活动结束）时，当前活动记录一般包含如下内容：连接数据返回地址动态链：指向调用该过程前的最新活动记录地址的指针。运行时，使运行栈上各数据区按动态建立的次序结成链。链头为栈顶起始位置。静态链：指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。形式单元：存放相应的实在参数的地址或值。局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。指针S

3、P指向现行过程（即最新进入工作的那个过程）的活动记录在栈里的起始位置。活动记录结构图临时单元内情向量局部变量形式单元静态链动态连返回地址TOPSP连接数据返回存储分配策略静态分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆。返回一、静态分配策略适用范围和特点：1、程序语言不允许递归过

4、程；2、不许含可变体积的数据项目或待定性质的名字；3、在编译时就能够确定一个程序在运行时所需的存贮空间大小，能够安排好目标程序运行的全部数据空间，并能确定每个数据项的单元地址。适于静态存贮分配的语言必须满足以下条件：(1)数组的上下界必须是常数；(2)过程调用不允许递归；(3）不允许采用动态的数据结构（即在程序运行过程中申请和释放的数据结构）。由于过程调用不允许递归，数据项的存贮地址就与过程相联系。过程调用所使用的局部数据区可以直接安排在过程的目标代码之后，并把各数据项的存贮地址填入相关的目标代码中，以便在过程运行时访问这个局部数据区。这里，不存在对存贮区的再利用问题。在执行目标

5、程序时不必进行运行时的存贮空间管理，过程的进入和退出变得极为简单。例：一个程序段的局部数据区返回返回二、动态分配策略适用：程序语言允许递归过程和可变（体积的）数组，其程序数据空间的分配需采用某种动态策略（在程序运行时动态地进行分配）。栈式动态分配策略：目标程序可用一个栈作为动态的数据空间。运行时，每当进入一个过程或分程序，它所需的数据空间就动态地分配于栈顶，一旦退出，它所占用的空间就予以释放。堆式动态分配策略：如果程序语言允许用户动态地申请和释放存贮空间，而且申请和释放之间不一定遵守先请后放和后请先放的原则，此时就必须让运行程序持有一个大存贮区（称为堆），凡申请者从堆中分给一块，

6、凡释放者退还给堆。返回简单的栈式存贮分配适用于简单程序语言的实现：语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。C语言就是这样一种语言。其局部名称的存储分配，可以直接采用栈式存储分配策略。1、栈式存储分配使用栈式存储分配法意味着把存储组成一个栈。运行时，每当进入一个过程（一个新的活动开始）时，就把它的活动记录压入栈，从而形成过程工作时的数据区，一个过程的活动记录的体积在编译时是可静态确定的。当该活动结束（过程退出）时，再把它的活动记录弹出栈，这样，它在栈顶上的数据区也随即不复存在。C语言的程序结构全局数据说明Main(){Main中的数据说明

7、}voidR(){R中的数据说明}voidR(){R中的数据说明}C语言程序的存储组织R的活动记录Q的活动记录Main的活动记录主程序全局数据区TOPSPSP:总指向现行过程活动记录的起点，用于访问局部数据。TOP:始终指向（已占用）栈顶单元。2、C的活动记录C的活动记录有以下四个项目。1、连接数据（两项）：(1)老SP值，即前一活动记录的起始地址；(2)返回地址。2、参数个数。3、形式单元（存放实在参数的值或地址）。4、过程的局部变量、数组内情向量和临时工作单元。C过程的活动记