北京工商大学编译原理第013章.ppt

第十三章运行时存储空间的组织,第一节变量及存储分配程序投入运行的必要条件：一组可运行的代码一个运行环境分配空间、提供运行信息,1.代码空间:线性存放着目标指令序列在GAM中,当前执行的指令位置由指令指针ip指示。2.数据空间变量、常数、控制和管理信息、描述符等,一.程序的存储空间,(1)静态分配:在运行前就可确定数据空间的大小,在编译时刻就能进行的存储分配(2)动态分配运行时才能进行的存储分配栈分配:变量生存期的嵌套性堆分配:生存期的随机交叉特性,数据空间的分配策略,二.活动记录单元实例=代码段+活动记录活动记录记录了程序单元的一次激活所需的信息和数据。如果是栈分配，一个单元的每次激活，都应建立相应的活动记录。,1.活动记录的内容(1)返回地址(2)动态链和静态链(3)形式单元(4)变量存储区：包括局部变量或其描述符、临时变量,返回地址,动态链,静态链,变量存储区,形式单元,注：省略了CPU现场,2.活动记录的特点除了变量存储区外,其余部分存储长度编译时可以确定,则元素i的地址为D+offset(i)其中,D是活动记录的首地址offset(i)是i在活动记录中的位移,三.变量的存储分配1.静态变量:不管在程序单元的哪一次激活,均绑定于相同的存储位置条件:活动记录和变量的存储位置在编译时可以确定2.半静态变量:编译时确定相对位置,单元被激活后,x绑定于D+offset(x)条件:语言允许递归调用,3.半动态变量:如半动态数组(数组大小在运行时才确定，确定后，不能够改变)intam.n;在活动记录（对应数组定义的位置）安排描述符；数组的存储空间安排在活动记录的最后；,对半动态数组a描述符包含两个部分：一是a在活动记录中存储空间的的首地址另一个部分则记录了动态数组(每一维的)上、下界等其他信息,4.动态变量:,某些数据对象，存储区域的大小在运行时仍有可能发生变化如动态数组(数组大小在运行时才确定，还可以改变)如类型在运行时可以改变的变量（动态类型变量）,4.动态变量:,即使到它所在单元被激活时，其活动记录的长度仍不能确定动态变量的存储空间安排在堆中活动记录中为动态变量设置2个指针一个指向该变量的描述符(堆中)一个指向该变量的存储空间(堆中),1.静态分配只允许静态变量,变量与存储区域的绑定关系在编译时便可建立。不允许递归调用,不允许半动态数组,不允许动态类型的数据对象,即不允许有非静态变量。如:FORTRAN。,四.活动记录存储分配模式,2.栈式分配单元之间的调用关系遵循LIFO模式;活动记录的建立和撤消也满足LIFO;分配方法当激活一个程序单元时,其活动记录就动态地分配于栈顶。,P的活动记录,Q的活动记录,R的活动记录,如：P调用Q，Q调用R,.,.,.,.,3.堆分配出现下列情况时,使用堆式分配:(1)单元活动结束后,局部变量的值还需保留;（C语言有特别的处理方式）(2)调用单元与被调用单元的生存期出现交叉现象。,4.存储空间的组织,代码,全局变量和常量数据,栈,堆,第二节静态分配,FORTRAN语言的特点1.模块结构一个主程序段和若干个(可以是0个)辅程序段组成;辅程序段可以是子程序、函数段或数据块；各段可以独立编译。2.说明语句无严格语序,且具有显式说明和隐式说明。,3.公用(COMMON)和等价(EQUIVALENCE)语句建立了数据空间的同一性（数据共享）。4.不允许过程的递归性;每个数据名所需的存储空间大小都是常量;所有数据名的性质是确定的。,一.FORTRAN程序运行时的结构每个单元的活动记录在运行前可建立其生存期延续到整个程序结束。,(1)变量约束于活动记录的常量位移变量的引用采用二元式(单元名,变量在活动记录中的位移)指令的引用也可采用二元式(单元名，指令在代码段中的位移),1.FORTRAN程序编译过程,(2)连接时将程序所有单元连接起来，将代码段分配到代码区，活动记录分配到数据区。将（编译时）二元式转换为地址。,(3)装入时将连接后的可重定位代码装入主存储器并定位，成为可直接执行的机器代码，并将ip指向第一条指令，程序处于可执行状态。,2.FORTRAN程序在GAM中的存储结构,单元1代码段,单元2代码段,单元n代码段,全局数据,单元1活动记录,单元2活动记录,单元n活动记录,.,.,ip,二.运行环境的转换约定：dunit_name,j：unit_name的活动记录中位移为j的存储单元内容cunit_name,j：unit_name的代码段中位移为j的指令Dm,Cm：连接后的实际存储地址EcallF;FcallG;GcallF;,.,.,.,.,.,(1)保存返回地址Dfree:=ip+5或20(2)保存主调过程的currentDfree+1:=current(3)建立P的currentcurrent:=free(4)调整freefree:=free+L(5)转子ip:=(2)一个单元激活后（进入该单元），遇到半动态数组说明时，调用上述指令（填内情向量，分配数组空间），并调整free:=free+L。,三.动态变量的存储分配在堆上进行存储分配;动态变量的描述符和变量存储区均分配在堆上,非局部环境的引用必须考虑变量的作用域1.静态作用域规则最近嵌套规则(1)嵌套的层次最外层单元为0层，若P是Q的直接外层，则Q的层次=P的层次1,四.非局部环境,unitA;,y:int;,unitB;,endB;,y:int;,unitC;,endD;,endC;,.,unitD;,.,endA;,endE;,z:int;,unitF;,endG;,unitG;x,y:int;.,.,unitE;,z:=x+y;,endF;,.,A,B,C,D,E,F,G,x:int;,变量的作用域是指可访问该变量的程序范围若在单元U1中使用变量x(I)变量x在单元U1中被说明，则x的作用域局部于U1;(II)变量x在U1中没有被说明，则x的作用域是包围U1的说明了x的最小外层单元。,(2)最近嵌套规则,2.动态作用域规则是一种最近活动规则，对非局部变量，引用的应是最近外层中说明的。动态作用域的最近外层指的是动态调用的外层如A-E-F-G-F的调用序列：当前F的调用外层为G。,1.静态作用域规则(1)静态连接和静态链静态连接：指向直接外层的最新活动记录的指针，活动记录位移为2的存储单元中。静态链：各嵌套程序单元的活动记录中，静态连接的序列构成静态链。,五.对非局部环境的引用,A,E,F,G,F,AcallE;EcallF;FcallG;GcallF;,.,.,.,.,.,P297,(2)非局部变量x的地址的求法假设单元p中引用了外层单元t中的变量x且p,t的深度分别为np,nt。设d=npnt,将x约束于（t,offset）问题的关键是找t的最新活动记录Dt而Dtoffset即为x的地址。,npnt=0:x为p中的局部变量Dt=currentnpnt=1:t是p的直接外层DtDcurrent+2npnt=2:t是p的再外层Dt=DDcurrent+2+2npnt=3:t是p的再外层的外层Dt=DDDcurrent+222,令npnt=d,则f(d):=ifd=0thencurrentelseDf(d-1)+2沿p的静态链在栈中向下搜索d步。,即,f(0)=currentf(1)Dcurrent+2f(2)=DDcurrent+2+2,(3)静态连接的确定单元A调用单元B的几种情形:,(3)nA-nB=1,(4)nA-nB1,B0,B0,(1)nA-nB=-1,B0,A,B,callB,B,A,callB,B,callB,A,(2)nA-nB=0,B0,B,A,callB,(1)nA-nB=-1,B的静态连接=f(0)(2)nA-nB=0,B的静态连接=f(1)(3)nA-nB=1,B的静态连接=f(2)(4)nA-nB=d,B的静态连接=f(d+1)静态连接Dfree+1:=f(d+1),(4)调用语句callB的处理Dfree:=ip+6Dfree+1:=currentDfree+2:=f(d+1)current:=freefree:=free+Lip:=B的代码段首址,2.动态作用域规则此时，静态连接是一指针指向动态调用直接外层的活动记录其实与动态连接一致。,1.程序单元间通信方式非局部环境和参数传递2.参数形参，实参3.形参三种类型数据参数，过程参数，类型参数,第五节参数传递,一.数据参数(3种参数传递方式)引址调用值调用名调用,传值得结果传值得结果,programmainvarA,B：integer;procedureP(x,y,z);beginy:=y+1;z:=z+xend;beginA:=2;B:=3;P(A+B,A,A);write(A)end,将实参的地址传递给对应的形参，作为形参的地址形参与实参是别名。PASCAL:变量参数C+:引用参数,1.引用调用（传地址）,(1)传值(单向):实参的值形参