编译原理学习笔记 7.3 动态存储分配

前言

参考课上PPT内容。 该学习笔记目前仅打算个人使用。
后续会进一步整理，包括添加笔记内容，标明参考资料。

更新中。。。

跳过目录

---

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

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

分配策略是: 整个数据区为一个堆栈
(1) 当进入一个过程时，在栈顶为其分配一个数据区。
(2) 当退出一个过程时，撤消该过程的数据区。

例1:

BBLOCK;
REAL X, Y; STRING NAME;
M1: PBLOCK( INTEGER IND ) ;
INTEGER X;
CALL M2( IND + 1 );
END M1;
M2: PBLOCK( INTEGER J );
BBLOCK;
ARRAY INTEGER F( J );
LOGICAL TEST1;
…
END
END M2;
CALL M1( X / Y )

运行中数据区的分配情况：

活动记录

一个典型的活动记录可以分为三部分：

局部数据区：
存放模块中定义的各个局部变量。
参数区： 存放隐式参数和显式参数。

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

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

ret value ： 函数返回值（无值则空）

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

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

对于例1中所举的程序段，模块4可以引用模块1和模块3中所定义的变量，故在模块4的display区，应包括AR1和AR3的基地址。

变量二元地址（ BL、 ON）
BL：变量声明所在的层次。可以用它找到该层数据区开始地址。
（注意为嵌套层次，并列过程具有相同层次）
ON：相当于显示参数区开始位置的位移（相对地址）。

例：

程序模块1

x(1, 0) 
y(1, 1)
NAME(1, 2)

过程块M1

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

高层（内层）模块可以引用低层（外层）模块中的变量，例如在M1中可引用外层模块中定义的变量 Y。

在 M1 中引用Y时，可通过其 display 区找到程序块 1 的活动记录基地址，加上 Y 在该数据区的相对地址就可以求得 y 的绝对地址。

例：下面给出源程序的目标程序运行时，运行栈（数据区栈）的跟踪情况

e）当模块4执行完，则abp:=prev abp，这样abp恢复到进入模块4时情况，运行栈情况如（ c）。

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

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

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

建造display区的规则

若j＝ i＋ 1

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

若j≤i 即调用外层模块或同层模块

3 运行时的地址计算

假设要访问的变量的二元地址为：（ BL， ON）

• 在LEV层模块中引用BL层模块定义的变量

地址计算公式：

if BL = LEV then
addr := abp + (BL - 1) + nip + ON
else if BL < LEV then
addr := display[BL] + (BL - 1) + nip + ON
else
write(“地址错误，不合法的模块层次” )

(BL - 1) ：display区大小
nip：隐式参数区大小