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

第九章运行时存储空间组织,目标程序运行时的活动,过程的活动一个过程的活动指该过程的一次执行。参数传递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;pbegina:=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):,程序输出结果a为9,参数传递方式为“传地址”,执行语句y:=y+1后,参数传递方式为“传地址”,执行语句z:=z+x后,程序输出结果a为8,参数传递方式为“传结果”,执行语句y:=y+1后,参数传递方式为“传结果”,执行语句z:=z+x后,程序输出结果a为7,程序结束，调用返回后：,参数传递方式为“传值”,执行语句y:=y+1后,参数传递方式为“传值”,执行语句z:=z+x后,程序输出结果a为2,运行时存储器的划分,静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。可变(动态)数组：若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变(动态)数组。,数据区管理方法,静态存储方法动态存储方法栈式：函数递归定义、调用堆式：动态申请、释放、new、delete,活动记录,连接数据返回地址静态链：指向调用该过程前的最新活动记录地址的指针动态链：指向静态直接外层最新活动记录地址的指针形式单元局部数据区：局部变量、内情向量、临时工作单元,静态存储分配,静态分配：若在编译时就能确定程序在运行时所需存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。Fortran语言就采用了静态存储分配的策略。数据区,简单的栈式存储分配,main()Q();P()Q()P();,C语言活动记录的内容,连接数据参数个数形式单元函数的局部变量、数组内情向量、临时单元,嵌套过程语言的栈式实现,主要特点：（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。,嵌套过程语言的栈式实现,关键技术：解决对非局部量的引用（存取）。设法跟踪每个外层过程的最新活动记录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);endRbeginR(1,x);endQprocedureS;varc,i:integer;begina:=1;Q(c);endbegina:=0;S;end,0,1,1,2,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);endRbeginR(1,x);endQprocedureS;varc,i:integer;begina:=1;Q(c);endbegina:=0;S;end,0,1,1,2,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);endRbeginR(1,x);endQprocedureS;varc,i:integer;begina:=1;Q(c);endbegina:=0;S;end,0,1,1,2,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);endRbeginR(1,x);endQprocedureS;varc,i:integer;begina:=1;Q(c);endbegina:=0;S;end,0,1,1,2,Display表和活动记录,Display表-嵌套层次显示表当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层直至最外层的每一过程的最新活动记录的基地址。,用Display表的方案,(1)主程序-(2)P-(3)Q-(4)R,用Display表的方案,(1)主程序-(2)P-(3)Q-(4)R,R的活动记录Q的活动记录P的活动记录主程序的活动记录,d1d0,display,top,sp,（4）,当过程的层次为n，它的display为n+1个值。一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。全局DISPLAY地址,DISPLAY表的维护和建立,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);endRbeginR(1,x);endQprocedureS;varc,i:integer;begina:=1;Q(c);endbegina:=0;S;end,0,1,1,2,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);endRbeginR(1,x);endQprocedureS;varc,i:integer;begina:=1;Q(c);endbegina:=0;S;end,0,1,1,2,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);endRbeginR(1,x);endQprocedureS;varc,i:integer;begina:=1;Q(c);endbegina:=0;S;end,0,1,1,2,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);endRbeginR(1,x);endQprocedureS