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

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第九章 运行时存储空间组织,目标程序运行时,的,的活动,过程的活动,一个过程的活动,指,指该过程的一次,执,执行。,参数传递,1.,参数 形参：,过,过程定义时出现,实参：过程调用,时,时出现,2.,参数传递的途径,：,：传地址,(call by reference),传值,(call by value),传名,(,换名,)(callby name),参数传递途径,传地址,把实参的地址传,递,递给相应的形参,。,。,过程段中每个形,参,参都有相应单元,，,，称为形式单元,，,，用来存放相应,实,实参的地址。,若实参是变量则,直,直接传递地址，,若,若实参是常数或,表,表达式，则先计,算,算其值并存放于,某,某一临时单元，,再,再传递临时单元,的,的地址。,传结果,(call by reference),与传地址相似，,其,其实质：每个形,参,参对应两个单元，第一个单元存,放,放实参地址，第,二,二个存放实参的,值,值。过程体中对,形,形参的动作均看,成,成对第二个单元,的,的直接访问，在,过,过程完成返回前,必,必须把第二个单,元,元的内容存放到,第,第一个单元所指,的,的实参单元中。,Procedure swap(n,m:real);,var j:real;,begin,j:=n;,n:=m;,m:=j;,end,传地址过程,调用,swap(i,k(i),的过程：,(1),将,i,，,k(i),地址传递到已,知,知单元,J,1,和,J,2,中,(2)n:=J,1,;m:=J,2,;,(3)j:=n,;,(4)n:=m;,(5)m:=j;,参数传递途径,传值,Procedure swap(n,m:real);,var j:real;,begin,j:=n;,n:=m;,m:=j;,end,传值过程,a:=1;b:=2;,调用,swap(a,b),执行过程：,n:=a,m:=b,j:=n,n:=m,m:=j,局部变量,m,n,j,的值改变，但,不,不影响,a,，,b,的值,参数传递途径,传名,把被调用段的,过,过程体抄到调,用,用出现的位置,，,，并将形参替,换,换成相应实参,（,（文字替换）,。,。,Procedure swap(n,m:real);,var j:real;,begin,j:=n;,n:=m;,m:=j;,end,传名过程,调用,swap(i,k(i),的过程：,j:=i,;,i:=k(i);,k(i):=j;,对于下面程序,：,：,Procedure p(x,y,z);,begin,y:=y+1;,z:=z+x;,end;p,begin,a:=2;,b:=3;,p(a+b,a,a),printa,end.,若参数传递的,方,方法分别为,（,（,1,）传名（,2,）传地址（,3,）传结果,（,（,4,）传值。执,行,行时所输出的,a,分别是什么？,参数传递方式,为,为“传名”,Procedure p(a+b,a,a);,begin,a:=a+1;,a:=a+a+b;,end;p,此时调用者数,据,据区为,(a):,执行,a:=a+1,后数据区为,(b):,执行,a:=a+a+b,后数据区为,(c):,3,2,b,：,a,：,(a),3,3,b,：,a,：,(b),3,9,b,：,a,：,(c),程序输出结果,a,为,9,参数传递方式,为,为“传地址”,3,2,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),&a,T,y,：,x,：,被调用者数据区,&a,z,：,执行语句,y:=y+1,后,3,3,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),&a,T,y,：,x,：,被调用者数据区,&a,z,：,参数传递方式,为,为“传地址”,执行语句,z:=z+x,后,3,8,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),&a,T,y,：,x,：,被调用者数据区,&a,z,：,程序输出结果,a,为,8,参数传递方式,为,为“传结果”,3,2,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),执行语句,y:=y+1,后,3,2,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),5,T,x_val,：,x_add,：,被调用者数据区,&a,&a,3,2,y_val,：,y_add,：,z_val,：,z_add,：,5,T,x_val,：,x_add,：,被调用者数据区,&a,&a,2,2,y_val,：,y_add,：,z_val,：,z_add,：,参数传递方式,为,为“传结果”,执行语句,z:=z+x,后,3,2,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),程序输出结果,a,为,7,5,T,x_val,：,x_add,：,被调用者数据区,&a,&a,3,7,y_val,：,y_add,：,z_val,：,z_add,：,程序结束，调,用,用返回后：,3,7,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),参数传递方式,为,为“传值”,3,2,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),2,5,y,：,x,：,被调用者数据区,2,z,：,执行语句,y:=y+1,后,3,2,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),3,5,y,：,x,：,被调用者数据区,2,z,：,参数传递方式,为,为“传值”,执行语句,z:=z+x,后,3,2,&b,：,&a,：,调用者数据区,5,临时单元,T,：,(a+b,的值,),3,7,y,：,x,：,被调用者数据区,2,z,：,程序输出结果,a,为,2,运行时存储器,的,的划分,程序区,栈区,静态区,目标区,堆区,可变数组，函数活动记录,目标代码区,静态数据区,Stack,heap,静态：如果一,个,个名字的性质,通,通过说明语句,或,或隐或显规则,而,而定义，则称,这,这种性质是“,静,静态”确定的,。,。,动态：如果名,字,字的性质只有,在,在程序运行时,才,才能知道，则,称,称这种性质为,“,“动态”确定,的,的。,可变,(,动态,),数组：,若一个数组所,需,需的存储空间,的,的大小在编译,时,时就已知道，,则,则称它为确定,数,数组，否则称,为,为可变,(,动态,),数组。,数据区管理方,法,法,静态存储方法,动态存储方法,栈式：函数递,归,归定义、调用,堆式：动态申,请,请、释放、,new,、,delete,活动记录,连接数据,返回地址,静态链：指向,调,调用该过程前,的,的最新活动记,录,录地址的指针,动态链：指向,静,静态直接外层,最,最新活动记录,地,地址的指针,形式单元,局部数据区：,局,局部变量、内,情,情向量、临时,工,工作单元,静态存储分配,静态分配：若,在,在编译时就能,确,确定程序在运,行,行时所需存储,空,空间的大小，,则,则在编译时就,能,能够安排好目,标,标程序运行时,的,的全部数据空,间,间，并能确定,每,每个数据项的,单,单元地址。,Fortran,语言就采用了,静,静态存储分配,的,的策略。,数据区,简单的栈式存,储,储分配,main(),Q();,P(),Q(),P();,1010,SP,TOP,老,SP 1010,TOP+1=SP,2010,返回地址,TOP,SP,2010,TOP,P,的活动记录,Q,的活动记录,主函数的活动记录,C,语言活动记录,的,的内容,连接数据,参数个数,形式单元,函数的局部变,量,量、数组内情,向,向量、临时单,元,元,老,SP,返回地址,参数个数,形式单元,简单变量,内情向量,临时单元,sp,嵌套过程语言,的,的栈式实现,主要特点,：,（语言）一个,过,过程可以引用,包,包围它的任一,外,外层过程所定,义,义的标识符（,如,如变量，数组,或,或过程等）。,（实现）一个,过,过程可以引用,它,它的任一外层,过,过程的最新活,动,动记录中的某,些,些数据。,嵌套过程语言,的,的栈式实现,关键技术：解,决,决对非局部量,的,的引用（存取,）,）。,设法跟踪每个,外,外层过程的最,新,新活动记录,AR,的位置。,跟踪办法：,1.,用静态链。,2.,用,DISPLAY,表。,每个过程的,AR,有,3,个联系单元：,SL,：静态链，指向定义该过程的直接外过程（或主程序）,运,运行时最新数据段的基地,址,址。,DL,：动态链，指向调用该过程前正在,运,运行过程的数,据,据段基地址。,RA,：返回地址，记录调用该,过,过程时目标程序的断点，即调用过程,指,指令的下一条,指,指令的地址。,program P;,var a,x:integer;,procedure Q(b:integer);,var i:integer;,procedure R(u:integer;v:integer);,var c,d:integer;,begin,if u=1thenR(u+1,v),v:=(a+c)*(b-d);,endR,begin,R(1,x);,endQ,procedureS;,varc,i:integer;,begin,a:=1;,Q(c);,end,begin,a:=0;,S;,end,0,1,1,2,programP;,vara,x:integer;,procedureQ(b:integer);,vari:integer;,procedureR(u:integer;v:integer);,varc,d:integer;,begin,ifu=1thenR(u+1,v),v:=(a+c)*(b-d);,endR,begin,R(1,x);,endQ,procedureS;,varc,i:integer;,begin,a:=1;,Q(c);,end,begin,a:=0;,S;,end,0,1,1,2,i,c,0(,形参个数,),0,返回地址,x,0,a,0,返回地址,0,过程,P,中调用,S,时的活动记录,0,1,2,3,4,5,6,7,8,9,10,SP,TOP,动态链,静态链,programP;,vara,x:integer;,procedureQ(b:integer);,vari:integer;,procedureR(u:integer;v:integer);,varc,d:integer;,begin,ifu=1thenR(u+1,v),v:=(a+c)*(b-d);,endR,begin,R(1,x);,endQ,procedureS;,varc,i:integer;,begin,a:=1;,Q(c);,end,begin,a:=0;,S;,end,0,1,1,2,i,c,0,返回地址,x,0,a,0,过程,S,中调用,Q,时的活动记录,0,1,2,3,4,5,6,7,8,9,10,SP,TOP,动态链,静态链,返回地址,0,0(,形参个数,),5,11,返回地址,12,0,13,1(,形参个数,),14,b(,形参,),15,i,16,programP;,vara,x:integer;,procedureQ(b:integer);,vari:integer;,procedureR(u:integer;v:integer);,varc,d:integer;,begin,ifu=1thenR(u+1,v),v:=(a+c)*(b-d);,endR,begin,R(1,x);,endQ,procedureS;,varc,i:integer;,begin,a:=1;,Q(c);,end,begin,a:=0;,S;,end,0,1,1,2,过程,Q,中调用,R,时的活动记录,i,c,0,返回地址,x,0,a,0,0,1,2,3,4,5,6,7,8,9,10,SP,TOP,动