编译原理运行时存储空间组织

《编译原理运行时存储空间组织》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章运行时存储空间组织6.1静态存储分配6.2简单的栈式存储分配6.3嵌套过程语言的栈式实现6.4堆式动态存储分配6.5参数传递补遗6.1静态存储分配如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址，存储空间的这种分配方法叫做静态分配。对FORTRAN语言来说，其特点是不允许过程有递归性，每个数据名所需的存储空间大小都是常量(即不允许含可变体积的数据，如可变数组)，并且所有数据名的性质是完全确定的(不允许出现在运行时再动态确定其性质的名字这种情况)。这些特点确保整个程序所需

2、数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。静态存储分配是一种最简单的存储管理。一般而言，适于静态存储分配的语言必须满足以下条件：(1)数组的上下界必须是常数；(2)过程调用不允许递归；(3)不允许采用动态的数据结构(即在程序运行过程中申请和释放的数据结构)。满足这些条件的语言除了FORTRAN之外，还有BASIC等语言。在这些语言中，编译程序可以完全确定程序中数据项所在的地址(通常为相对于各数据区起始地址的位移量)。由于过程调用不允许递归，因此数据项的存储地址就与过程相联系。过程调用所使用的局部数据区可以直接安排在过程的目标代码之

3、后，并把各数据项的存储地址填入相关的目标代码中，以便在过程运行时访问这个局部数据区。在此，不存在对存储区的再利用问题；目标程序执行时不必进行运行时的存储空间管理，过程的进入和退出变得极为简单。FORTRAN语言的静态存储管理特点是FORTRAN程序中的各程序段均可独立地进行编译。在编译过程中，给程序中的变量或数组分配存储单元的一般做法是：为每一个变量(或数组)确定一个有序的整数对；其中，第一个整数用来指示数据区(局部数据区或公用区)的编号，第二个整数则用来指明该变量(或数组)所对应的存储起始单元相对于其所在数据区起点的位移(即相对于数据区起点的地址)；并将这一对整

4、数填入符号表相应登记项的信息栏中。至于各数据区的起始地址在编译时可暂不确定，待各程序段全部编译完成之后，再由连接装配程序最终确定，并将各程序段的目标代码组装成一个完整的目标程序。一个FORTRAN程序段的局部数据区可由图6–1所示的项目组成。其中，隐参数是指过程调用时的连接信息(不在源程序中明显出现)，如调用时的返回地址、调用时寄存器的保护等；形式单元用来存放过程调用时形参与实参结合的实参地址或值。图6–1一个FORTRAN程序段的局部数据区6.2简单的栈式存储分配我们首先考虑一种简单程序语言的实现，这种语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用

5、，允许过程含有可变数组。例如，C语言除不允许含有可变数组外，就是这样一种语言。C语言的程序结构如下：全局数据说明main( ){main中的数据说明}voidR( ){R中的数据说明}voidQ(){Q中的数据说明}例如，下面计算n！的C语言程序就是一个递归调用的程序，它的执行过程可以用栈来实现。#include“stdio.h”longfactorial(intn){if(n>1)return(n*factorial(n−1));elsereturn(1);}main( ){intnum;do{scanf(“%d”,&num);if(num>=0&&num<15

6、)printf(“%d”,factorial(num));elseprintf(“error!”);}while(num>=0);}6.2.1栈式存储分配与活动记录使用栈式存储分配法意味着程序运行时，每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶，此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等；在进入过程和执行过程的可执行语句之前，再把局部数组所需空间累筑于栈顶，从而形成过程工作时的完整数据区。注意，每个过程的活动记录的体积在编译时可以静态地确定。但由于允许含有可变数组，所以数组的大小只有在运行时才能知道。因数组区的

7、大小不能预先获知，为了扩充方便，所以只能将数组区累筑于活动记录之上的当前栈顶。当一个过程工作完毕返回时，它在栈顶的数据区(包括活动记录和数组区)也随即不复存在。对C语言来说，由于其不含可变数组，因而它的活动记录本身包含了局部数组的空间。图6–2和图6–3分别给出了C语言和含可变数组的某简单语言程序运行时的数据空间结构，即显示了主程序在调用了过程Q，Q又调用了过程R，且在R投入运行后的存储结构。SP指示器总是指向执行过程活动记录的起点，而TOP指示器则始终指向(已占用)栈顶单元。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端；在分配数组区之后(如果有的话)

8、，TOP又