编译原理(10)

《编译原理(10)》由会员分享，可在线阅读，更多相关《编译原理(10)（28页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,（,）,1,第十章 目标程序运行时的存贮组织,读入整数并排序的,Pascal,程序,Program sort(,input,output,);,var,a:array0.10 of integer;,Procedure,readarray,;,Var,i:integer,;,Begin,For i:=1 to 9 do,read(ai,),End;,Function,partition(y,z:integer):integer,;,var,i,j,x,v:integer,;,Begin,End;,P

2、rocedure,quicksort(m,n:integer,);,Var,i:integer,;,Begin,If(n,m)then begin,i:=,partition(m,n,);,Quicksort(m,i-1);,Quicksort(i+1,n);,end;,End;,Begin,a0:=-9999;,a10:=9999;,readarray,;,quicksort(1,9),End.,2,关于源程序的一些问题,我们编写的这些源程序实际上是静态的程序文本；,它们的目的是要在计算机上正确的运行；,在运行过程中，这些静态程序文本必须于程序运行时的活动状态联系在一起，才能实现程序的目的；

3、,那么，程序运行时，源程序文本中的标示符对应运行时的不同数据对象；,数据对象的空间分配和释放需要管理策略，这些策略由运行的支撑程序包运行管理。,这就是编译程序要完成的运行环境和存贮管理。,3,关于源程序的一些问题,源程序可以由不同的过程组成；,在执行过程中，,过程,的每次执行称为过程的一个,活动,。,如果这个过程设计为递归调用过程，那么，则会在某一个时刻可能有它的几个活动都活跃着；,过程的每一次调用，都会引起一个活动，这个活动就会调用编译软件的存贮管理的软件包给活动的数据对象分配相应的数据空间；,4,关于源程序的一些问题,过程,过程定义,是一个声明，它的最简单形式是把一个标识符和一个语句联系起

4、来；,标识符是过程名；,语句是过程体；,过程调用,表现为过程名出现在执行语句中；,如果过程调用出现在,表达式,中，则这个过程就是函数，这个调用就是,函数调用,；,函数,是特殊的过程，它是具有一个返回值的过程；,其实一个完整的,程序,就是一个过程；,过程参数,形式参数,：过程定义中表明的标识符；,实在参数,：过程调用中表明的标识符；,在过程调用中，实在参数要取代形式参数；,这需要编译程序的运行环境存贮空间管理；,5,关于源程序的一些问题,活动树,每次过程的调用都会产生一个活动；,过程的调用可能会嵌套或者递归，这时可能会有多个活动同时活跃，活动树产生了！,控制流,程序执行时过程的调用是按照一定的步

5、骤和顺序实施的，这就是所谓的控制流；,控制流是连续的。程序的执行由一些连续的步骤组成的，在任何一步，控制都处于程序中的某点；,过程的每次执行都从过程体的起点开始，最后控制返回到直接跟随本次调用点的位置；,过程间控制流的特点为活动树产生和应用提供了条件；,活动的生存期：,是过程执行的第一步和最后一步之间的步序列，包括消耗在执行被这个过程所调用的其他过程所用的时间，以及再由那些被调用过程又调用别的过程所用的时间，以此类推。,不同过程的活动生存期可能重叠，这时就出现了所谓的递归和嵌套等。,6,关于源程序的一些问题,递归,如果一个过程的前一个活动结束前，它的一个新的活动又开始，则这样的过程是递归的；,

6、递归过程不必直接调用自己，过程,p,可以调用另一个过程,q,，然后,q,通过一系列过程调用之后再调用了,p,，这也是递归调用；,活动树,描述控制进入和离开活动的方式可以用一棵的方式，这就是活动树；,活动树的每一个结点代表了过程的一个活动；,根结点代表主程序的活动；,结点,a,是结点,b,的父结点，当且仅当控制流从,a,的活动进入,b,；,a,结点处于,b,结点的左边，当且仅当,a,的生存期先于,b,的生存期；,结点和活动是一一对应的，所以控制结点就是控制活动。,7,关于源程序的一些问题,s,r,q(1,9),q(5,9),p(1,9),q(1,3),q(2,3),P(1,3),q(1,0),q

7、(3,3),P(2,3),q(2,1),q(7,9),p(5,9),q(5,5),q(9,9),q(7,7),p(7,9),活动树,8,9,10.0,概述,在代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配。,编译程序需要一定的存贮空间以使目标程序在其上运行，该存贮空间需容纳生成的目标代码和目标代码运行时的数据空间。,数据空间包括,：用户定义的各种类型的数据对象（变量和常量）所需的存贮空间；作为保留中间结果和传递参数的临时工作单元；调用过程时所需的连接单元；组织输入,/,输出所需的缓冲区。,编译过程中，有些数据对象所占用的空间,可以确定,，有些数据对象具有可变体积和待编译性质

8、，,无法在编译时确定,存贮空间的位置。,作为运行时存贮分配的一个原则是尽可能对数据对象进行静态分配。,10,10.0,概述,存贮空间常常划分为：目标代码区、静态数据区、栈区、堆区。,目标代码区用以存放目标代码，是固定长度，编译时能够确定。,静态数据区用以存放编译时能确定所占用空间的数据。,堆栈区用于可变数据以及管理过程活动的控制信息。,存贮组织要解决的问题是把静态的源程序与该程序的目标程序运行时的动态活动联系起来，即要搞清楚运行中的程序信息是如何进行存贮和访问的。,所谓数据空间,分配,，本质上看，是将程序中的每个名字与一个存贮位置关联起来，该存贮位置用以容纳名字的值。,源语言的结构特点、源语言

9、的数据类型、源语言中决定名字作用域的规则等因素影响存贮空间的管理和组织的复杂程度，决定数据空间分配的基本策略。,code,Static data,stack,(,可变区域,),heap,名字（标识符）,存贮位置,值,环境,状态,11,10.1,数据空间的三种不同使用方法和管理方法,数据空间的使用和管理方法从大类分为两种：,静态和动态,。而动态又分为：,栈式和堆式两种,。,静态存贮分配策略,：如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存贮位置。,动态存贮分配策略,：目标程序在运行时所需要的数据空间，在编译时无法知道，它所

10、需要的数据空间的大小要待程序运行是动态地确定。有两种存贮分配方式：,栈式,和,堆式,。,栈式存贮,：,1,、将整个程序的数据空间设计为一个栈；,2,、每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间；,3,、过程所需数据空间包括两部分：一部分是本次调用中的数据对象；另一部分是用以管理过程活动的记录信息；,4,、当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动继续进行。,堆式存贮,：,1,、自由地申请数据空间和退还数据空间；,2,、数据空间的利用不服从“先申请后释放，后申请先释放”的原则；,3,、这种存贮方式空间的利用率可能受到限制。容易产

11、生碎片。,12,10.2,栈式存贮分配的实现,栈式存贮分配的基本策略是调用一个过程时在栈顶分配所需数据空间，返回时，在栈顶释放数据空间。,过程的活动记录,是一段连续的存贮区，用以存放过程的一次执行所需要的信息。,信息包括：,临时工作单元,：计算表达式过程中需要存放中间结果用的临时值单元；,局部变量,：一个过程的局部变量；,保存机器状态,：容纳该过程执行前关于机器状态的信息，如程序计数器、寄存器的值等；,存取链,：用以存取非局部变量，这些变量存放于其他过程活动记录中。（,所谓链，实际上是链接，包含指针,）；,控制链,：指向调用该过程的那个过程的活动记录；,实参,：形式单元。由调用过程向该被调用过

12、程提供实参的值；,返回地址,：保存该被调用过程返回后的地址。,临时工作单元,局部变量,机器状态信息,存取链,控制链,实参,返回地址,13,10.2.1,简单的栈式存贮分配的实现,简单的特征是：,没有分程序结构，过程定义不嵌套，允许过程递归调用,。,存贮空间的分配策略,：运行时，每当进入一个过程时，则为该过程分配一段存贮空间，当一个过程工作完毕后返回时，它所占用的存贮区则释放。,程序在运行时，存贮空间（栈）中在某一个时刻可能会包含不同过程的几个活动记录；可能会包含某个过程的几个活动记录（递归调用）。,同一个存贮位置，不同的运行时刻分配给不同的数据对象。,在栈的最顶端数据区有两个指针：,SP,总是

13、指向现行过程活动记录的起点；,TOP,总是指向占用的栈顶单元。,Program main;,全局变量或数组的说明；,proc R;,end(R,);,proc Q,end(Q,),主程序执行语句,end.(main,),14,10.2.1,简单的栈式存贮分配的实现,R,的活动,记录,Q,的活动,记录,主程序全局,数据区,Q,的活动,记录,Q,的活动,记录,主程序全局,数据区,Q,的活动,记录,主程序全局,数据区,R,的活动,记录,主程序全局,数据区,TOP,SP,控制链（老,SP,）,返回地址,参数个数,实参（形式单元）,局部简单变量,局部数组的内情向量,临时工作单元,TOP,SP,主程序全局

14、数据区,Q,的活动记录,R,的活动记录,R,的数组区,TOP,SP,15,主要特点,：（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）；（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据；必须设法跟踪每个外层过程的最新活动记录的位置。,关键技术,：,嵌套过程主要解决对非局部变量的引用问题,。,跟踪的办法有两种,：一种是在过程活动记录中增设存取链，指向包含该过程的直接外层过程的最新活动记录的起始位置；另一种是每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表,display,。,存取链和控制链分别是存取非局部变量和指定直接外部过程。

15、,嵌套层次,：指过程定义的层数。,Display,是一个数组，也可以看作为一个小栈。自顶向下每个单元依次存放着现行层、直接外层、,、最外层等每一层过程的最新活动记录地址。,10.2.2,嵌套过程语言的栈式实现,16,举例,程序中过程定义的嵌套情况,Sort,看成整个程序的最外层。,过程,readarray,、,exchange,、,quicksort,是次外层。,过程,partition,是最内层。,在过程,readarray,、,exchange,和,partition,中引用的,a,均不是它们的局部变量，而是过程,sort,过程的局部变量。,这就遇到了一个非局部变量的存取问题。,必须设法跟

16、踪每个外层过程的最新活动记录的位置。,Sort,readarray,exchange,quicksort,partition,17,举例,过程,sort,调用过程,quicksort,。,动态栈的存贮情形如下图,Quicksort,过程活动记录中斜线描述的存贮单元用以记录过程,quicksort,引用过程,sort,中的变量,a,和,x,。,如何引用呢？通过指针！,在这个单元中设置存取链，指向包含该过程的直接外层过程的最新活动记录的其始地址。,局部变量,k,v,局部变量,a,x,可以引用的过程,sort,的局部变量,过程,quicksort,的活动记录,过程,sort,的活动记录,局部变量,.,.,存取链,控制链,TOP,SP,18,sort,quicksort,quicksort,partition exchange,变量,a,x,控制链,存取链,局部变量,k,v,控制链,存取链,局部变量,k,v,控制链,存取链,局部变量,y,z,控制链,存取链,局部变量,i,j,Exchange,的活动记录,partition,的活动记录,quicksort,的活动记录,quicksort,的活动