《编译原理(王晓斌)第十三章.ppt》由会员分享，可在线阅读，更多相关《编译原理(王晓斌)第十三章.ppt（58页珍藏版）》请在三一办公上搜索。
1、第十二章 运行时存储空间的组织,电子科技大学计算机科学与工程学院,要执行和实现目标程序，需要一个运行环境来支持，要对程序中的变量进行存储分配，并提供各种运行信息。因此，本章主要讨论:运行时存储空间的组织,电子科技大学计算机科学与工程学院,第一节 程序的存储空间,程序投入运行的必要条件：1.一组可运行的代码2.一个运行环境 分配空间:变量、临时变量、数组、单元 提供运行信息：返回地址、主调过程的存储区,电子科技大学计算机科学与工程学院,假定当前指令指针ip的值为i,则当前指令的存储地址用Ci表示,一、代码空间,线性存放着目标指令序列在GAM中,当前执行的指令位置由指令指针ip指示,电子科技大学计
2、算机科学与工程学院,二、数据空间,编译程序给源程序中的各种类型的变量和常数分配的存诸空间，称为程序的数据空间。,若某个变量分配在D的i个单元，则用Di表示该变量的存诸位置（地址）,数据空间在运行时是可以改变的，即动态的,电子科技大学计算机科学与工程学院,(1)内容:变量、常数、控制和管理信息、描述符等,(2)静态分配:在运行前就可确定数据空间的大小 在编译时刻就能进行的存储分配,(3)动态分配:运行时才能进行的存储分配,栈分配:因变量生存期的嵌套性堆分配:因生存期的随机交叉特性,电子科技大学计算机科学与工程学院,临时变量,返回指针,动态链接,静态链接,现场保护,参数个数,参数单元,局部变量,被
3、调用单元返回时的地址,指向调用单元最新活动记录的指针,指向被调用单元直接外层的最新活动记录的指针,保存调用时的机器状态,调用单元向被调用单元传递的单元个数,为形式参数分配的存储单元,为局部变量分配的存储单元,为临时变量分配的存储单元,三、活动记录,一个程序单元的一次激活所需的信息管理是通过相应的活动记录来实施的。一个单元的每次激活，都应建立相应的活动记录，它是单元实例的一部分。,除了变量存储区外,其余部分存储长度编译时可以确定,则元素i的地址可用下式计算 D+offset(i)其中,offset(i)是i在活动记录中的位移;D是活动记录的首地址,活动记录的特点,电子科技大学计算机科学与工程学院
4、,四、变量的存储分配,条件是:语言允许递归调用,1.静态变量:不管在程序单元的哪一次活动中,均绑定于相同的存储位置,条件是:活动记录,变量的存储位置在编译时可以确定,2.半静态变量:编译时确定相对位置,单元被激活后,x绑定于D+Offset(x),电子科技大学计算机科学与工程学院,3.半动态变量:动态数组 编译时在活动记录中建立描述符,例:1.m int a;1.n int b;,4.动态变量:动态分配编译时在活动记录中为动态变量设置二个指针,一个指向该变量的描述符,另一个指向该变量的存储空间,电子科技大学计算机科学与工程学院,五、存储分配模式,1.静态分配,只允许静态变量,变量与存储区域的绑
5、定关系在编译时便可建立,并完成存储分配。不允许递归调用,不允许动态数组,不允许动态类型的数据对象,即不允许有非静态变量。如:FORTRAN语言。,电子科技大学计算机科学与工程学院,2.栈式分配,各单元之间的调用关系遵循“后进先出”模式,活动记录的建立和撤消也满足“后进先出”模式,用栈分配活动记录,分配方法:当激活一个程序单元时,其活动记录就动态地分配于栈顶。,电子科技大学计算机科学与工程学院,R的活动记录,Q的活动记录,P的活动记录,如：P调用Q，Q调用R,.,.,.,电子科技大学计算机科学与工程学院,3.堆分配,由于动态变量表示的数据对象,它的长度、个数都有可能在执行中改变,即在其生存期中动
6、态改变,就不可能在栈上为这样的对象作分配。,出现下列情况时,必须用堆式分配:(1)单元活动结束后,局部变量的值还需保留;(2)调用单元与被调用单元的生存期不满足嵌套关系,即出现交叉现象。,电子科技大学计算机科学与工程学院,代码,静态数据,栈,堆,存储空间的组织,电子科技大学计算机科学与工程学院,第五节 参数传递,先看例子:procedure swap(a,b:integer);var temp:integer;begin temp:=a;a:=b;b:=temp end;call swap(x,y);.,形式参数,实在参数,1.程序单元间通信方式有非局部环境和参数传递2.参数，形参，实参3.参
7、数传递的三种类型：数据参数传递 过程参数传递 类型参数传递,几点说明:,以调用 swap(i,ai)为例，且调用前 i=3 a 的几个元素分别为7，1，4，5，8,1.引用调用（传地址）,在单元中对形参的引用，实际上是对形式单元中实参地址的间接引用,将实参的地址传递给相应的形参,swap(i,ai);相当于执行:a:=i的地址;b:=a3的地址;temp:=a;(temp=3)a:=b;(i=4)b:=temp;(a3=temp=3)执行结果:i=4,a3=3,2.值调用,形参只起局部变量作用(1)传值:实参的值形式单元(2)结果调用:形参的结果值实参单元(3)传值得结果：实参的值形式单元 形
8、参的结果值实参单元 实现技术：一个形参对应两个单元,对“传值得结果”swap(i,ai);相当于执行:a1:=i的地址;a2:=3;b1:=a3的地址;b2:=4;temp:=a2;(temp=a2=3)a2:=b2;(a2=b2=4)b2:=temp;(b2=temp=3)a1:=a2;(i=a2=4)b1:=b2;(a3=b2=3)执行结果:i=4,a3=3,3.名调用,用实参原样替换形参的出现若被调用单元中的局部名与调用处的名发生冲突，则对局部名重新命名实现技术：把实参处理成一个子程序（thunk,称为参数子程序），对形参的每次引用就调用该子程序,swap(i,ai);相当于执行:tem
9、p:=i;(temp=i=3)i:=ai;(i=a3=4)ai:=temp;(ai=a4=temp=3)执行结果:i=4,a4=3(a3不变),练习,program main;var a,b:integer;procedure P(x,y,z)beginy:=y+1;z:=z+x;end begina:=2;b:=3;P(a+b,a,a);Write(a,b);End.,对引址调用、传值和名调用三种参数传递方式，打印的a,b的值分别是什么,电子科技大学计算机科学与工程学院,2023年5月28日,早期的FORTRAN语言是典型的静态语言，它具有如下特点：不允许过程的递归调用；无动态数组和动态类型
10、；程序无嵌套层次结构；以早期的FORTRAN为例进行静态分配。,第二节 静态分配,电子科技大学计算机科学与工程学院,2023年5月28日,INTEGER I,J COMMON I CALL X GOTO 1010 CONTINUE END,SUBROUTINE X INTEGER K,JCOMMON IK=5I=6J=I+KRETURNEND,以下面的FORTRAN程序说明静态分配,主程序,子程序,调用子过程X,空语句,返回语句,电子科技大学计算机科学与工程学院,2023年5月28日,经过词法及语法分析生成如下描述符(表格),(i,j)表示程序单元i的活动记录中偏移为j的位置；公用区和主程序从
11、0开始分配，子程序从1开始分配,MAIN的第三条指令,电子科技大学计算机科学与工程学院,活动记录,程序的目标模块,填返回地址,CALL X,GOTO 10,CONTINUE,K=5,I=6,J=I+K,RETURN,电子科技大学计算机科学与工程学院,连接后的程序代码和活记录,主程序MAIN的代码,子程序X的代码,COMMON区的活动记录,主程序MAIN的活动记录,子程序X的活动记录,第三节 栈式分配,语言特点：允许递归允许动态数组允许过程嵌套定义,一、只含半静态变量的栈式分配,仅允许递归调用变量及活动记录长度可静态确定一个单元可多次激活而有多个实例，每个活动记录是在单元每次激活时动态建立并与代
12、码段建立绑定关系的,1.特点,2.处理方法,（1）current:表示当前活动记录的开始位置,（2）free:表示数据存储器下一个可用单元,（3）变量绑定于它在活动记录中的常数位移I 变量通过current变址访问,（4）A调用B时：在A活动记录的栈顶之上建立起绑定 于B的当前实例的活动记录,（5）从B返回时，释放其活动记录,3.动态连接和动态链,动态连接：A调用B时，B的活动记录中保存的A的活动记录地址,动态链：由动态连接组成的一个调用链,F,G,F,E,A,A call E;E call F;F call G;G call F;,.,.,.,.,.,4.CALL P 的处理,返回地址,动态
13、连接,返回地址,动态连接,A的活动记录,即将建立的P的活动记录,current,free,ACALL p,(1)保存返回地址,D free:=？,(2)保存主调过程的current,Dfree+1:=current,(3)建立P的current,current:=free,(4)调整free,free:=free+L,(5)转子,ip:=P的代码段首地址,CALL P,返回地址,动态链,返回地址,动态链,A的活动记录,P的活动记录,current,free,进入过程P以后,5.RETURN语句的处理,(1)恢复free free:=current(2)恢复主调过程的current curren
14、t:=Dcurrent+1(3)返回 ip:=D free,二、半动态变量的栈式分配,1.活动记录内容,数组存储区,允许动态数组,2.动态数组空间的分配,（1)编译时，分配内情向量表区，并产生在运行时动态建立内情向量和分配数组空间的指令。,(2)一个单元激活后（进入该单元），遇到动态数组说明时，调用上述指令（填内情向量，分配数组空间），并调整free:=free+L,非局部环境的引用必须考虑变量的作用域1.静态作用域规则最近嵌套规则 最外层单元为0层，若P是Q的直接外层，则Q的层次=P的层次 1,(1)嵌套的层次,三、允许过程嵌套定义的栈式分配,非局部环境引用规则,(2)最近嵌套规则,(I)变
15、量x在单元U1中被说明，则x的作用 域局部于U1，或称x在U1中是可见的,(II)变量x在U1中没有被说明，则x的作用域 是包围U1的说明了x的最小外层单元,2.动态作用域规则,最近活动规则对非局部变量的引用：最近外层中说明的动态作用域的最近外层：指的是动态调用外层,如A-E-F-G-F的调用序列：当前F的调用外层为G,对非局部环境的引用,1.静态作用域规则,对非局部变量，引用的应是最近的“嵌套外层”中说明的变量,静态连接：,指向嵌套直接外层的最新活动记录的指针，它处于活动记录位移为2的存储单元中,静态链：,各嵌套程序单元的活动记录中，静态连接的序列构成一个静态链,（1）静态连接和静态莲,CA
16、LL P,内容回顾,1.静态分配,2.栈式分配,3.堆分配,变量与存储区域的绑定关系在编译时便可建立，并完成存储分配,当一个程序单元被激活时,在栈顶分配其活动记录；当程序单元退出时，在栈顶将其活动记录撤销,动态变量的首地址、长度、类型等在编译时无法确定，在执行过程中也可能改变,内容回顾,1.静态分配,2.栈式分配,3.堆分配,分配方式,递归调用,动态数组,过程嵌套定义,只含半静态变量的栈式分配,CALL P,D free:=IP+5,Dfree+1:=current,current:=free,free:=free+L,ip:=P的代码段首地址,return,内容回顾,允许过程嵌套定义的栈式分
17、配,静态作用域规则,动态作用域规则,D free:=ip+5,Dfree+1:=current,free:=free+L,ip:=P的代码段首地址,CALL P,current:=free,保存静态链接：Dfree+2:=？,(2)非局部变量x的地址的求法,假设单元p中引用了单元t中的变量x，且p,t的深度分别为np,nt，记：,d=np nt,Dt为t的最新活动记录的首地址,np nt=0:x为p中的局部变量 Dt=currentnp nt=1:t是p的直接外层 Dt Dcurrent+2np nt=2:t是p的再外层 Dt=DDcurrent+2+2np nt=3:t是p的再外层的外层 D
18、t=DDDcurrent+2 2 2,f(d)=if d=0 then current else Df(d-1)+2,令np nt=d,f(d)表示沿p的静态链在栈中向下搜索d步,(3)静态连接的确定,单元A调用单元B的几种情形,形式I：,nA-nB=0,B的静态连接f(1),形式II：,nA-nB=-1,B的静态连接f(0),形式III：,nA-nB=1,B的静态连接f(2),形式IV：,nA-nB=2,B的静态连接f(3),令np nt=d,B的静态连接f(d+1),(4)调用语句call B 的处理,D free:=ip+6,Dfree+1:=current,free:=free+L,ip:=P的代码段首地址,current:=free,Dfree+2:=f(d+1),2.动态作用域规则,静态连接是一指针指向动态调用直接外层的活动记录其实与动态连接一致,
