第9章运行时存储空间组织

编译原理第九章运行时存储空间组织制作人：李明新共22页第1页19-12-21第九章运行时存储空间组织知识结构：存储器组织和分配概述基本概念语言中的参数形式参数传递方法运行时存储器的划分运行时存储器的划分活动记录运行时存储存储分配策略空间组织对语言的要求静态存储分配实现方法实现方法动态存储分配过程的活动记录DISPLAY表的作用和生成第一节目标程序运行时的活动编译程序最终目的是将源程序翻译成等价的目标代码。了解目标代码在运行时，用户在源程序中定义各种信息（如变量）的存放和访问.存储组织和管理是一个复杂而又十分重要的问题，主要讨论：⑴活动记录的建立和管理；⑵存储组织和分配的策略；⑶全局信息的访问。一、过程的活动编译原理第九章运行时存储空间组织制作人：李明新共22页第2页19-12-21在程序执行过程中，程序中数据的存取是通过与之对应的存储单元进行的。数据地址、代码地址在编译时均安排为相对地址(以0为基地址)。1、参数过程或函数，被调用时引用的变量或表达式。2、形式参数被调用的过程或函数中引用的变量。3、实在参数过程或函数调用时定义的变量或表达式（调用时替换过程或函数引用的形式参数）。4、活动生存期过程的一次调用称为一个活动(或一个活动的生存期)。5、递归过程的递归调用，当一个过程在没有退出当前的活动时，又开始其新的活动称递归调用：直接递归调用:procedurepbeginP()end间接递归调用:procedurepbeginQ()endprocedureQbeginp()end编译原理第九章运行时存储空间组织制作人：李明新共22页第3页19-12-216、作用域如果变量在一过程中定义并只在该过程中被引用，称之为局部变量，否则为全局变量。二、参数的四种传递方法例PROCEDUREP（X，Y，Z）PROCEDUREq（）beginbegin{调用段}Y:=y+1A:=2;Z:=Z+XB:=3;end{p}P(A+B,A,A)PRINTAend1、传地址每个形参存放相应的实参的地址，对形参的任何访问都按间接地址访问（访问的对象是实参的地址）。调用段实参单元被调用段形参单元T5XYTA238AB3ZA因为Z，Y均为A的地址，所以PRINTA的值为8。2、得结果每个形参对应两个单元：一个存放实参的地址，一个存放实参的值，在过程体中对形参的任何引用或赋值，都看成对它的第二单元直接访问（结果间接存入第一单元（地址））。XT5Y:=Y+12+1编译原理第九章运行时存储空间组织制作人：李明新共22页第4页19-12-21YA23Z:=Z+X2+5ZA27因为Z，Y的第一单元均存放A的地址，而第二单元均存放A的值，所以PRINTA的值为7。3、传值每个形参对应一个单元，存放相应的实参的值,在过程体中对形参可以直接访问（计算只是在过程体进行，不改变实参的值）。X5Y=Y+1=3Y23Z=Z+X=7Z27因为无法将Z的值传给A对应的单元,所以PRINTA的值为2。4、传名把被调用段中所有形参都换成相应的实参，直接访问实参。实参形参A：=A+1；-Y:=y+1;A：=A+A+B-Z:=Z+XT5A239B3因用实参的值，直接执行过程体，所以PRINTA的结果为9。三、存储空间组织必须考虑的问题1、过程是否允许递归？2、当控制从一个过程的活动返回时，对局部名称值的如何编译原理第九章运行时存储空间组织制作人：李明新共22页第5页19-12-21处理？3、过程是否允许引用非局部名称？4、过程调用时如何传递参数；过程是否可以作为参数被传递和作为结果被返回？5、存储空间可否在程序控制下进行动态分配？6、存储空间是否必须显示地释放？第二节运行时存储器的安排一、运行时存储器的安排目标代码过程调用时使用。用于动态数据申请静态数据栈↓↑堆二、活动记录过程在一次执行中所需要的存储空间（数据空间）。TOP临时单元动态数组内情向量局部变量形式单元编译原理第九章运行时存储空间组织制作人：李明新共22页第6页19-12-21静态链连接数据动态链返回地址SP老SP（动态链）说明:1、SP为现行过程活动记录的基地址，作为变址器的基地址。2、连接数据⑴返回地址用于保存调用段中调用语句下一条代码地址⑵动态链指向调用该过程前的调用段最新活动记录地址的指针，用于返回调用段的活动记录（数据空间）⑶静态链指向直接外层最新活动记录地址指针，访问非局部数据。3、内情向量用于保存动态数组的基本信息。4、形式单元存放相应实参的地址或数值。三、存储分配策略1、静态分配在编译时对所有数据对象分配固定大小的存储单元，且在运编译原理第九章运行时存储空间组织制作人：李明新共22页第7页19-12-21行时始终不变。对程序语言的要求:⑴不允许过程递归调用；⑵不含可变体积的数组。2、动态分配在编译时不能确定其数据在存贮空间的位置及所要求数据空间的大小。即无法确定所需数据空间大小和位置。⑴动态数组数组所需数据空间大小在运行时才能确定⑵动态分配的实现在编译时生成一些代码，在运行时动态申请和释放空间。3、堆式动态分配用户程序中申请和回收空间第三节静态存储分配在编译时可确定数据单元的地址（相对地址）一、局部数据区的安排(布局)临时变量数组简单变量确定大小的数组形式单元寄存器保护区返回地址编译原理第九章运行时存储空间组织制作人：李明新共22页第8页19-12-21图9.4局部数据区二、编译程序的地址分配编译程序的地址分配工作，是对符号表中变量名字填入地址(数据区序号,相对地址),在生成目标代码时变量用地址表示。三、临时变量的地址分配如果两个临时变量的作用域不相交，则它们共用一个存储单元。大多临时变量只被定值一次，引用一次，利用栈存放临时变量地址,K为栈指针。例：X:=A*B－C*D+E*F四元式序列如下:四元式临时变量名地址⑴（*，A，B，T1）T1a⑵（*，C，D，T2）T2a+1⑶（－，T1，T2，T3）T3a⑷（*，E，F，T4）T4a+1⑸（+，T3，T4，T5）T5a⑹（:=，T5，，X）临时变量地址代真后的四元式序列如下:四元式K(初值为a)⑴（*，A，B，$a）a+1⑵（*，C，D，$(a+1)）a+2⑶（－，$a，$(a+1)，$a）a+1⑷（*，E，F，$(a+1)）a+2⑸（+，$a，$(a+1)，$a）a+1⑹（:=，$a，，X）a+1第四节简单的栈式分配编译原理第九章运行时存储空间组织制作人：李明新共22页第9页19-12-21一、对程序语言的要求1、允许过程递归调用；2、允许使用可变数组；3、不允许嵌套的过程定义。二、过程调用使用数据区的特点1、非递归调用一个过程只对应一个数据区（活动记录），调用一个过程，使用该过程的数据区，该过程结束后才可能被再次调用，因此可以使用同一数据区。2、递归调用一个过程可能对应多个活动记录，调用一过程，需要为过程的该次活动申请数据区（活动记录），若此次活动未结束，该过程又被调用（开始一次新的活动），需为这次活动再申请另一块数据区（活动记录）。3、过程调用的特点先调用的后返回（退出），调用过程时，先申请一个数据空间（活动记录），若该次活动未结束，又被调动，再申请一活动记录…，当一次活动结束时，回收该次的活动记录，因为先调用的后返回，活动记录回收为:先分配的后回收,所以，活动记录的申请和回收用栈的方式。例：全局数据说明Main()编译原理第九章运行时存储空间组织制作人：李明新共22页第10页19-12-21{Main中的数据说明}Q的活动记录voidR()TOP→{R中的数据说明R的活动记录调用Q过程SP→…Q的活动记录}…voidQ()Main的活动记录{Q中的数据说明调用R过程…全局数据}栈式数据空间其中：TOP始终指向栈顶单元,SP指向现行过程活动记录的起始地址（基地址）。三、活动记录的数据安排TOP→临时工作单元内情向量简单变量形式单元参数个数返回地址SP→老SP连接数据（用于过程结束返回调用段）：1、老SP值，调用段最新活动记录的基地址。编译原理第九章运行时存储空间组织制作人：李明新共22页第11页19-12-212、返回地址，调用段代码地址，用于返回调用段。在目标代码表示为X[SP]（变址访问）。四、过程调用、过程返回时的代码1、编译时如何为目标程序进行动态分配对过程调用语句时生成一系列”申请空间”代码,当目标程序运行这些代码时，便在运行栈顶申请空间，同样，在过程调用返回时，运行编译生成的“回收”代码，便可以回收空间。申请活动记录（数据空间）和回收空间主要体现在活动记录基地址SP的变化，目标代码用变址方式X[SP],即（SP(基地址)+数据的相对地址）就可以访问相应的数据空间。⑴进入过程前的代码中间代码：目标代码parT1(i+3)[TOP]:=TiParT2或（i+3）[TOP]:=addr(Ti)ParTn1[TOP]:SPCallp,n3[TOP]:nJSRP⑵进入过程后先执行SP:=TOP+1；1[SP]:=返回地址TOP:=TOP+1⑶Return(E)返回语句的代码把当前活动记录基地址改为调用段最新活动记录基地址，根据返回地址，代码运行转到该地址。TOP:=SP-1编译原理第九章运行时存储空间组织制作人：李明新共22页第12页19-12-21SP:=0[SP]老SPTOPX:=2[TOP]返回地址返回地址被调用段活动记录UJ0[X]SP老SP调用段活动记录第五节嵌套式过程语言的栈式实现一、嵌套式过程语言的特点一个过程的活动期间，如何在本过程活动记录中引用包围它的某一外层过程的数据。此时SP仅指向本过程活动记录基地址。解决方法：1、编译识别每个过程定义时，为其编上层次号2、引用包围它的某一外层过程的数据，要根据数据所在的层次确定该外层过程最新活动记录基地址。3、可以用两种办法记录外过程最新活动记录的基地址（静态链和display表）。例（P2589.15图）层次变量作用域0ProgramP;Vara,x:integer;1ProcedureQ(b:integer)Vari:integer;2ProcedureR(u:integer;Varv:integer);Varc,d:integerBeginIfu=1thenR(u+1,v)……u,v,编译原理第九章运行时存储空间组织制作人：李明新共22页第13页19-12-21V:=(a+c)*(b-d);c,db………iend{R}begin…aR(1,x);xend{Q}procedureS;varc,i:integer;1begina:=1;引用0层的aQ(c);c,iendbegina:=0;S;end二、静态链和活动记录为了在本过程的活动记录中引用包围它的某一外层过程的数据，在本过程的活动记录中添加静态链，静态链是指向其直接外层过程的最新活动记录基地址临时单元内情向量简单变量形参单元形参个数静态链编译原理第九章运行时存储空间组织制作人：李明新共22页第14页19-12-21P调用SP调用S,S调用QP最新活动记录基地址为0P最新活动记录基地址为0S直接外过程是PS直接外过程是P返回地址动态链（老SP）R(0层)Q(1层)S(1层)P(0层)TOPSP16i15b(形参)141（形参个数）130(静态链)12返回地址11510i9c80(形参个数)70(静态链)6返回地址504x3a20(静态链)1返回地址00TOPSP10i9c80(形参个数)70(静态链)6返回地址504x3a20(静态链)1返回地址00编译原理第九章运行时存储空间组织制作人：李明新共22页第15页19-12-21Q直接外过程是PTOP24d23c22v(形参)21u(形参)202（形参个数）1911(静态链)18返回地址SP1711动16i15b(形参)141（形参个数）130(静态链)12返回地址11510i9c80(形参个数)70(静态链)6返回地址50静4x态3a链编译原理第九章运行时存储空间组织制作人：李明新共22页第16页19-12-21态链201返回地址00TOP