编译原理 第九章——运行时存储空间组织

第九章运行时存储空间组织目标程序运行时的活动过程的活动一个过程的活动指该过程的一次执行。参数传递1.参数形参：过程定义时出现实参：过程调用时出现2.参数传递的途径：传地址(callbyreference)传值(callbyvalue)传名(换名)(callbyname)参数传递途径——传地址把实参的地址传递给相应的形参。过程段中每个形参都有相应单元，称为形式单元，用来存放相应实参的地址。若实参是变量则直接传递地址，若实参是常数或表达式，则先计算其值并存放于某一临时单元，再传递临时单元的地址。传结果(callbyreference)与传地址相似，其实质：每个形参对应两个单元，第一个单元存放实参地址，第二个存放实参的值。过程体中对形参的动作均看成对第二个单元的直接访问，在过程完成返回前必须把第二个单元的内容存放到第一个单元所指的实参单元中。Procedureswap(n,m:real);varj:real;beginj:=n;n:=m;m:=j;end传地址过程调用swap(i,k(i))的过程：(1)将i，k(i)地址传递到已知单元J1和J2中(2)n:=J1;m:=J2;(3)j:=n↑;(4)n↑:=m↑;(5)m↑:=j;参数传递途径——传值Procedureswap(n,m:real);varj:real;beginj:=n;n:=m;m:=j;end传值过程a:=1;b:=2;调用swap(a,b)执行过程：n:=am:=bj:=nn:=mm:=j局部变量m,n,j的值改变，但不影响a，b的值参数传递途径——传名把被调用段的过程体抄到调用出现的位置，并将形参替换成相应实参（文字替换）。Procedureswap(n,m:real);varj:real;beginj:=n;n:=m;m:=j;end传名过程调用swap(i,k(i))的过程：j:=i;i:=k(i);k(i):=j;对于下面程序：Procedurep(x,y,z);beginy:=y+1;z:=z+x;end;{p}begina:=2;b:=3;p(a+b,a,a)printaend.若参数传递的方法分别为（1）传名（2）传地址（3）传结果（4）传值。执行时所输出的a分别是什么？参数传递方式为“传名”Procedurep(a+b,a,a);begina:=a+1;a:=a+a+b;end;{p}此时调用者数据区为(a):执行a:=a+1后数据区为(b):执行a:=a+a+b后数据区为(c):32b：a：(a)33b：a：(b)39b：a：(c)程序输出结果a为9参数传递方式为“传地址”32&b：&a：调用者数据区5临时单元T：(a+b的值)&aTy：x：被调用者数据区&az：执行语句y:=y+1后33&b：&a：调用者数据区5临时单元T：(a+b的值)&aTy：x：被调用者数据区&az：参数传递方式为“传地址”执行语句z:=z+x后38&b：&a：调用者数据区5临时单元T：(a+b的值)&aTy：x：被调用者数据区&az：程序输出结果a为8参数传递方式为“传结果”32&b：&a：调用者数据区5临时单元T：(a+b的值)执行语句y:=y+1后32&b：&a：调用者数据区5临时单元T：(a+b的值)5Tx_val：x_add：被调用者数据区&a&a32y_val：y_add：z_val：z_add：5Tx_val：x_add：被调用者数据区&a&a22y_val：y_add：z_val：z_add：参数传递方式为“传结果”执行语句z:=z+x后32&b：&a：调用者数据区5临时单元T：(a+b的值)程序输出结果a为75Tx_val：x_add：被调用者数据区&a&a37y_val：y_add：z_val：z_add：程序结束，调用返回后：37&b：&a：调用者数据区5临时单元T：(a+b的值)参数传递方式为“传值”32&b：&a：调用者数据区5临时单元T：(a+b的值)25y：x：被调用者数据区2z：执行语句y:=y+1后32&b：&a：调用者数据区5临时单元T：(a+b的值)35y：x：被调用者数据区2z：参数传递方式为“传值”执行语句z:=z+x后32&b：&a：调用者数据区5临时单元T：(a+b的值)37y：x：被调用者数据区2z：程序输出结果a为2运行时存储器的划分程序区栈区静态区目标区堆区可变数组，函数活动记录目标代码区静态数据区Stackheap静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。可变(动态)数组：若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变(动态)数组。数据区管理方法静态存储方法动态存储方法栈式：函数递归定义、调用堆式：动态申请、释放、new、delete活动记录连接数据返回地址静态链：指向调用该过程前的最新活动记录地址的指针动态链：指向静态直接外层最新活动记录地址的指针形式单元局部数据区：局部变量、内情向量、临时工作单元静态存储分配静态分配：若在编译时就能确定程序在运行时所需存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。Fortran语言就采用了静态存储分配的策略。数据区简单的栈式存储分配main(){…Q();…}P(){…}Q(){…P();…}…1010SPTOP老SP1010TOP+1=SP2010返回地址TOPSP2010TOPP的活动记录Q的活动记录主函数的活动记录C语言活动记录的内容连接数据参数个数形式单元函数的局部变量、数组内情向量、临时单元老SP返回地址参数个数形式单元简单变量内情向量临时单元sp嵌套过程语言的栈式实现主要特点：（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。嵌套过程语言的栈式实现关键技术：解决对非局部量的引用（存取）。设法跟踪每个外层过程的最新活动记录AR的位置。跟踪办法：1.用静态链。2.用DISPLAY表。每个过程的AR有3个联系单元：SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。DL：动态链，指向调用该过程前正在运行过程的数据段基地址。RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。programP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;v:integer);varc,d:integer;beginifu=1thenR(u+1,v)……v:=(a+c)*(b-d);……end{R}begin……R(1,x);……end{Q}procedureS;varc,i:integer;begina:=1;Q(c);……endbegina:=0;S;……end0112programP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;v:integer);varc,d:integer;beginifu=1thenR(u+1,v)……v:=(a+c)*(b-d);……end{R}begin……R(1,x);……end{Q}procedureS;varc,i:integer;begina:=1;Q(c);……endbegina:=0;S;……end0112ic0(形参个数)0返回地址x0a0返回地址0过程P中调用S时的活动记录012345678910SPTOP动态链静态链programP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;v:integer);varc,d:integer;beginifu=1thenR(u+1,v)……v:=(a+c)*(b-d);……end{R}begin……R(1,x);……end{Q}procedureS;varc,i:integer;begina:=1;Q(c);……endbegina:=0;S;……end0112ic0返回地址x0a0过程S中调用Q时的活动记录012345678910SPTOP动态链静态链返回地址00(形参个数)511返回地址120131(形参个数)14b(形参)15i16programP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;v:integer);varc,d:integer;beginifu=1thenR(u+1,v)……v:=(a+c)*(b-d);……end{R}begin……R(1,x);……end{Q}procedureS;varc,i:integer;begina:=1;Q(c);……endbegina:=0;S;……end0112过程Q中调用R时的活动记录ic0返回地址x0a0012345678910SPTOP动态链静态链返回地址00(形参个数)511返回地址120131(形参个数)14b(形参)15i161117返回地址1811192(形参个数)20u(形参)21v(形参)22c23d24Display表和活动记录Display表---嵌套层次显示表当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层…直至最外层的每一过程的最新活动记录的基地址。例：programmain(i,0);程序结构图……procR(c,d);……Rend/*R*/procP(a);主……procQ(b);……PQcallRR(x,y);end/*Q*/callQ……Q(z);callPend/*P*/……callRP（W）；……R（U，V）；……end/*main*/用Display表的方案(1)主程序---(2)P---(3)Q---(4)R主程序的活动记录d[0]spdisplaytop（1）P的活动记录主程序的活动记录d[1]d[0]displaysptop（2）用Display表的方案(1)主程序---(2)P---(3)Q---(4)RQ的活动记录P的活动记录主程序的活动记录displayd[2]d[1]d[0]sptop（3）R的活动记录Q的活动记录P的活动记录主程序的活动记录d[1]d[0]displaytopsp（4）•当过程的层次为n，它的display为n+1个值。•一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。•全局DISPLAY地址DISPLAY表的维护和建立0老SP1返回地址2全局DISPLAY地址3参数个数4形式单元……dDISPLAY...简单变量数组内情向量临时变量programP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;v:integer);varc,d:integer;beginifu=1thenR(u+1,v)……v:=(a+c)*(b-d);……end{R}begin……R(1,x);……end{Q}procedureS;varc,i:integer;begina:=1;Q(c);……endbegina:=0;S;……end0112programP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;v:integer);varc,d:integer;beginifu=1thenR(u+1,v)