编译原理第九章目标程序运行时的存贮组织

第九章目标程序运行时的存贮组织从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配。一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入/输出所需的缓冲区。目标代码所占用空间的大小，在编译时能确定，有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。但有些数据对象具有可变体积和待编译性质，而无法在编译时确定存储空间的位置。因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如图9-1就是一种典型划分，代码（code）区用以存放目标代码，这是固定长度的，即编译时能确定的。静态数据区（staticdata）用以存放编译时能确定所占用空间的数据，堆栈区（stackandheap）用于可变数据以及管理过程活动的控制信息。编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。我们知道，即便有些名字在程序中只声明了一次，但该名字可能对应运行时不同的运行空间位置以容纳每次执行时的值。因此，源语言的结构特点、源语言数据类型、源语言中决定名字作用域的规则等因素影响存储空间的管理和组织的复杂程序，决定数据空间分配的基本策略。本章重点：存储空间的使用管理方法、栈式动态存储分配的实现第一节数据空间的三种不同使用方法和管理方法数据空间的使用和管理方法分成三种：静态存储分配、栈式动态存储分配和堆式动态存储分配。1、静态存储分配如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，那么则称这种分配策略为静态存储分配。如像FORTRAN这样的语言，其程序是段结构的，如图9-1-1所示，即由主程序段和若干子程序段组成。各程序段中定义的名字一般是彼此独立的（除公共块和等价语句说明的名字以外），也即各段的数据对象名的作用域在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不同段间互相引用、赋值。另外它的每个数据名所需的存储空间大小都是常量（即不许含可变体积的数据，如可变数组），且所有数据名的性质是完全确定的。这样，整个程序所需数据空间的总量在编译时完全确定，从而每个数据名的地址就可静态进行分配。换句话说，一旦存储空间的某个位置分配给了某个数据名（关联起来）之后，在目标程序的整个运行过程，此位置（地址）就属于该数据名了。2、动态存储分配codestaticdatastack↓↑heap图9-1目标程序运行时存储区的典型划分…主子1子2子n图9-1-1FORTRAN程序构成特点如果一个程序设计语言允许递归过程，可变数组或可变数据结构，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小待程序运行时动态地确定。有两种动态存储分配方式：栈式（stack）和堆式（heap）。3、栈式动态存储分配这种分配策略是将整个程序的数据空间设计为一个栈。它适用于PASCAL，C，ALGOL之类语言的实现，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间，过程所需的数据空间包括两部分，一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等；另一部分则是用以管理过程活动的记录信息，即当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器（返地址）、寄存器的值等，也都必须保留在栈中。当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动重新开始。至于在这种分配策略下，如何实现动态地分配和释放一个过程的数据空间，如何实现对非局部变量的引用、参数传递以及可变数据结构（如可变数组）的空间分配办法等等，将在后面给予讨论。4、堆式动态存储分配如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制（如C++中的new,delete,PASCAL的new，便是这种机制）或者不仅有过程而且有进程的程序结构，即空间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的状态分配方案就不适用了。这种情况下通常使用一种称为堆式的动态存储分配方案。假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运行之后，程序运行空间将被分划成许多块块，有些占用，有些空闲。那么当运行程序要求一块体积为N的空间时，需要决定应该从哪个空闲块得到这个空间。理论上讲，应该从比N稍大一些的空闲块中取出N个单元，以便使大的空闲块派更大的用场，但实际难度很大，实际中常常采用的办法是：先遇到哪块比N大就从其中取出N个单元。即使这样，也会发生找不到一块比N大的空闲块，但所有空闲块的总和比N大得多的情况，这时，有的分配管理系统采用废品回收的办法来应付。第二节栈式存储分配的实现前面提到，使用栈式存储分析策略意味着，运行时每当进入一个过程，就在栈顶为该过程分配所需的数据空间，当一个过程工作完毕返回时，它的栈顶的数据空间也即释放。下面讨论栈式存储分配的实现。为讨论方便，首先引入一个术语——过程的活动记录AR（ActivationRecord）。过程的活动记录是一段连续的存储区，用以存放过程的一次执行所需要的信息，这些信息可以如图9-2-1所示。但并不是所有的语言，所有的编译程序全部使用这些信息。对它的简单描述如下：1、临时工作单元，比如计算表达式过程中需存放中间结果用的临时值单元。2、局部变量，一个过程的局部变量。3、保存机器状态，容纳该过程执行前关于机器状态的信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。4、存取链，用以存取非局部变量，这些变量存放于其它过程活动记录中。并不是所有语言需要该信息。5、控制链，指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。6、实参，也称形式单元，由调用过程向该被调过程提供实参的值（或地址）。当然在实际编译程序中，也常常使用机器寄存器传递实参。7、返回地址，保存该被调过程返回后的地址。这些域的大小在编译时是已知的，如果局部变量中包含有可变数组，那么则采用内情向量，将内情向量置于过程活动记录中。另外，有些语言的编译程序还将参数个数存放于活动记录中，以便进行参数个数人检查。一、简单的栈式存储分配的实现首先从一种最简单的程序设计语言结构讲起：没有分程序结构，过程定义不嵌套，但允许过程递归调用。临时工作单元局部变量机器状态信息存取链控制链实参返回地址图9-2-1过程的活动记录programmain；全局变量或数组的说明；procR；…end（R）；procQ；…end（Q）；主程序执行语句end.(main)图9-2-2过程定义不嵌套的程序结构R的活动记录Q的活动记录主程序全局数据区Q的活动记录Q的活动记录主程序全局数据区Q的活动记录主程序全局数据区R的活动记录主程序全局数据区（a）（b）（c）（d）TOPSP图9-2-3栈式存储分配其程序结构如图9-2-2所示。这种情况下，采用栈式动态分配策略，即运行时，每当进入一个过程，则为该过程分配一段存储区，当一个过程工作完毕返回时，它所占用的存储区则可释放。程序运行时的存储空间，（栈）中在某一时刻可能会包含某个过程的几个活动记录（某个过程递归调用的情况）；另外，同样一个存储位置，可能不同运行时刻分配给不同的数据对象。例如，图9-2-3的程序结构中，若主程序调用了过程Q，Q又调用了R，在R进入运行后的存储结构如图9-2-3（a）所示。若主程序调用了过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构如图9-2-3（b）所示。若主程序先调用过程Q，然后主程序接着调用R，且Q过程不调用Q和R，这时Q和R进入运行后的存储结构分别如图9-2-3（c）和9-2-3（d）所示。常常使用两个指针指示栈最顶端的数据区，一个称为SP，一个称为TOP。SP总是指向现行过程活动记录的起点，TOP则始终指向已占用的栈顶单元。这种语言若含有可变数组，则其过程活动记录的内容可如图9-2-4所示。这里把控制链也称作老临时工作单元局部数组的内情向量局部简单变量实参（形式参数）参数个数返回地址控制链（老SP）图9-2-4无嵌套定义的过程活动记录TOPSPR的数组区R的活动记录Q的活动记录主程序全局数据区图10.6过程的活动记录图9-2-5分配了数组区之后的运行栈TOPSPSP，即调用该过程的那个过程的最新活动记录的起点。假定图9-2-4所示为图9-2-3（a）中现行过程R的活动记录，SP为此过程活动记录的起点，TOP指向为此过程创设的活动记录的顶端，并假定R含有可变数组，则在分配了数组区之后TOP就指向数组区（整个运行栈）的顶端。图9-2-5表明分配数组区之后的运行栈情况，可以与图9-2-3（a）对照。在过程段中对任何局部变量x的引用可表示为变址访问x[sp]，此处x代表变量x的相对数，也就是相对于活动记录起点的地址。这个相对数在编译时可完全确定下来。过程的局部数组的内情向量的相对地址在编译时也同样可确定下来。数组空间分配之后，对数组元素的引用也就容易用变址访问的方式来实现。栈式存储分配就简单介绍这里。第三节参数传递当一个过程调用其它过程时，调用过程和被调过程之间的通信经由非局部量或者经由参数传递。如图9-3-1的过程exchangel既使用了非局部量数组a，又使用了形式参数（简称形参）i和j，将a[i]和a[j]的值进行交换。语句exchangel(m,n)；表示了对图9-3-1中过程exchangel的一次调用，其中m,n为实在参数，简称实参。我们所讨论的问题是，为执行exchangel(m,n)，形参i,j应按何种方式同实参m,n相联，换句话说，如何把实在参数传递给相应的形式参数呢？有几种形实参对应的方法，分别称作值调用，地址（引用）调用，名字调用以及宏扩展。也就是说，参数传递的几种不同途径是传值，传地址，传名及宏扩展等。之所以存在有不同的方法，源于一个表达式的表示是如何给于不同的解释的。比如，在一个赋值语句a[i]：=a[j]中，表达式a[j]表示一个值，而a[i]表示一个存储位置，用于存放a[j]的值。通常术语左值（1—value）指表达式代表的存储，右值（r—value）指该存储位置中含有的值。“左”和“右”来自赋值语句的“左”端和“右”端。参数传递方法的不同主要基于实在参数是表达一个右值，一个左值，还是实在参数本身的文本（字）。知道一个语言使用的参数传递的方法非常重要，因为一个程序的结果依赖于所使用的方法。观察图9-3-2的PASCAL程序。我们知道该程序的输出是a=2，b=1如果将第3行的关键字var去掉，则该程序的输出是a=1，b=2。有关键字var时，PASCAL语言的参数传递使用的方式是传地址；去掉var，则使用的方式是传值。一、传值现在讨论传值的实现。传值，即call-by-value，也称值调用。这是最简单的参数传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：1、形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。2、调用过程计算实参的值，并将它们的右值（r-value）放在形式单元开辟的空间中。3、被调用过程执行时，就像使用局部变量一样使用这些形式单元。传值或值调用的重要特点是对形式参数的任何运算来不影响调用过程的活动记录中实参的值。也即在图9-3-2程序中，如果第3行的关键字var去掉以后，PASCAL将以传值方式将x和y传递给过程swap。第12行swap(a,b)调用过