《编译原理课件第十章目标程序运行时的存储组织.ppt》由会员分享，可在线阅读，更多相关《编译原理课件第十章目标程序运行时的存储组织.ppt（82页珍藏版）》请在三一办公上搜索。
1、第十章目标程序运行时的存储组织,第一节 数据空间的三种不同使用方法和管理方法,第二节 栈式存储分配的实现,第三节 参数传递,第四节 过程调用、过程进入和过程返回,知识结构,8.1 概述8.2 静态存储分配8.3 栈式存储分配8.4 堆式存储分配8.5 本章小结,第八章 运行时的存储组织与管理,8.1 概述,从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配所谓运行时的环境是指目标计算机的寄存器和存储器的结构，以及用来管理存储器并保存执行过程所需要的信息。几乎所有的程序设计语言都使用3种类型的存储环境：完全静态环境、基于栈的存储环境和基于堆的存储环境中的一种或几种。,
2、8.1 概述,从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织输入/输出所需的缓冲区。,8.1 概述,存储管理复杂度取决于源语言本身，具体包括：允许的数据类型的多少语言中允许的数据项是 静态确定 动态确定程序决定名字的作用域的规则和结构段结构过程定义不嵌套，只允许过程递归调用分程序结构 分程序嵌套 过程定义嵌套,存储区划分成：目标区、静态数据区、栈区、堆区：目标代码区用以存放目标代码，这是固定长度的，即编译时能确定的全程/
3、静态数据区用以存放编译时能确定所占用空间的数据堆/栈区用于可变数据以及管理过程活动的控制信息,8.1 运行时存储空间的划分,过程的活动记录,过程的活动记录是一段连续的存储区，用来存放过程的一次执行所需要的信息。,8.2 过程活动记录,编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定在程序设计语言语义学中，使用environment表示将一个名字映射到一个存储位置的函数，state表示存储位置到值的映射，如图10.2所示：,数据空间的使用和管理方法分成三种：静态存储分配栈式动态存储分配堆式动态存储分配,静态存储分配：在编译时能确定目标程序运
4、行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置如像FORTRAN程序是段结构的，如图10.3所示：,8.2 静态存储分配,图10.4给出一个FORTRAN77的程序例子：PROGRAM CNSUMECHARACTER*50 BUF/程序体所拥有的静态量BUFINTEGER NEXT/程序体所拥有的静态量NEXTCHARACTER C,PRDUCE/程序体所拥有的静态量CDATA NEXT/1/,BUF/C=PRDUCE()BUF(NEXT:NEXT)=C NEXT=NEXT+1 IF(C.EN.)GOTO 6 WRITE(*,(A)BUF(1
5、1)END,(12)CHARACTER FUNCTION PRDUCE()CHARACTER*80 BUFFER INTEGER NEXT SAVE BUFFER,NEXT/PRDUCE函数体所拥有的静态量BUFFER,NEXT(16)DATA NEXT/81/(17)IF(NEXT.GT.80)THEN(18)READ(*,(A)BUFFER(19)NEXT=1(20)END IF(21)PRDUCE=BUFFER(NEXT:NEXT)(22)NEXT=NEXT+1(23)END,图10.5中描述了该程序中局部变量的静态存储位置：,动态存储分配,如果一个程序设计语言允许递归过程、可变数组或允
6、许用户自由申请和释放空间，那么，就需要采用动态存储管理技术,8.3 栈式动态存储分配,这种分配策略是将整个程序的数据空间设计为一个栈,10.2栈式存储分配的实现,过程的活动记录AR(Activation Record)：是一段连续的存储区，用以存放过程的一次执行所需要的信息，这些信息如图10.6所示：,临时工作单元：如计算表达式过程存放的中间结果局部变量：一个过程的局部变量机器状态信息：如程序计数器、寄存器的值存取链：用以存取非局部变量控制链：指向调用该过程的那个过程的活动记录实参：由调用过程向该被调过程提供实参的值(或地址)返回地址：保存该被调过程返回后的地址,一.简单的栈式存储分配的实现最
7、简单的程序设计语言结构如图10.7所示：program main;/主程序头全局变量或数组的说明；proc R;/过程R的头/过程R的体end(R);/过程R的尾proc Q;/过程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进入运行后的存储结构分别如图1
8、0.8(c)和10.8(d)所示：,常常使用两个指针指示栈最顶端的数据区：SP：总是指向现行过程活动记录的起点TOP：始终指向已占用的栈顶单元,这种语言若含有可变数组，则其过程活动记录的内容如图10.9所示：,图10.10表明分配数组区之后的运行栈情况，可以与图10.8（a）对照：,二.嵌套过程语言的栈式实现Pascal语言程序结构的特点是允许过程嵌套定义，如图10.11所示：,图10.11的Pascal程序中过程定义的嵌套情况如下：sort readarray exchange quicksort partition,假如过程sort激活（调用）了过程quicksort，这时存储栈中的情形如
9、图10.12所示，其中在quicksort过程活动记录中有一存储单元（用斜线描绘）用以记录过程quicksort可以引用sort中定义的变量a和x。也就是说，为了解决对非局部变量的存取问题，必须设法跟踪每个外层过程的最新活动记录的位置,一种跟踪方法是：在过程活动记录中增设存取链,指向包含该过程的直接外层过程的最新活动记录的起始位置。过程活动记录的内容如图10.13（a）所示。图10.12所提到的情况可用图10.13（b）所示：,因为PL/O的过程是无参过程，PL/O也无动态数组，所以它的过程活动记录的内容如图10.14所示：,再回到图10.11例子，如果该程序的某次执行顺序为：sortquic
10、ksortquicksortpartitionexchange图10.15给出了进入过程exchange之后运行栈的示意，仅标明存取链和控制链的值,另一种跟踪方法是：每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display嵌套层次：指过程定义的层数，始终假定主程序的层数为0，因此主程序称为0层过程,计数过程的层数用一个计数器Level，初值为0，每遇到过程说明则增1，过程说明结束则减1display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址,图10.11的程序，假定有如下四
11、种调用情况：（a）sortquicksort（b）sortquicksort quicksort（c）sortquicksort quicksortpartition（d）sort quicksortquicksortpartition exchange图10.16(a)-(d)分别说明上述四种情形的运行栈和display,display本身的体积在编译时可确定，它作为单独的表分配存储还是作为活动记录的一部分，比如置于实参的上端（如图10.17所示），则取决于编译程序的设计者,当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display?当P1调用P2时必须把P0的display地
12、址作为连接数据之一传给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地址，必须在
13、P1调用P2时设法把P1的display地址作为连接数据之一传送给P2,于是连接数据变为三项：（1）老SP值；（2）返回地址；（3）全局display地址这样，整个活动记录的组织就如图10.17所示,三.分程序结构的存储管理一个分程序是一个含有它自己的局部数据（变量）声明的语句在C语言中，一个分程序的语法形式是：声明语句例如图10.19的C程序中的分程序B0，B1，B2和B3，分程序的特征是它们的嵌套结构，使用界符标明分程序的开始和结束，C语言用,分程序结构可以用栈式存储分配实现一种办法是把分程序看成一个“无参过程”，只不过是在该分程序入口处调用，分程序出口处返回。分程序在哪里定义就在哪里被调
14、用另一种办法是每次为一个完整的过程体分配存储，即把一个过程体中的所有分程序所需的存储一次分配好，如图10.19的C程序,可以为这里所有声明的名字分配一块存储，如图10.20所示：,ALGOL的结构特点是除了允许过程嵌套定义还含有分程序的结构，如图10.21的一个ALGOL过程：,如采用将分程序看成“无参过程”，则效率很低，因为：第一，分程序不存在被调用的问题，不必要在进入一个分程序时，将连接数据和display都放进活动记录中第二，当从内层分程序向外转移时可能同时要结束若干个分程序，那么怎样恢复所要到达的那个分程序的数据区呢？,克服上述缺点的办法是：首先，代替原来的那个统一的栈顶指示器，让每个
15、过程和分程序都有自己的栈顶指示器TOP，它的值保存在各自的活动记录中其次，不把分程序看作“无参过程”，而让每个分程序享用包围它的那个最小过程的display,每个过程的活动记录所含的内容有：1.过程的TOP单元，指向活动记录的栈顶位置2.连接数据：(1)老SP值(2)返回地址(3)全局display地址(4)调用时的栈顶单元地址，称作老TOP3.参数个数和形式单元4.display表,5.过程所管辖的各分程序的局部数据单元对每个分程序来说,它们包括：(1)一个名为TOP的单元，当进入时它含现行栈顶地址，以后用来存放栈的新高度(2)分程序的局部变量、数组内情向量和临时工作单元,图10.22给出了
16、过程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
17、值，得到图10.23（f）,10.3参数传递,当一个过程调用其他过程时，调用过程和被调过程之间的通信经由非局部量或者经由参数传递,如图10.24的过程exchange1既使用了非局部量数组a，又使用了形式参数i和j，将ai和aj的值进行交换（1）procedure exchange1(i,j:integer);（2）var x:integer;（3）begin;（4）x:=ai;ai:=aj;aj:=x;（5）end;图10.24带有非局部变量和形参的Pascal过程,把实在参数传递给相应的形式参数方法：传值、传地址、传名、宏扩展等观察图10.25的Pascal程序，程序的输出是a=2,b=1
18、，如果将第3行的关键字var 去掉，则该程序的输入是a=1,b=2,一.传值call-by-value（值调用）将实参计算出它的值，然后把它传给被调过程：1.形式参数当作过程的局部变量处理2.调用过程计算实参的值，并将它们的右值放在为形式单元开辟的空间中,3.被调用过程执行时，就像使用局部变量一样使用这些形式单元传值的重要特点是对形式参数的任何运算不影响调用过程的活动记录中实参的值通过值调用的过程可以由非局部量或由指针而对调用过程发生影响,比如图10.26的C程序中，x和y声明为整型指针，第8行调用swap(&a,&b)中的操作符导致将指向a和b的指针传给过程swap。该程序的输出为：a is
19、 now 2,b is now 1,二.传地址当参数通过引用传递时，也称作传地址，或引用调用调用过程传给被调过程的是指针，指向实参存储位置的指针1.如实参是一个名字或是具有左值的表达式，则左值本身传递过去2.如实参是一个表达式，比如a+b或2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去3.被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问,例如，在图10.25的程序中，若用实参i和ai对过程swap进行调用，即swap(i,ai)，其效果如下步骤所述：1.将i和ai的地址（左值）拷贝到被调过程的活动记录中，比如说分别对应形参x和y的单元ar
20、g1和arg22.将局部变量temp设为由arg1所指单元的内容（即令temp等于I0，其中I0是i的初值），这一步对应于swap定义中的第6行语句：temp:=x3.将arg1所指单元的内容设为等于temp的值，即设aI0=i,这一步对应swap中第7行的x:=y4.将arg2所指单元的内容设为等于temp的值，即设aI0=i，这一步对应y:=temp,三.过程参数一个嵌套过程（函数）可以作为参数传递，比如图10.27的PASCAL程序中，过程c把f作为参数传递给b，而b通过引用形参h调用f,图10.28说明了这点，当过程c传递f时，c可以决定f的存取链，或者说f的存取链或display可以
21、根据c的存取链或display来建立：,10.4过程调用、过程进入和过程返回,对于过程调用的四元式序列：par T1par T2par Tncall P,n,在运行时是如何执行的？/par和call产生什么相应的目标 代码对于par Ti（i=1,2,n)的处理是：根据par Ti（i=1,2,n)中Ti的种别而生成传送指令，或将参数的值 或将参数的地址传送至新的过程的活动记录的形式单元中,对于call p,n则应生成传送参数个数n的指令；保护现行SP至新过程的活动记录（老SP）；转子，转向P的第一条指令；定义新SP；保护返回地址；定义新值；填写display或存取链内容等指令如果过程含动态数
22、组（局部），则应生成对数组进行存储分配的指令，即生成运行时动态地建立内情向量和分配数组空间的目标指令在过程执行语句的工作过程中，凡引用形参、局部变量或数组元素都可根据过程活动记录起点的相对位置访问,当过程P工作完毕要返回到调用段时，若语言有形如return（E）的返回语句，或P是个函数过程时，则可把已算好的值传送至某个特定的寄存器中，调用段将从这个特定的寄存器中获得被调过程的结果值。然后所生成的目标指令则应完成的工作是：恢复SP；恢复TOP，按保存的返回地址实行无条件转移,8.4 堆式动态存储分配,假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间
23、先后不一，经一段运行之后，程序运行空间将被划分成许多块，有些占用，有些空闲。那么当运行程序要求一块体积为N的空间时，需要决定应该从哪个空闲块得到这个空间。理论上讲,应该从比N稍大一些的空闲块中取出N个单元，以便使大的空闲块派更大的用场，但实现难度很大,实际中常常采用的办法：先遇到哪块比N大就从其中取出N个单元即使这样，也会发生找不到一块比N大的空闲块，但所有空闲块总和比N大得多，这时，有的分配管理系统采用废品回收的办法来应付,8.5 临时变量的存储分配,产生中间代码时，为了暂存中间结果，编译程。序会大量引进临时变量名，其属性简单，不登记到符号表，只在它们出现的地方加上类型信息皆可。一般的分配原
24、则：如果两个临时变量名的作用域不相交，则它们可以分到同一单元种。一个临时变量名自第一次赋值的地方器至最后一次被引用的地方止，这区间的程序所能达到的全体四元式构成它的作用域。,8.5 临时变量的存储分配,临时变量的存储分配的简单实现：令临时变量名均分配在局部数据区中，若某一单元已分配给某些临时变量，则把这些名字的作用域（它们必须是互不相交的）作为单元的分配信息记录下来。每当要对新临时变量名进行分配时，首先要求求出该变量名的作用域，若它的作用域与某个单元所记录的全部作用域均不相交，就把这个单元分配给这个新名，同时把它的作用域也添加到该单元的分配信息之中。如果新临时变量的作用域和所有已分配单元的作用
25、域均有冲突，就分配给它一个新的单元，同时把新名的作用域作为此单元的分配信息。,【本章小结】目标代码运行时，存储区域的整体布局,以及各区域的作用各种不同数据变量区的不同分配组织方式允许过程嵌套定义的语言，栈式动态分配的组织管理过程活动纪录的各项内容和它们的作用，以及活动纪录的组织方式参数传递的不同方式及其实现过程调用和返回时，相应目标代码以及栈式动态分配区的管理,第10章习题第1题：下面的程序执行时输出的a分别是什么?若(1)参数的传递办法为传值；(2)参数的传递办法为传地址。program main(input,output);procedure p(x,y,z);beginy=y+1;z=z
26、+x;end;begina=2;b=3;p(a+b,a,a);print a end.,第2题：过程参数的传递方式有几种?简述传地址和传值的实现原理。第3题：下面是一个Pascal程序program PP(input,output)var K:integer;function F(N:integer):integerbeginif N=0 then F:=1else F:=N*F(N-1);end;begin K:=F(10);.end;当第二次（递归地）进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？,第4题：对如下的Pascal程序，画出程序执行到（1）和（2）点时的运行
27、栈。program Tr(input,output);var i:integer;d:integer;procedure A(k:real);var p:char;procedure B;var c:char;begin.(1).end;Bprocedure C;var t:real;begin.(2).end;Cbegin.B;C;.end;Abeginmain.A(d);.end.,第5题：有如下示意的Pascal源程序program main;var a,b,c:integer;procedure X(i,j:integer);var d,e:real;procedure Y;var f,g:real;begin.end;Yprocedure Z(k:integer);var h,i,j:real;begin.end;Zbegin.10:Y;.11:Z;.end;Xbegin.X(a,b);.end.main 并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和DISPLAY的内容。（1）已开始而尚未执行完毕的标号为10的语句。（2）已开始而尚未执行完毕的标号为11的语句。,第10章作业题P247：5.6.,
