哈工大编译原理第7章.ppt

《哈工大编译原理第7章.ppt》由会员分享，可在线阅读，更多相关《哈工大编译原理第7章.ppt（91页珍藏版）》请在三一办公上搜索。

1、1,第七章 运行时刻环境,2,序7.1 源语言中的一些问题7.2 存储组织7.3 运行时刻存储分配策略7.4 非局部名字的访问7.5 符号表,3,序 计算环境 运行时的环境 计算 目标代码,映射,源程序,源程序中的名字（常量，变量）目标机存储空间。它受命于源程序的执行语义。,源程序由一组过程按某种规则组成。,过程的一次执行称作一次活动.,4,在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。,PROCEDURE sub(x,y:real);VAR i,j:integer;a:ARRAY1.5 OF real;e,f:real;BEGIN f:=e+i*j;E

2、ND;,5,f,符号表,名字 形 类型 偏移量,活动记录布局=,老SP,(sp,0),x 形 real 3,返回地址,(sp,1),y 形 real 4,2,(sp,2),(sp,3),(sp,5),i int 5,i,(sp,9),j int 9,j,(sp,13),a array 13,a,(sp,53),e,e real 53,(sp,61),f real 61,(sp,4),x,y,t1,t2,t3,(sp,62),(sp,63),(sp,64),6,中间代码*i j t1*(sp,20)(sp,21)(sp,29)+e t1 t2+(sp,27)(sp,29)(sp,30)itor

3、t2 t3 itor(sp,30)(sp,31):=t3 f:=(sp,31)(sp,28),确定活动记录中局部数据的地址：假设sp标记一个活动记录的开始的位置，dx表示x的地址相对于sp的偏移量。那么，x在过程的目标代码中的地址可写成 dx（sp）,7,7.1 有关源程序中的一些问题 目的：构造运行程序的策略和方法1.1 过程1.2 活动树1.3 控制栈1.4 说明的作用域1.5 名字的绑定1.6 参数传递1.7 构造运行程序和源程序有关的 一些问题,8,1.1 过程,构成源程序的两个过程行文，,源程序由一组过程组成，,不同的程序设计语言，,由过程构成源程序的方法不同。,要么是嵌套的，,要么

4、是平行的。,9,1.2 活动树,程序执行期间的控制流：,1程序执行的控制是顺序的；,2过程的每一次执行都是从过程体的开头开始，并最终把控制返回到紧接着该过程被调用点的后面。,10,一个过程p的一次活动的生存期:,main,P,其中包括执行过程p所调用的过程的执行时间，以及这些过程所调用的过程的执行时间，如此等等。,在该过程体第一步到最后一步之间的语句的执行时间。,p,11,这种活动生存期的嵌套性质可以通过在每一个过程中插入两个打印语句来加以跟踪。,2、如果a和b是两个过程活动，那么它们的生存期要么是并列的,要么是嵌套的。,控制流的特点：1、每当控制流从过程p的活动进入到过程q的活动中后，它将返

5、回到过程p的同一次活动中。,12,program sort（input，output）；var a：array0.10 of integer；procedure readarray；var i：integer；begin end；function partition（y，z：integer）:integer；var i，j，x，v：integer；begin end;procedure quicksort（m，n：integer）；var i：integer；begin end end；begin end.,程序见P254页,13,执行开始 enter readarray leave read

6、array enter quicksort（1，9）enter partition（1，9）leave partition（l，9）enter quicksort（1，3）.leave quicksort（1，3)enter quicksort（5，9）.leave quicksort（5，9）leave quicksort（1，9）执行结束,这是递归调用,14,递归：一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。,活动树：,在一棵活动树中：,2.根结点代表主程序的活动;,3.代表a的结点是b结点的父结点当且仅当控制从活动a进入活动b;,4.结点a在结点b的左边当且仅

7、当a的生存期发生在b的生存期之前,用一颗树来描绘控制进入和离开活动的途径。这样的树称作活动树。,1.每一个结点代表一个过程的活动;,15,s,r,q(1,9),p(1,9),q(1,3),p(1,3),q(1,0),q(2,3),p(2,3),q(2,1),q(3,3),q(5,9),p(5,9),q(5,5),q(7,9),p(7,9),q(7,7),一棵活动树,假设I=4,假设I=1,假设I=1,假设I=2,假设I=6,假设I=8,假设I=8,q(9,9),16,结论:,且每一个活动只有一个结点表示;,当控制进入某一个活动时，,可以直接说，控制在这个结点上。,一个结点代表一个唯一的活动，,

8、17,1.3 控制栈,因此，用一个栈保存过程活动的生存踪迹;,程序执行的控制流对应于从根开始，按先根次序遍历活动树.,当一个活动开始执行时，,把代表这个活动的结点推进栈；,当这个活动结束时，,把代表这个活动的结点从栈中弹出。,18,例2 栈和活动树的变化,栈,s,s,r,S r,q(1,9),S q(1.9),p(1,9),S q(1.9)p(1,9),q(1,3),S q(1.9)q(1,3),p(1,3),S q(1.9)q(1,3)p(1,3),q(1,0),S q(1.9)q(1,3)q(1,0),q(2,3),S q(1.9)q(1,3)q(2,3),19,结点序列：s,q（1，9）

9、，q（l，3），q（2，3）,控制栈中的活动都是活跃的，,从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系。,从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的节点,当前控制进入的活动在栈顶；,20,结论：扩充控制栈可用来实现如Pascal语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。,21,一个名字在源程序行文中可能有几处说明，语言的作用域规则规定了：,1.说明把名字与名字的属性信息绑定在一起。,1.4 说明的作用域,2.说明的作用域是一个说明起作用的范围（源程序行文）。如：局部变量、全局变量,Int

10、 a10;,在语句序列中引用的一个名字是在何处说明的名字。,22,3.编译时,处理说明语句时,把名字及其属性信息填写进符号表(add(id.entry,id.vul);,处理引用 名字时，查找这个名字的属性信息（lookup(id),符号表管理程序根据语 言的 作用域规则，使 lookup(id)返回id的作用域中绑定的属性信息。,23,可以说，函数environment把一个名字映射为一个l-value（左-值）,1.5名字与存储的绑定,引进两个函数，environment和state。environment把名字映射到一个存储单元上；,state把存储单元映射到那里所存放的值上。,而函数s

11、tate把一个l-value（左-值）映射为一个r-value（右-值）。,如下图所示。,名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程。,24,名字,存储单元,值,存储分配,程序运行,environment,state,l-value,r-value,图：从名字到值的两个阶段映射,25,静态概念 动态对应过程定义 过程活动名字说明 名字的绑定说明的作用域 活动的生存期,1.6 参数传递,实在参数和形式参数结合的方法：,传值调用（call-by-value）,引用调用（call-by-reference）,复制恢复（copy-restore）,传名调用（call-by-

12、name）,27,1.7 提出的问题,编译程序组织存储分配所采用策略和方法主要取决于对源程序中下面的问题的回答。,1过程可以是递归的吗？,2当控制从过程的一次活动返回时，局部名的值将发生什么 变化?,3一个过程可以访问非局部名吗？,4当调用过程时参数是怎样传递的？,28,上面的问题对运行时的存贮分配有很大的影响，,5过程可以作为参数被传递吗？,6过程可以作为结果被返回吗？,7.可以在程序控制下进行动态存储分配吗？,8.显式的存储重新分配（指撤除分配后的分配）是必须的吗？,我们将在后面章节里，对以上问题进行讨论并介绍与之相应的存贮分配策略,29,7.2 存储组织,2.1 运行时刻内存的划分,运行

13、时刻的存储空间必须划分成块，用来存放:,1.生成的目标代码;,2.数据目标;,3.用于保存过程活动踪迹的一个控制栈。,30,目标代码,静态数据,栈,堆,1.编译后知道目标代码的大小。,存储空间划分的各部分：,2.Pascal,c,Fortran,3.栈:Pascal,c,4.堆:Pascal,c,31,2.2 活动记录,对于pascal语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；,一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。,当这个过程的活动执行完后，把它从栈顶弹出。,把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录

14、。,32,源语言不同，实现方法不同，组成活动记录的域不同。常见语言的活动记录如后图所示。,33,返回值,实在参数,控制链,访问链,保存机器状态,局部变量,临时变量,临时变量：编译产生。,保存机器状态：调用过程的活动在调用点的机器状态，包括计数器，各种寄存器的值。,局部数据：过程中定义的 局部量。,访问链：指向本活动要访问的非局部数据所在的活动记录.,控制链:指向主调过程的活动记录的首地址。,形式单元,内情向量,连接数据,局部数据,sp,top,34,2.3 编译时刻的局部数据的设计 局部数据域是编译时刻在编译过程中分配的。例如：,PROCEDURE sub(x,y:real);VAR i,j:

15、integer;a:ARRAY1.5 OF real;e,f:real;BEGIN f:=e+i*j;END;,名字所需的存贮空间的数量是由它的类型确定的,多字节对象存放于连续的字节中，,以第一个字节的地址作为该对象的地址,35,f,符号表,名字 形 类型 偏移量,活动记录布局=,老SP,(sp,0),x 形 real 3,返回地址,(sp,1),y 形 real 4,2,(sp,2),(sp,3),(sp,5),i int 5,i,(sp,9),j int 9,j,(sp,13),a array 13,a,(sp,53),e,e real 53,(sp,61),f real 61,(sp,4

16、),x,y,t1,t2,t3,(sp,62),(sp,63),(sp,64),36,中间代码*i j t1*(sp,5)(sp,9)(sp,62)+e t1 t2+(sp,53)(sp,62)(sp,63)itor t2 t3 itor(sp,63)(sp,64):=t3 f:=(sp,64)(sp,61),确定活动记录中局部数据的地址：假设sp标记一个活动记录的开始的位置，dx表示x的地址相对于sp的偏移量。那么，x在过程的目标代码中的地址可写成 dx（sp）,37,编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，,运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录

17、（栈箭头加上活动记录长度）。,38,7.3 运行时刻存储分配策略,3.1 静态存储分配:FORTRAN3.2 栈式存储分配:C,PASCAL3.3 堆式存储分配:C,PASCAL,采用哪种分配策略是由源语言的语义决定的。,39,3.1 静态存储分配,局部名字的值在过程活动停止后仍保留下来。,且这种绑定在运行时刻不再发生变化。,在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置，,40,限制：,1.在编译时刻知道数据目标的大小和它们在内存位置上 约束；,2.不能递归调用过程（一个过程的两个活动的生存期不相交,一个过程的所有活动可以使用同一个活动记录）；,3.不能动态地建立数据结构。,41

18、,（1）PROGRAM CNSUME（2）CHARACTER*50 BUF（3）INTEGER NEXT（4 CHARACTER C，PRDUCE（5）DATA NEXT1，BUF/（6）CPRDUCE（）。（7）BUF（NEXT：NEXT）C（8NEXTNEXT1（9）IF（C.NE.)GOTO 6（10）WRITE（*，(A)）BUF（11）END,42,(12）CHARACTER FUNCTION PRDUCE（）（13)CHARACTER*80 BUFFER（14）INTEGER NEXT（15）SAVE BUFFER，NEXT(16)DATA NEXT81（17）IF(）THEN（1

19、8)READ（*，（A)BUFFER（19）NEXT1（20)END IF（21）PRDUCEBUFFER（NEXT：NEXT）（22)NEXTNEXT1（23)END 一个Fortran 77程序,43,CNSUME目标代码,PRDUCE目标代码,Char*50 buf int next char c,Char*80 buffer int next,Cnsume活动记录,prduce活动记录,目标代码,静态数据,44,与静态分配不同的是，,基于控制栈的原理：,3.2 栈式存储分配,活动记录的推人和弹出，,存储空间被组织成栈，,分别对应于活动的开始和结束。,在每次活动中把局部名字和新的存储单元

20、绑定，,在活动结束时，活动记录从栈中弹出，,因而局部名字的存储空间也随之消失。,45,图6.11表明当控制流通过图的活动树时，,活动记录被推入或弹出运行时刻的栈中的情况，,设寄存器top标记栈顶。,46,s,r,q(1,9),p(1,9),q(1,3),p(1,3),q(1,0),q(2,3),p(2,3),q(2,1),q(3,3),q(5,9),p(5,9),q(5,5),q(7,9),p(7,9),q(7,7),图6.3 一棵活动树,q(9,9),47,s,Sa:array,top,r,ri:integer,top,top,q(1,9),q(1,9)i:integer,top,p(1,9

21、),p(1,9)i:integer,top,top,q(1,3),q(1,3)i:integer,top,图 6.11 栈式分配活动记录在栈中的变化,48,3.2.1 简单栈式存贮分配,条件：,C满足上述条件,C程序结构：,全局数据说明Main()Main数据说明Void R()R数据说明Void Q()Q数据说明,不允许嵌套定义,允许递归调用,49,假设调用顺序为：,对于全局数据，,main的活动记录,全局数据区,Q的活动记录,R的活动记录,top,sp,是可以静态确定的，,因此在编译时就可确定这些非局部数据的存贮分配,main-Q-R,则程序运行时存贮组织为：,50,C的活动记录,有四个项

22、目：,1、连接数据 老SP-主调过程活动记录首址返回地址,2、参数个数,3、形参单元,4、过程的局部变量、数组内情向量和临时工作单元,51,C的活动记录,老SP,返回地址,参数个数 n,形式单元,简单变量,内情向量,临时工作单元,SP,TOP,变量和形参运行时的绝对地址是：绝对地址=活动记录首地址+相对地址2,0,1,2,(i+2)sp 或(i+3)top,54,52,目标代码（调用序列）完成任务：,C的过程调用、,1.调用者对实在参数求值，,过程语句 p(e1,e2,en),过程进入、,数组空间分配,和过程返回时刻的存贮管理,并把它们传送给 被调用过程的活动记录的参数域。,53,4被调用者初

23、始化其局部数据并开始执行。,3被调用者存放寄存器值和其它状态信息。,2调用者在被调用者的活动记录中存放返回地址和老sp之值，,之后调用者改变 TOP的值,54,过程调用四元式：,Par t1Par tnCall p,n,Par和call产生的目标代码：Par ti,因为形式单元与活动记录首地址之间的距离是确定的，为,(i+3)top=ti(传值）(i+3)top=addr(ti)(传地址）,此工作由主调过程完成,具体实现方法：,51,55,四元式call p,n应翻译成：top=sp（保护现行）top=n(传送参数个数）jsr p(转向的第一条指令）,转入后，建立自己的新的活动记录：SP=to

24、p+1 1sp=返回地址top=top+L/L为的活动记录所需单元数,56,返回序列，return目标代码完成的任务是：,1被调用者将返回值放入临近主调者的活动记录的地方,2利用状态域中的信息，被调用者恢复 sp和其它寄存器，并且按返回地址转 移到调用者的代码之中。,3调用者复制返回值到自己的活动记录中。,57,返回语句：return(E)E为返回值，放在临时单元中,接下来恢复调用现场：top=sp-1 sp=0sp x=2top Uj 0 x,首先：将送入特定寄存器,58,任务的划分，根据源语言、目标机器和操 作系统等具体情况而定。,上述任务，由运行支持子程序完成，可视为虚机指令。,59,P

25、rogram p;Var a,x:integerBegin a=0;S;end,Procedure Q(b:integer);Var i:integer;Begin.R(1,x);.end,Procedure R(u:integer;var v:integer)Var c,d:integer;Begin If u=1 then R(u+1,v);v=(a+c)*(b-d);end,Procedure SVar c,i:integer;Begin a=1;Q(c);end,1,2,2,3,3.2.2 嵌套过程语言的栈式实现,60,嵌套深度：主程序为1,过程S和R都引用了最外层过程说明的a；,一、

26、非局部名字的访问的实现,局部变量和形参可以用上节的方法处理,非局部名字的访问所要解决的问题就是:,过程Q引用了最外层过程说明的x；,而R又引用了其直接说明的变量b,如何找到所有外层过程活动记录的地址,61,常用跟踪外层过程最新活动记录的方法有两种：,访问链,1、访问链和活动记录,访问链为活动记录的一个域,控制链(老SP),返回地址,访问链,形参个数,形参单元,临时单元内情向量简单变量,SP,TOP,和显示表（Display表）,它是从一个过程当前活动记录,指向其直接外层的最新活动记录,的一个指针。,62,从P开始执行,过程P调用S,4 x 3 a 2 0 1 返回地址0 0,Top Sp,过程

27、P的活动记录,i c 0(形参个数）7 0（访问链）6 返回地址5 0（控制链）,过程S的活动记录,Top Sp,63,16 i15 b(形参）14 1(形参个数）13 0（访问链）12 返回地址11 5（控制链）,过程S调用Q时,过程Q的活动记录,Top Sp,控,24d23 c22 v(形参）21 u(形参）20 2(形参个数）19 11（访问链）18 返回地址17 11（控制链）,过程Q调用R,过程R的活动记录,Top Sp,64,过程R递归调用R,32d31 c30 v(形参）29 u(形参）28 2(形参个数）27 11（访问链）26 返回地址25 17（控制链）,过程R的活动记录,

28、Top Sp,65,2、嵌套层次显示表（display)和活动记录,嵌套层次显示表（display)是一个指针数组，,假设当前运行的过程的层数为i，,当前运行过程为R,则D表内容为：,3 R的活动记录首地址2 Q的活动记录首地址1 P的活动记录首地址,数组的元素指向现行层、,直接外层、,、直至最外层(1层）,的最新活动记录的首地址,则嵌套层次显示表（display)含有i个单无,66,由一个非局部变量说明所在的静态层数和相对活动记录的相对地址，,活动记录结构：,临时变量内情向量简单变量Display形参单元形参个数全局display返回地址控制链（老SP）,就可得到绝对地址：,绝对地址=dis

29、play静态层数+相对地址,top d 3 2 1 sp-0,67,假定在现行过程中引用了某一外层k的变量x，,如何建立D表：,则获得x的值的指令如下：,LD R1,(d+k)SPLD R2,XR1,P1调用P2的嵌套可能为如下两种情况：,68,假定P2的嵌套深度为k2，,对应于(a)情况，P1的嵌套深度为k2-1,P1的D表长度为k2-1P2的D表长度为k2,此时的D表内容为：P1的D表+P2自已的SP,69,对应于(b)情况，P1的嵌套深度也为k2,此时的D表内容为：P1的D表的前k2-1项+P2自已的SP,P1、P2的D表长度都为k2,70,只需从P1的D表中自底向上取k2-1个单元，,

30、因此只需把P1的D表地址作为连接数据传给P2即可，,只要知道主调过程P1的D表，,就可以建立P2的D表,再填上P2自己的SP值，,就构成了P2的D表,连接数据变为：,老SP 返回地址全局D表地址,当P1调用 P2时，,综合以上两种情况，,71,4 x 3 a 2 0(D表）1 返回地址 0 0,Top Sp,过程P的活动记录,过程P中调用S时的分析栈及D表内容,12 i11 c10 5(S的 0 D表）0(形参个数）7 2(全局D表)6 返回地址50（控制链）,Top Sp,过程S的活动记录,72,1913（Q的18 0 D表）17 b(形参）16 1(形参个数）15 9(全局D表)14 返回

31、地址13 5（控制链）,过程Q的活动记录,过程S中调用Q时的分析栈及Q表内容,Top Sp,30d c28 20(R的2713260D表）25 v(形参）24 u(形参）23 2(形参个数）22 18(全局D表)21 返回地址20 13（控制链）,过程Q中调用R时的分析栈及R表内容,Top Sp,过程R的活动记录,73,过程R中递归调用R时的分析栈及R表内容,过程R的活动记录,41 d40 c39 31(R的38 13370D表）36 v(形参）35 u(形参）34 2(形参个数）3318(全局D表)32 返回地址31 13（控制链）,Top Sp,74,可变长度的数据,源程序的例子 PROC

32、EDURE exam(l,m,n:integer);VAR a:array 1.l of real;b:array 1.m of real;c:array 1.n of real;BEGIN END;,75,编译时，不知 a,b,c的大小，仅对每个数组设置一个指针。,76,Control link,a,b,c,sp,top,Array a,Array b,Array c,top,P的活动记录,P的动态数组,图6.13 动态分配的数组,77,3.3 堆式存储分配,通常使用一种称之为堆的动态存贮分配方案,适应上述的存贮需求,1局部名的值在活动结束时必须被保存。,2.被调用者的活动生存期超过调用者。

33、,3、new(p);dispose(p);,用活动树不能够正确描绘这种语言的过程之间的控制流。,78,堆是一片足够 大的存贮空间，,每当需要时，就从这片空间中分配一块，,用完时，再归还给堆,79,存贮映象,X W Y Z,WXYz,80,存在的问题：,1、如何分配,2、如何解决碎片问题,3、空闲块不够分配,81,堆式动态存贮分配的实现,一、定长块管理,将堆空间划分成等长的若干块，按照相邻的顺序把所有的块链成一个链表，指针available指向第一块,分配时每次都分配指针available所指的块，指针available移到下一空闲块,占用 占用 占用 空闲 空闲 空闲 空闲,available

34、,82,归还时，把归还的块插入链表中,占用 空闲 占用 空闲 空闲 空闲,available,83,二、变长块管理,开始时，存贮区为一整块。,分配时，就从中分割出满足需要的一块，分配给应用程序,归还时，如果新归还的块能和现有空闲块合并，则合并成一块；否则，把归还的空闲块插入链表中,84,三种分配策略：,1、首次满足法 只要在空闲链表中找到满足需要的一块，就进行分配。大就切，小就分,2、最优满足法 对空闲队列从头至尾扫描，找到最接近申请块的空闲块，进行分配。,为了避免每次都从头扫描到尾，常按递增的顺序组织空闲链表,85,回收时，将释放的空闲块插入到链表的适当位置,3、最差满足法 将空闲链表中满足

35、条件的最大的空闲块，切割后，分配给应用程序；剩余的部分插入链表中,当然回收时，也要将释放的空闲块插入到链表的适当位置,86,内存需示范围 产生碎片分配 回收最优 较大 较小 查表 查表最差 较窄 均匀 不 查表首次 二者之间 查表 不,87,对于第三个问题，有的系统采用垃圾回收的方法，收回那些目前无用或很少用的空间，进行再分配。,隐式存贮分配,需要知道哪些空闲块是不用的？,设置回收子程序的访问信息，存贮块格式如下：,块长度访问计数标记指针用户使用空间,88,回收过程分为两个阶段：,1、标记阶段。对已分配的块进行访问跟踪，如果这个块被访问过，就为其增加一个标记,2、回收阶段。所有未加标记的块回收

36、到一起，插入空闲链表中，消除标记,89,十一、一个Pascal语言程序在执行某一时刻时，其活动记录和isplay表如图所示：,D4D3D2D1,R活动记录活动记录活动记录活动记录主程序活动记录,、试问此时正在执行的调用有哪些？、指出、它们之间的嵌套关系,、主程序,90,十二、考虑下面的的程序Main()char*cp1=“12345”,*cp2=“abcdefghij”;strcpy(cp1,cp2);Printf(“cp1=%sn cp2=%sn”,cp1,cp2);执行结果：Cp1=abcdefghijCp2=ghij问：为什么cp2所指的串被修改了？,91,1 2 3 4 5 0 a b c d e f g h I j 0,程序运行时，运行栈中字符指针cp1,cp2所指的空间格局为：,执行语句strcpy(cp1,cp2)后，cp1,cp2所指的空间格局为：,a b c d e f g h I j 0 f g h I j 0,cp1,cp2,cp1,cp2,