编译原理 第七部分
数据空间
数据空间包括：用户定义的各种类型的数据对象(变量和常数)所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入/输出所需的缓冲区。
目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。
存储管理复杂程度取决于源语言本身，包括：
- 允许的数据类型的多少
- 语言中允许的数据项是
- 静态确定
- 动态确定
程序决定名字的作用域的规则和结构
- 段结构
- 过程定义不嵌套，只允许过程递归调用
- 分程序结构
- 分程序嵌套
- 过程定义嵌套
数据空间的三种分配策略
运行时数据空间的三种分配策略：
- 静态存储分配
- 动态存储分配
- 栈式动态存储分配
- 堆式动态存储分配
采用哪种分配策略是由源语言的语义决定的。
静态存储分配
如果在编译时就能确定目标程序运行中所需要的全部数据空间的大小，则编译时就能安排好目标程序的全部数据空间，并能确定每个数据项的单元地址、存储空间，这种分配方法叫做静态存储分配
动态存储分配
如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。
栈式存储分配
在允许递归调用且每次调用都要重新分配局部变量的语言中，编译程序不能静态地分配活动记录。对于这种语言应该采用栈式存储分配，其分配策略是将整个存储空间设计成一个栈，每当调用一个过程时就将它的活动记录压入栈，在栈顶形成过程工作时的数据区，当过程结束时再将其活动记录弹出栈。
过程的活动记录AR(Activation Record)，是一段连续的存储区，用以存放过程的一次执行所需要的动态信息
栈式动态存储分配策略适用于PASCAL，C，ALGOL之类具有递归结构的语言的实现。
简单栈式存储分配
对于没有分程序结构，过程定义不允许嵌套但允许过程递归调用的语言，可以采用一种简单的栈式存储分配策略。
C语言就是满足上述特点的一种语言，其过程的活动记录一般采用如图所示的结构。
过程的每一个局部变量或形参在活动记录中的相对地址是确定的，因此可以知道程序运行时，变量和形参在栈上的绝对地址是：绝对地址＝活动记录基地址（SP）十相对地址
堆式存储分配
如果一种程序语言允许数据对象能够自由地分配和释放，那么由于空间的使用不一定按照“先申请后释放”的原则，这时栈式存储分配就不适用了。对于这种语言通常采用堆式存储分配方法。
堆式存储分配方法的基本思想是：一个程序开始执行时有很大一块存储空间，运行期间如果需要就从里面申请一块存储空间，使用完毕归还。
堆式存储分配最简单的实现方法是按定长进行分配。初始化时将堆存储空间分成若干个长度相等的块，按邻块的顺序把这些块链成一个链表。每次申请空间时就从链表最前面的未使用结点开始分配，归还时把结点插入链表，归还时最好保证第一个未使用的结点之后没有已分配的块。采用这种方式，编译程序不需要知道分配出去的存储块将存放何种类型的数据，用户可以根据需要使用整个存储块。
定长块管理实现起来比较方便，但是内存的使用效率偏低，堆式存储分配通常按变长块进行。按这种方法，初始化存储区时没有把空间分段，每次申请时都从空闲区分出满足要求的最小块；归还时，如果新归还的块能和现有的空闲块合并就把它们合成一块。如果有若干个空闲块满足需要时，通常采用以下几种不同的分配策略。
- 首次匹配法
- 最优匹配法
- 最差匹配法
无论采用哪种分配策略，当找不到合适的空闲区时，就要调用碎片收集程序，将无法使用的碎片连成一块以备使用
临时变量的存储分配
在产生中间代码时，为了暂存中间结果，编译程序会大量引进临时变量名。临时变量都是简单变量，它们的属性非常简单，因此没有登记到符号表内，而只要在它们出现的地方加上类型信息即可
临时变量的分配原则
一般的分配原则是：如果两个临时变量名的作用域不相交，则它们可以分配到同一单元中。
一个临时变量名自它第一次被赋值的地方起直至它最后一次被引用的地方止，这区间的程序所能到达的全体四元式构成了它的作用域。
活动记录
过程活动记录
活动记录在运行栈上的分配
活动记录的结构
嵌套过程
Display表的结构和维护