编译原理：第九章 运行时存储空间组织

一、概述

静态分配策略：

编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变

栈式存储分配：

运行时把存储器作为一个栈进行管理，每当调用一个过程，它所需的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。

堆式存储分配：

在运行时把存储器组织为堆，允许用户动态申请和归还存储空间，凡申请者从堆中分给一块，凡释放者退回给堆。

二、栈式存储分配的实现

2.1 活动举例

float fac(int n){
    float f;
    if (n==0) f=1;
    else f=n*fac(n-1);
    return f;
}
void main( ){
    int i=2;
    printf(“%f”,fac(i));
} 

执行时过程调用的顺序：

2.2 一些定义

2.2.1 活动

一个过程的活动：是指该过程的一次执行，每次执行一个过程体，产生该过程体的一个活动

一个活动的生存期：是指从该过程体的第一步操作到最后一步操作之间的操作序，包括执行该过程时调用其它过程花费的时间

名字说明作用域：一个说明在程序里能起作用的范围

2.2.2 活动记录（AR）

含义：存储管理过程活动所 需信息的一块连续的存储空间

作用：当调用过程时，将在栈顶为过程此次活动分配活动记录

SP 指向现行过程（即最新进入工作的那个过程)的活动记录在栈里的首地址，用于访问局部数据。

2.3 简单栈式存储分配举例

对语言的限制：没有分程序结构、过程定义不许嵌套、允许过程的递归调用

全局数据说明
main（）
{ main中的数据说明
  …Q();…}
void R()
{ R中的数据说明
  …}
void Q()
{ Q中的数据说明
  …R();…}

2.4 嵌套过程语言的栈式实现

对语言的限制：允许嵌套定义、允许递归调用

program P；
var a,x:integer；
    -----------------------------Q
    procedure Q(b:integer);
    var i:integer;
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%R
        procedure R(u:integer;var v:integer);
        var c,d:integer;
        begin … if u=l then R(u+1,v)Q // R调用R
              v:=(a+c)*(b-d); …
        end {R}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%R  
    begin … R(1,x);… end {Q} // Q调用R
    ------------------------------Q
    *******************************S
    procedure S;
    var c,i:integer; 
    begin a:=1;Q(c);… end {S}  //S调用Q
    *******************************S
begin a:=0;S;… end {P} // P调用S

执行顺序：P->S->Q->R->R(递归)

活动记录：

静态链举例：

主程序的静态链结点值为主程序AR的首地址SP。

存在问题：当过程的嵌套层数过多时，沿静态链要经过若干结点才可找所需的非局部量

2.5 display表

2.5.1 定义

为解决嵌套层数多时寻找效率低的问题，引入display表（过程嵌套层次显示表）的概念。

注意：c 、a 这些变量的所在层次以及偏移量（相对数）都在词法分析时存在符号表中，可以直接查询。

之所以要记录每一层的最新AR首地址，是因为，同一层的某个局部变量可能会被改变，只有最新的活动记录中的才是当前值。

2.5.2 实现

主要有两种方式，外置display表和内嵌display表。

内嵌display表：放入AR中，作为AR的一部分。

注意：主程序无 全局display ,其display表占用AR中 全局display 的位置,值为0(主程序AR首地址SP)

例： 现行过程中引用k层变量x，可用以下两条指令获得：

LD R1,(d+k)[SP] 获得k层AR首地址。

原理：首先获取当前AR中display的地址d，那么第k层AR首地址为d+k，加上基地址[sp] 就是第k层AR首地址。

LD R2,x[R1] 把x值传递给R2。

2.5.3 举例

动态链： 调用者活动记录首地址，即栈中上一个活动记录首地址。

静态链： 直接外层最新AR的首地址（这里由于display表的存在，所以填全局display）。

全局display： 调用者活动记录 display表的首地址。

display表： 存放每一层最新活动记录的首地址 ，先获取调用者的活动记录display表，在此基础上进行更新，如果当前活动记录在第 i 层，则display有 i+1 层。

• P活动记录：
  • 编号1：存动态链，由于是第一个活动记录，所以填0
  • 编号2：返回地址
  • 编号3：全局display，由于是主程序的活动记录，没有全局display，该位置填写display表，只有一项，即第0层活动记录首地址0。
  • 编号4-5 ：当前活动记录的局部变量
• S活动记录：
  • 编号5：动态链，上一个活动记录首地址，即P首地址 0 。
  • 编号6：返回地址
  • 编号7：全局display，填写调用者的display表地址，即P的display表地址0
  • 编号9-10：S的display表，先调用P的display表，再更新，包括第0层和第1层最新活动记录首地址（0和5）
• Q活动记录：
  • 编号13：动态链，填调用者活动记录首地址5。
  • 编号15：全局display，填调用者display表首地址9。
  • 编号16：填形参个数
  • 编号17：填具体形参
  • 编号18-19：Q的display表，先调用调用者S的display表，再进行更新，内容为每一层的最新活动记录首地址（0和13），因为第1层最新活动为Q自身，活动变量首地址为13。
• R1活动记录：
  • 编号21：动态链，调用者Q活动变量首地址13。
  • 编号23：全局display，填调用者Q的display表首地址18。
  • 编号27-29：R1的display表，先获得Q的display表，再更新，由于R1在第2层，所以display表为0、13、21。
• 后面同上。