搜索
程序设计语言与编译第十二章运行时存储空间的组织电子科技大学计算机科学与工程学院要执行和实现目标程序，需要一个运行环境来支持，要对程序中的变量进行存储分配，并提供各种运行信息。因此，本章主要讨论:运行时存储空间的组织程序设计语言与编译电子科技大学计算机科学与工程学院第一节程序的存储空间程序投入运行的必要条件：1.一组可运行的代码2.一个运行环境分配空间:变量、临时变量、数组、单元提供运行信息：返回地址、主调过程的存储区程序设计语言与编译电子科技大学计算机科学与工程学院ip代码存储器（C）数据存储器（D）假定当前指令指针ip的值为i,则当前指令的存储地址用C[i]表示一、代码空间线性存放着目标指令序列在GAM中,当前执行的指令位置由指令指针ip指示程序设计语言与编译电子科技大学计算机科学与工程学院二、数据空间编译程序给源程序中的各种类型的变量和常数分配的存诸空间，称为程序的数据空间。ip代码存储器（C）数据存储器（D）若某个变量分配在D的i个单元，则用D[i]表示该变量的存诸位置（地址）数据空间在运行时是可以改变的，即动态的程序设计语言与编译电子科技大学计算机科学与工程学院(1)内容:变量、常数、控制和管理信息、描述符等(2)静态分配:在运行前就可确定数据空间的大小在编译时刻就能进行的存储分配(3)动态分配:运行时才能进行的存储分配栈分配:因变量生存期的嵌套性堆分配:因生存期的随机交叉特性程序设计语言与编译电子科技大学计算机科学与工程学院临时变量返回指针动态链接静态链接现场保护参数个数参数单元局部变量被调用单元返回时的地址指向调用单元最新活动记录的指针指向被调用单元直接外层的最新活动记录的指针保存调用时的机器状态调用单元向被调用单元传递的单元个数为形式参数分配的存储单元为局部变量分配的存储单元为临时变量分配的存储单元三、活动记录一个程序单元的一次激活所需的信息管理是通过相应的活动记录来实施的。一个单元的每次激活，都应建立相应的活动记录，它是单元实例的一部分。程序设计语言与编译除了变量存储区外,其余部分存储长度编译时可以确定,则元素i的地址可用下式计算D+offset(i)其中,offset(i)是i在活动记录中的位移;D是活动记录的首地址活动记录的特点电子科技大学计算机科学与工程学院程序设计语言与编译四、变量的存储分配条件是:语言允许递归调用1.静态变量:不管在程序单元的哪一次活动中,均绑定于相同的存储位置条件是:活动记录,变量的存储位置在编译时可以确定2.半静态变量:编译时确定相对位置,单元被激活后,x绑定于D+Offset(x)电子科技大学计算机科学与工程学院程序设计语言与编译3.半动态变量:动态数组编译时在活动记录中建立描述符例:[1..m]inta;[1..n]intb;4.动态变量:动态分配编译时在活动记录中为动态变量设置二个指针,一个指向该变量的描述符,另一个指向该变量的存储空间电子科技大学计算机科学与工程学院程序设计语言与编译五、存储分配模式1.静态分配只允许静态变量,变量与存储区域的绑定关系在编译时便可建立,并完成存储分配。不允许递归调用,不允许动态数组,不允许动态类型的数据对象,即不允许有非静态变量。如:FORTRAN语言。电子科技大学计算机科学与工程学院程序设计语言与编译2.栈式分配各单元之间的调用关系遵循“后进先出”模式活动记录的建立和撤消也满足“后进先出”模式用栈分配活动记录分配方法:当激活一个程序单元时,其活动记录就动态地分配于栈顶。电子科技大学计算机科学与工程学院程序设计语言与编译R的活动记录Q的活动记录P的活动记录如：P调用Q，Q调用R.........电子科技大学计算机科学与工程学院程序设计语言与编译3.堆分配由于动态变量表示的数据对象,它的长度、个数都有可能在执行中改变,即在其生存期中动态改变,就不可能在栈上为这样的对象作分配。出现下列情况时,必须用堆式分配:(1)单元活动结束后,局部变量的值还需保留;(2)调用单元与被调用单元的生存期不满足嵌套关系,即出现交叉现象。电子科技大学计算机科学与工程学院程序设计语言与编译代码静态数据栈堆存储空间的组织电子科技大学计算机科学与工程学院程序设计语言与编译第五节参数传递先看例子:procedureswap(a,b:integer);vartemp:integer;begintemp:=a;a:=b;b:=tempend;……callswap(x,y);…...形式参数实在参数程序设计语言与编译1.程序单元间通信方式有非局部环境和参数传递2.参数，形参，实参3.参数传递的三种类型：数据参数传递过程参数传递类型参数传递几点说明:程序设计语言与编译以调用swap(i,a[i])为例，且调用前i=3a的几个元素分别为7，1，4，5，8程序设计语言与编译1.引用调用（传地址）在单元中对形参的引用，实际上是对形式单元中实参地址的间接引用将实参的地址传递给相应的形参程序设计语言与编译swap(i,a[i]);相当于执行:a:=i的地址;b:=a[3]的地址;temp:=a;(temp=3)a:=b;(i=4)b:=temp;(a[3]=temp=3)执行结果:i=4,a[3]=3程序设计语言与编译2.值调用形参只起局部变量作用(1)传值:实参的值形式单元(2)结果调用:形参的结果值实参单元(3)传值得结果：实参的值形式单元形参的结果值实参单元实现技术：一个形参对应两个单元程序设计语言与编译对“传值得结果”swap(i,a[i]);相当于执行:a1:=i的地址;a2:=3;b1:=a[3]的地址;b2:=4;temp:=a2;(temp=a2=3)a2:=b2;(a2=b2=4)b2:=temp;(b2=temp=3)a1:=a2;(i=a2=4)b1:=b2;(a[3]=b2=3)执行结果:i=4,a[3]=3程序设计语言与编译3.名调用用实参原样替换形参的出现若被调用单元中的局部名与调用处的名发生冲突，则对局部名重新命名实现技术：把实参处理成一个子程序（thunk,称为参数子程序），对形参的每次引用就调用该子程序程序设计语言与编译swap(i,a[i]);相当于执行:temp:=i;(temp=i=3)i:=a[i];(i=a[3]=4)a[i]:=temp;(a[i]=a[4]=temp=3)执行结果:i=4,a[4]=3(a[3]不变)程序设计语言与编译练习programmain;vara,b:integer;procedureP(x,y,z)beginy:=y+1;z:=z+x;endbegina:=2;b:=3;P(a+b,a,a);Write(a,b);End.对引址调用、传值和名调用三种参数传递方式，打印的a,b的值分别是什么程序设计语言与编译电子科技大学计算机科学与工程学院2020年6月23日早期的FORTRAN语言是典型的静态语言，它具有如下特点：①不允许过程的递归调用；②无动态数组和动态类型；③程序无嵌套层次结构；以早期的FORTRAN为例进行静态分配。ip代码存储器数据存储器单元n代码段…单元2代码段单元1代码段全局数据活动记录单元n活动记录…单元2活动记录单元1活动记录第二节静态分配程序设计语言与编译电子科技大学计算机科学与工程学院2020年6月23日INTEGERI,JCOMMONICALLXGOTO1010CONTINUEENDSUBROUTINEXINTEGERK,JCOMMONIK=5I=6J=I+KRETURNEND以下面的FORTRAN程序说明静态分配主程序子程序调用子过程X空语句返回语句程序设计语言与编译电子科技大学计算机科学与工程学院2020年6月23日经过词法及语法分析生成如下描述符(表格)(MAIN,0)…INTJ(COMMON,0)…INTI地址…类型名字主程序MAIN的符号表C(MAIN,3)10地址标号标号表(X,0)X(MAIN,0)MAIN地址名字单元名表(X,2)…INTJ(COMMON,0)…INTI(X,1)…INTK地址…类型名字子程序X的符号表(COMMON,0)…INTI地址…类型名字公用区COMMON的符号表(i,j)表示程序单元i的活动记录中偏移为j的位置；公用区和主程序从0开始分配，子程序从1开始分配MAIN的第三条指令程序设计语言与编译电子科技大学计算机科学与工程学院活动记录程序的目标模块JIJK返回地址MAIN的活动记录X的活动记录COMMON的活动记录0001243210haltnoopip:=&C(MAIN,3)ip:=&C(x,0)D(X,0):=ip+2MAIN的代码段43210haltip:=D(X,0)D(X,2):=D(COMMON,0)+D(X,1)D(COMMON,0):=6D(X,1):=5X的代码段填返回地址CALLXGOTO10CONTINUEK=5I=6J=I+KRETURN程序设计语言与编译电子科技大学计算机科学与工程学院连接后的程序代码和活记录9876543210haltip:=D[2]D[4]:=D[0]+D[3]D[0]:=6D[3]:=5haltnoopip:=3ip:=5D[2]:=ip+243210JK返回地址JI连接后的代码段连接后的活动记录主程序MAIN的代码子程序X的代码COMMON区的活动记录主程序MAIN的活动记录子程序X的活动记录程序设计语言与编译第三节栈式分配语言特点：允许递归允许动态数组允许过程嵌套定义程序设计语言与编译一、只含半静态变量的栈式分配仅允许递归调用变量及活动记录长度可静态确定一个单元可多次激活而有多个实例，每个活动记录是在单元每次激活时动态建立并与代码段建立绑定关系的1.特点程序设计语言与编译2.处理方法（1）current:表示当前活动记录的开始位置（2）free:表示数据存储器下一个可用单元（3）变量绑定于它在活动记录中的常数位移I变量通过current变址访问（4）A调用B时：在A活动记录的栈顶之上建立起绑定于B的当前实例的活动记录（5）从B返回时，释放其活动记录程序设计语言与编译3.动态连接和动态链动态连接：A调用B时，B的活动记录中保存的A的活动记录地址动态链：由动态连接组成的一个调用链程序设计语言与编译FGFEAAcallE;EcallF;FcallG;GcallF;...............程序设计语言与编译4.CALLP的处理返回地址动态连接返回地址动态连接A的活动记录即将建立的P的活动记录currentfreeA…CALLp…程序设计语言与编译(1)保存返回地址D[free]:=？(2)保存主调过程的currentD[free+1]:=current(3)建立P的currentcurrent:=free(4)调整freefree:=free+L(5)转子ip:=P的代码段首地址CALLP程序设计语言与编译返回地址动态链返回地址动态链A的活动记录P的活动记录currentfree进入过程P以后程序设计语言与编译5.RETURN语句的处理(1)恢复freefree:=current(2)恢复主调过程的currentcurrent:=D[current+1](3)返回ip:=D[free]程序设计语言与编译二、半动态变量的栈式分配1.活动记录内容临时变量返回指针动态链接静态链接现场保护参数个数形式单元局部变量数组存储区允许动态数组程序设计语言与编译2.动态数组空间的分配（1)编译时，分配内情向量表区，并产生在运行时动态建立内情向量和分配数组空间的指令。(2)一个单元激活后（进入该单元），遇到动态数组说明时，调用上述指令（填内情向量，分配数组空间），并调整free:=free+L程序设计语言与编译非局部环境的引用必须考虑变量的作用域1.静态作用域规则——最近嵌套规则最外层单元为0层，若P是Q的直接外层，则Q的层次=P的层次＋1(1)嵌套的层次三、允许过程嵌套定义的栈式分配非局部环境引用规则程序设计语言与编译unitA;y:int;unitB;endB;y:int;unitC;e