编译原理 第19讲(第十章)- -

第十章目标程序运行时的组织概述数据表示目标程序运行时的栈式存储组织参数传递堆式存储概述10.1概述-代码生成解决语义gap高级语言支持的概念Type value

expressionVariable

procedureFunction

parameters目标机支持的概念bits

bytes

wordsRegistersStack

addressRoutine(sub

routine)概述在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。一般来讲，假如从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入/输出所需的缓冲区。目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。概述运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如下图就是一种典型划分，代码(code)区用以存放目标代码，这是固定长度的，即编译时能确定的；静态数据区(static

data)用以存放编译时能确定所占用空间的数据；堆栈区(stack

and

heap)用于可变数据以及管理过程活动的控制信息。目标代码区静态数据区

Stackheap概述代码生成前如何安排目标机资源运行时组织的几个问题数据表示-如何在目标机中表示每个源语言类型的值表达式求值-如何组织表达式的计算存储分配-如何组织不同作用域变量的存储过程实现-如何以例程实现过程，函数，参数传递允许的数据类型的多少语言中允许的数据项是静态确定动态确定3．程序结构(决定名字的作用域的规则和结构)A

．段结构(Fortran)B

．过程定义不嵌套，只允许过程递归调用C

．分程序结构分程序嵌套过程定义嵌套4．存储类别的多少GlobalStaticLocaldynamic决定运行管理复杂程度的因素—源语言本身静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。10.2

数据表示各种数据对象的存储分配数据对象的属性name

名字/名称type

类型location

内存地址值简单变量：char:1

byteintegers:

2

or

4

bytesfloats:

4

to

16

bytesbooleans:

1

bit

(but

usually

1

byte)valuecomponent

成分指针：unsigned

integers一维数组：一块连续的存储区多维数组：一块连续的存储区，按行存放结构（记录）：把所有域（field)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储区，但方法（成员函数）不存在该对象里指令：10.3目标程序运行时的存储组织存储分配策略：静态存储分配动态存储分配——栈式和堆式注：可以混合使用4

简单的栈式分配方案4

嵌套过程的栈式分配方案4

分程序结构的存储分配方案4

堆式存储静态存储分配这种存储分配非常简单，如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配策略为静态存储分配。静态存储分配举例FORTRAN语言由主程序段和若干子程序段组成。各程序

段中定义的名字一般是彼此独立的，也即各段的数据对象名的作用域在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不同段间互相引用、赋值。另外它的每个数据名所需的存储空间大小都是常量（即不许含可变体积的数据，如可变数组)。这样，整个程序所需数据空间的总量在编译时完全确定，从而每个数据名的地址就可静态进行分配。静态存储分配举例PROGRAM

CNSUMECHARACTER

*

50

BUFINTEGER

NEXT//程序体所拥有的静态量BUF//程序体所拥有的静态量NEXTCHARACTER

C,PRDUCE//程序体所拥有的静态量CDATA

NEXT

/1/,

BUF

/

‘

’

/6

C=PRDUCE()BUF(NEXT:NEXT)=CNEXT=NEXT+1IF(C

.EN.

‘

’

)GOTO

6(10)WRITE

(

*

,‘

(A)’

)BUFENDCHARACTER

FUNCTION

PRDUCE()(13)(14)(15)CHARACTER

*

80

BUFFERINTEGER

NEXTSAVE

BUFFER,

NEXT//PRDUCE函数体所拥有的静态量BUFFER,NEXTDATA

NEXT

/81/IF

(NEXT

.GT.80)THEN,‘

(A)’

)BUFFERREAD

(

*NEXT=1END

IF(16)(17)(18)(19)(20)(21)(22)PRDUCE=BUFFER(NEXT:NEXT)NEXT=NEXT+1(23)

END在Fortran

90之前的Fortran

版本都没有递归.有递归则不能进行静态存储分配动态存储分配如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。动态存储分配举例若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变数组。procedure

A(m,n:integer);begin

real

z;array

B[m:n];begin·

·

·end;end;B[m:n]为可变数组，B的上下界是过程A的实参，A被调用时才能确定。使用malloc为说明方便，假定源程序是由过程组成，运行时称作过程的激活。一个过程的一次执行所需要的信息，使用一个连续的存储区来管理这个区（块），叫做一个活动记录AR或frame帧一般这个区AR要记录：（运行栈的存储分配）l

临时值（如计算表达式时的中间工作单元。）l

局部变量（数据）l

保存运行过程前的状态（返回地址，寄存器值……）l

形参（形式单元）l

返回值（RA对函数，有时可使用寄存器存放返回值）l

存取链（SL可选，对于非局部量的引用。）l

控制链（DL可选，指向调用者的活动记录，释放栈。）术语--过程活动记录AR目标代码的解释执行(运行栈S)4

M调用过程Pz

RAz

DLz

SLz.z.ztzbztzPzMzb10.3.1简单的栈式分配方案4程序结构特点:过程定义不嵌套，过程可递归调用，含可变数组;例:main4全局变量的说明proc

R……end

R;proc

Q……end

Q;主程序执行语句4

end

main演示函数调用退出时sp和top的变化Main---->Q---R->

Main--->Q---->QTOSPTOP---->临时工作单元局部简单变量局部数组的内情向量保存运行过程前的状态（返回地址，寄存器值……）实参（形式单元）和参数个数SP----->控制链（老SP）P

----->R的数组区R的活动记录>Q的数组区Q的活动记录主程序全局数据区Q的数组区Q的活动记录Q的数组区Q的活动记录主程序全局数据区10.3.2嵌套过程语言的栈式分配方案主要特点：4（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。4（实现）一个过程执行时可以引用它的任一外层过程的最新活动记录中的某些数据。我们所熟悉的PASCAL语言程序结构的特点是允许过程嵌套定义，一个过程可以引用包围它的任一外层过程所定义的标识（如变量，数组或过程等）。它的存储分配也看成是采用栈式动态分配策略，只是它的过程活动记录中应增设一些内容，用以解决对非局部变量的引用问题。（回忆简单栈式存储分配：局部量＋全局量）例子1(1)

program

sort(input,

output);//sort的过程头procedure

readarray;

//sort内嵌套定义的readarray的过

var

i:integer;begin…a…end{readarray};

//readarray的过程体procedure

exchange(i,j:integer);//sort内嵌套定义的exchangevar

a:

array

[0..10]

of

integer;x:

integer;(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)beginx∶=a[i];a[i]∶=a[j];a[j]∶=x;//exchange的过程体end{exchange};procedurequicksort(m,n:integer);//sort内嵌套定义的quicksvar

k,v:integer;function

partition(y,z:integer):integer;//quicksort内嵌套定义的partition的函var

i.j:integer;//partition的函数体begin…a……v…exchange(i,j);end{partition};(14)(15)(16)(17)(18)(19)(20)begin…end{quicksort};(21)

begin…end{sort}//quicksort的过程体//sort的例程体例子1（简略图）//sort的例程体的简略视图begin………readarray{

var

i:

integer;…对a的访问…}exchange{

…对a的访问…}quicksort{

var

k,v:

integer;partition{

var

i.j:integer;…对a的访问…}}end只要一个函数在调用点前出现过，则可以对该函数进行var

a:array[0..10]of

integer;x:in调te用ge。r;sort可以调用r,e,q（在哪里？）quicksort中可以调用partition（在哪里？）partition中可以调r，e，q但是在s,r,e中都不能调用p，因为它是q私有的。因此一个函数被激活的时候，它的外层都处于激活状态，也就是说在栈中有活动记录。因此不会出现p被调用时，找不到quicksort的活动记录。（p只可能在q中被调用）例子1（问题）过程readarray,exchange和partition中引用的a均不是它们的局部变量，而是过程sort的局部变量。假如过程sort激活(调用)了过程quicksort,这时存储栈中的情形示意如图，其中在quicksort过程活动记录中有一(或一些)存储单元(用斜线描绘)用以记录过程

quicksort可以引用sort中定义的变量a和x。也就是说，为了解决对非局部量的存取问题，必须设法跟踪每个外层过程的最新活动记录的位置。关键技术：解决对非局部量的引用（存取）设法跟踪每个外层过程的最新活动记录AR的位置。跟踪办法：用静态链（如SL）。用嵌套层次显示表DISPLAY。用静态链解决对非局部量的引用（存取）(参见简略图)过程exchange由过

程（函数）partition调用，但exchange的直接外层过程是sort，所以过程exchange的活动记录的存取链指向sort的活动记录的始址。如果该程序的某次执行顺序为(调用次序)：

sort→quicksort→quicksort→partition→exchange…过程partition中引用了sort中说明的变量a，而partition的直接外层是quicksort，

quicksort的直接外层过程是sort，partitio对非局部量a的引用通过两次拉链实现。存取链就是静态链，控制链就是动态链用Display表解决对非局部量的引用（存取）另外一种存取非局部变量的办法，也是常用的有效办法。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表Display。这里所提到的“嵌套层次”，是指过程定义的层数，始终假定主程序的层数为0，因此主程序称为0层过程。如某过程p是在层次为i的过程q内定义的，并且q是包围p的直接外层，那么p的过程层数为i+1。一般编译程序处理过程说明时，将把过程层数作为重要的属性登记在符号表中。计数过程的层数很容易实现，用一个计数器Level，初值为0，每遇到过程说明则增1，过程说明结束则减1.Display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，……直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址。也即，嵌套层次i的过程的局部变量a是在由Display元素d[i]所指的那个活动记录中存放的。也就是说，嵌套层次i+1过程中的非局部变量可能在i,i-1,…,0层，对它的存取是通过display元素

d[i],d[i-],…,d[0]而获得的。例子2假定现在进入的过程的层数为i，则它的display表含有i+1个元素，依次指向现行层、直接外层……直至最外层（0层）等每一层过程的最新活动记录的地址。假定有如下四种调用情况：(a)sort→quicksort…;(b)sort→quicksort→quicksort…;(c)sort→quicksort→quicksort→partition…;

(d)sort→quicksort→quicksort→partition→exchange例子2：用Display表解决对非局部量的引用程序结构图program

main(i,0);……proc

R(c,d);……Rend

/*R*/主proc P

(a);……proc

Q

(b);PQ

callRcall

Qcall

Pcall

R……R(x,y);end

/*Q*/……Q(z);end

/*P*/……P（W

）；……R

（U

，V

）；……end

/*main*/例子3例子3：用Display表解决对非局部量的引用(1)main--->(2)P--->(3)Q--->(4)R（3）（4）主程序的活动记录d[0]spdisplaytop（1）P

的活动记录主程序的活动记录d[1]d[0]displaytopsp（2）Q

的活动记录P

的活动记录主程序的活动记录displayd[2]d[1]d[0]sptopR

的活动记录Q

的活动记录P

的活动记录主程序的活动记录displayd[1]d[0]topsp例子4现在我们要讨论，当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display。为了建立自己的display，P2必须知道它的直接外层过程(记为P的display。这意味着：当P1调用P2时必须把P0的display地址作为连接数据一传给P2。第一个激活的总是主程序，它的display表很简单，就只有一项，该指向自身的活动记录的起始地址。（有了初值，有了递推规则，那么每个动记录的display都能构造出来。）一般，P0或者就是P1自身或者既是P1又是P2的直接外层(见上图的(a)、(b)两种情形)。不论哪一种情形，只要在进入P2后能够知道P1的display就能知道P0的display，从而可直接构造出P2的display。事实上，只需从P1的display中自底而上地取过l2个单元(l2为P2的层数)再添上进入