编译原理第10章运行时的存储组织与分配

编译原理目标程序运行时的存储组织引言在编译原理中，目标程序是指通过编译器将高级源代码转换为机器可执行的程序。

在目标程序运行时，需要一定的存储空间来存储程序的指令和数据。

本文将介绍编译原理中目标程序运行时的存储组织的基本概念和原理。

程序的内存模型目标程序在运行时的存储组织是通过内存模型来描述的。

内存模型定义了目标程序在内存中的存储方式和访问机制。

常见的内存模型有栈式模型、堆式模型和段式模型等。

栈式模型栈式模型将程序的内存划分为栈和堆两部分。

栈用于存储程序的局部变量、函数调用和返回地址等信息，而堆用于动态存储分配，如动态创建的对象以及通过malloc等函数分配的内存。

栈式模型的存储空间是连续分配的，栈的大小是固定的，而堆的大小可以根据需要进行动态调整。

堆式模型堆式模型将程序的内存划分为堆和栈两部分。

堆是动态分配的内存空间，用于存储程序运行时动态创建的对象和变量。

栈则用于存储函数调用的临时变量、函数参数和返回地址等信息。

堆式模型的存储空间可以动态调整，但需要手动管理内存的分配和释放，以避免内存泄漏和内存碎片的产生。

段式模型段式模型将程序的内存划分为若干个段，每个段用于存储特定类型的数据。

常见的段包括代码段、数据段、堆段和栈段等。

代码段用于存储程序的指令，数据段用于存储常量、全局变量和静态变量等数据，堆段和栈段与堆式模型和栈式模型类似。

段式模型可以更灵活地管理不同类型的数据，提高了内存的利用率。

存储器分配在目标程序运行时，编译器负责将程序的指令和数据分配到合适的存储器中。

存储器分配的主要目标是提高程序的执行效率和优化存储空间的利用率。

静态存储器分配静态存储器分配是在编译时确定存储器的分配方式。

静态存储器分配将程序的指令和数据分配到固定的内存地址上，程序运行时不会改变存储器分配。

静态存储器分配适用于程序结构稳定、数据量较小的场景，但难以适应动态创建和销毁对象的情况。

栈式存储器分配栈式存储器分配将程序的局部变量、函数调用和返回地址等信息存储在栈中。

Fall 2010li weihuaDepartment of Computer Science & technology, Informationalschool, Yunnan University Compilers ：Principles and Techniques Chapter 10 Run-Time Environments运行时存储组织的作用与任务 程序在存储器中的布局存储分配策略活动记录运行时存储组织的作用与任务−代码生成前如何安排目标机资源的使用−几个问题•数据表示如何在目标机中表示每个源语言类型的值•存储分配如何组织不同作用域变量的存储•过程实现如何实现过程/函数调用，参数传递代码生成前需要安排目标机资源的使用−代码生成的实质•建立如下关联/绑定（biding）源程序/中间代码的脚本↔运行时的脚本源程序/中间代码的名字↔运行时的存储−目标机资源的使用•内存/缓存：存放目标代码和数据（包括系统数据）•寄存器：存放控制信息和数据信息（常为中间信息）•操作系统资源数据表示−源程序中数据对象在内存或寄存器中的表示形式•源程序中数据对象的属性名字（name），类型（type），值（value）,成员（component），偏移地址（offset），……•数据对象在内存或寄存器中的表示形式位、字节、字、字节序列、……•有些机器要求数据存放时要按某种方式对齐（align）如：要求所有数据存放的起始地址为能够被4整除数据表示举例−基本类型数据char 数据 1 byte integer 数据 4 bytesfloat 数据8 bytes boolean数据 1 bit / 1 byte 指针 4 bytes数组一块连续的存储区（按行/列存放）结构/记录所有域（field)存放在一块连续的存储区存储分配策略−静态分配•在编译期间为数据对象分配存储−动态分配•栈式分配将数据对象的运行时存储按照栈的方式来管理•堆式分配从数据段的堆空间分配和释放数据对象的运行时存储静态存储分配−在编译期间就可确定数据对象的大小•不宜处理递归过程或函数−某些语言中所有存储都是静态分配•如汇编语言，FORTRAN语言−多数语言只有部分存储进行静态分配•可静态分配的数据对象如大小固定且在程序执行期间可全程访问的全局变量，以及程序中的常量（literals，constants）•如C 语言中的static和extern变量栈式存储分配−用于有效实现层次嵌套的程序结构•如实现过程/函数，块层次结构−可以实现递归过程/函数•比较：静态分配不宜实现递归过程/函数−运行栈中的数据单元是活动记录（activation record)（专门介绍）堆式存储分配−从堆空间为数据对象分配/释放存储•灵活数据对象的存储分配和释放不限时间和次序−显式的分配或释放（explicit allocation / dealocation）•程序员负责应用程序的（堆）存储空间管理（借助于）编译器和运行时系统所提供的默认存储管理机制）−隐式的分配或释放（implicit allocation / dealocation）•（堆）存储空间的分配或释放不需要程序员负责，由编译器和运行时系统自动完成堆式存储分配−某些语言有显式的堆空间分配和释放命令•如：Pascal 中的new, depositC++ 中的new, delete•比较：C 语言没有堆空间管理机制，malloc()和free()是标准库中的函数，可以由library vendor提供−某些语言支持隐式的堆空间释放−不释放堆空间的方法z只分配空间，不释放空间，空间耗尽时停止z适合于堆数据对象多数为一旦分配，永久使用的情形z在虚存很大及无用数据对象不致带来很大零乱的情形也可采用运行时存储组织堆式存储分配−显式释放堆空间的方法•用户负责清空无用的数据空间（通过执行释放命令）•堆管理程序只维护可供分配命令使用的空闲空间•问题：可能导致灾难性的dangling pointer错误例：Pascal 代码片断C++ 代码片断var p,q: ^real; …new(p);q:=p; dispose(p);q^:=1.0;float * p,*q; …p=new float; q=p;delete p;*q:=1.0;堆式存储分配−堆空间的管理•分配算法面对多个可用的存储块，选择哪一个如：最佳适应算法（选择浪费最少的存储块）最先适应算法（选择最先找到的足够大的存储块）循环最先适应算法（起始点不同的最先适应算法）•碎片整理算法压缩合并小的存储块，使其更可用（可以分专门的话题讨论，超出本课程范围）（部分内容可参考数据结构和操作系统课程）活动记录−嵌套过程语言的栈式分配•主要问题解决对非局部量的引用（存取）•解决方案采用Display 寄存器表为活动记录增加静态链域活动记录−嵌套过程语言的栈式分配•采用Display 寄存器表Display 寄存器表（简称Display 表）记录各嵌套层当前过程的活动记录在运行栈上的起始位置（基地址）当前激活过程的层次为K（主程序的层次设为0），则对应的Display 表含有K+1 个单元，依次存放着现行层，直接外层…直至最外层的每一过程的最新活动记录的基地址嵌套作用域规则确保每一时刻Display 表内容的唯一性Display 表的大小（即最多嵌套的层数）取决于实现活动记录−嵌套过程语言的栈式分配•采用静态链（static link）Display 表的方法要用到多个寄存器，有时并不情愿这样做（寄存器资源很宝贵），一种可选的方法是采用静态链，只保留一个寄存器（即SP）指向当前AR所有活动记录都增加一个静态链（如在offset为0 处）的域，指向定义该过程的直接外过程（或主程序）运行时最新的活动记录在过程返回时当前AR 要被撤销，为回卷（unwind）到调用过程的AR（恢复SP），还需增加一个动态链过程调用与参数传递−参数传递方式•传值call-by-value传递的是实际参数的右值（r-value）•传地址call-by-reference（-address, -location）传递的是实际参数的左值（l-value）−注表达式的左值代表存储该表达式值的地址表达式的右值代表该表达式的值过程调用与参数传递−参数传递方式•实现call-by-value形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置用以存放实参调用过程计算实参的值，将其放于对应的存储空间被调用过程执行时，就像使用局部变量一样使用这些形式单元过程调用与参数传递−参数传递方式•实现call-by-reference把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：若实在参数是一个名字，或具有左值的表达式，则传递左值若实在参数是无左值的表达式，则计算值，放入一存储单元，传此存储单元地址That’s all for today.Thank You。

编译原理程序运行时的存储组织一、程序的应该存储区域1.代码区：也称为文本区或者只读区，用于存放程序的目标代码。

代码区是只读的，不允许修改。

在程序运行过程中，代码区的内容不会发生变化。

2.全局数据区：用于存放全局变量和静态数据。

全局数据区在程序开始运行时就被分配好空间，在程序的整个运行过程中都存在，直到程序结束。

3.堆区：用于存放动态分配的内存空间，也称为动态内存分配区。

堆区的内存空间是在程序运行时动态分配和释放的，可以根据程序的需要进行扩大或者缩小。

4.栈区：用于存放函数的局部变量和函数调用信息。

栈区的空间是在程序运行时自动分配和释放的，由编译器负责管理。

在函数调用时，会为函数分配一块栈区空间，函数返回后，该空间被自动释放。

二、内存管理方式1.静态内存管理：静态内存管理是指在程序编译阶段，由编译器根据程序的静态内存需求，在编译过程中为程序分配好固定大小的内存空间，静态内存管理的特点是内存空间的分配和释放都是在编译时确定的，程序运行时不需要进行内存管理。

2.动态内存管理：动态内存管理是指在程序运行时根据需要动态地分配和释放内存空间，动态内存管理的特点是内存空间的分配和释放是在程序运行过程中动态确定的。

动态内存管理可以通过堆区进行。

三、内存分配和释放编译原理程序在运行时的存储组织中，对于静态内存区域的分配和释放是由编译器在编译时确定的，程序在运行时无法进行修改。

对于动态内存区域的分配和释放，可以通过堆区进行，可以使用以下几个函数进行动态内存的分配和释放：1. 分配内存：程序可以使用malloc函数、calloc函数或者realloc函数来分配内存空间。

malloc函数用于分配指定字节数的内存空间，calloc函数用于分配指定数量和大小的内存空间，realloc函数用于调整已经分配的内存空间的大小。

2. 释放内存：程序在使用完动态分配的内存空间后，需要使用free函数来释放内存空间。

free函数会将之前分配的内存空间标记为可用状态，可以供其他程序使用。

第十章目标程序运行时的存储组织课前索引【课前思考】◇回顾一般的编译过程,能否找到本章所讲内容在哪个过程？◇为什么编译程序要考虑目标程序运行时存储区的管理和组织？◇请归纳C语言和PASCAL语言的程序结构和数据类型的不同点【学习目标】全面了解目标程序运行时存储区的整体布局；每种存储区的组织方式和管理方法；并通过实例着重掌握，对允许过程嵌套定义的情况，栈式动态存储分配的组织方式和运行时进栈退栈的活动实现方法。

【学习指南】在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。

一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。

我们这里所说的运行时的存储区组织，是指目标程序运行时的数据空间的管理和组织。

【难重点】◇目标程序运行时，存储区域的整体布局，以及各区域的作用。

◇各种不同类型的数据表示。

◇允许过程嵌套定义的情况，栈式动态分配的组织管理。

◇对过程的调用，进入和退出时，栈式动态分配的工作原理。

◇过程活动纪录的各项内容和它们的作用，以及活动纪录的组织方式。

◇过程参数传递的不同方式。

【知识结构】从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。

一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。

数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入/输出所需的缓冲区。

目标代码所占用空间的大小在编译时能确定。

有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。

而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。

因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如图10.1就是一种典型划分，代码(code)区用以存放目标代码，这是固定长度的，即编译时能确定的；静态数据区(static data)用以存放编译时能确定所占用空间的数据；堆栈区(stack and heap)用于可变数据以及管理过程活动的控制信息。