《编译原理课件-(9)》由会员分享，可在线阅读，更多相关《编译原理课件-(9)（37页珍藏版）》请在金锄头文库上搜索。
1、2008年3月,湖北大学数计学院计科系,第9章 运行时的存储组织与管理,（翻译程序必须分配目标程序运行时所需的存储空间，这些空间包括：用户定义的各种类型的变量和常数所需的存储单元；作为保留中间结果和参数传递用的临时工作单元；调用过程或函数时所需的连接单元，返回地址以及组织输入输出所需要的缓冲区。本章介绍有关运行时的存储组织和管理问题。）,Compiler,2008年3月,湖北大学数计学院计科系,9.1 数据区和属性字 9.2 基本数据类型的存储分配 9.3 数组的存储分配 9.4 记录结构的存储分配 9.5 参数传递方式及其实现 9.6 栈式存储分配方法 9.7 堆式存储分配方法 9.8 临时
2、工作单元的存储分配 9.9 小结,2008年3月,湖北大学数计学院计科系,9.1 数据区和属性字,例：PASCAL主程序中所说明的变量运行时所需要的存储单元以及主程序运行时所需要的临时工作单元一起构成了一个数据区。,数据区,数据区是指一片相连的存储单元。,2008年3月,湖北大学数计学院计科系,在编译时，任何变量运行时存储单元都可由一对偶（数据区编号，位移）表示。其中，数据区编号是分配给数据区的唯一编号；位移是指该存储单元相对于该数据区起址的距离（或单元数）。,例如：对于编号为10的数据区 它的第1个存储单元可表示为（10,0） 第2个存储单元可表示为（10,1） 第i个存储单元可表示为（10
3、,i-1）,2008年3月,湖北大学数计学院计科系,程序中出现的简单变量和常量数组，由于它们所需的存储单元数在编译时就可以确定，所以在编译时就可以给它们分配存储单元，这种在编译阶段进行的存储分配工作称为静态存储分配，由静态存储分配产生的数据区称为静态数据区。在整个运行过程中，这种数据区是固定不变的。,在运行阶段分配的数据区统称为动态数据区。在运行时，一个动态数据区不是固定不变的，随着相应程序单位的调用和返回，它也会随之建立和撤销数据区。,2008年3月,湖北大学数计学院计科系,问题：C语言程序引用sizeof函数时，该函数的计算是在编译该程序时完成的，还是在运行该程序时完成的？,解答：在C语言
4、中，sizeof函数的计算是在编译时进行的，因为每个类型的大小是确定的，不会随程序的运行而发生变化，所以完全可以在编译时计算出来。,2008年3月,湖北大学数计学院计科系,begin procedure A begin procedure B begin end; procedure C begin end; end; procedure D begin end; end;,若主程序和每个过程都有自己的数据区，那么将所能引用的数据区的起址按照它们建立的先后顺序排列起来就构成一个DISPLAY表。,2008年3月,湖北大学数计学院计科系,属性字,程序中变量的属性常常不能在编译阶段全部确定出来。为
5、此编译阶段在给变量分配存储地址的同时，还为它分配一个属性字，用以记录该变量在运行时所确定的属性。,例如动态数组，在运行时，一旦知道了存储空间属性，就调用getarea分配存储空间，并把所分配的存储空间的起址存放在相应的属性字中，以后总是通过这个属性字去访问相应的数组元素的地址。,2008年3月,湖北大学数计学院计科系,9.2 基本数据类型的存储分配,基本数据类型：整型、实型、布尔型和指示器型。,整型变量：通常占用数据区中的一个单元，其值按机器内部的标准整数形式存储。 实型变量：通常占用一个字。 布尔型变量：占用一个字，常用零表示“false”值，用非零表示“true”值。 指示器型变量：通常占
6、用一个单元。在某些情况下，也把指示器表示成两个相邻单元，一个是其属性字，指明它的类型，另一个单元包含它所真正指向的值。,2008年3月,湖北大学数计学院计科系,9.3 数组的存储分配,单块存储方式,单块存储方式就是把数据区中的一片相连单元分配给数组的元素，数组的所有元素则按次序连续地存储在这片数据区中。元素的排列次序通常为两种：按行的次序和按列的次序。,两种存储方式：单块存储、多块存储,2008年3月,湖北大学数计学院计科系,对array A1m , 1n of integer所说明的数组，如果以按行的次序存储数组元素的值，则任一数组元素Ai , j在数据区中的地址可由下式求得：,addres
7、s(Ai , j)=address(A1,1)+(i-1)*n+(j-1),address(Ai , j)=address(A1,1)-n-1+(i*n+j),2008年3月,湖北大学数计学院计科系,对array A1m , 1n 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、数计学院计科系,设A是下面的说明语句定义的一个n维数组： array Al1u1 , l2u2 , , lnun of integer 假设di=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+Varp
9、art 其中，Conspart= address(Al1,l2,.,ln) -(l1*d2+l2)*d3+l3)*d4+ln-1)*dn+ln) Varpart=(i1*d2+i2)*d3+in-1)*dn+in,Begin Varpart:=1 ; j:=1 ; while jn do begin Varpart:=Varpart*dj+1+ij+1 ; j:=j+1; end end,Varpart,2008年3月,湖北大学数计学院计科系,信息向量与数组分配程序,数组的信息向量：属性字,2008年3月,湖北大学数计学院计科系,数组分配程序： begin i:=1 ; Size:=1 ; C
10、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月,湖北大学数计学院计科系,多块存储方式,多块存储方式是对每一行都分配一个单块数据区，每行的元素按递增次序存放在这块数据区中。此
11、外，还设一个指示器表，用以指示这些单块数据区的开始位置。,2008年3月,湖北大学数计学院计科系,9.4 记录结构的存储分配,记录结构是由不同类型的数据组合起来的一种结构。,例如，记载学生信息（名字、学号、年龄）的卡片就可以写成如下的记录形式： record name:char-string20; number:integer; age:integer; end,存储分配方式： 将其分量依次连续存储在一个数据区中。,2008年3月,湖北大学数计学院计科系,9.5 参数传递方式及其实现,一个过程或子程序一经定义，就可以被调用。调用与被调用者之间的信息交流是通过全局量或经由参数传递的方式进行。,参
12、数传递方式： 换名、传值、传地址、传结果以及数组名用做参数和过程名用做参数。,2008年3月,湖北大学数计学院计科系,换名：用过程体的代码直接替换过程调用语句，其中的形参被替换为相应的实参。 传值：过程调用时，将实参的值传递给形参。形参值的改变不会引起实参的变化。 传地址：过程调用时，将实参的地址传递给形参。形参值的改变会引起实参的变化。 传结果：过程调用时，形参用两个存储单元分别存放实参的值和地址。调用完毕，将形参的值按存储的地址返回给实参。,形参：过程定义语句中的参数。 实参：过程调用语句中的参数。,2008年3月,湖北大学数计学院计科系,问题：对于下面的程序： procedure P（X
13、 , 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 栈式存储分配方法,栈式存储分配方法：指把整个程序的存储空间都安排在一个栈内。,主要思想： 进入主程序时，将主程序定义的各类量（全程量）所需存储空间分配于栈的顶部； 每当调用一个子程序（过程/函数）时，就将它所需的存储空间分配于栈的当前顶部； 每当一个子程序（过程/
14、函数）运行结束时，就从栈中释放它所占空间； 整个程序执行完后，释放它所占用的全部空间。,2008年3月,湖北大学数计学院计科系,一个过程的活动是指该过程的一次执行。即每次执行一个过程体，产生该过程体的一个活动。,过程P的一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序列，包括执行P时调用其它过程花费的时间。,在任一时刻，几个过程可以同时处于正在执行的进程中，但只有一个过程是当前正在工作的，这个过程称为现行过程。其它的过程只是处于等待现行过程的完成和返回。,过程的活动与活动记录,活动记录：为了记录过程一次活动的数据信息而分配的一片连续的存储区域。,2008年3月,湖北大
15、学数计学院计科系,在某些程序设计语言中，过程可以嵌套定义或调用，一个过程可以引用包围它的任一外层过程所定义的变量或数组，也就是说，运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。,跟踪外围过程最新活动记录地址的方法： 静态链 Display表,2008年3月,湖北大学数计学院计科系,1、静态链和活动记录,思想：利用一个称为静态链的指针，该指针为活动记录的一个域，指向直接外层过程最新活动记录的首地址。,活动记录结构,静态链：从一个过程的当前活动记录指向其直接外层过程的最新活动记录的首地址。,动态链：指向调用该过程前正在运行的过程的最新活动记录的首地址。,2008年3月,湖
16、北大学数计学院计科系,Program P ; var a , x : integer ; procedure Q (b:integer); var 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 ) ; endS begin a:=0 ; S ; end.P,活动记录结构,2008年3月,湖北大学数计学院计科系,2、嵌套层次显示表( display )和活动记录,思想：利用一张display表，该表为活动记录的一部分，记录所有外层过程最新活动记录的首地址。,活动记录
