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

1、第九章 运行时存储空间组织第一页，共四十一页。目标程序运行时的活动过程的活动 一个过程的活动指该过程的一次执行。参数传递 1. 参数 形参：过程定义时出现 实参：过程调用时出现 2. 参数传递的途径： 传地址(call by reference) 传值 (call by value) 传名(换名)(call by name)第二页，共四十一页。参数传递途径传地址把实参的地址传递给相应的形参。过程段中每个形参都有相应单元，称为形式单元，用来存放相应实参的地址。若实参是变量则直接传递地址，若实参是常数或表达式，则先计算其值并存放于某一临时单元，再传递临时单元的地址。传结果(call by refe

2、rence)与传地址相似，其实质：每个形参对应两个单元，第一个单元存放实参地址，第二个存放实参的值。过程体中对形参的动作均看成对第二个单元的直接访问，在过程完成返回前必须把第二个单元的内容存放到第一个单元所指的实参单元中。第三页，共四十一页。Procedure s); var j:real; begin j:=n; n:=m; m:=j; end传地址过程调用s(i)的过程：(1)将i，k(i)地址传递到已知单元J1和J2中(2) n:=J1; m:=J2;(3) j:=n;(4) n:=m;(5) m:=j;第四页，共四十一页。参数传递途径传值Procedure s); var j:real

3、; begin j:=n; n:=m; m:=j; end传值过程a:=1;b:=2;调用s)执行过程：n:=am:=bj:=nn:=mm:=j局部变量m,n,j的值改变，但不影响a，b的值第五页，共四十一页。参数传递途径传名把被调用段的过程体抄到调用出现的位置，并将形参替换成相应实参（文字替换）。Procedure s); var j:real; begin j:=n; n:=m; m:=j; end传名过程调用s(i)的过程： j:=i; i:=k(i); k(i):=j;第六页，共四十一页。对于下面程序： Procedure p (x,y,z) ; begin y:=y+1; z:=z+

4、x; end; p begin a:=2; b:=3; p (a+b , a , a) print a 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):32b：a：(a)33b：a：(b)39b：a：(c)程序输出结果a为9第八页，共四十一页。参数传递方式为“传地址”32&b：&a：调

5、用者数据区5临时单元T：(a+b的值)&aTy：x：被调用者数据区&a z：执行语句y:=y+1后33&b：&a：调用者数据区5临时单元T：(a+b的值)&aTy：x：被调用者数据区&a z：第九页，共四十一页。参数传递方式为“传地址”执行语句z:=z+x后38&b：&a：调用者数据区5临时单元T：(a+b的值)&aTy：x：被调用者数据区&a z：程序输出结果a为8第十页，共四十一页。参数传递方式为“传结果”32&b：&a：调用者数据区5临时单元T：(a+b的值)执行语句y:=y+1后32&b：&a：调用者数据区5临时单元T：(a+b的值)5T x_val ：x_add：被调用者数据区&a&

6、a32y_val ：y_add ：z_val ：z_add ：5T x_val ：x_add：被调用者数据区&a&a22y_val ：y_add ：z_val ：z_add ：第十一页，共四十一页。参数传递方式为“传结果”执行语句z:=z+x后32&b：&a：调用者数据区5临时单元T：(a+b的值)程序输出结果a为75T x_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

7、+b的值)25y：x：被调用者数据区2 z：执行语句y:=y+1后32&b：&a：调用者数据区5临时单元T：(a+b的值)35y：x：被调用者数据区2 z：第十三页，共四十一页。参数传递方式为“传值”执行语句z:=z+x后32&b：&a：调用者数据区5临时单元T：(a+b的值)37y：x：被调用者数据区2 z：程序输出结果a为2第十四页，共四十一页。运行时存储器的划分程序区栈区静态区目标区堆区可变数组，函数活动记录 目标代码区 静态数据区 Stack heap第十五页，共四十一页。静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。动态：如果名字的性质只有在程

8、序运行时才能知道，则称这种性质为“动态”确定的。可变 (动态)数组： 若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变(动态)数组。第十六页，共四十一页。数据区管理方法静态存储方法动态存储方法 栈式：函数递归定义、调用 堆式：动态申请、释放、new、delete活动记录连接数据 返回地址 静态链：指向调用该过程前的最新活动记录地址的指针 动态链：指向静态直接外层最新活动记录地址的指针形式单元局部数据区：局部变量、内情向量、临时工作单元第十七页，共四十一页。静态存储分配静态分配：若在编译时就能确定程序在运行时所需存储空间的大小，则在编译时就能够安排好目标程序运行时的

9、全部数据空间，并能确定每个数据项的单元地址。 Fortran语言就采用了静态存储分配的策略。数据区 第十八页，共四十一页。简单的栈式存储分配main( ) Q( ); P( ) Q( ) P( ); 1010SPTOP老SP 1010TOP+1=SP2010返回地址TOPSP2010TOPP的活动记录Q的活动记录主函数的活动记录第十九页，共四十一页。C语言活动记录的内容连接数据参数个数形式单元函数的局部变量、数组内情向量、临时单元老SP返回地址参数个数形式单元简单变量内情向量临时单元sp第二十页，共四十一页。嵌套过程语言的栈式实现主要特点： （语言）一个过程可以引用包围它的任一外层过程所定义的

10、标识符（如变量，数组或过程等）。 （实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。第二十一页，共四十一页。嵌套过程语言的栈式实现关键技术：解决对非局部量的引用（存取）。设法跟踪每个外层过程的最新活动记录AR的位置。跟踪办法： 1. 用静态链。 2. 用DISPLAY表。第二十二页，共四十一页。每个过程的AR有3个联系单元：SL： 静态链，指向定义该过程的直接外过程 （或主程序）运行时最新数据段的基地址。DL： 动态链，指向调用该过程前正在运行过程的数据段基地址。RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。第二十三页，共四十一页。pro

11、gram 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=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112第二十四页，共四十一页。program P; var a,x:integer; pr

12、ocedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112ic0(形参个数)0返回地址x0a0返回地址0过程P中调用S时的活动记录012345678910SPTOP动态链静态链第二十五页，共四十一

13、页。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=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112ic0返回地址x0a0过程S中调用Q时的活动记录012345678910S

14、PTOP动态链静态链返回地址00 (形参个数)511返回地址120131(形参个数)14b(形参)15i16第二十六页，共四十一页。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=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c)

15、; endbegin a:=0; S; end0112过程Q中调用R时的活动记录ic0返回地址x0a0012345678910SPTOP动态链静态链返回地址00 (形参个数)511返回地址120131(形参个数)14b(形参)15i161117返回地址1811192 (形参个数)20u (形参)21v (形参)22c23d24第二十七页，共四十一页。Display表和活动记录Display表-嵌套层次显示表 当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层直至最外层的每一过程的最新活动记录的基地址。第二十八页，共四十一页。第二十九页，共四十一页。用Dis

16、play表的方案(1)主程序-(2)P-(3)Q-(4)R主程序的活动记录 d0spdisplaytop（1） P 的活动记录主程序的活动记录 d1d0displaysptop（2）第三十页，共四十一页。用Display表的方案(1)主程序-(2)P-(3)Q-(4)RQ 的活动记录 P 的活动记录主程序的活动记录 displayd2d1d0sptop（3）R 的活动记录 Q 的活动记录 P 的活动记录主程序的活动记录 d1d0 displaytopsp（4）第三十一页，共四十一页。 当过程的层次为n，它的 display为n+1个值。 一个过程被调用时，从调用过程的DISPLAY表中自下向上

17、抄录n个SP值，再加上本层的SP值。全局DISPLAY地址DISPLAY表的维护和建立0老SP1返回地址2全局DISPLAY地址3参数个数4形式单元dDISPLAY.简单变量数组内情向量临时变量第三十二页，共四十一页。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=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q pro

18、cedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112第三十三页，共四十一页。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=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer;

19、begin a:=1; Q(c); endbegin a:=0; S; end0112500(形参个数)2(全局display)返回地址x0a0(display)返回地址0过程P中调用S时的display表012345678910SPTOPc11i12display第三十四页，共四十一页。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=1 then R(u+1,v) v:=(a+c)*

20、(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112502返回地址x0a0过程S中调用Q时的display012345678910SPTOP返回地址00 (形参个数)c11i12513返回地址149(display)151(形参个数)16b(形参)170181319displaydisplay第三十五页，共四十一页。program P; var a,x:integer; procedure Q(b:integer); var i:int

21、eger; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112过程Q中调用R时的display502返回地址x0a0012345678910SPTOP返回地址00c11i12513返回地址14915116b1701813191320返回地址2118(全局display)222(形参个数)23U(形参)24v(形参)2502613272028c