编译原理课件第十章目标程序运行时的存储组织.ppt

第十章目标程序运行时的存储组织,第一节数据空间的三种不同使用方法和管理方法,第二节栈式存储分配的实现,第三节参数传递,第四节过程调用、过程进入和过程返回,知识结构,8.1概述8.2静态存储分配8.3栈式存储分配8.4堆式存储分配8.5本章小结,第八章运行时的存储组织与管理,8.1概述,从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配所谓运行时的环境是指目标计算机的寄存器和存储器的结构，以及用来管理存储器并保存执行过程所需要的信息。几乎所有的程序设计语言都使用3种类型的存储环境：完全静态环境、基于栈的存储环境和基于堆的存储环境中的一种或几种。,8.1概述,从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织输入/输出所需的缓冲区。,8.1概述,存储管理复杂度取决于源语言本身，具体包括：允许的数据类型的多少语言中允许的数据项是静态确定动态确定程序决定名字的作用域的规则和结构段结构过程定义不嵌套，只允许过程递归调用分程序结构分程序嵌套过程定义嵌套,存储区划分成：目标区、静态数据区、栈区、堆区：目标代码区用以存放目标代码，这是固定长度的，即编译时能确定的全程/静态数据区用以存放编译时能确定所占用空间的数据堆/栈区用于可变数据以及管理过程活动的控制信息,8.1运行时存储空间的划分,过程的活动记录,过程的活动记录是一段连续的存储区，用来存放过程的一次执行所需要的信息。,8.2过程活动记录,编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定在程序设计语言语义学中，使用environment表示将一个名字映射到一个存储位置的函数，state表示存储位置到值的映射，如图10.2所示：,数据空间的使用和管理方法分成三种：静态存储分配栈式动态存储分配堆式动态存储分配,静态存储分配：在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置如像FORTRAN程序是段结构的，如图10.3所示：,8.2静态存储分配,图10.4给出一个FORTRAN77的程序例子：PROGRAMCNSUMECHARACTER*50BUF/程序体所拥有的静态量BUFINTEGERNEXT/程序体所拥有的静态量NEXTCHARACTERC,PRDUCE/程序体所拥有的静态量CDATANEXT/1/,BUF/C=PRDUCE()BUF(NEXT:NEXT)=CNEXT=NEXT+1IF(C.EN.)GOTO6WRITE(*,(A)BUF(11)END,(12)CHARACTERFUNCTIONPRDUCE()CHARACTER*80BUFFERINTEGERNEXTSAVEBUFFER,NEXT/PRDUCE函数体所拥有的静态量BUFFER,NEXT(16)DATANEXT/81/(17)IF(NEXT.GT.80)THEN(18)READ(*,(A)BUFFER(19)NEXT=1(20)ENDIF(21)PRDUCE=BUFFER(NEXT:NEXT)(22)NEXT=NEXT+1(23)END,图10.5中描述了该程序中局部变量的静态存储位置：,动态存储分配,如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术,8.3栈式动态存储分配,这种分配策略是将整个程序的数据空间设计为一个栈,10.2栈式存储分配的实现,过程的活动记录AR(ActivationRecord)：是一段连续的存储区，用以存放过程的一次执行所需要的信息，这些信息如图10.6所示：,临时工作单元：如计算表达式过程存放的中间结果局部变量：一个过程的局部变量机器状态信息：如程序计数器、寄存器的值存取链：用以存取非局部变量控制链：指向调用该过程的那个过程的活动记录实参：由调用过程向该被调过程提供实参的值(或地址)返回地址：保存该被调过程返回后的地址,一.简单的栈式存储分配的实现最简单的程序设计语言结构如图10.7所示：programmain;/主程序头全局变量或数组的说明；procR;/过程R的头/过程R的体end(R);/过程R的尾procQ;/过程Q的头/过程Q的体end(Q);/过程Q的尾主程序执行语句/主程序体end.(main)/主程序尾,例如，图10.7的程序结构中，若主程序调用了过程Q，Q又调用了R,在R进入运行后的存储结构如图10.8(a)所示：若主程序调用了过程Q，Q递归调用自己，在Q过程第2次进入运行后的存储结构如图10.8(b)所示：若主程序先调用过程Q，然后主程序接着调用R，且Q过程没有调用Q和R，这时Q和R进入运行后的存储结构分别如图10.8(c)和10.8(d)所示：,常常使用两个指针指示栈最顶端的数据区：SP：总是指向现行过程活动记录的起点TOP：始终指向已占用的栈顶单元,这种语言若含有可变数组，则其过程活动记录的内容如图10.9所示：,图10.10表明分配数组区之后的运行栈情况，可以与图10.8（a）对照：,二.嵌套过程语言的栈式实现Pascal语言程序结构的特点是允许过程嵌套定义，如图10.11所示：,图10.11的Pascal程序中过程定义的嵌套情况如下：sortreadarrayexchangequicksortpartition,假如过程sort激活（调用）了过程quicksort，这时存储栈中的情形如图10.12所示，其中在quicksort过程活动记录中有一存储单元（用斜线描绘）用以记录过程quicksort可以引用sort中定义的变量a和x。也就是说，为了解决对非局部变量的存取问题，必须设法跟踪每个外层过程的最新活动记录的位置,一种跟踪方法是：在过程活动记录中增设存取链,指向包含该过程的直接外层过程的最新活动记录的起始位置。过程活动记录的内容如图10.13（a）所示。图10.12所提到的情况可用图10.13（b）所示：,因为PL/O的过程是无参过程，PL/O也无动态数组，所以它的过程活动记录的内容如图10.14所示：,再回到图10.11例子，如果该程序的某次执行顺序为：sortquicksortquicksortpartitionexchange图10.15给出了进入过程exchange之后运行栈的示意，仅标明存取链和控制链的值,另一种跟踪方法是：每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display嵌套层次：指过程定义的层数，始终假定主程序的层数为0，因此主程序称为0层过程,计数过程的层数用一个计数器Level，初值为0，每遇到过程说明则增1，过程说明结束则减1display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址,图10.11的程序，假定有如下四种调用情况：（a）sortquicksort（b）sortquicksortquicksort（c）sortquicksortquicksortpartition（d）sortquicksortquicksortpartitionexchange图10.16(a)-(d)分别说明上述四种情形的运行栈和display,display本身的体积在编译时可确定，它作为单独的表分配存储还是作为活动记录的一部分，比如置于实参的上端（如图10.17所示），则取决于编译程序的设计者,当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display?当P1调用P2时必须把P0的display地址作为连接数据之一传给P2,如果P2是一个真实过程，那么P0或者就是P1自身或者既是P1又是P2的直接外层（图10.18的(a)(b)两种情形），不论哪一种情形，只要在进入P2后能够知道P1的display就能知道P0的display，从而可直接构造出P2的display。也就是说，在这种情况下，只需所P1的display地址作为连接数据之一传送给P2就能够建立P2的display,如果P2是形式参数，那么调用P2意味着调用P2当前相应的实在过程此时的P0应是这个实在过程的直接外层过程假定P0的display地址可从形式单元P2所指示的地方获得为了能在P2中获得P0的display地址，必须在P1调用P2时设法把P1的display地址作为连接数据之一传送给P2,于是连接数据变为三项：（1）老SP值；（2）返回地址；（3）全局display地址这样，整个活动记录的组织就如图10.17所示,三.分程序结构的存储管理一个分程序是一个含有它自己的局部数据（变量）声明的语句在C语言中，一个分程序的语法形式是：声明语句例如图10.19的C程序中的分程序B0，B1，B2和B3，分程序的特征是它们的嵌套结构，使用界符标明分程序的开始和结束，C语言用,分程序结构可以用栈式存储分配实现一种办法是把分程序看成一个“无参过程”，只不过是在该分程序入口处调用，分程序出口处返回。分程序在哪里定义就在哪里被调用另一种办法是每次为一个完整的过程体分配存储，即把一个过程体中的所有分程序所需的存储一次分配好，如图10.19的C程序,可以为这里所有声明的名字分配一块存储，如图10.20所示：,ALGOL的结构特点是除了允许过程嵌套定义还含有分程序的结构，如图10.21的一个ALGOL过程：,如采用将分程序看成“无参过程”，则效率很低，因为：第一，分程序不存在被调用的问题，不必要在进入一个分程序时，将连接数据和display都放进活动记录中第二，当从内层分程序向外转移时可能同时要结束若干个分程序，那么怎样恢复所要到达的那个分程序的数据区呢？,克服上述缺点的办法是：首先，代替原来的那个统一的栈顶指示器，让每个过程和分程序都有自己的栈顶指示器TOP，它的值保存在各自的活动记录中其次，不把分程序看作“无参过程”，而让每个分程序享用包围它的那个最小过程的display,每个过程的活动记录所含的内容有：1.过程的TOP单元，指向活动记录的栈顶位置2.连接数据：(1)老SP值(2)返回地址(3)全局display地址(4)调用时的栈顶单元地址，称作老TOP3.参数个数和形式单元4.display表,5.过程所管辖的各分程序的局部数据单元对每个分程序来说,它们包括：(1)一个名为TOP的单元，当进入时它含现行栈顶地址，以后用来存放栈的新高度(2)分程序的局部变量、数组内情向量和临时工作单元,图10.22给出了过程A（见图10.21）的活动记录的结构：,下面用一个例子说明进出分程序时数据区的变化过程：图10.23（a）表示已调用了图10.21的过程A，控制已转入A中，但尚未开始执行过程体时栈的内容图10.23（b）反映了已进入过程体分程序（B1），但尚未分配数组空间时栈的内容。分程序B1的TOP值直接抄自外层分程序的TOP单元图10.23（c）反映了分配数组B后的情形，此时B1的TOP值上升到指示新栈顶，但过程A的TOP值不动图10.23（d）反映了进入分程序B2之后的情形,进入分程序B4时又抄写B1的TOP,并对数组C进行分配，于是得到图10.23（e）当进入分程序B5时，再次抄写直接外层的TOP值，得到图10.23（f）,10.3参数传递,当一个过程调用其他过程时，调用过程和被调过程之间的通信经由非局部量或者经由参数传递,如图10.24的过程exchange1既使用了非局部量数组a，又使用了形式参数i和j，将ai和aj的值进行交换（1）procedureexchange1(i,j:integer);（2）varx:integer;（3）begin;（4）x:=ai;ai:=aj;aj:=x;（5）end;图10.24带有非局部变量和形参的Pascal过程,把实在参数传递给相应的形式参数方法：传值、传地址、传名、宏扩展等观察图10.25的Pascal程序，程序的输出是a=2,b=1，如果将第3行的关键字var去掉，则该程序的输入是a=1,b=2,一.传值call-by-value（值调用）将实参计算出它的值，然后把它传给被调过程：1.形式参数当作过程的局部变量处理2.调用过程计算实参的值，并将它们的右值放在为形式单元开辟的空间中,3.被调用过程执行时，就像使用局部变量一样使用这些形式单元传值的重要特点是对形式参数的任何运算不影响调用过程的活动记录中实参的值通过值调用的过程可以由非局部量或由指针而对调用过程发生影响,比如图10.26的C程序中，x和y声明为整型指针，第8行调用swap(procedurep(x,y,z);beginy=y+1;z=z+x;end;begina=2;b=3;p(a+b,a,a);printaend.,第2题：过程参数的传递方式有几种?简述传地址和传值的实现原理。第3题：下面是一个Pascal程序programPP(input,output)varK:integer;functionF(N:integer):integerbeginifN=0thenF:=1elseF:=N*F(N-1);end;beginK:=F(10);.end