编译原理及实现技术课件：第九章 运行时的存储空间

1、第九章 运行时的存储空间运行时存储空间的结构和分配过程活动记录AR运行时变量的访问运行时环境why了解程序运行时内存结构从而在目标代码中实现what(1)运行时内存的组织结构;(2)内存空间分配;(3)抽象地址的具体化;how在目标代码中体现这些机制静态动态基于栈式静态区分配堆区分配栈区分配变量访问环境知识结构目标程序运行时的活动活动：过程的一次执行。如果a和b是两个活动，则它们的生存期或者是不重叠的，或者是嵌套的。活动树：由活动构成的一个树，其中树中的每个节点代表一个活动。树的根节点是程序的主过程（函数）的活动。在树中若b为a的儿子节点，则必有a活动调用了b活动。在树中若a为b的左兄弟节点，

2、则必有a活动先于b活动执行。名字的作用域和绑定作用域：一个声明起作用的程序部分称为该声明的作用域。一个名字在程序中只声明一次，该名字在程序运行时也可能代表不同的数据对象。 环境和状态：环境表示将名字映射到存储单元的函数，状态表示将存储单元映射到它所保存的值的函数 。绑定：如果环境将名字x映射到存储单元s，我们就说x被绑定（binding）到s。运行时的存储空间结构要保存的信息： 目标代码；数据；库函数代码； 过程活动的控制信息等运行时的存储空间结构：库代码空间目标代码空间静态区空间堆区空间栈区空间最大地址最小地址静态存储分配存储对象的存储位置在程序的整个生命周期是固定的。 分配对象： 全程变量

3、 常量 信息表分配方法： 块地址法：(DataArea,Offset) 变址模式：(Register,Offset)实例#define n 5int sum = 0;int square(int i)int j=i*i;return j;void main()int j = square(n);sum = sum +j;square临时变量t1square局部变量jsquare形参变量isquare信息main临时变量t1main局部变量jmain信息静态区sumn目标代码堆区的存储分配可随时分配和释放空间存储对象：动态申请空间的变量的值释放空间方法：显式释放：隐式释放：单指针释放、计数释放法

4、、标记释放法分配空间方法：最佳符合法；首次优先法；循环首次优先法栈式存储分配存在递归调用存储对象：过程中被声明的形参、局部变量 临时变量分配方法：对每个被调用过程分配一段存储空间，sp存放当前过程空间的开始地址；对变量X：（Level，off),则其存放地址为offsp。过程结束时自动释放空间；不能存储：值的生命周期长于过程的变量；动态申请空间的变量；过程活动记录过程活动记录(AR)：过程的一个现场记录记录内容：过程控制信息：先行活动记录的动态链指针、返回地址、层数和长度等机器状态信息：寄存器状态等全局变量信息:非局部变量的信息局部变量值：形参变量、局部变量和临时变量AR的结构：动态链指针返回

5、值寄存器状态变量访问环境形参变量区局部变量区临时变量区控制状态信息机器状态信息/中断现场变量访问信息变量sp过程层数/AR大小返回地址抽象地址分配(，off） LabelDec （，off） (，off） ConstDec （，off）(，off） TypeDec （，off） (，off） VarDec（，off+n）(，off） ProcDec （，off） (，off） FuncDec （，off）(，off） Proc p( （+1，off0）(，off） Func f( （+1，off0） (，off） Proc P( （+1，off0） (，off） Fucn F( （+1，off

6、0）(，off） T* ID （，off+2）(，off） T ID （，off+m）抽象地址分配例子（，10）#define pai 3.14/（，10）Label L100，L200;（，10）typedef arrint a10;（，10）int x;（，12）int a5;（，22）float f（+1，off0）float * x,（+1，off0+2）arr a,（+1，off0+22）arr * c,（+1，off0+24）void *G（）,（+1，off0+26）float *F（）（+1，off0+28）（+1，off0+28+2)/off1=off0+28（，22） 过程

7、层数假定主程序的层数为0，称为第0层过程。如果过程 Q是在层数为i的过程P内定义，并且P是包围Q的最小过程，那么，Q的层数就为i+1。调用链：过程名序列 若M是主程序名，则（M）是一个调用链；若(M,R)是调用链，且在R中有S的调用，则(M, , R, S)也是调用链。记为CallChain(S)= (M, ,R, S)动态链：过程活动记录序列 如果有调用链CallChain(S)=(M,R, S)， 则它对应的动态链为： DynamicChain=AR(M),AR(R),AR(S)声明链：过程名序列（M）是过程声明链；若（M，P）是声明链，且P中有过程Q的声明，则（M，P，Q）也是过程声明链

8、。记作DeclaChain（Q）= （M，P，Q）活跃活动记录过程S在动态链中可有多个AR，但只有最新的AR(S)是可访问的，称其为S活跃活动记录，记为LAR(S)。变量访问环境Q的声明链中的每个过程的活跃活动记录构成的链称为Q的当前变量访问环境，记为：VarVisitEnv(LAR(Q)=LAR(M), LAR(P), LAR(Q)实例（伪C代码）void P()void Q();R();void R()void S();T();void T()S();Q();调用链CC(X)CC(T)=(P,Q,R,S,T)动态链AR(P),AR(Q),AR(R),AR(S),AR(T)声明链DC(X)D

9、C(T)=(P,R,S,T)活跃过程记录LAR(X)变量访问环境VVE(X)VVE(T)=LAR(P),LAR(R),LAR(S),LAR(T)静态链方法目标程序运行时的动作（1）调用一个过/函时，建立新的活动记录；退出一个过/函时，删除它的当前活动记录。这些工作由目标程序来完成，分别分散在过程调用语句、过程入口和过程出口部分的目标代码中。过/函调用语句所完成的工作1）在新建立的活动记录里保存现役活动记录的始地址：0top:=sp;2）在新建立的活动记录里记入先行Display表的始地址：实在过程语句情形：3top:=sp+ Noff。形式过程语句情形：3top:=(第二形参单元)。其中第二形

10、参单元是给形参过程名分配的第二个单元。3）把实参信息传送到新活动记录区的形参单元中；4）转向相应过程的目标程序。5）如果是函数调用，则把函数值读到某寄存器中。目标程序运行时的动作（2）过/函入口完成的工作1）在新建立的活动记录里保存返回地址：1top:=返回地址2）在要建立的新活动记录里生成DISPLAY表：从3top所指的先行DISPLAY表自底向上抄录个单元的内容（是被调用过程的层数），再添上新的sp值。3）使新建的活动记录成为现役活动记录：sp:=top;top:=top+Moff过/函出口完成的工作1）删除本层活动记录，使动态外层的活动记录成为现役活动记录：top:=sp;sp:=0s

11、p2）按1top中的返回地址返回。参数传递（1）值调用1）把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。2）调用过程计算实参，并把右值放入形参的存储单元中。引用调用 1）如果实参是有左值的名字或表达式，则把该左值放入形参的存储单元。如果实参是a + b或2这样没有左值的表达式，则把它的值计算到新的存储单元，然后传递这个单元的地址。2）在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参的。参数传递（2）值-结果调用 1）在控制流到被调用过程之前，由调用过程计算实参，然后将实参的右值和左值同时传给被调用过程。2）在被调用过程中，像值调用那样使用实

12、参的右值。3）在被调用过程中，当控制返回调用过程时，根据传递来的实参的左值，将形参当前的值复写到实参存储单元。换名调用 1）把过程当作宏来对待，也就是在调用点，用被调用过程的体来替换调用者的调用，但是形参用对应的实参文字来代替。这种文字替换方式称为宏展开或内联展开。2）被调用过程的局部名与调用过程的名字保持区别。可以认为在宏展开前，被调用过程的每个局部名字系统地被重新命名成可区别的名字。3）为保持实参的完整性，实参可以由括号包围 变量访问环境的实现方法Display表方法全局表法局部表法静态链方法寄存器方法 局部Display表方法对于每个AR求出其变量访问环境，并把它以地址表的形式(Disp

13、lay表)保存在AR中。因为每个AR都自带Display表，称这种方法为局部化Display表方法。如果层数为N的过程P的变量访问环境为： VarVisitEnv(AR(P)=ARi1,ARi,n+1, arij表示ARij的始地址，则 ari1,ari,n+1是AR(P)的Display表. Display表的求法NewAR.Display= CurrentAR.Display的前N项newsp动态链指针 Display表 newsp动态链指针 Display表 spar0,ar1,arN-1,ar0,ar1,arN-1,newsp例：有过程M,Q,R,S，其中level(M)=0;leve

14、l(Q)=1;level(R)=1;level(S)=2，各AR的Display表分别如下：Z单元ar0ar1newspX单元Y单元AR(M)AR(Q)AR(R)AR(S)ar1ar2ar0spDisplay 表Off-Display局部Display表时变量的访问对一个变量X(L, off)，地址为：当L= CurrentAR.level时：addr(X)=sp+D+off 否则:addr(X)=CurrentAR.DisplayL+ off即sp+L+off静态链方法原Display表部分变成一个单元，称为静态链单元，存放静态链指针。静态链指针的确定： 若NewAR.level= Curr

15、entAR.level+1-k，则 NewAR.StaticChainPointer=Indir(sp,k) 其中Indir(sp,k)表示sp的k次间接内容。nilAR(M)ar0ar0AR1ar1ar1AR2ar2ar2CurrentARar3 ar?NewARar4sp使用静态链时变量的访问变量X(L,off)的地址：若L= CurrentAR.Level,则addr(X)= sp+D+ off 若L= CurrentAR.Level-k,则addr(X)= Indir(sp,k)+D+ off全局Display表和寄存器方法设置一个总的Display表，其长度为最大嵌套层数（系统确定），其中Displayi存放第i层最新AR的指针。Di表示。当层数为j的过程Q被调用时：将旧的Dj的内容保存到NewAR(Q)中：NewAR(Q).RessumeAddr = Dj改写Dj的内容：Dj=NewAR(Q)的地址；当退出Q时：恢复原来Dj的内容：Dj=CurrentAR.ResumeAddr变量X(L,off)的地址：addr(X)= DL+off