资源目录
压缩包内文档预览：(预览前20页/共52页)
编号：21836409
类型：共享资源
大小：13.06MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
编译
原理
实用教程
杨德芳
课件
ppt
- 资源描述：
-
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
- 内容简介：
-
第9章运行时存储空间的组织和管理,本章学习目标,翻译程序必须分配目标程序运行时所需要的存储空间。这些空间包括：用户定义的各类型的变量和常数所需要的存储空间；作为保留中间结果和参数传递用的临时工作单元；调用过程或函数时所需要的连接单元。返回地址以及组织输入/输出所需要的缓冲区。本章主要内容： 静态存储分配 栈式存储分配 堆式动态存储分配,9.1存储分配策略,在目标代码生成之前，编译程序必须进行目标程序运行环境的设计和数据空间的分配。编译程序需要从操作系统中为目标程序的运行申请一段存储区。这段存储空间包括两部分，一部分为容纳目标代码的区域，另一部分为目标代码运行时需要的数据空间。这部分数据空间包括：用户定义的各种类型的数据对象所需要的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需要的连接单元，以及组织输入/输出所需要的缓冲区。目标代码需要的内存空间编译时可以确定，而有些数据对象只有运行时填入。 数据空间的使用和管理方法可以分成三种：静态存储分配、栈式动态存储分配和堆式动态存储分配。,9.2静态存储分配,如果在编译时就能够确定一个程序在运行时所需的存储空间大小，那么则在编译时就能安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分配方法叫做静态分配。对于FORTRAN语言来说，其特点是不允许过程有递归性，每个数据名所需要的存储空间大小都是常量；并且所有数据名的性质是完全确定的。这些特点确保整个程序所需要数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。 静态分配是一种最简单的存储管理。适应静态存储分配的语言必须满足以下条件： （1）数组的上下界必须是常数。 （2）过程调用不允许递归。 （3）不允许采用动态的数据结构。,满足这些条件的语言除了FORTRAN之外，还有BASIC等语言。 对于PASCAL语言和C语言是不能仅仅使用静态存储分配的，这是因为，对于这样的语言： （1）有些数据对象的大小在编译时刻不能确定，也可能对它们在内存中位置的限制不能确定。 （2）需要支持递归过程的实现，一个过程的不同活动不能有相同的局部名字结合。 （3）需要动态建立数据结构。,9.3栈式存储分配,使用栈式存储分配策略，运行时每当进入一个过程，就在栈顶为该过程分配所需要的数据空间，当一个过程执行完毕，就将栈顶的数据空间释放。 为了研究方便，引进一个过程的活动记录。过程的活动记录是一段连续的存储区，存放过程依次执行所需要的信息。过程的活动记录描述如图9-1所示：（1）临时工作单元，比如计算表达式过程中需要存放中间结果的临时值的单元。 （2）局部变量，是指一个过程的变量。 （3）机器状态信息，即容纳该过程执行前关于机器状态的信息，如计数器、寄存器的值。这些值需要在控制从该过程返回时给予恢复。,（4）存取链，用以存取非局部变量，这些变量存放在其他过程活动记录中。 （5）控制链，指向调用该过程的那个过程的活动记录。 （6）实参数，也称为形式单元；是调用过程向该被调用过程提供实参的值。当然，在实际编译程序中，也用机器的寄存器传递参数。 （7）返回地址，保存该被调过程返回后的地址。 活动记录中的信息的大小在编译时就确定了。如果局部变量中含有可变数组，可以将内情向量表放入过程活动记录。下面介绍3种栈式分配的实现。,9.3.1简单的栈式存储分配 首先考虑一种简单程序设计语言的实现。这种语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。 使用栈式存储分配意味着程序运行时，当进入一个过程就有一个相应的活动记录压入栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。在进入过程和执行过程的可执行语句之前，再把局部数组所需要的空间压入栈顶，从而形成过程工作时的完整数据区。,例如，有C语言运行程序如下： floAt x; /块1 int m1(int ind) /块2 int x; x=m2(ind+1); int m2(int j) /块3 int f10; bool test1; mAin( ) /块4 int x; x=2; printf(“%dn”,m1(x/5); ,若主程序调用了过程Q，Q又调用了过程R，在R进入运行后的存储结构如图9-4（a）所示。若主程序调用了过程Q，Q又调用了自己，在Q过程第2次进入运行后，存储空间的分配就是9-4（b）。若主程序先调用了过程Q，执行完后又调用过程R，存储结构如9-4（c）和9-4（d）所示。,使用两个指针指示栈最顶端的数据区，一个是SP，一个为TOP。SP指向现行活动记录的的起点，TOP指向栈顶单元。如果是含有可变数组的语言，则它的过程活动记录为图9-5所示。 在过程段中对任何局部变量x的引用可表示为变址xsp，此处x代表变量x的相对数，也就是相对于活动记录起点的地址，这个相对数在编译时确定,说明：每个过程的活动记录的体积在编译时就可以静态地确定。但由于允许含有可变数组，所以数组的大小只有在运行时才能知道。因数组区的大小不能预先获知，为了扩充方便，所以只能将数组区压入活动记录之上的当前栈顶。当一个过程工作完毕返回时，它在栈顶的数据区（包括活动记录和数组区）也就不再存在。,9.3.2嵌套过程语言的栈式实现,具有嵌套结构的高级程序设计语言比较典型的是PASCAL语言。它的存储分配也是动态的栈式存储分配。下面以PASCAL语言为例说明具有嵌套结构的存储空间的分配。 program sort(input,output) var a: array010 of integer; x:integer; procedure readarray; var i:integer; begin aend readarrAy; procedure exchange(i,j:integer); begin x:=ai;ai:=aj:aj:=x; endexchange,procedure quicksort(m,n:integer); var k,v:integer; function partition(y,z:integer):integer; var i,j:integerl begin a v exchange(i,j); end;partition; begin endquicksort; begin end. 上面的嵌套情况如下: sort readarray exchange quicksort partition,控制链又称为动态链，它指向的是调用它的过程的存储空间的起始地址，存取链又称为静态链，它是指向定义它的存储过程的起始地址。 （2）假设该程序的某次执行次序为： sortquicksortquicksortpartitionexchange,建立和执行过程为：主程序（从最外层过程开始）sort开始执行，继而进入过程quicksort ，而又一次进入过程quicksort，接着进入过程partition，进入过程exchange。 如果过程partition中引用了主程序说明的变量a，而partition的直接外层是quicksort，quicksort的直接外层是sort，partition对非局部变量a的引用通过两次拉链实现，执行完一个过程，就将该过程分配的存储单元弹栈。 （3）嵌套层次表display 另外一种存取非局部变量的办法，也是经常使用的有效的办法，即每次进入一个过程后，在建立它的活动记录的同时，建立一张嵌套层次表display。这里所提到的“嵌套层次”，是指过程定义的层数，假定主程序的层数是第0层。如果过程p是第i层，p是在q内定义的，q是包围p的直接外层，那么p 的过程层数是i+1层。一般在编译处理时，将层数作为一个重要的属性登记在符号表中。,display是一个指针数组d，也可以看作是一个小栈。自顶向下每个单元依次存放着现行层，直接外层，直到最外层（0层，主程序层）等每一层过程的最新活动记录的地址。嵌套层次i+1过程中的非局部变量可能在i，i-1，,0层，对它的存取是通过display元素di,di-1,d0获得。 假设现在进入的层数为 i，则它的display表含有i+1个元素，依次指向现行层、直接外层、直到最外层等每一层过程的最新活动记录。 假设有如下的4种调用情况： 1）sortquicksort; 2）sortquicksortquicksort; 3） sortquicksortquicksortpartition 4） sortquicksortquicksortpartitionexchange,display本身的体积在编译时可以确定。至于display本身作为单独的表分配存储，还是作为活动记录的一部分，放在实参的上端，取决于编译程序设计者。假定将 display表作为活动记录的一部分，由于每个过程的形式参数在编译时已经知道，则display的相对地址d（相对于活动记录的起点）在编译时也就完全确定下来。所以，若在现行过程中有了某一外层过程的变量，则很容易生成相应的存取指令。,例题1 在下面的PASCAL程序中，已经第二次（递归地）进入f，请给出f第3次进入后的运行栈及DISPLAY的示意图。 PROGRAM test(input,output) var k:integer; FUNCTION f(n:integer):integer; begin if n=0 then f:=1 else f:=n*f(n-1); end; begin k:=f(10) write(k) end. 【解答】 f第3次进入后的运行栈及DISPLAY的示意图如图9-8所示。,9.3.3分程序结构的存储管理,一个分程序是一个含有它自己的局部数据声明的语句。 在C语言中，一个分程序的语法格式为： 声明 语句 分程序中变量的作用域是声明它的分程序中，即：谁定义谁使用。当分程序中声明的变量和分程序的外层变量出现重名时，遵循“最近有效”的原则。 例如，有如下的分程序结构：,main( ) int a=0; int b=0; int b=1; int a=2; B2 printf(“%d%dn”,a,b); B0 B1 int b=3; B3 printf(“%d%dn”,a,b); printf(“%d%dn”,a,b); printf(“%d%dn”,a,b); ,分程序结构的组织和存储管理也可以采用栈式存储结构。例如ALOGL语言的结构特点是除了允许过程嵌套定义还含有分程序外的结构。例如： procedure Am,n:integer m,n; B1:begin reAl z:array Bm:n B2:begin real d,e; L3; End; B4:begin array C1:m; B5:begin real e; L6; end; end; L8:end;,采用如下方式进行组织和管理。 （1）每个过程的活动记录所含的内容。 1）过程的TOP单元，指向活动记录栈顶位置。 2）.连接数据，共4项：老的TOP、返回地址、全局display表和调用时的栈顶单元地址，称为老的TOP值。 3）参数个数和形式单元 4）display表。 5）分程序的局部变量、数组内情向量和临时工作单元。,（2）分程序结构的数据区的变化图。 下面以过程A的执行过程来分析存储空间的分配。在进入每个分程序时，按照下列原则操作。 每个分程序在进入时，都有它自己的一个TOP单元，刚进入时，都有它自己的一个TOP单元，TOP单元值是有其直接外层分程序的TOP单元的内容赋予。 定义了TOP值后，对该分程序所有的局部数组进行地址分配。每分配一个数组区后，TOP的值就进行调整指向新的栈顶位置。该过程看成是第0层分程序，它通过调用进入，它的TOP值为调用时的栈顶地址加上它的活动记录的长度L，L是在编译时静态计算出来的。 根据上述原则，执行上面的A过程，得到了分程序结构数据区的变化如图9-10所示。当调用A过程时，控制转入A中，但是没有执行过程体，没有到达B1，先分配A的活动记录的空间，当执行到分程序B1时，将B1的TOP和A的TOP指向同一个位置，并为分程序分配B1的变量和内情向量，依次类推，一直执行到B5为止。数组B和数组C的元素放在栈顶。,9.4堆式动态存储分配,如果一种程序语言允许数据对象能够自由地分配和释放，那么只有栈式存储分配就不适应了。在这种情况下，通常使用一种称为堆式动态存储分配方案。假定运行程序有一个大的存储空间，需要时就从这个空间中借用一块。不用时再退还给它。经过一段时间，存储空间就会变成许多小块。 对于堆式存储分配，需要解决两个问题：一是堆空间的分配；另一个问题是堆空间的回收。在许多语言中，都有显式的堆空间分配的分配和回收函数。例如PASCAL语言中的new和dispose。C语言中的alloc和free以及C+语言中的new和delete。,9.5参数传递方式及其实现,定义和调用过程是程序设计语言的主要特征之一。过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言能力的主要途径。一个过程一旦定义后，就可以被调用。调用过程和被调用过程之间交换信息要通过全局量或参数传递。调用过程提供的参数称为实在参数，被调用过程提供的参数称之为形式参数，这些参数的含义在高级程序设计语言中我们已经学习过，这里不再介绍。 9.5.1参数传递的方法 形式参数提供了参数替换的手段，在过程调用时可以使用不同的数据为实参来替换形式参数，从而实现了同一个过程可以对不同的实在参数进行相同操作的功能。那么，如何把实参转换为相应的形式参数？主要有三种方式：传值、传地址和传名。,1传值是最简单的参数传递方法。所谓传值，指计算出实在参数的值，然后把它传递给与被调用过程相对应的形式参数。具体步骤如下： （）把形式参数当作过程的局部变量处理，即在被用过程的活动记录中开辟形式参数的存储空间（即形式单元）。 （）调用过程计算出实在参数的值，并将该值放入形式单元开辟的空间中。 （）被调用过程执行时就像使用局部变量一样使用这些形式单元。 传值的一个重要特点是对形式参数的任何运算都不影响调用过程的活动记录中实在参数的值，即参数传递后实在参数和对应的形式参数不再发生联系了。,传地址,所谓传地址，指把实在参数的地址传递给相应的形式参数所对应的形式单元。如果实在参数是一个变量，则直接将该变量的地址传递给相应的形式单元；如果实在参数是常数或表达式，则先计算其值并存放在某一个临时单元中，然后将这个临时单元的地址传递给相应的形式单元。被调用过程执行时，对形式参数的任何引用或赋值都被处理成对形式单元的间接访问，即将形式单元中存放的地址转到调用过程的活动记录中去访问实在参数。对形式参数的任何运算实际上就是对实在参数的运算，而形式参数只不过起到了一个查找实在参数指针作用。因此，当被调用过程工作完备，形式单元所指的实在参数就保留了运算结果。,传名,所谓传名指高级语言ALGOL60所定义的一种特殊的参数传递方式，其传递参数如下： （）过程调用的作用相当于把被调用过程的过程体复制到调用处，并将过程体中所出现的形式参数在文字上替换成相应的实在参数，称为宏扩展 （）被调用过程中的局部名如果与过程调用的实在参数发生冲突，则在宏扩展前对被调用过程中的这些局部名重新命名以避免重名冲突。 （）为表现实在参数的整体性，必要时在替换前把实在参数用括号括起来。,9.5.2参数传递的示例,以下面程序为例，对3种参数的传递进行比较。 program para; int a,b procedure p(x,y,z) y=y+1; z=z+x; a=2;b=3; p(a+b,a,a); print a (1)传值：用T代表a+b的临时变量，如图9-11（a）所示，动态分析得到a=2； （2）传地址：用T代表a+b的临时变量，分析得到图9-11 (b)所示，动态分析得到a=8；,（3）传名：由于传名时的过程调用就是把过程体抄到调用出现的地方，所以实际执行的程序为： A=2； B=3; A=A+1;/*形参Y换成A*/ A=A+（A+B）/*形参Z换成A，形参X换成(A+B)*/ print A 经分析得到A=9。 不同的参数传递方法得到的结果不同，因此，如何选择参数传递的方法将影响语言的语义，这是编译程序在参数处理时应注意的问题。,（3）传名：由于传名时的过程调用就是把过程体抄到调用出现的地方，所以实际执行的程序为： A=2； B=3; A=A+1;/*形参Y换成A*/ A=A+（A+B）/*形参Z换成A，形参X换成(A+B)*/ print A 经分析得到A=9。 不同的参数传递方法得到的结果不同，因此，如何选择参数传递的方法将影响语言的语义，这是编译程序在参数处理时应注意的问题。,小结,编译程序必须为目标程序的运行分配存储空间。在编译阶段进行的存储空间分配工作称为静态存储分配。静态分配工作一般在词法分析阶段完成，而在运行连接阶段进行的存储空间分配工作称为动态存储分配。 栈式存储分配方法是把整个程序的存储空间都安排在一个栈里，这种方法特别适用于带有嵌套结构的程序设计语言中。 若一个程序设计语言允许用户动态申请和释放存储空间，而且申请和释放之间不一定遵循“后申请先归还”的原则，那么栈式动态分配方案就不适应了。在这种情况下，通常适应堆式存储结构。 数组的存储分配工作借助于信息向量表和数组处理程序来完成。,习 题,一、单项选择题 1动态存储分配可采用的分配方案是 。 A.队列存储分配 B. 栈式存储分配 C.线性存储分配 D.链式存储分配 2静态存储分配允许程序出现 。 A.递归过程 B. 可变体积的数据项目 C.静态变量 D.待定性质的名字 3在C的活动记录中不包含 存储空间。 A.静态变量 B. 自动变量 C.形参变量 D.临时
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号