编译原理第10章 存储组织.pptVIP

编译原理之存储组织 华东交通大学软件学院 万仲保 第十章 目标程序运行时的存储组织 概述 数据空间的使用方法和管理方法 栈式存储分配的实现 参数传递 过程操作 练习 概述 一般来讲，假如编译程序从操作系统中得到一块存储区以位目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。 数据空间应包括： 用户定义的各种类型的数据对象(变量和常数)所需的存储空间、作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元、以及组织输入/输出所需的缓冲区。 运行时的存储区常常划分成： 目标区、静态数据区、栈区和堆区。 运行时存储区的典型划分 编译程序对数据空间的分配 运行时存储区的典型划分 代码(code)区用以存放目标代码，这是固定长度的，即编译时能确定的。 静态数据区(static data)用以存放编译时能确定所占用空间的数据。 堆栈区(stack and heap)用于可变数据以及管理过程活动的控制信息。 编译程序对数据空间的分配 基本原则是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。 数据空间的分配： 本质上看是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。 在程序设计语言语义学中，使用术语environment表示将一个名字映射到一个存储位置的函数，术语state表示存储位置到值的映射。 数据空间的使用方法和管理方法 术语： 静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。 动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。 静态存储分配 动态存储分配 静态存储分配 如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，那么则称这种分配策略为静态存储分配。 示例 FORTRAN 77的示例程序 该程序中局部变量的静态存储位置 FORTRAN 77的程序 局部变量的静态存储位置 动态存储分配 如果一个程序设计语言允许递归过程、可变数组或可变数据结构，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。 分类： 栈式动态存储分配 堆式动态存储分配 栈式动态存储分配 这种分配策略是将整个程序的数据空间设计为一个栈。它适用于Pascal，C，ALGOL之类的语言的实现，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。 过程所需的数据空间包括两部分： 一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等； 另一部分则是用以管理过程活动的记录信息，即当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器(返回地址)、寄存器的值等等，也都必须保留在栈中。 当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动重新开始。 堆式动态存储分配 如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制(如C++中的new，delete．Pascal的new，便是这种机制)，或者不仅有过程而且有进程的程序结构，即空间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的动态分配方案就不适用了。这种情况下通常使用一种称为堆式的动态存储分配方案。 假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运行之后，程序运行空间将被分划成许多块块，有些占用，有些空闲。那么当运行程序要求一块体积为N的空间时，需要决定应该从哪个空闲块得到这个空间。 理论上讲，应该从比N稍大一些的空间块中取出N个单元，以便位大的空闲块派更大的用场，但实现难度很大，实际中常常采用的办法是：先遇到哪块比N大就从其中取出N个单元。即使这样，也会发生找不到一块比N大的空闲块，但所有空闲块的总和比N大得多的情况，这时，有的分配管理系统采用废品回收的办法来应付。 栈式存储分配的实现 过程的活动记录 简单的栈式动态分配实现 嵌套过程语言的栈式实现 分程序结构的存储管理 过程的活动记录 过程的活动记录是一段连续的存储区．用以存放过程的一次执行所需要的信息。 简单描述 简单描述 1．临时工作单元，比如计算表达式过程中需存放中间结果用的临时值单元。 2．局部变量，一个过程的局部变量。 3 ．保存机器状态，容纳该过程执行前关于机器状态信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。 4．存取链，用以存取非局部变量，这些变量存放于其它过程活动记录中。并不是所有语言需要该信息。 5．控制链，指