编译原理课件-9

第9章运行时的存储组织与管理

（翻译程序必须分配目标程序运行时所需的存储空间，这些空间包括：用户定义的各种类型的变量和常数所需的存储单元；作为保留中间结果和参数传递用的临时工作单元；调用过程或函数时所需的连接单元，返回地址以及组织输入输出所需要的缓冲区。本章介绍有关运行时的存储组织和管理问题。）Compiler

2008年3月湖北大学数计学院计科系9.1数据区和属性字9.2基本数据类型的存储分配9.3数组的存储分配9.4记录结构的存储分配9.5参数传递方式及其实现9.6栈式存储分配方法9.7堆式存储分配方法9.8临时工作单元的存储分配9.9小结

2008年3月湖北大学数计学院计科系9.1数据区和属性字例：PASCAL主程序中所说明的变量运行时所需要的存储单元以及主程序运行时所需要的临时工作单元一起构成了一个数据区。数据区数据区是指一片相连的存储单元。

2008年3月湖北大学数计学院计科系在编译时，任何变量运行时存储单元都可由一对偶（数据区编号，位移）表示。其中，数据区编号是分配给数据区的唯一编号；位移是指该存储单元相对于该数据区起址的距离（或单元数）。例如：对于编号为10的数据区它的第1个存储单元可表示为（10,0）第2个存储单元可表示为（10,1）

……

第i个存储单元可表示为（10,i-1）

2008年3月湖北大学数计学院计科系程序中出现的简单变量和常量数组，由于它们所需的存储单元数在编译时就可以确定，所以在编译时就可以给它们分配存储单元，这种在编译阶段进行的存储分配工作称为静态存储分配，由静态存储分配产生的数据区称为静态数据区。在整个运行过程中，这种数据区是固定不变的。

在运行阶段分配的数据区统称为动态数据区。在运行时，一个动态数据区不是固定不变的，随着相应程序单位的调用和返回，它也会随之建立和撤销数据区。

2008年3月湖北大学数计学院计科系问题：C语言程序引用sizeof函数时，该函数的计算是在编译该程序时完成的，还是在运行该程序时完成的？解答：在C语言中，sizeof函数的计算是在编译时进行的，因为每个类型的大小是确定的，不会随程序的运行而发生变化，所以完全可以在编译时计算出来。

2008年3月湖北大学数计学院计科系beginprocedureAbeginprocedureBbegin…end;procedureCbegin…end;end;procedureDbegin…end;…end;若主程序和每个过程都有自己的数据区，那么将所能引用的数据区的起址按照它们建立的先后顺序排列起来就构成一个DISPLAY表。例：当执行过程C时，DISPLAY表为主程序的数据区起址过程A的数据区起址过程C的数据区起址

2008年3月湖北大学数计学院计科系属性字程序中变量的属性常常不能在编译阶段全部确定出来。为此编译阶段在给变量分配存储地址的同时，还为它分配一个属性字，用以记录该变量在运行时所确定的属性。例如动态数组，在运行时，一旦知道了存储空间属性，就调用getarea分配存储空间，并把所分配的存储空间的起址存放在相应的属性字中，以后总是通过这个属性字去访问相应的数组元素的地址。

2008年3月湖北大学数计学院计科系9.2基本数据类型的存储分配基本数据类型：整型、实型、布尔型和指示器型。整型变量：通常占用数据区中的一个单元，其值按机器内部的标准整数形式存储。实型变量：通常占用一个字。布尔型变量：占用一个字，常用零表示“false”值，用非零表示“true”值。指示器型变量：通常占用一个单元。在某些情况下，也把指示器表示成两个相邻单元，一个是其属性字，指明它的类型，另一个单元包含它所真正指向的值。

2008年3月湖北大学数计学院计科系9.3数组的存储分配单块存储方式

单块存储方式就是把数据区中的一片相连单元分配给数组的元素，数组的所有元素则按次序连续地存储在这片数据区中。元素的排列次序通常为两种：按行的次序和按列的次序。两种存储方式：单块存储、多块存储

2008年3月湖北大学数计学院计科系对arrayA[1..m,1..n]ofinteger所说明的数组，如果以按行的次序存储数组元素的值，则任一数组元素A[i,j]在数据区中的地址可由下式求得：address(A[i,j])=address(A[1,1])+(i-1)*n+(j-1)address(A[i,j])=address(A[1,1])-n-1+(i*n+j)

2008年3月湖北大学数计学院计科系对arrayA[1..m,1..n]ofinteger所说明的数组，如果以按行的次序存储数组元素的值，则任一数组元素A[i,j]在数据区中的地址可由下式求得：address(A[i,j])=address(A[1,1])+(i-1)*n+(j-1)address(A[i,j])=address(A[1,1])-n-1+(i*n+j)注：上式中的第一部分是一常数，仅需计算一次。

2008年3月湖北大学数计学院计科系设A是下面的说明语句定义的一个n维数组：

arrayA[l1..u1,l2..u2,..,ln..un]ofinteger

假设di=ui-li+1,i=1,2,…,n，即di为第i对界偶的界差，亦即第i维中不同下标值的个数，在按行的次序存放方式的前提下，数组元素A[i1,i2,...,in]的地址为：

address(A[l1,l2,...,ln])+(i1-l1)*d2*d3*…*dn+(i2-l2)*d3*d4*…*dn+…+(in-1-ln-1)*dn+(in-ln)

2008年3月湖北大学数计学院计科系经整理后，得

address(A[i1,i2,...,in])=Conspart+Varpart其中，Conspart=address(A[l1,l2,...,ln])-((…((l1*d2+l2)*d3+l3)*d4+…+ln-1)*dn+ln)

Varpart=(…(i1*d2+i2)*d3+…+in-1)*dn+inBegin

Varpart:=1;j:=1;whilej<ndobegin

Varpart:=Varpart*dj+1+ij+1;j:=j+1;endendVarpart

2008年3月湖北大学数计学院计科系信息向量与数组分配程序数组的信息向量：属性字l1u1d1l2u2d2………lnundnnConsparttypeBaseloc

2008年3月湖北大学数计学院计科系数组分配程序：begini:=1;Size:=1;Conspart:=0;whilei≤ndobegin

di:=ui-li+1;Size:=Size*di;

Conspart:=Conspart*di+li;

把li,ui,di填入信息向量中;i:=i+1end

调用getarea，按Size分配数据区；

Baseloc:=该数据区起址；

Conspart:=Baseloc-Conspart;

把n,Conspart,type和Baseloc填入信息向量中

end.

2008年3月湖北大学数计学院计科系多块存储方式

多块存储方式是对每一行都分配一个单块数据区，每行的元素按递增次序存放在这块数据区中。此外，还设一个指示器表，用以指示这些单块数据区的开始位置。

2008年3月湖北大学数计学院计科系9.4记录结构的存储分配记录结构是由不同类型的数据组合起来的一种结构。例如，记载学生信息（名字、学号、年龄）的卡片就可以写成如下的记录形式：

recordname:char-string[20];

number:integer;

age:integer;end存储分配方式：将其分量依次连续存储在一个数据区中。

2008年3月湖北大学数计学院计科系9.5参数传递方式及其实现一个过程或子程序一经定义，就可以被调用。调用与被调用者之间的信息交流是通过全局量或经由参数传递的方式进行。参数传递方式：

换名、传值、传地址、传结果以及数组名用做参数和过程名用做参数。

2008年3月湖北大学数计学院计科系换名：用过程体的代码直接替换过程调用语句，其中的形参被替换为相应的实参。传值：过程调用时，将实参的值传递给形参。形参值的改变不会引起实参的变化。传地址：过程调用时，将实参的地址传递给形参。形参值的改变会引起实参的变化。传结果：过程调用时，形参用两个存储单元分别存放实参的值和地址。调用完毕，将形参的值按存储的地址返回给实参。形参：过程定义语句中的参数。实参：过程调用语句中的参数。

2008年3月湖北大学数计学院计科系问题：对于下面的程序：

procedureP（X,Y,Z）；

beginY:=Y+1;Z:=Z+X;endP；

beginA:=2;B:=3;P（A+B,A,A）

printAend.

若参数传递的办法分别为（1）换名（2）传地址（3）传结果（4）传值。试问：程序执行后输出的A值分别是多少？

2008年3月湖北大学数计学院计科系9.6栈式存储分配方法栈式存储分配方法：指把整个程序的存储空间都安排在一个栈内。主要思想：①进入主程序时，将主程序定义的各类量（全程量）所需存储空间分配于栈的顶部；②每当调用一个子程序（过程/函数）时，就将它所需的存储空间分配于栈的当前顶部；③每当一个子程序（过程/函数）运行结束时，就从栈中释放它所占空间；④整个程序执行完后，释放它所占用的全部空间。

2008年3月湖北大学数计学院计科系一个过程的活动是指该过程的一次执行。即每次执行一个过程体，产生该过程体的一个活动。过程P的一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序列，包括执行P时调用其它过程花费的时间。在任一时刻，几个过程可以同时处于正在执行的进程中，但只有一个过程是当前正在工作的，这个过程称为现行过程。其它的过程只是处于等待现行过程的完成和返回。过程的活动与活动记录活动记录：为了记录过程一次活动的数据信息而分配的一片连续的存储区域。

2008年3月湖北大学数计学院计科系

在某些程序设计语言中，过程可以嵌套定义或调用，一个过程可以引用包围它的任一外层过程所定义的变量或数组，也就是说，运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。跟踪外围过程最新活动记录地址的方法：静态链Display表

2008年3月湖北大学数计学院计科系1、静态链和活动记录思想：利用一个称为静态链的指针，该指针为活动记录的一个域，指向直接外层过程最新活动记录的首地址。活动记录结构静态链：从一个过程的当前活动记录指向其直接外层过程的最新活动记录的首地址。动态链：指向调用该过程前正在运行的过程的最新活动记录的首地址。动态链（老SP）返回地址静态链形参个数形参单元简单变量信息向量临时单元SP

2008年3月湖北大学数计学院计科系ProgramP;

vara,x:integer;procedureQ(b:integer);

var

i:integer;procedureR(u:integer;var

v:integer);

varc,d:integer;beginifu=1thenR(u+1,v);v:=(a+c)*(b-d);

end{R}beginR(1,x);end{Q}procedureS;

varc,i:integer;begina:=1;Q(c);end{S}begina:=0;S;

end.{P}活动记录结构临时单元信息向量简单变量形参单元形参个数静态链返回地址动态链（老SP）

2008年3月湖北大学数计学院计科系2、嵌套层次显示表(display)和活动记录思想：利用一张display表，该表为活动记录的一部分，记录所有外层过程最新活动记录的首地址。活动记录结构Display表：该表自顶向下每个单元依次存放着现行层，直接外层，…，直至最外层（主程序层）等每一层过程最新活动记录的首地址。全局display：主调程序的活动记录中display表的首地址。display动态链（老SP）返回地址全局display形参个数形参单元简单变量信息向量临时单元SP

2008年3月湖北大学数计学院计科系ProgramP;

vara,x:integer;procedureQ(b:integer);

var

i:integer;procedureR(u:integer;var

v:integer);

varc,d:integer;beginifu=1thenR(u+1,v);v:=(a+c)*(b-d);

end{R}beginR(1,x);end{Q}procedureS;

varc,i:integer;begina:=1;Q(c);end{S}begina:=0;S;

end.{P}活动记录结构临时单元信息向量简单变量display形参单元形参个数全局display返回地址动态链（老SP）

2008年3月湖北大学数计学院计科系9.7堆式存储分配方法

基本思想：当一个程序开始执行时，有很大一片单元用做空闲存储区，当程序开始运行时，可多次调用getarea分配存储空间。运行结束，则调用freearea释放占用的存储空间。多次调用getarea和freearea之后，原来的存储区可能变成如下形式：…空闲使用空闲空闲使用…空闲使用使用需对空闲区进行有效管理。首次匹配法、最优匹配法、最差匹配法

2008年3月湖北大学数计学院计科系首次匹配法：按序查看空闲区，选出其中第一个满足所需容量要求的空闲区来进行分配。时间：分配时查表，归还时不需查表缺点：容易造成存储空间浪费最优匹配法：选出空闲区中最接近于（大于或等于）所需容量要求的空闲块来进行分配。时间：须将空闲块由小到大进行排序，分配、归还时均需查表缺点：花费时间较多最差匹配法：选出最大的空闲块来进行分配。时间：须将空闲块由大到小进行排序，归还时均需查表缺点：可能无法满足较大的存储空间要求

2008年3月湖北大学数计学院计科系9.8临时工作单元的存储分配临时工作单元也称为临时工作变量。其作用域为从该变量开始确定其值到最后一次使用它之间的这段时间间隔。涉及临时工作变量v的代码可分为两大类：1、“STv”，即对v赋值，从而确定了变量v的作用域的起点；2、“用v”，其中包括“LDv”、“+v”、“*v”等等。就一个代码序列中同一个v而言，这种用v指令的最后一条就是v的作用域的终点。

2008年3月湖北大学数计学院计科系例如，对于算术表达式((a+b)*(c+d)+e*f)*(g-h)一般编译程序将生成如下目标代码：①LDaADDb③STT2LDeMULfADDT2②STT1LDcADDdMULT1④STT3LDgSUBhMULT3T1的作用域T2的作用域T3的作用域由于T1、T2、T3的作用域互不相交，所以只需一个临时工作变量T1就够了。

2008年3月湖北大学数计学院计科系例如，对于算术表达式(a+b)*(c*d+e*f)一般编译程序将生成如下目标代码：LDaADDbSTT1LDcMULdSTT2LDeMULfADDT2MULT1T2的作用域T1的作用域

T1的作用域包含了T2的作用域，所以需要两个临时工作变量。

2008年3月