编译原理课件-(9).ppt

1、 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系第9章 运行时的存储组织与管理 （翻译程序必须分配目标程序运行时所需的存储空间，这些空间包括：用户定义的各种类型的变量和常数所需的存储单元；作为保留中间结果和参数传递用的临时工作单元；调用过程或函数时所需的连接单元，返回地址以及组织输入输出所需要的缓冲区。本章介绍有关运行时的存储组织和管理问题。） 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.1 数据区和属性字9.2 基本数据类型的存储分配9.3 数组的存储分配9.4 记录结构的存储分配9.5 参数传递方式及其实现9.6 栈式存储分配方法9.7 堆式存储分配方

2、法9.8 临时工作单元的存储分配9.9 小结 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.1 数据区和属性字例：PASCAL主程序中所说明的变量运行时所需要的存储单元以及主程序运行时所需要的临时工作单元一起构成了一个数据区。数据区数据区数据区是指一片相连的存储单元。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 在编译时，任何变量运行时存储单元都可由一对偶（数据区编号，位移）（数据区编号，位移）表示。其中，数据区编号数据区编号是分配给数据区的唯一编号；位移位移是指该存储单元相对于该数据区起址的距离（或单元数）。例如：对于编号为10的数据区 它的第1个存储

3、单元可表示为（10,0） 第2个存储单元可表示为（10,1） 第i个存储单元可表示为（10,i-1） 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 程序中出现的简单变量和常量数组，由于它们所需的存储单元数在编译时就可以确定，所以在编译时就可以给它们分配存储单元，这种在编译阶段进行的存储分配工作称为静态存储分配静态存储分配，由静态存储分配产生的数据区称为静态数据区静态数据区。在整个运行过程中，这种数据区是固定不变的。 在运行阶段分配的数据区统称为动态数据区动态数据区。在运行时，一个动态数据区不是固定不变的，随着相应程序单位的调用和返回，它也会随之建立和撤销数据区。 2008年年

4、3月月湖北大学数计学院计科系湖北大学数计学院计科系问题问题：C语言程序引用sizeof函数时，该函数的计算是在编译该程序时完成的，还是在运行该程序时完成的？解答：在C语言中，sizeof函数的计算是在编译时进行的，因为每个类型的大小是确定的，不会随程序的运行而发生变化，所以完全可以在编译时计算出来。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系begin procedure A begin procedure B begin end; procedure C begin end; end; procedure D begin end; end; 若主程序和每个过程都有自己的数

5、据区，那么将所能引用的数据区的起址按照它们建立的先后顺序排列起来就构成一个DISPLAY表。例：当执行过程C时，DISPLAY表为主程序的数据区起址过程A的数据区起址过程C的数据区起址 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系属性字 程序中变量的属性常常不能在编译阶段全部确定出来。为此编译阶段在给变量分配存储地址的同时，还为它分配一个属性字属性字，用以记录该变量在运行时所确定的属性。 例如动态数组，在运行时，一旦知道了存储空间属性，就调用getarea分配存储空间，并把所分配的存储空间的起址存放在相应的属性字中，以后总是通过这个属性字去访问相应的数组元素的地址。 2008

6、年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.2 基本数据类型的存储分配基本数据类型：整型、实型、布尔型和指示器型。整型变量：通常占用数据区中的一个单元，其值按机器内部的标准整数形式存储。实型变量：通常占用一个字。布尔型变量：占用一个字，常用零表示“false”值，用非零表示“true”值。指示器型变量：通常占用一个单元。在某些情况下，也把指示器表示成两个相邻单元，一个是其属性字，指明它的类型，另一个单元包含它所真正指向的值。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.3 数组的存储分配单块存储方式 单块存储方式单块存储方式就是把数据区中的一片相连单元分配给

7、数组的元素，数组的所有元素则按次序连续地存储在这片数据区中。元素的排列次序通常为两种：按行的次序按行的次序和按列的次序按列的次序。两种存储方式：单块存储、多块存储 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 对array A1.m , 1.n of integer所说明的数组，如果以按行的次序存储数组元素的值，则任一数组元素Ai , j在数据区中的地址可由下式求得：address(Ai , j)=address(A1,1)+(i-1)*n+(j-1)address(Ai , j)=address(A1,1)-n-1+(i*n+j) 2008年年3月月湖北大学数计学院计科系湖

8、北大学数计学院计科系 对array A1.m , 1.n of integer所说明的数组，如果以按行的次序存储数组元素的值，则任一数组元素Ai , j在数据区中的地址可由下式求得：address(Ai , j)=address(A1,1)+(i-1)*n+(j-1)address(Ai , j)=address(A1,1)-n-1+(i*n+j)注注：上式中的第一部分是一常数，仅需计算一次。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 设A是下面的说明语句定义的一个n维数组： array Al1.u1 , l2.u2 , . , ln.un of integer 假设di

9、=ui-li+1 , i=1,2,n，即di为第i对界偶的界差，亦即第i维中不同下标值的个数，在按行的次序存放方式的前提下，数组元素Ai1,i2,.,in的地址为： address(Al1,l2,.,ln)+(i1-l1)*d2*d3*dn +(i2-l2)*d3*d4*dn + +(in-1-l n-1)*dn +(in-ln) 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系经整理后，得 address(Ai1,i2,.,in)=Conspart+Varpart其中，Conspart= address(Al1,l2,.,ln) -(l1*d2+l2)*d3+l3)*d4+ln

10、-1)*dn+ln) Varpart=(i1*d2+i2)*d3+in-1)*dn+inBegin Varpart:=1 ; j:=1 ; while jn do begin Varpart:=Varpart*dj+1+ij+1 ; j:=j+1; endendVarpart 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系信息向量与数组分配程序数组的信息向量：属性字l1u1d1l2u2d2lnundnnConsparttypeBaseloc 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系数组分配程序数组分配程序： begin i:=1 ; Size:=1 ; C

11、onspart:=0; while i n do begin di:=ui-li+1 ; Size:=Size*di ; Conspart:=Conspart*di+li ; 把li , ui , di填入信息向量中; i:=i+1 end 调用getarea，按Size分配数据区； Baseloc:=该数据区起址； Conspart:=Baseloc-Conspart ; 把n , Conspart , type和Baseloc填入信息向量中 end. 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系多块存储方式 多块存储方式多块存储方式是对每一行都分配一个单块数据区，每行的元

12、素按递增次序存放在这块数据区中。此外，还设一个指示器表，用以指示这些单块数据区的开始位置。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.4 记录结构的存储分配记录结构记录结构是由不同类型的数据组合起来的一种结构。例如，记载学生信息（名字、学号、年龄）的卡片就可以写成如下的记录形式： record name:char-string20; number:integer; age:integer; end存储分配方式： 将其分量依次连续存储在一个数据区中。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.5 参数传递方式及其实现 一个过程或子程序一经定义，就可

13、以被调用。调用与被调用者之间的信息交流是通过全局量或经由参数传递参数传递的方式进行。 参数传递方式： 换名换名、传值传值、传地址传地址、传结果传结果以及数组名用做参数和过程名用做参数。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系换名：用过程体的代码直接替换过程调用语句，其中的形参被替换为相应的实参。传值：过程调用时，将实参的值传递给形参。形参值的改变不会引起实参的变化。传地址：过程调用时，将实参的地址传递给形参。形参值的改变会引起实参的变化。传结果：过程调用时，形参用两个存储单元分别存放实参的值和地址。调用完毕，将形参的值按存储的地址返回给实参。形参形参：过程定义语句中的参

14、数。 实参实参：过程调用语句中的参数。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系问题：对于下面的程序： procedure P（X , Y , Z）； begin Y:=Y+1 ; Z:=Z+X; end P； begin A:=2 ; B:=3 ; P（A+B , A , A） print A end. 若参数传递的办法分别为（1）换名（2）传地址（3）传结果（4）传值。 试问：程序执行后输出的A值分别是多少？ 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.6 栈式存储分配方法栈式存储分配方法：指把整个程序的存储空间都安排在一个栈内。主要思想：进入主

15、程序时，将主程序定义的各类量（全程量）所需存储空间分配于栈的顶部；每当调用一个子程序（过程/函数）时，就将它所需的存储空间分配于栈的当前顶部；每当一个子程序（过程/函数）运行结束时，就从栈中释放它所占空间；整个程序执行完后，释放它所占用的全部空间。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 一个过程的活动活动是指该过程的一次执行。即每次执行一个过程体，产生该过程体的一个活动。 过程P的一个活动的生存期活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序列，包括执行P时调用其它过程花费的时间。 在任一时刻，几个过程可以同时处于正在执行的进程中，但只有一个过

16、程是当前正在工作的，这个过程称为现行过程现行过程。其它的过程只是处于等待现行过程的完成和返回。过程的活动与活动记录活动记录活动记录：为了记录过程一次活动的数据信息而分配的一片连续的存储区域。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 在某些程序设计语言中，过程可以嵌套定义或调用，一个过程可以引用包围它的任一外层过程所定一个过程可以引用包围它的任一外层过程所定义的变量或数组义的变量或数组，也就是说，运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。跟踪外围过程最新活动记录地址的方法：静态链Display表 2008年年3月月湖北大学数计学院计科系湖北大

17、学数计学院计科系1、静态链和活动记录思想思想：利用一个称为静态链的指针，该指针为活动记录的一个域，指向直接外层过程最新活动记录的首地址。活动记录结构静态链：从一个过程的当前活动记录指向其直接外层过程的最新活动记录的首地址。动态链：指向调用该过程前正在运行的过程的最新活动记录的首地址。动态链（老SP）返回地址静态链静态链形参个数形参单元简单变量信息向量临时单元SP 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系Program P ; var a , x : integer ; procedure Q (b:integer); var i:integer ; procedure R

18、 (u:integer;var v:integer); var c , d:integer; begin if u=1 then R ( u+1 , v) ; v:=(a+c)*(b-d); endR begin R(1 , x); endQ procedure S; var c , i :integer; begin a:=1; Q ( c ) ; endSbegin a:=0 ; S ; end.P活动记录结构临时单元信息向量简单变量形参单元形参个数静态链静态链返回地址动态链（老SP） 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系2、嵌套层次显示表( display )和

19、活动记录思想思想：利用一张display表，该表为活动记录的一部分，记录所有外层过程最新活动记录的首地址。活动记录结构Display表：该表自顶向下每个单元依次存放着现行层，直接外层，直至最外层（主程序层）等每一层过程最新活动记录的首地址。全局display：主调程序的活动记录中display表的首地址。display动态链（老SP）返回地址全局全局display形参个数形参单元简单变量信息向量临时单元SP 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系Program P ; var a , x : integer ; procedure Q (b:integer); var

20、i:integer ; procedure R (u:integer;var v:integer); var c , d:integer; begin if u=1 then R ( u+1 , v) ; v:=(a+c)*(b-d); endR begin R(1 , x); endQ procedure S; var c , i :integer; begin a:=1; Q ( c ) ; endSbegin a:=0 ; S ; end.P活动记录结构临时单元信息向量简单变量display形参单元形参个数全局全局display返回地址动态链（老SP） 2008年年3月月湖北大学数计学院

21、计科系湖北大学数计学院计科系9.7 堆式存储分配方法 基本思想基本思想：当一个程序开始执行时，有很大一片单元用做空闲存储区，当程序开始运行时，可多次调用getarea分配存储空间。运行结束，则调用freearea释放占用的存储空间。 多次调用getarea和freearea之后，原来的存储区可能变成如下形式：空闲使用空闲空闲使用空闲使用使用需对空闲区进行有效管理。首次匹配法、最优匹配法、最差匹配法 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系首次匹配法首次匹配法：按序查看空闲区，选出其中第一个满足所需容量要求的空闲区来进行分配。 时间：分配时查表，归还时不需查表 缺点：容易造

22、成存储空间浪费最优匹配法最优匹配法：选出空闲区中最接近于（大于或等于）所需容量要求的空闲块来进行分配。 时间：须将空闲块由小到大进行排序，分配、归还时均需查表 缺点：花费时间较多最差匹配法最差匹配法：选出最大的空闲块来进行分配。 时间：须将空闲块由大到小进行排序，归还时均需查表 缺点：可能无法满足较大的存储空间要求 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系9.8 临时工作单元的存储分配 临时工作单元临时工作单元也称为临时工作变量。其作用域为从该变量开始确定其值到最后一次使用它之间的这段时间间隔。涉及临时工作变量v的代码可分为两大类：1、“ST v”，即对v赋值，从而确定了

23、变量v的作用域的起点；2、“用v”，其中包括“LD v”、“+ v”、“* v”等等。就一个代码序列中同一个v而言，这种用v指令的最后一条就是v的作用域的终点。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系例如，对于算术表达式 (a+b)*(c+d)+e*f)*(g-h)一般编译程序将生成如下目标代码：LD a ADD bST T2 LD e MUL f ADD T2ST T1 LD c ADD d MUL T1ST T3 LD g SUB h MUL T3T1的作用域T2的作用域T3的作用域由于T1、T2、T3的作用域互不相交，所以只需一个临时工作变量T1就够了。 2008

24、年年3月月湖北大学数计学院计科系湖北大学数计学院计科系例如，对于算术表达式 (a+b)*(c*d+e*f)一般编译程序将生成如下目标代码：LD aADD bST T1LD cMUL dST T2LD eMUL fADD T2MUL T1T2的作用域T1的作用域 T1的作用域包含了T2的作用域，所以需要两个临时工作变量。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 若不考虑表达式优化算法，所有临时变量v的使用指令（即“用v”）只能有一次，也就是说，它只要出现就是最后一次。可用栈来控制临时工作单元的分配：在需要将信息存入临时工作单元时，生成“送T”指令，该T从临时工作单元栈中取

25、得，此栈下推一格，表示T已占用；T作为运算对象进运算对象栈时，必须加以标记，以区别于其它工作单元；当生成一条“用T”型指令时，表示此工作单元内容已用完，因此可以释放它。此时，若T是临时工作单元栈的栈顶单元，则将此栈上顶一格，以表明T这一单元已不占用了。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 在考虑表达式优化后，若对公共子表达式不重复编出指令， 而是将其结果存入临时工作单元中供多次使用。则一般要在生成一段指令之后才能确定各变量的作用域，才能考虑节省临时工作单元的问题。为了确定vi的最后一次使用，必须反向扫描已编出的代码序列，并对vi分配临时工作单元。对每条“用vi”指令

26、，若还没给vi分配存储单元，就从栈顶取出一空闲单元分配给vi ，并在该指令中用该存储单元的地址替换vi ；若已给分配了存储单元，则仅做替换工作；对每条“送vi”指令，根据步骤 ，此vi必定已分配了存储单元，需用该存储单元的地址去替换指令中的vi ，并且，因为这是变量vi作用域的起点，因此，释放该变量占用的存储单元，把它交还可用存储单元栈（放到栈顶）。 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系 假设有已编出的指令（仅考虑与vi相关的指令）为送 v1送 v2用 v2用 v1送 v3用 v1用 v3送 v4用 v3用 v4送 T1送 T2用 T2用 T1送 T2用 T1用 T2送 T1用 T2用 T1 2008年年3月月湖北大学数计学院计科系湖北大学数计学院计科系本章重点：参数传递方式及实现利用display表的栈式存储管理