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

1、第九章第九章 运行时的存储空间运行时的存储空间运行时存储空间的结构和分配运行时存储空间的结构和分配过程活动记录过程活动记录ARAR运行时变量的访问运行时变量的访问运行时的存储空间结构运行时的存储空间结构 要保存的信息：要保存的信息： 目标代码；数据；库函数代码；目标代码；数据；库函数代码； 过程活动的控制信息等过程活动的控制信息等 运行时的存储空间结构：运行时的存储空间结构：库代码空间库代码空间目标代码空间目标代码空间静态区空间静态区空间堆区空间堆区空间栈区空间栈区空间最大地址最大地址最小地址最小地址目标程序运行时的活动目标程序运行时的活动 活动：活动：过程的过程的一次执行一次执行。如果。如果

2、a a和和b b是两个是两个活动，则它们的生存期或者是不重叠的，活动，则它们的生存期或者是不重叠的，或者是嵌套的。或者是嵌套的。 活动树：活动树：由活动构成的一个树，其中由活动构成的一个树，其中1.1. 树中的每个节点代表一个活动。树中的每个节点代表一个活动。2.2. 树的根节点是程序的主过程（函数）的活动。树的根节点是程序的主过程（函数）的活动。3.3. 在树中若在树中若b b为为a a的儿子节点，则必有的儿子节点，则必有a a活动调用活动调用了了b b活动。活动。4.4. 在树中若在树中若a a为为b b的左兄弟节点，则必有的左兄弟节点，则必有a a活动先活动先于于b b活动执行。活动执行

3、。名字的作用域和绑定名字的作用域和绑定 作用域：作用域：一个声明起作用的程序部分称为一个声明起作用的程序部分称为该声明的作用域。一个名字在程序中只声该声明的作用域。一个名字在程序中只声明一次，该名字在程序运行时也可能代表明一次，该名字在程序运行时也可能代表不同的数据对象。不同的数据对象。 环境和状态：环境和状态：环境表示将名字映射到存储环境表示将名字映射到存储单元的函数，状态表示将存储单元映射到单元的函数，状态表示将存储单元映射到它所保存的值的函数它所保存的值的函数 。 绑定：绑定：如果环境将名字如果环境将名字x x映射到存储单元映射到存储单元s s，我们就说我们就说x x被绑定（被绑定（bi

4、ndingbinding）到）到s s。过程活动记录过程活动记录 过程活动记录过程活动记录( (AR)AR)：过程的一个现场记录过程的一个现场记录 记录内容记录内容： 过程控制信息：先行活动记录的动态链指针、返回过程控制信息：先行活动记录的动态链指针、返回地址、层数和长度等地址、层数和长度等 机器状态信息：寄存器状态等机器状态信息：寄存器状态等 全局变量信息全局变量信息: :非局部变量的信息非局部变量的信息 局部变量值：形参变量、局部变量和临时变量局部变量值：形参变量、局部变量和临时变量ARAR的结构：的结构：动态链指针动态链指针返回地址返回地址过程层数过程层数机器状态机器状态变量访问环境变量

5、访问环境返回值返回值形参变量区形参变量区局部变量区局部变量区临时变量区临时变量区控制状态信息控制状态信息机器状态信息机器状态信息变量访问信息变量访问信息本层变量和返回值本层变量和返回值spsp抽象地址分配抽象地址分配I.I.（，offoff） LabelDec LabelDec （，offoff） （，offoff） ConstDec ConstDec （，offoff）（，offoff） TypeDec TypeDec （，offoff） （，offoff） VarDecVarDec（，off+noff+n）（，offoff） ProcDec ProcDec （，offoff） （，offo

6、ff） FuncDec FuncDec （，offoff）II.(II.(，offoff） Proc p() Proc p() （+1+1，off1+off1+1+1） ( (，offoff） T Func f() T Func f() （+1+1，off1+off1+1+1） ( (，offoff） Proc P() Proc P() （，off+2off+2） ( (，offoff） T Func F() T Func F() （，off+2off+2） III.(III.(，offoff） T T * * ID ID （，off+1off+1） ( (，offoff） T ID T ID

7、 （，off+noff+n）IV. (IV. (，offoff） Proc p( Proc p( （+1+1，off0off0） ( (，offoff） Func f( Func f( （+1+1，off0off0） ( (，offoff） Proc P( Proc P( （+1+1，off0off0） ( (，offoff） Fucn F( Fucn F( （+1+1，off0off0）抽象地址分配例子抽象地址分配例子（，1010）#define pai 3.14#define pai 3.14/（，1010）Label L100Label L100，L200;L200;（，1010）typ

8、edef arrint a10;typedef arrint a10;（，1010）int x;int x;（，1212）intint a5;a5;（，2222）float ffloat f（+1+1，4 4）float float * * x, x,（+1+1，5 5）arr a,arr a,（+1+1，1515）arr arr * * c, c,（+1+1，1616）void void * *G G（）（）, ,（+1+1，1818）float float * *F F（）（）（+1+1，2020） （+1+1，20+20+2)+2)（，1616） 目标程序运行时的动作（目标程序运行时的动

9、作（1 1）调用一个过调用一个过/ /函时，建立新的活动记录；退出一个过函时，建立新的活动记录；退出一个过/ /函时，函时，删除它的当前活动记录。这些工作由目标程序来完成，分别删除它的当前活动记录。这些工作由目标程序来完成，分别分散在过程调用语句、过程入口和过程出口部分的目标代码分散在过程调用语句、过程入口和过程出口部分的目标代码中。中。 过过/ /函调用语句所完成的工作函调用语句所完成的工作1 1）在新建立的活动记录里保存现役活动记录的始地址：）在新建立的活动记录里保存现役活动记录的始地址：0top:=sp;0top:=sp;2 2）在新建立的活动记录里记入先行）在新建立的活动记录里记入先行

10、DisplayDisplay表的始地址：表的始地址：实在过程语句情形：实在过程语句情形：3top:=sp+ Noff3top:=sp+ Noff。形式过程语句情形：形式过程语句情形：3top:=(3top:=(第二形参单元第二形参单元) )。其中第二形参单元是给形参过程名分配的第二个其中第二形参单元是给形参过程名分配的第二个单元。单元。3 3）把实参信息传送到新活动记录区的形参单元中；）把实参信息传送到新活动记录区的形参单元中；4 4）转向相应过程的目标程序。）转向相应过程的目标程序。5 5）如果是函数调用，则把函数值读到某寄存器中。）如果是函数调用，则把函数值读到某寄存器中。目标程序运行时的

11、动作（目标程序运行时的动作（2 2） 过过/ /函入口完成的工作函入口完成的工作1 1）在新建立的活动记录里保存返回地址：）在新建立的活动记录里保存返回地址：1top:=1top:=返回地址返回地址2 2）在要建立的新活动记录里生成）在要建立的新活动记录里生成DISPLAYDISPLAY表：表：从从3top3top所指的所指的先行先行DISPLAYDISPLAY表自底向上抄录表自底向上抄录个单元的内容（个单元的内容（是被调用过程的层是被调用过程的层数），再添上新的数），再添上新的spsp值。值。3 3）使新建的活动记录成为现役活动记录：）使新建的活动记录成为现役活动记录：sp:=sp:=top

12、;toptop;top:=:=top+Mofftop+Moff 过过/ /函出口完成的工作函出口完成的工作1 1）删除本层活动记录，使动态外层的活动记录成为现役活动）删除本层活动记录，使动态外层的活动记录成为现役活动记录：记录：top:=top:=sp;spsp;sp:=0sp:=0sp2 2）按）按1top1top中的返回地址返回。中的返回地址返回。参数传递（参数传递（1 1） 值调用值调用1 1）把形参当作所在过程的局部名看待，形参的存储单元在该）把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。过程的活动记录中。2 2）调用过程计算实参，并把右值放入形参的存储单元中。）

13、调用过程计算实参，并把右值放入形参的存储单元中。 引用调用引用调用 1 1）如果实参是有左值的名字或表达式，则把该左值放入形参）如果实参是有左值的名字或表达式，则把该左值放入形参的存储单元。如果实参是的存储单元。如果实参是a + ba + b或或2 2这样没有左值的表达式，这样没有左值的表达式，则把它的值计算到新的存储单元，然后传递这个单元的地址。则把它的值计算到新的存储单元，然后传递这个单元的地址。2 2）在被调用过程的目标代码中，任何对形参的引用都是通过）在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参的。传给该过程的指针来间接引用实参的。参数传递（参数传递

14、（2 2） 值值- -结果调用结果调用 1 1）在控制流到被调用过程之前，由调用过程计算实参，然后将）在控制流到被调用过程之前，由调用过程计算实参，然后将实参的右值和左值同时传给被调用过程。实参的右值和左值同时传给被调用过程。2 2）在被调用过程中，像值调用那样使用实参的右值。）在被调用过程中，像值调用那样使用实参的右值。3 3）在被调用过程中，当控制返回调用过程时，根据传递来的实）在被调用过程中，当控制返回调用过程时，根据传递来的实参的左值，将形参当前的值复写到实参存储单元。参的左值，将形参当前的值复写到实参存储单元。 换名调用换名调用 1 1）把过程当作宏来对待，也就是在调用点，用被调用过

15、程的体）把过程当作宏来对待，也就是在调用点，用被调用过程的体来替换调用者的调用，但是形参用对应的实参文字来代替。这来替换调用者的调用，但是形参用对应的实参文字来代替。这种文字替换方式称为宏展开或内联展开。种文字替换方式称为宏展开或内联展开。2 2）被调用过程的局部名与调用过程的名字保持区别。可以认为）被调用过程的局部名与调用过程的名字保持区别。可以认为在宏展开前，被调用过程的每个局部名字系统地被重新命名成在宏展开前，被调用过程的每个局部名字系统地被重新命名成可区别的名字。可区别的名字。3 3）为保持实参的完整性，实参可以由括号包围）为保持实参的完整性，实参可以由括号包围 静态存储分配静态存储分

16、配 存储对象的存储位置在程序的整个生命周存储对象的存储位置在程序的整个生命周期是固定的。期是固定的。 分配对象：分配对象： 全程变量全程变量 常量常量 信息表信息表 分配方法：分配方法： 块地址法：块地址法：( (DataArea,Offset)DataArea,Offset) 变址模式：变址模式：( (Register,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临时变量

17、t1square局部变量jsquare形参变量isquare信息main临时变量t1main局部变量jmain信息静态区sumn目标代码堆区的存储分配堆区的存储分配 可随时分配和释放空间可随时分配和释放空间 存储对象：存储对象： 动态申请空间的变量的值动态申请空间的变量的值 释放空间方法：释放空间方法： 显式释放：显式释放： 隐式释放：单指针释放、计数释放法、标记释隐式释放：单指针释放、计数释放法、标记释放法放法 分配空间方法：分配空间方法： 最佳符合法；首次优先法；循环首次优先法最佳符合法；首次优先法；循环首次优先法栈式存储分配栈式存储分配 存在递归调用存在递归调用 存储对象：存储对象： 过

18、程中被声明的形参、局部变量过程中被声明的形参、局部变量 临时变量临时变量 分配方法：分配方法： 对每个对每个被调用过程被调用过程分配一段存储空间，分配一段存储空间，spsp存放存放当前过程空间的开始地址；对变量当前过程空间的开始地址；对变量X X：（：（LevelLevel，off),off),则其存放地址为则其存放地址为offspoffsp。过程结束时自过程结束时自动释放空间；动释放空间； 不能存储：不能存储： 值的生命周期长于过程的变量；值的生命周期长于过程的变量； 动态申请空间的变量；动态申请空间的变量； 过程层数过程层数假定主程序的层数为假定主程序的层数为0 0，称为第，称为第0 0层

19、过程。如果过程层过程。如果过程 Q Q是在层数为是在层数为i i的过程的过程P P内定义，并且内定义，并且P P是包围是包围Q Q的最小的最小过程，那么，过程，那么，Q Q的层数就为的层数就为i+1i+1。 调用链调用链：过程名序列过程名序列 若若M M是主程序名，则（是主程序名，则（M M）是一个调用链；是一个调用链；若若( (M,M,R),R)是调用链，且在是调用链，且在R R中有中有S S的调用，则的调用，则(M, (M, , R, S), R, S)也是调用链。记为也是调用链。记为CallChainCallChain(S)= (M, (S)= (M, ,R, S),R, S) 动态链：

20、动态链：过程活动记录序列过程活动记录序列 如果有调用链如果有调用链CallChainCallChain(S)=(M,(S)=(M,R, S),R, S)， 则它对应的动态链为：则它对应的动态链为： DynamicChainDynamicChain= = AR(M),AR(M),AR(R),AR(S),AR(R),AR(S) 声明链：声明链：过程名序列过程名序列（M M）是过程声明链；若（）是过程声明链；若（M M，P P）是声明链，）是声明链，且且P P中有过程中有过程Q Q的声明，则（的声明，则（M M，P P，Q Q）也是过）也是过程声明链。记作程声明链。记作DeclaChainDecla

21、Chain（Q Q）= = （M M，P P，Q Q） 活跃活动记录活跃活动记录过程过程S S在在动态链动态链中可有多个中可有多个ARAR，但只有，但只有最新最新的的AR(S)AR(S)是可访问的，称其为是可访问的，称其为S S活跃活动记录，记为活跃活动记录，记为LAR(S)LAR(S)。 变量访问环境变量访问环境Q Q的的声明链声明链中的每个过程的中的每个过程的活跃活动记录活跃活动记录构成的链构成的链称为称为Q Q的当前变量访问环境，记为：的当前变量访问环境，记为：VarVisitEnv(LAR(Q)=LAR(M), LAR(P), VarVisitEnv(LAR(Q)=LAR(M), LA

22、R(P), LAR(Q)LAR(Q)实例（伪实例（伪C C代码）代码）void P()void Q();R();void R()void S();T();void T()S();Q(); 调用链调用链CC(X)CC(X)CC(T)=(P,Q,R,S,T)CC(T)=(P,Q,R,S,T) 动态链动态链AR(P),AR(Q),AR(R),AR(S),AR(T)AR(P),AR(Q),AR(R),AR(S),AR(T) 声明链声明链DC(X)DC(X)DC(T)=(P,R,S,T)DC(T)=(P,R,S,T) 活跃过程记录活跃过程记录LAR(X)LAR(X) 变量访问环境变量访问环境VVE(X)

23、VVE(X)VVE(Q)=LAR(P),LAR(R),LAR(S),LAR(T)VVE(Q)=LAR(P),LAR(R),LAR(S),LAR(T) 静态链方法静态链方法变量访问环境的实现方法变量访问环境的实现方法 DisplayDisplay表方法表方法 全局表法全局表法 局部表法局部表法 静态链方法静态链方法 寄存器方法寄存器方法 局部局部DisplayDisplay表方法表方法 对于每个对于每个ARAR求出其变量访问环境，并把它求出其变量访问环境，并把它以地址表的形式以地址表的形式( (DisplayDisplay表）保存在表）保存在ARAR中。中。因为每个因为每个ARAR都自带都自带D

24、isplayDisplay表，称这种方法表，称这种方法为为局部化局部化DisplayDisplay表方法。表方法。 如果层数为如果层数为N N的过程的过程P P的变量访问环境为：的变量访问环境为： VarVisitEnv(AR(P)=AR VarVisitEnv(AR(P)=ARi1i1, ,AR,ARi,n+1i,n+1, ar arijij表示表示ARARijij的始地址，则的始地址，则 arari1i1, ,ar,ari,n+1i,n+1 是是AR(P)AR(P)的的DisplayDisplay表表. . DisplayDisplay表的求法表的求法NewAR.Display= Curr

25、entAR.DisplayNewAR.Display= CurrentAR.Display的前的前N N项项 newspnewsp动态链指针动态链指针 DisplayDisplay表表 newspnewsp动态链指针动态链指针 DisplayDisplay表表 spsp arar0 0,ar,ar1 1, ,ar,arN-1N-1, , arar0 0,ar,ar1 1, ,ar,arN-1N-1,newsp,newsp例：例：有过程有过程M,Q,R,SM,Q,R,S，其中其中level(M)=0;level(Q)=1;level(R)=1;level(S)=2level(M)=0;level

26、(Q)=1;level(R)=1;level(S)=2，各各ARAR的的DisplayDisplay表分别如下：表分别如下：Z Z单元单元ar0ar0ar1ar1newspnewspX X单元单元Y单元单元AR(M)AR(M)AR(Q)AR(Q)AR(R)AR(R)AR(S)AR(S)ar1ar1ar2ar2ar0ar0spspDisplayDisplay 表表Off-Off-DisplayDisplay局部局部DisplayDisplay表时变量的访问表时变量的访问对一个变量对一个变量X(L, off)X(L, off)，地址为：地址为： 当当L= CurrentAR.levelL= Cur

27、rentAR.level时：时：addr(X)addr(X)=sp+D+off=sp+D+off 否则否则: :addr(X)addr(X)=CurrentAR.DisplayL+ off=CurrentAR.DisplayL+ off即即sp+D+L+offsp+D+L+off静态链方法静态链方法原原DisplayDisplay表部分变成一个单元，称为静态链单表部分变成一个单元，称为静态链单元，存放静态链指针。元，存放静态链指针。静态链指针的确定：静态链指针的确定： 若若NewAR.level= CurrentAR.level+1-kNewAR.level= CurrentAR.level+

28、1-k，则则 NewAR.StaticChainPointer=Indir(sp,k) NewAR.StaticChainPointer=Indir(sp,k) 其中其中Indir(sp,k)Indir(sp,k)表示表示spsp的的k k次间接内容。次间接内容。nilnilAR(M)AR(M)ar0ar0ar0ar0AR1AR1ar1ar1ar1ar1AR2AR2ar2ar2ar2ar2CurrentARCurrentARar3ar3 ar? ar?NewARNewARar4ar4spsp使用静态链时变量的访问使用静态链时变量的访问变量变量X(L,off)X(L,off)的地址：的地址： 若若L= CurrentAR.Level,L= CurrentAR.Level,则则addr(X)addr(X)= sp+D+ off = sp+D+ off 若若L= CurrentAR.Level-k,L= CurrentAR.Level-k,则则addr(X)addr(X)= Indir(sp,k)+D+ off= Indir(sp,k)+D+ off全局全局Dis