编译原理 第十章 目标程序运行时的存储组织.doc

第9章符号表第十章 目标程序运行时的存储组织课前索引【课前思考】 回顾一般的编译过程,能否找到本章所讲内容在哪个过程？ 为什么编译程序要考虑目标程序运行时存储区的管理和组织？ 请归纳C语言和PASCAL语言的程序结构和数据类型的不同点【学习目标】全面了解目标程序运行时存储区的整体布局；每种存储区的组织方式和管理方法；并通过实例着重掌握，对允许过程嵌套定义的情况，栈式动态存储分配的组织方式和运行时进栈退栈的活动实现方法。【学习指南】在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。我们这里所说的运行时的存储区组织，是指目标程序运行时的数据空间的管理和组织。【难重点】 目标程序运行时，存储区域的整体布局，以及各区域的作用。 各种不同类型的数据表示。 允许过程嵌套定义的情况，栈式动态分配的组织管理。 对过程的调用，进入和退出时，栈式动态分配的工作原理。 过程活动纪录的各项内容和它们的作用，以及活动纪录的组织方式。 过程参数传递的不同方式。【知识结构】第11章代码优化从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入/输出所需的缓冲区。目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如图10.1就是一种典型划分，代码(code)区用以存放目标代码，这是固定长度的，即编译时能确定的；静态数据区(static data)用以存放编译时能确定所占用空间的数据；堆栈区(stack and heap)用于可变数据以及管理过程活动的控制信息。图10.1 目标程序运行时存储区的典型划分codestatic datastack heap所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。我们知道，即便有些名字在程序中只声明了一次，但该名字可能对应运行时不同的存储位置，比如，一个递归调用的过程，在执行时，其同一个局部名字应该对应不同的运行空间位置以容纳每次执行时的值。在程序设计语言语义学中，使用术语environment表示将一个名字映射到一个存储位置的函数，术语state表示存储位置到值的映射，使用术语environment函数表示env: NS (N到S的映射)如图10.2所示。图10.2 名字 到存储、到值的映射编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。决定存储管理复杂程度的因素-源语言本身，比如源语言允许的数据类型有多少？语言中允许的数据项是静态确定还是动态确定？程序结构有什么特点，是段结构还是分程序结构？过程定义是否允许嵌套？等等。 源语言的结构特点、源语言的数据类型、源语言中决定名字作用域的规则等因素影响存储空间的管理和组织的复杂程度，决定数据空间分配的基本策略。本章将介绍存储空间的使用管理方法，重点针对栈式动态存储分配的实现进行讨论。10.1 数据空间的三种不同使用方法和管理方法数据空间的使用和管理方法分成三种：静态存储分配、栈式动态存储分配和堆式动态存储分配。10.1.1 静态存储分配这种存储分配非常简单，如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配策略为静态存储分配。如果一个名字的性质通过说明语句或隐式或显式规则而定义，则称这种性质是静态确定的。像FORTRAN这样的语言，其程序是段结构的，即由主程序段和若干子程序段组成。各程序段中定义的名字一般是彼此独立的（除公共块和等价语句说明的名字以外），也即各段的数据对象名的作用域在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不同段间互相引用、赋值。另外它的每个数据名所需的存储空间大小都是常量（即不许含可变体积的数据，如可变数组），且所有数据名的性质是完全确定的。这样，整个程序所需数据空间的总量在编译时完全确定，从而每个数据名的地址就可静态进行分配。换句话说，一旦存储空间的某个位置分配给了某个数据名（关联起来）之后，在目标程序的整个运行过程中，此位置（地址）就属于该数据名了。图10.4给出一个FORTRAN 77的程序例子。在图10.5中描述了该程序中局部变量的静态存储位置。图10.4 一个FORTRAN 77的例子 (1) PROGRAM CNSUME(2) CHARACTER * 50 BUF /程序体所拥有的静态量BUF(3) INTEGER NEXT /程序体所拥有的静态量NEXT(4) CHARACTER C, PRDUCE /程序体所拥有的静态量C(5) DATA NEXT /1/, BUF / /(6) 6 C=PRDUCE()(7) BUF(NEXT:NEXT)=C (8) NEXT=NEXT+1(9) IF(C .EN. )GOTO 6(10) WRITE ( *, (A) )BUF(11) END(12) CHARACTER FUNCTION PRDUCE()(13) CHARACTER * 80 BUFFER(14) INTEGER NEXT(15) SAVE BUFFER, NEXT/PRDUCE函数体所拥有的静态量BUFFER, NEXT(16) DATA NEXT /81/(17) IF (NEXT .GT.80)THEN(18) READ ( *, (A) )BUFFER(19) NEXT=1(20) END IF(21)PRDUCE=BUFFER(NEXT:NEXT)(22) NEXT=NEXT+1(23)END图10.5 FORTRAN77的静态存储分配10.1.2 动态存储分配如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变数组。例 : procedure A(m,n:integer);begin real z;array Bm:n;begin end;end;Bm:n 为可变数组，B的上下界是过程A的实参，A被调用时才能确定。动态存储管理技术有两种方式：栈式（stack）和堆式（heap）。下面简述这两种方式的原则。1.栈式动态存储分配这种分配策略是将整个程序的数据空间设计为一个栈。在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等；另一部分则是用以管理过程活动的记录信息。即当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器（返回地址）、寄存器的值等等，也都必须保留在栈中。当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动继续进行。至于在这种分配策略下，如何实现动态地分配和释放一个过程的数据空间，如何实现对非局部变量的引用、参数传递以及对可变数据结构（如可变数组）的空间分配办法等等，将在后面几节给予详细讨论。栈式动态存储分配策略适用于PASCAL，C，ALGOL之类具有递归结构的语言的实现。 2堆式动态存储分配如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制（如+中的new，delete，PASCAL的new，等机制），或者不仅有过程而且有进程的程序结构的情况下，空间的使用未必服?quot;先申请后释放，后申请先释放的原则，那么栈式的动态分配方案就不适用了。通常使用一种称为堆式的动态存储分配方案。Pascal语言中，标准过程new能够动态建立一个新记录，它实际上是从未使用的自由区（空闲空间）中找一个大小合适的存储空间并相应地置上指针。标准过程dispose是释放记录new与dispose不断改变着堆存储器的使用情况。这种分配方式的存储管理技术甚为复杂，我们这里举出这种分配方法必须考虑的几个问题。首先，当运行程序要求一块体积为N的空同时，我们应该分配哪一块给它呢？理论上说，应从比N稍大一点的一个空闲块中取出N个单元，以便使大的空闲块派更大的用场。但这种做法较麻烦。因此，常常仍采用先碰上哪块比N大就从其中分出N个单元的原则。但不论采用什么原则，整个大存区在一个定时间之后必然会变面零碎不堪。总有一个时候会出现变样的情形：运行程序要求一块体积为N的空间，但发现没有比N大的空闲块了，然而所有空闲块的总和却要比N大得多！出现这种情形时怎么办呢？这是一个比前面的问题难得多的问题。解决办法似乎很简单，这就是，把所有空闲块连接在一起，形成一片可分配的连续空间。这里主要问题是，我们必须调整运行程序对各占用块的全部引用点。还有，如果运行程序要求一块体积为N的空间，但所有空闲块的总和也不够N，那又应怎么办呢？有的管理系统采用一种吊做废品回收的办法来对付这种局面。即寻找那些运行程序业己无用但尚未释放在占用块，或者那些行程序目前很少使用的点用块，把这此占用块收回来，重新分配。但是，我们如何知道哪些块运行时在使用或者目前很少使用呢？即便知道了，一经收回后运行程序在某个时候又要用它时又应该怎么办呢？要使用废品回收技术，除了在语言上要有明确的具体限制外，还需要有特别的硬件措施，否则回收几乎不能实现。堆式动态储分配的实现通常有如下三种途径：1 定长块管理堆式动态储分配最简单的实现是按定长块进行。初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链成一个链表，用指针available指向链表中的第一块。分配时每次都分配指针available所指的块，然后available指向相邻的下一块。归还时，把所归还的块插入链表。考虑插入方便，可以把所归还的块插在available所指的块之前，然后available指向新归还的块。2 变长块管理除了按定长块进行分配之外，还可以根据需要分配长度不同的存储块，可以随要求而变。按这种方法，初始化时存储空间是一个整块。按照用户的需要，分配时先是从一个整块里分割出满足需要的一小块，以后，归还时，如果新归还的块能和现有的空间能合并，则合并成一块；如果不能和任何空闲块合并，则可以把空闲块链成一个链表。再进行分配时，从空闲块链表中找出满足需要的一块，或者整块分配出去，或者从该块上分割一小块分配出去。若空闲块表中有若干个满足需要的空闲块时，该分配哪一块呢？通常有三种不同的分配策： 首次满足去：只要在空闲块链表中找到满足需要的一块，就进行分配。如果该块很大，则按申请的大小进行分割，剩余的块仍留在空闲块链表中；如果该块不很大，比如说，比申请的块大不了几个字节，则整块分配出去，以免使空闲链表中留下诈多无用的小碎块。 最优满足法：将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户，则系统在分配前首先要对空闲块链表从头至尾描一遍，然后从中找出一块不小于申请块且最接近于申请块的空闲块分配，在用最优满足法进行分配时，为避免每次分配都要扫描整个链表，通常将空闲块链表空间的大小从小到大排序。这样，只要找到第一块大小申请块的空闲块即可进行分配。当然，在回收时变需将释放在空闲块插入到链表的适当位置上去。 最差满足法：将空闲块表中不小于申请块且是最大的空闲的一部全分配给用户。此时的空闲块链表按空闲的块的大小从大到小排序。这样每次分配无需查找，只需从链表中删除第一个结点，并将其中一部分分配给用户，而其它部分作为一个新的结点插入到空闲块表的适当置上去。上述三种分配策略各有所长。一般来说，最优满足法适用于请求分配的内存大小范围较广的系统。因为按最优满足法分配时，总是找大小最接近于请求的空闲块，系统中可能产生一些存储量很小而无法利用的小片内存，事时也保留那些很大的内存块以备响应后面可能发生的内存量较大的请求。反之，由于最差满足法每次都是从内存最大的结点开始分配，从而使链表中的结点趋于均匀。因此，它适用于请求分配的内存大小范围较窄的系统，而首次满足法的分配是随机的，因此它介于两者之间，通常适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息情况。从时间上来比较，首次满足法在分配时需查询空闲块链表，而回收时仅需插入到表头即可，最差满足法恰好相反，分配时无需查表，回收时则为将新的空闲块插入表中适当的位置，需先进行查找，最优满足法则不论分配与回收，均需查找链表，因此最费时间。不同的情况应采用不同的方法。通常在选择时需考虑下列因素：用户的要求；请求分配量的大小分布；分配和释放的频率以及效率对系统的重要性等等。至于存储回收的实现我们这里不进行讨论。第11章代码优化10.2 栈式存储分配的实现前面提到，使用栈式存储分配策略意味着，运行时每当进入一个过程，就在栈顶为该过程的临时工作单元，局部变量，机器状态及返回地址等信息分配所需的数据空间，当一个过程工作完毕返回时，它在栈顶的数据空间也即释放。本节我们将以三种语言结构为例，详细讨论栈式存储分配的实现。为讨论方便，首先引入一个术语-过程的活动记录AR(Activation Record)。过程的活动记录是一段连续的存储区，用以存放过程的一次执行所需要的动态信息，这些信息可以如图10.6所示。图 10.6 过程的活动记录临时工作单元局部变量机器状态信息存取链控制链实参返回地址对它们的简单描述如下： 临时工作单元：比如计算表达式过程中需存放中间结果用的临时值单元。 局部变量：一个过程的局部变量。 机器状态信息：保存该过程执行前关于机器状态的信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。 存取链：用以存取非局部变量，这些变量存放于其它过程的活动记录中。并不是所有语言需要该信息。 控制链：指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。 实参：也称形式单元，由调用过程向该被调过程提供实参的值（或地址）。当然在实际编译程序中，也常常使用机器寄存器传递实参。 返回地址：保存该被调过程返回后的地址。这些域的大小在编译时是已知的，如果局部变量中包含有可变数组，那么则采用第9.2节中所介绍的内情向量，将内情向量置于过程活动记录中。另外，有些语言的编译程序还将参数个数存放于活动记录中，以便进行参数个数的检查。10.2.1 简单的栈式存储分配的实现首先从一种最简单的程序设计语言结构讲起：没有分程序结构，过程定义不嵌套，但允许过程递归调用。其程序结构如图10.7所示。图 10.7过程定义不嵌套的程序结构program main; /主程序头全局变量或数组的说明；proc R; /过程R的头 /过程R的体end (R); /过程R的尾proc Q; /过程Q的头 /过程Q的体end (Q); /过程Q的尾主程序执行语句 /主程序体end.(main) /主程序尾这种情况下，采用栈式动态分配策略，即，运行时，每当进入一个过程，则为该过程分配一段存储区，当一个过程工作完毕返回时，它所占用的存储区可释放。程序运行时的存储空间(栈)中在某一时刻可能会包含某个过程的几个活动记录（某个过程递归调用的情况）；另外，同样的一个存储位置，在不同运行时刻可能分配给不同的数据对象。例如图10.7的程序结构中，若主程序调用了过程Q，Q又调用了R，在R进入运行后的存储结构如图10.8（a）所示。若主程序调用了过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构如图10.8（b）所示。若主程序先调用过程Q，然后主程序接着调用R，且Q过程不调用Q和R，这时Q和R进入运行后的存储结构，先后分别如图10.8（c）和10.8（d）所示。 图 10.8栈式存储分配常常使用两个指针指示栈最顶端的数据区，一个称为SP，一个称为TOP。SP总是指向现行过程活动记录的起点，TOP则始终指向已占用的栈顶单元。这种语言若含有可变数组，则其过程活动记录的内容可如图10.9所示。图10.9无嵌套定义的过程活动记录内容图10.10分配了数组区之后的运行栈这里把控制链也称作老SP，即调用该过程的那个过程的最新活动记录的起点。假定图10.9所示为图10.8（a）中现行过程R的活动记录，SP为此过程活动记录的起点，TOP指向为此过程创设的活动记录的顶端，并假定R含有可变数组，则在分配了数组区之后TOP就指向数组区（整个运行栈）的顶端。图10.10表明分配数组区之后的运行栈情况，可以与图10.8（a）对照。在过程段中对任何局部变量x的引用可表示为变址访问xSP，此处x代表变量x的相对数，也就是相对于活动记录起点的地址。这个相对数在编译时可完全确定下来。过程的局部数组的内情向量的相对地址在编译时也同样可确定下来。数组空间分配之后，对数组元素的引用也就容易用变址访问的方式来实现。10.2.2 嵌套过程语言的栈式实现我们所熟悉的PASCAL语言程序结构的特点是允许过程嵌套定义，一个过程可以引用包围它的任一外层过程所定义的标识（如变量，数组或过程等）。如图10.11所示。若不考虑它的文件和指针类型，它的存储分配也是采用栈式动态分配策略，只是它的过程活动记录中应增设一些内容，用以解决对非局部变量的引用问题。图10.11具有嵌套过程的PASCAL程序(1) program sort(input, output); /sort的过程头(2)var a: array 0.10 of integer;(3)x: integer;(4)procedure readarray; /sort内嵌套定义的readarray的过程头(5)var i: integer;(6)beginaendreadarray; /readarray的过程体(7)procedure exchange(i,j: integer);/sort内嵌套定义的exchange的过程头(8)begin(9) x=ai; ai=aj; aj=x; /exchange的过程体(10) endexchange;(11) procedure quicksort(m,n: integer);/sort内嵌套定义的quicksort的过程头(12) var k,v: integer; (13) function partition(y,z:integer):integer;/quicksort内嵌套定义的partition的函数头(14)var i.j:integer;(15)begin a /partition的函数体(16)v(17) exchange(i,j);(18) endpartition;(19) beginendquicksort; /quicksort的过程体(20) beginendsort. /sort的例程体图10.11的PASCAL程序中过程定义的嵌套情况如下：sortreadarrayexchangequicksortpartition这里不妨将整个程序sort看成最外层的过程。过程readarray,exchange和partition中引用的a均不是它们的局部变量，而是过程sort的局部变量。假如过程sort激活(调用)了过程quicksort,这时存储栈中的情形示意如图10.12，其中在quicksort过程活动记录中有一(或一些)存储单元(用斜线描绘)用以记录过程quicksort可以引用sort中定义的变量a和x。也就是说，为了解决对非局部量的存取问题，必须设法跟踪每个外层过程的最新活动记录的位置。图 10.12存储栈布局实现对非局部量的存取的方法-跟踪每个外层过程的最新活动记录AR的位置。跟踪办法： 用静态链（如PL/0的SL）。 用DISPLAY表。跟踪的办法很多，我们介绍两种，一种是在过程活动记录中增设存取链，指向包含该过程的直接外层过程的最新活动记录的起始位置。过程活动记录的内容如图10.13（a）所示。图10.12所提到的情况可用图10.13（b）说明。图 10.13 嵌套定义过程的活动记录和存储栈回顾PL/0编译程序，其假想机汇编解释程序的环境之一是数据栈stack，它的存储分配策略便是栈式动态分配的，因为PL/0是PASCAL的一个子集，它的过程允许嵌套定义，它的过程活动记录中便有存取链，在PL/0编译程序中我们称作静态链。因为PL/0的过程是无参过程，PL/0也无动态数组，所以它的过程活动记录的内容如图10.14所示。图 10.14 PL/0编译程序的过程活动记录再回到图10.11的例子。如果该程序的某次执行顺序为：sortquicksortquicksortpartitionexchange即主程序(最外层过程)sort开始执行,继而进入过程quicksort，而又一次进入过程quicksort，接着进入过程partition，进入过程exchange。图10.15给出了进入过程exchange之后运行栈的示意，我们仅把存取链和控制链的值标明。图 10.15 运行栈可以看出，过程exchange由过程（函数）partition调用，但exchange的直接外层过程是sort，所以过程exchange的活动记录的存取链指向sort的活动记录的始址。 另外，过程partition中引用了第(2)行说明的变量a，而partition的直接外层是quicksort，quicksort的直接外层过程是sort，partition对非局部量a的引用通过两次拉链实现。另外一种存取非局部变量的办法，也是常用的有效办法。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display。这里所提到的嵌套层次，是指过程定义的层数，始终假定主程序的层数为0，因此主程序称为0层过程。如某过程p是在层次为i的过程q内定义的，并且q是包围p的直接外层，那么p的过程层数为i+1。一般编译程序处理过程说明时，将把过程层数作为重要的属性登记在符号表中。计数过程的层数很容易实现，用一个计数器Level，初值为0，每遇到过程说明则增1，过程说明结束则减1，PL/0编译程序就是这样处理的。display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址。也即，嵌套层次i的过程的局部变量a是在由display元素di所指的那个活动记录中存放的。也就是说，嵌套层次i+1过程中的非局部变量可能在i,i-1,0层，对它的存取是通过display元素di,di-,d0而获得的。假定现在进入的过程的层数为i，则它的display表含有i+1个元素，依次指向现行层、直接外层直至最外层（0层）等每一层过程的最新活动记录的地址。例如图10.11的程序，假定有如下四种调用情况：(a)sortquicksort;(b)sortquicksortquicksort;(c)sortquicksortquicksortpartition;(d)sortquicksortquicksortpartitionexchange。则图10.16的（a），（b），（c），（d）分别说明了上述四种情形的运行栈和display。确实看出，display显示了存取链的信息。图 10.16 display表display本身的体积在编译时可确定。至于display本身作为单独的表分配存储，还是作为活动记录的一部分，比如置于实参（形式单元）的上端（如图10.17所示），则取决于编译程序的设计者。假定将display作为活动记录的一部分，由于每个过程的形式单元数目在编译时是知道的，那么display的相对地址d（相对于活动记录起点）在编译时也是完全确定的。因此，若现行过程中引用了某一外层过程的变量，则很容易生成相应的存取指令。现在我们要讨论，当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display。为了建立自己的display，P2必须知道它的直接外层过程(记为P0)的display。这意味着，当P1调用P2时必须把P0的display地址作为连接数据之一传给P2。图 10.17 display作为活动记录的一部分图 10.18 P1调用P2的两种不同嵌套图 10.18(a)调用情形一 图 10.18(b)调用情形二如果P2是一个真实过程(P2不是形式参数)，那么，P0或者就是P1自身或者既是P1又是P2的直接外层(见图10.18的(a)、(b)两种情形)。不论哪一种情形，只要在进入P2后能够知道P1的display就能知道P0的display，从而可直接构造出P2的display。事实上，只需从P1的display中自底而上地取过l2个单元(l2为P2的层数)再添上进入P2后新建立的SP值就构成了P2的display。也就是说，在这种情况下，我们只需把P1的display地址作为连接数据之一传送给P2就能够建立P2的display。如果P2是形式参数，那么，调用P2意味着调用P2当前相应的实在过程。此时的P0应是这个实在过程的直接外层过程。我们假定P0的display地址可从形式单元P2所指示的地方获得。为了能在P2中获得P0的display地址，我们必须在P1调用P2时设法把P1的display地址作为连接数据之一(称为全局display地址)传送给P2。于是连接数据变为三项:(1) 老SP值；(2) 返回地址；(3) 全局display地址。这样，整个活动记录的组织就如图10.17所示。注意，0层过程（主程序）的display只含一项，这一项就是主程序开始工作时所建立的第一个SP值。10.3 参数传递当一个过程调用其它过程时，调用过程和被调过程之间的通信经由非局部量或者经由参数传递。如图10.19的过程exchangel既使用了非局部量数组，又使用了形式参数(简称形参)i和j，将ai和aj的值进行交换。图 10.19 带有非局部变量和形参的PASCAL过程 (1) procedure exchangel(i，j: integer);/过程exchangel的头，带有形式参数i ， j(2)var x: integer;(3) begin;(4)x=ai; ai=aj; aj =x/数组a是非局部变量(5) end;语句exchangel(m，n);表示了对图10.19中过程exchangel的一次调用，其中m，n为实在参数，简称实参。我们所讨论的问题是，为执行exchangel(m，n)，形参i，j应按何种方式同实参m，n相联，换句话说，如何把实在参数传递给相应的形式参数呢？有几种形实参对应的方法，分别称作值调用，地址（引用）调用，名字调用以及宏扩展。也就是说，参数传递的几种不同途径是传值，传地址，传名及宏扩展等等。知道一个语言使用的参数传递的方法非常重要，因为一个程序的结果依赖于所使用的方法。观察图10.20的PASCAL程序。我们知道该程序的输出是a=2，b=1如果将第3行的关键字var去掉，则该程序的输出是a=1，b=2。图 10.20 带有过程swap的PASCAL程序(1) program reference(input, output);/reference过程定义头(2) var a, b: integer;(3) procedure swap(var x, y: integer);/reference过程内定义的swap的过程(4) var temp integer;(5) begin /swap的过程体(6)temp=x;(7) x=y;(8) y=temp(9) end;(10) begin /reference的过程体(11)a=1; b=2;(12)swap(a,b);(13)writeln(a=,a); writeln(b=,b)(14) end.有关键字var时，PASCAL语言的参数传递使用的方式是传地址；去掉var，则使用的方式是传值。PASCAL语言的变量参数是在参数前加关键字var。这种参数的传递方式是传地址例如：过程 swap(var x,y:integer);swap(a,b)；(a,b为调用时的实参)调用结果：a,b的值被改变。在参数前不加关键字var时是值调用。这种参数的传递方式是传值。例如：过程 swap(x,y:integer);swap(a,b)；其结果：a,b调用前的值不被改变。10.3.1 传值现在讨论传值的实现。传值，即call by value，也称值调用。这是最简单的参数传递方法。具体来讲是这样的： 在被调过程的活动记录中开辟形参的存储空间，这些存储位置即是我们所说的形参或形式单元。 调用过程计算实参的值，并将它们的右值（r value）放在为形式单元开辟的空间中。 被调用过程执行时，就像使用局部变量一样使用这些形式单元。在图10.20程序中，第12行swap（a,b）调用过程将不会影响a和b的值。其结果等价于执行下列运算：x =ay =btemp =xx =yy =temp这里，x，y和temp局部于swap，虽然赋值改变了局部量x，y和temp的值，但当控制从该调用返回而swap的该活动记录释放后，这些改变即消失，这种调用方式不影响调用过程的活动记录。10.3.2 传地址当参数通过引用传递时，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向实参存储位置的指针。1. 如实参是一个名字或是具有左值的表达式，则左值本身传递过去。2. 如实参是一表达式，比方a+b或2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。3. 被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。例如，在图10.20的程序中，若用实参i和ai对过程swap进行调用，即swap(i，ai)，其效果如下步骤所述：1. 将i和ai的地址(左值)拷贝到被调过程的活动记录中，比如说分别对应形参x和y的单元arg1和arg2。2. 将局部变量temp设为由arg1所指单元的内容(即令temp等于i0，其中i0是i的初值)，这一步对应于swap定义中的第6行语句:temp =x。3. 将arg1所指单元的内容设为arg2所指单元的值，即i=ai0，这一步对应swap中第7行的x=y。4. 将arg2所指单元的内容设为等于temp的值，即，设ai0=i，这一步对应y=temp。通过值调用的过程可以由非局部量或由指针而对调用过程发生影响。比如图10.21的C程序中，x和y声明为整型指针(在第2行)，第8行调用swap(&a，&b)中的&操作符导致将指向a和b的指针传给过程swap。该程序的输出为： a is now 2， b is now 1该例中指针的使用恰好提示了一个编译程序怎样实现引用调用。图 10.21在一个值调用过程中使用指针的C程序(1) swap(x,y) /定义swap过程(2) int *x,*y;(3) int temp; /swap的过程体(4)temp=x; x=y; y=temp;(5) (6) main() /主程序 (7) int a=1, b=2;(8)swap(&a, &b); /调用swap,其实在参数是a和b的地址(9)printf(a is now%d,b is now%dn, a, b);(10) C语言过程的参数只有值参，要实现传地址可采用传递指针型实参。除了传值和传地址两种参数传递方法之外，还有得结果(valueresult)，传名call by name等等。这里我们不予讨论。10.3.3 过程参数一个过程(函数)可以作为参数传递，比如图10.22的PASCAL程序中，过程c把f作为参数传递给b，而b通过引用形参h调用f。我们要注意的是：函数f有一非局部量m，图中特地将m圈起来。但m的作用域并不包括b的过程体。b中的语句writeln（h（2）激活f，是因为形参h引用f，writeln打印的是调用f（2）的结果。那么b激活f时，怎样设置f活动记录的存取链（display）呢？答案是，当一个嵌套过程作为参数传递时，必须连同它的存取链（display）一同传递过去。图10.23说明了这点，当过程c传递f时，c可以决定f的存取链，或者说f的存取链或display可以根据c的存取链或display来建立。c必须把f连同f的存取链一起传给b，那么在b中激活f时，b活动记录的存取链就可以正确设置了。图10.22 嵌套过程作为参数传递(1) program param(input， output);/例程param的头(2) procedure b(function h(n:integer): integer);/嵌套过程b的头，其形式参数是一个具有一个整型形参n的整型函数h(3) begin writeln(h(2) end b;/b的过程体(4) procedure c; /嵌套过程c的头(5) var :integer;(6) function f(n;integer): integer;/过程c中嵌套定义的具有一个整型形参n的整型函数f(7) begin f=+n endf;/f的函数体(8) begin =0;b(f) endc;/c的过程体，其中b(f)调用b函数，/而实参是函数f，调用时替换形参函数h(9) begin(10) c (11) end图10.23 连同存取链一起传递过程实参一般来讲，过程P把过程T做为实参传递给Q时，也是一种传地址方式，P可以先建立两个相继的临时单元，第一个单元B1存放过程T的入口地址；第二单元B2存放现行display地址或存取链地址。然后把第一临时单元地址传送给Q（即放置于Q活动记录的形式单元，比方说Z中）。假定过程Q执行到引用形参Z时，Z中已含有上述B1的地址，则B1的内容将用来作为转子指令的目的地址（即转进过程T）。B2的内容将传送给T。除了实参是过程的情况外，还有实参为数组的情况，实参为标号的情况以及实参为形式参数的情况。我们不再讨论。10.4 过程调用、过程进入和过程返回经过上述讨论之后，我们归纳一下，对于过程调用的四元式序列：par T1par T2par Tncall P,n在运行时是如何执行的。或者说，对于par和call应产生什么相应的目标代码？前面讲过，过程活动记录中有形式单元，形式单元与活动记录起点之间的距离是确定的。因此对于par Ti(i=1,2,n)的处理是：根据par Ti(i=1,2,n)中Ti的种别而生成传送指令，或将参数的值或将参数的地址传送至新的过程的活动记录的形式单元中。对于call p,n则应生成传送参数个数n的指令；保护现行SP至新过程的活动记录（老SP）；转子，转向P的第一条指令；定义新SP；保护返回地址；定义新值；填写display或存取链内容等指令。如果过程含动态数组（局部），则应生成对数组进行存储分配的指令，即生成运行时动态地建立内情向量和分配数组空间的目标指令（内情向量表区已分配在过程活动记录中）。这些指令主要完成计算各维的上下界，计算并填好内情向量的所有信息，计算所需的数组空间，然后在TOP所指的位置之上留出数组所需空间，将TOP调整为指向数组区的顶端。在过程执行语句的工作过程中，凡引用形参、局部变量或数组元素都可根据过程活动记录起点的相对位置访问。当过程P工作完毕要返回到调用段时，若语言有形如return（E）的返回语句，或P是个函数过程时，则可把已算好的值传送至某个特定的寄存器中，调用段将从这个特定的寄存器中获得被调过程的结果值。然后所生成的目标指令则应完成的工作是：恢复SP；恢复TOP，按保存的返回地址实行无条件转移。本章小结 【本章小结】 目标代码运行时，存储区域的整体布局，以及各区域的作用。 各种不同数据变量区的不同分配组织方式。 允许过