编译原理教程_9 运行时存储组织

Myth丶恋晨 2023-01-21 11:18 14阅读 0赞

> 文章原稿  
> https://gitee.com/fakerlove/fundamentals-of-compiling

### 文章目录 ###

*  9. 运行时存储组织
 *   *  9.1 概述
     *  9.2 静态存储分配
     *  9.3 动态存储分配
     *   *  9.3.1 活动记录
         *  9.3.2 建造display区的规则
         *  9.3.3 运行时的地址计算

# 9. 运行时存储组织 #

![bdac40b54b2fe9400e5fafcc79410d72.png][]

## 9.1 概述 ##

运行时的存储组织及管理是目标程序**运行时**所需要存储空间的组织与管理以及源程序中**变量存储空间的分配**。

**静态存储分配**

在**编译阶段**由**编译程序**实现对存储空间的管理，和为源程序中的变量分配存储的方法。

条件：如果在**编译时能够确定**源程序中变量在运行时的数据空间大小，且运行时**不改变**

但并不是所有数据空间大小都能在编译过程中确定！

**动态存储分配**

在目标程序**运行阶段**由**目标程序**实现对存储空间的组织与管理，和为源程序中的变量分配存储的方法。

特点：在目标程序运行时进行分配；编译时要生成进行动态分配的目标指令。

## 9.2 静态存储分配 ##

（1）**分配策略**

由于每个变量所需空间的大小在编译时已知，因此可以用简单的方法给变量分配目标地址。

具体步骤：

*  开辟一数据区。(首地址在加载时确定)
 *  按编译顺序给每个模块分配存储。
 *  在模块内部按顺序给模块的变量分配存储，一般用相对地址，所占数据区的大小由变量类型确定。
 *  目标地址填入变量的符号表中。

这种分配策略要求语言**不允许指针或动态分配，不允许递归调用过程**（如果递归调用，就相当于又多加了一个函数，又需要分配存储空间了）。典型的例子是Fortran77

![img][]

（2）模块（fortran子程序）的完整数据区

子程序需要在数据区中保留**返回地址**，形参也要分配存储以存放相应的实参信息。编译时还要分配临时变量空间（用于存放表达式计算的中间结果等）

FORTRAN子程序的典型数据区：

![img][img 1]

## 9.3 动态存储分配 ##

由于编译时还不能具体确定某些数据空间的大小，故对它们分配存储空间必须在程序运行时进行。这时，**编译程序生成有关存储分配的目标代码**，**实际上的分配要在目标程序运行时进行**。这种分配方式称为动态存储分配。

对于分程序结构，而且允许递归调用的语言，常使用**栈式动态存储分配**，即使用一个类似于堆栈的“运行栈”来实现数据区的分配。

**分配策略**

整个数据区为一个堆栈

1.  当进入一个过程时，在栈顶为其分配一个数据区。
2.  当退出一个过程时，撤消该过程的数据区。

![img][img 2] ![img][img 3]

### 9.3.1 活动记录 ###

一个典型的活动记录可以分为三部分：![img][img 4]

（1）局部数据区：存放模块中定义的各个局部变量

（2）参数区：存放隐式参数（不出现在用户源程序中）和显式参数（出现在用户源程序中）。

![img][img 5]

形参数据区:每一形参都要分配数据空间，形参单元中存放**实参值或者实参地址**。

prev abp:存放调用模块记录**基地址**。该函数执行完时，释放其数据区，数据区指针指向调用前的位置。

ret addr:返回地址，即调用语句的**下一条执行指令地址**。

ret value :函数返回值(无值则空)，比如void函数，就是空的。

（3）display区：存放各外层模块活动记录的基地址。

![img][img 6]

变量二元地址（BL、ON）

BL：变量声明所在的层次，可以用它找到该层数据区开始地址。此为嵌套层次，并列过程具有相同的层次。

ON：相对于**显式参数区**开始位置的位移（相对地址）。

例如：

程序模块1:

x（1,0） x在第一层中被声明，在显式参数区开始的位置是0；

y（1，1） NAME（1，2）

过程块M1:

IND（2，0） x（2，1）

注意⚠️：**高层(内层)模块可以引用低层(外层)** 模块中的变量，例如**在M1中可引用外层模块中定义的变量 Y。**  
在 M1 中引用Y时，可通过其 display 区找到程序块 1 的活动记录基地址，加上 Y 在该数据区的相对地址就可以求得 y 的绝对地址，具体如何引用将在后面提到。

![img][img 7]\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MdXrPZcg-1621079380807)(picture/20201121213704.png)\]

以下是运行栈的跟踪情况：

![img][img 8]

![image-20201121213800089][]

![img][img 9]

![img][img 10]

因此可以画出完整的运行栈图：

![img][img 11] \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5YzMqIf1-1621079380813)(picture/20201121214111.png)\]

(f)当M2执行完，则abp:=prev abp，这样abp恢复到进入模块M2时情况，运行栈情况如(b)。

(g)当M1执行完，则abp:=prev abp，这样abp恢复到进入模块M1时情况，运行栈情况如(a)。

(h)当最外层模块执行完，运行栈恢复到进入模块时的情况，运行栈空。

### 9.3.2 建造display区的规则 ###

从i层模块进入（调用）j层模块：

（1）若j=i+1

![image-20201121214318955][]

复制i层的display，然后增加一个指向i层模块记录基地址的指针

![img][img 12]

![img][img 13]（第j层模块的display）

（2）若j<=i ,即调用外层模块或同层模块

![img][img 14]

将i层模块的display区中的前面第j-1个复制到第j层模块的display区

![img][img 15]

若发生了j>=i+2的情况，例如图中，i想要调用模块k

![img][img 16]

在这种情况是不行的，因为k的生命周期在j里面。当j执行完后到CALL k后，j（k的外层）生命周期已完结，不能直接调用k。

如果举一个特例的话，如果k中要调用j的变量，如果i直接调用k，那么k将会找不到来自外层的j的变量。

### 9.3.3 运行时的地址计算 ###

假设要访问的变量的二元地址为:(BL，ON) ，要在LEV层模块中引用BL层模块定义的变量。

![img][img 17]

如：

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VXUDUreR-1621079380821)(picture/20201121214054.png)\]

在abp（3）引用IND（2，0），会将abp设为display（2），即abp（2），加上display区大小BL-1=1，再加上隐式参数区大小nip=2，与偏移量0，即使IND的地址。

[bdac40b54b2fe9400e5fafcc79410d72.png]: /images/20221020/8d7ced5269fa45cda52d226a3e30979d.png
[img]: /images/20221020/fdadbf8324d749668e0415af3749d4a0.png
[img 1]: /images/20221020/ac65036aa4d7429085e17495df567595.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/99f2a2fa59920229ed8330fc1f946ded.png
[img 3]: /images/20221020/8a735358b98f44a4861295ba4430c608.png
[img 4]: /images/20221020/5dfb45828ef64df69f9964bdd6235b12.png
[img 5]: /images/20221020/4f4066b0b2514d469de08d44f05a0090.png
[img 6]: /images/20221020/381275da852f498da47dd9d18372ac61.png
[img 7]: https://img-blog.csdnimg.cn/img_convert/0ed1967daf8ea820e9a9f588b5135135.png
[img 8]: /images/20221020/4681c8f4320249d18cdb577d422a0ca0.png
[image-20201121213800089]: /images/20221020/e460aa23a341480b8a955ad2ee934e95.png
[img 9]: /images/20221020/5f91b6452fec4a12a7cbd075d7e19457.png
[img 10]: /images/20221020/4c469645299444adaaa0997420359524.png
[img 11]: https://img-blog.csdnimg.cn/img_convert/ed220b756ee52b819064141921aece33.png
[image-20201121214318955]: /images/20221020/b1df2b71cc714bb99f803d2d095d0f95.png
[img 12]: /images/20221020/d6850bf6be5841b399f88ad7b5fe4e91.png
[img 13]: /images/20221020/75afed835f6f4085bf65a91992cff2ae.png
[img 14]: /images/20221020/4d293482c2b7473694f286c115ffaf59.png
[img 15]: /images/20221020/be8ce8b3a565421b986452786a082133.png
[img 16]: /images/20221020/d9810a255dca4e73a35a840a9830ba1d.png
[img 17]: /images/20221020/c179ead9c29b4c829c4e35ac6598c2af.png