编译原理第九章

编译原理电子教案第九章运行时存储空间组织谢强计算机科学与技术学ieqiang@本章的主要内容目标程序运行时的活动运行时存储器的划分静态存储分配简单栈式存储分配嵌套过程语言的栈式实现堆式动态存储2本章要求

知识点：有关源语言中一些问题的讨论，存储组织，运行时刻存储分配策略，对非局部名字的访问，参数传递。深刻理解：活动记录，栈式存储分配，访问链（存取链），display表。熟练掌握：（1）对于已知过程，设计出其活动记录；（2）对于已知程序，若采用栈式存储分配，随着程序的执行，画出相应动态栈，访问链（存取链）以及display表的变化；3计算环境计算源程序映射运行时的环境目标代码计算源程序中的名字（常量，变量）→目标机存储空间。它受命于源程序的执行语义。

源程序由一组过程按某种规则组成。过程的一次执行称作一次活动，在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。编译程序根据如何组织运行环境而生成目标代码。

在程序语言中，程序中使用的存储单元都由标志符来表示。它对应的内存地址都是由编译程序在编译时或由其生成的目标程序在运行时进行分配。

4本章教学线索1目标程序运行时的活动1.1过程的活动1.2说明的作用域（作用范围）1.3名字与存储的绑定1.4参数传递2运行时存储器的划分3静态存储分配4简单栈式存储分配5嵌套过程语言的栈式实现6堆式动态存储51.1过程的活动过程：过程定义是一个说明，其最简单的形式是一个标识符和一段语句相关，标示符是过程名，语句是过程体。调用：当过程名出现在可执行语句里的时候，称该过程在这一点被调用。过程调用导致过程体的执行。过程的活动：一个过程的活动指的是该过程的一次执行，也就是说，每次执行一个活动。活动的生存期：指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行该过程时调用其它过程花费的时间。活动的生存期或者是嵌套的，或者是不重叠的。过程的递归：如果一个过程在没有退出当前的活动时，又开始其新的活动，则这个过程是递归的。（递归有直接递归和间接递归）61.2说明的作用域（作用范围）说明把名字与名字的属性信息绑定在一起。说明的作用域是一个说明起作用的范围（源程序行文）。一个名字在源程序行文中可能有几处说明，语言的作用域规则规定了在语句序列中引用的一个名字时，该名字是在何处说明的。编译时，处理说明语句时把名字及其属性信息填写进符号表（add（id.entry，））；处理引用名字时，查找这个名字的属性信息（lookup（）），符号表管理程序根据语言的作用域规则，使lookup（）返回id的作用域中绑定的属性信息。71.3名字与存储的绑定名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程。引进两个函数，environment和state。environment把名字映射到一个存储单元上；state把存储单元映射到那里所存放的值上。可以说，函数environment把一个名字映射为一个L-value（左-值）,而函数state把一个L-value（左-值）映射为一个R-value（右-值）。如图下图所示。存储单元值存储分配

程序运行environmentstateL-valueR-value从名字到值的两个阶段映射名字

静态概念动态对应过程定义过程活动名字说明名字的绑定说明的作用域活动的生存期81.4参数传递形参与实参：过程定义中的参数称为形参；过程调用中的参数称为实参。问题：如何把实在参数传递给形参？函数的返回值怎样获取？参数传递的三种形式：传地址：把实在参数的地址传递给相应的形式参数；传值：直接把实在参数的值传递给形式参数传名：换名，少见的方法！特别要注意传地址与传值的区别！9本章教学线索1目标程序运行时的活动2运行时存储器的划分2.1运行时刻内存的划分2.2活动记录2.3存储分配策略3静态存储分配4简单栈式存储分配5嵌套过程语言的栈式实现6堆式动态存储102.1运行时刻内存的划分运行时刻的存储空间必须划分以用来存放：生成的目标代码；数据目标；用于保存过程活动踪迹的一个控制栈。存储空间划分的各部分：

目标代码静态数据栈堆1.编译后知道目标代码的大小。2.Pascal主程序中的数据,c,FORTRAN3.栈:Pascal4.堆:Pascal112.2活动记录把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录。一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。对于Pascal语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；当这个过程的活动执行完后，把它从栈顶弹出。源语言不同，实现方法不同，组成活动记录的域不同。实现Pascal语言的活动记录的结构如图所示。临时单元内情向量局部向量形式单元静态链动态链返回地址连接数据SPTOP12连接数据：返回地址动态链：指向调用该过程前的最新活动记录地址的指针。运行时，使运行栈上各数据区按动态建立的次序结成链，链头为栈顶起始位置。静态链：指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。形式单元：存放相应的实在参数的地址或值。局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）132.3存储分配策略静态分配策略：在编译时对所有的数据对象分配固定的存储单元，并且在运行时始终保持不变。栈式动态分配策略：在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占的空间就予以释放。堆式动态分配策略：在运行时把存储器组织成堆结构，以便用户可以对存储空间进行申请与归还。14活动树程序执行期间的控制流：程序执行的控制是顺序的；过程的每一次执行都是从过程体的开头开始，并最终把控制返回到紧接着该过程被调用点的后面。用一颗树来描绘控制进入和离开活动的途径。这样的树称作活动树。在一棵活动树中：每一个结点代表一个过程的活动；

根结点代表主程序的活动；

代表a的结点是b结点的父结点当且仅当控制从活动a进入活动b；结点a在结点b的左边当且仅当a的生存期发生在b的生存期之前。控制栈程序执行的控制流对应于从根开始，按先根次序遍历活动树。因此，用一个栈保存过程活动的生存踪迹，把它称作控制栈。当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。15srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)控制栈ssrsq(1.9)sq(1.9)p(1,9)sq(1.9)q(1,3)sq(1.9)q(1,3)p(1,3)sq(1.9)q(1,3)q(1,0)sq(1.9)q(1,3)q(2,3)活动树与控制栈

控制栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列：

s,q（1，9），q（l，3），q（2，3），从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系。结论：扩充控制栈可用来实现如Pascal语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。16本章教学线索1目标程序运行时的活动2运行时存储器的划分3静态存储分配3.1静态分配3.2FORTRAN的局部数据区3.3临时变量的地址分配4简单栈式存储分配5嵌套过程语言的栈式实现6堆式动态存储173.1静态分配在编译时就能够确定一个程序在运行时所需要的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能够确定每个数据项的单元地址。适于静态管理的语言必须满足的条件：数组的上下界必须是常数过程调用不允许递归不允许用户动态地建立数据实体编译程序可以确定出现在程序中的数据实体的地址（一般相对于各数据区基地址的偏移量)。由于过程调用不允许递归，数据实体的存储地址就和过程相联系，过程调用的活动记录就可以直接安排在目标代码之后，并把各数据项的存储地址填入到相关的目标代码中，以便在运行时访问这些数据存储空间。这里，不存在对存储区域的再利用。目标代码运行时不必进行运行时的存储管理。183.2FORTRAN的局部数据区FORTRAN的编译程序将每个程序段都定义对应的局部数据区，每个数据区都有一个编号，在地址分配时，在符号表中，对每个数据名将登记上它是属于哪个数据区的，以及在该区中的相对位置（DA、ADDR）。一般情况下，程序段的局部数据区可以直接安排在该段程序的指令代码之后，编译时统计每个数据区的单元数，对于各区的首地址暂时不分配，在运行前再用一个“装入程序”（LOADER）把它们连成一个整体。FORTRAN的局部数据区内容：临时变量数组简单变量形式单元寄存器保护区返回地址称为：隐参数返回地址：用来保存调用此程序段时的返回地址；寄存器保护区：用来保存调用段留在寄存器中的有关信息。形式单元：用来存放实在参数的地址或值。193.3临时变量的地址分配

在三地址代码－四元式生成中将产生大量的中间变量，在存储空间的分配中也必须对这些临时变量分配存储空间。分配策略：如果两个临时变量名作用域不相交，则它们可以分配在同一单元中。一个临时变量名自它第一次被定值（赋值）的地方起直至它最后一次被引用的地方止，这区间的程序所能到达的全体四元式构成了它的作用域。令临时变量名都分配在局部数据区中，若某一单元已分配给某些临时变量名，则把这些名字的作用域（它们必须互不相交信息记录）作为此单元的分配信息记录下来。每当要对一个新临时变量名进行分配时，首先求出此名的作用域，然后按序检查每个已分配单元，一旦发现新求出的作用域与某个单元所记录的全部作用域均不相交时就把这个单元分配给这个新名，同时把它的作用域也添加到该单元的分配信息之中。如果新临时变量的作用域和所有已分配单元的作用域均有冲突，则就分配给它一个新的单元，同时把新名的作用域作为此单元的分配信息。20一般情况下，四元式中的临时变量都是一边生成，马上使用，一次赋值，一次使用，其作用域类似于配对使用的括号。因此，可以用一个栈来放表达式计算过程中的中间结果。令k为栈的指示器，设它的初值是局部区中用来存放临时变量值的区域首地址，每当发现对一个新的临时变量名Ti定值时，就用k的现行值作为Ti的地址，然后把k累增1。每当引用了某个临时变量名Ti作为操作数时（此时Ti的地址必已分配），就把指示器k的值递减1。例子：P25421本章教学线索1目标程序运行时的活动2运行时存储器的划分3静态存储分配4简单栈式存储分配4.1语言要求4.2基于栈的存储控制4.3同静态存储分配的区别4.4整体的分配情况4.5C语言的活动记录4.6C的过程调用、进入、数据对象空间分配和过程返回5嵌套过程语言的栈式实现6堆式动态存储224简单栈式存储分配基于控制栈的原理：

存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的开始和结束。与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的存储空间也随之消失。确定活动记录中局部数据的地址：假设sp标记一个活动记录的开始的位置，dx表示x的地址相对于sp的偏移量。那么，x在过程的目标代码中的地址可写成dx（sp），在运行时刻，当把x的活动记录筑于栈顶时，寄存器sp被赋于实际的地址，sp可以是一个寄存器。23调用序列和返回序列

通过在目标代码中生成调用序列和返回序列实现过程的调用。激活一个过程的活动是执行过程语句的结果。过程语句：

p(e1，e2，……，en)的目标代码（调用序列）完成任务：1）调用者对实在参数求值，并把它们传送给被调用过程的活动记录的参数域。2）调用者在被调用者的活动记录中存放返回地址和老sp之值。之后调用者把sp之值增加到top的下一个存储单元位置（被调用者的活动记录首地址）。3）被调用者存放寄存器值和其它状态信息。4）被调用者初始化其局部数据并开始执行。返回序列，return目标代码完成的任务是：被调用者在自己的活动记录的返回值域中放一个返回值。利用状态域中的信息，被调用者恢复sp和其它寄存器，并且按返回地址转移到调用者的代码之中。调用者复制返回值到自己的活动记录中。任务的划分，根据源语言、目标机器和操作系统等具体情况而定。上述任务，由运行支持子程序完成，可视为虚拟机指令。244.1语言要求过程不允许嵌套，但允许过程递归调用，如C语言。254.2基于栈的存储控制将存储组织成一个栈，过程的活动记录作为一个元素进行出入栈管理。运行时，每当进入一个过程时，就把它的活动记录入栈，而形成该过程工作时的数据区，当该活动结束时，再出栈。264.3同静态存储分配的区别不同的是：每次活动过程中，局部名字与新的存储单元绑定，活动结束后，活动记录从栈中弹出，局部名的存储空间也随之消失。注意：1）因而会出现同一过程的不同活动（不同时期）存储空间的分配不一样

2）由于递归，过程的活动可能有多个同时在栈中（活动记录）27

4.4整体的分配情况

R的活动记录Q的活动记录Main的活动记录全局数据区TopSP程序运行时的某一时刻，表明主过程Main调用Q，而Q又调用R。SP：总是指向现行过程活动记录的起点，用于访问局部数据；Top：总是指向（已占用）栈顶单元。284.5C语言的活动记录1）连接数据：老SP、返回地址2）参数个数3）形式单元4）过程的局部变量、数组内情向量、临时工作单元注意：C语言的非局部变量仅能出现在源程序头，非局部变量可采用静态存储分配5）局部变量（形参）的访问： 在编译时，对局部变量和形参都分配了存储单元，其地址为相对于活动记录基地址SP的偏移量。则其绝对地址就为：

绝对地址=活动记录基地址+相对地址

临时工作单元内情向量简单变量形式单元参数个数返回地址老SPSPTOP294.6C的过程调用、进入、数据对象空间分配和过程返回1）调用：将实参的地址或值传递给新的活动记录中的形式单元。 过程调用的四元式：paramT1paramT2……paramTncallP，n由于形式单元在活动记录中的起始位置是固定的，因此对于每一个形式参数paramTi，可以翻译为如下指令：（i+3）[TOP]=Ti

（传参数值）（i+3）[TOP]=addr（Ti）（传参数地址）2）过程进入四元式：CALLP，n的翻译：

1[TOP]=SP（保护现行的SP，即老SP）

3[TOP]=n（传递参数个数）

JSRP（转子指令，转向P的第一条指令）303）数据对象空间分配

SP=TOP+1（定义新的SP）

1[SP]=返回地址（保护返回地址）

TOP=TOP+L定义新的TOP

（L为过程P的活动记录所需的单元数，在处理说明语句时可以计算出来）4）过程的返回（过程的活动记录出栈，同时恢复栈顶活动记录的TOP和SP）如果有返回值（函数），将返回值传递到每个特定寄存器中。

TOP=SP–1SP=0[SP]x=2[TOP]UJ0[x]（UJ为无条件转移语句，按x中的返回地址实行变址转移）31本章教学线索1目标程序运行时的活动2运行时存储器的划分3静态存储分配4简单栈式存储分配5嵌套过程语言的栈式实现5.1嵌套过程语言非局部名字访问的实现5.2参数传递的实现6堆式动态存储325嵌套过程语言的栈式实现语言要求：过程不仅允许递归调用，还允许过程进行嵌套定义。存储分配的实现：采用栈式存储分配，对于运行时的局部名和形参完全可以采用简单栈式存储分配，由于允许过程嵌套定义，因此对非局部变量的访问需要单独处理，可以采用:静态链或显示表（Display）来实现。嵌套层次：记录过程在定义时所在的层数。约定主程序的层数为0。如果过程P的直接外层Q的层数为i，则P的层数就为i+1。在实现时，采用一个计数器，遇到过程定义procBegin时，计数器增加1，遇到过程结束procend时，计数器减1。将过程的层数作为过程名的一个属性记录在符号表中。335.1嵌套过程语言非局部名字访问的实现1）静态链和活动记录在活动记录中增加一个域，存储指向直接外层的最新活动记录的地址，这样形成的链称为静态链。它表明过程定义时的嵌套关系。活动记录中存储老SP形成的链称为动态链，它表明了过程活动时的调用关系。活动记录的结构：临时单元内情向量简单变量形式单元形参个数静态链返回地址动态链（老SP）SPTOP对于非局部变量的返回可以沿静态链进行访问。34programP;vara,xinteger;procedureQ(b:integer);vari:integer;procedureR(u:integer,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;end011224d23c22v（形参）21u（形参）202(形参个数）191118返回地址171116i15b(形参）141(形参个数）13012返回地址11510i9c80706返回地址504x3a201返回地址00PSQR过程Q调用R时活动记录情况352）嵌套层次显示表和活动记录在进入一个过程后，在建立其活动记录区的同时建立一张嵌套层次表display，该表给出了过程的嵌套关系，如果该过程的嵌套层次为i，则它的display表就包含i+1个单元（假设主过程的层次为0），display本身是一个栈。由于过程的层数可以静态确定，因此每个过程的display表的体积在编译时可以确定，可以将display表作为活动记录的一部分，置于形式单元的上端。例如：R的外层是Q，Q的外层是P，则R运行时display表的情况：R现行活动记录地址Q的最新活动记录地址P的活动记录地址36对于非局部变量的绝对地址就为：

绝对地址=display[静态层次]+相对地址（非局部变量所在的静态层次可以在编译时处理说明语句时确定，可以记录在符号表中）在活动记录中，display表的相对位置d是确定的，因此，在现行过程中引用了某一外层过程（k层）的变量x，可以用以下指令获取x的值：LDR1，（d+k）[SP]/*获取x所在的最新活动记录的SP值*/LDR2，x[R1]/*变址取数，把X的值传递给R2*/临时单元内情向量简单变量Display形参参数个数全局display返回地址老SP(动态链）SPTOP全局display：连接数据，用于记住调用过程的display表的地址，作为生成本过程display的关键参数。display根据全局display所指示的地址，从调用它的过程中的display表中抄入i个地址（假设该过程层数为i），然后将自己的起始地址放在display表顶。37programP;vara,xinteger;procedureQ(b:integer);vari:integer;procedureR(u:integer,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;end0112191318017b（形参）161（形参个数）159(全局display）14返回地址13512i11c105908072（全局display)6返回地址504x3a201返回地址00displaydisplaydisplayS调用Q时PSQ385.2参数传递的实现ParT，T为数组根据不同语言的要求或传递数组T的首地址，或传送它的内情向量地址。ParT，T为过程一般需要传递过程T的入口地址和现行的display地址。ParT，T为标号一般需要传递标号T的地址和标号定义所在过程的活动记录首地址。ParT，T为形式参数传递形式单元T的内容。39本章教学线索1目标程序运行时的活动2运行时存储器的划分3静态存储分配4简单栈式存储分配5嵌套过程语言的栈式实现6堆式动态存储6.1堆式分配的必要性（以C语言为例）6.2

堆式存储管理的实现6.3

减少碎片的技术6.4

空间的释放406堆式动态存储对于允许程序为变量在运行时动态申请和释放存储空间的语言，采用堆式分配是最有效的解决方案。堆式分配的基本思想是，为运行的程序划出适当大的空间(称为堆Heap)，每当程序申请空间时，就从堆的空闲区找出一块空间分配给程序，每当释放时则回收。416.1

堆式分配的必要性（以C语言为例）在C中处理链表等结构时,常常随机地插入或删除一些结点,利用指针变量和结构类型,可动态地生成新结点(使用malloc()函数),或删除之(使用free()函数).例如structnode{chardata;structnode*next;}；定义了链表的结点，下面函数可在表的尾部添加新结点:voidAppend(structnode*head,charch){structnode*p=head;while((p->next)!=NULL)p=p->next;p->next=malloc(sizeof(structnode));p->next->data=ch;p->next->next=NULL;}还可用下面的函数在表头删除一结点:voidDelete(structnode*head){structnode*p=head;if(p!=NULL){head=head->next;free(p);}}426.2

堆式存储管理的实现1定长块管理

堆式动态储分配最简单的实现是按定长块进行。初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链成一个链表，用指针available指向链