运行存储分配

存储组织

一个目标程序运行所需的存储空间主要包括代码区、数据区

存储分配策略

• 静态存储分配
  • 在编译时刻就可以确定大小的数据对象，可以在编译时刻就为它们分配存储空间
  • 要尽可能多的将数据对象进行静态分配，因为这些对象的地址可以被编译到目标代码中
• 动态存储分配
  • 对于不能在编译时完全确定数据对象的大小，需要在编译时产生各种必要的信息，而在运行时刻，再动态地分配数据对象的存储空间
  • 栈式存储分配
  • 堆式存储分配

活动记录

使用过程作为用户自定义动作的单元的语言，编译器通常以过程为单位分配存储空间

• 活动：过程体的每次执行称为该过程的一个活动
• 活动记录：过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录（具体实现就是栈帧）

活动记录的一般形式

• 实参（参数压栈）
  • 调用过程提供给被调用过程的参数
• 返回值
  • 被调用过程返回给调用过程的值
• 控制链（old ebp）
  • 指向调用者的活动记录
• 访问链
  • 用来访问存放于其他活动记录中的非局部数据
• 保存的机器状态（返回地址rtn）
  • 通常包括返回地址和一些寄存器中的内容
• 局部数据
  • 在该过程中声明的数据
• 临时变量
  • 比如表达式求值过程中产生的临时变量

静态存储分配

• 编译器为每个过程确定各其活动记录在目标程序中的位置
  • 过程中每个名字的存储位置确定
  • 这些名字的存储地址可以被编译到目标代码中
  • 过程每次执行时，它的名字都绑定到同样的存储单元

适用条件

• 数组上下界必须常数
• 不允许过程的递归调用
• 不允许动态建立数据实体

（BASIC，FORTRAN）

顺序分配法

按照过程出现的先后顺序逐段分配存储空间，各过程的活动记录占用互不相交的存储空间

层次分配法

通过对过程间调用关系进行分析，凡属无相互调用关系的并列过程，尽量使其局部数据共享存储空间

栈式存储分配

当一个过程被调用时，该过程的活动记录被压入栈；当过程结束时，该活动记录被弹出栈

活动树

用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树

• 树中的每个结点对应于一个活动
• 根节点是启动程序执行的main过程的活动（位于栈底）
• 在表示过程p的某个活动的结点上，其子结点对应于被p的这次活动调用的各个过程的活动
  • 按照这些活动被调用的顺序，自左向右地显示它们
  • 一个子结点必须在其右兄弟结点的活动开始之前结束

设计活动记录的一些原则

• 在调用者和被调用者之间传递的值一般被放在被调用者的活动记录的开始位置，这样它们可以尽可能地靠近调用者的活动记录
• 固定长度的项被放置在中间位置
  • 控制链、访问链、机器状态字
• 在早期不知道大小的项被放置在活动记录的尾部
• 栈顶指针寄存器top_sp指向活动记录中局部数据开始的位置，以该位置作为基地址

调用序列和返回序列

过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等

• 调用序列
  • 实现过程调用的代码段，为每一个活动记录在栈中分配空间，并在此记录的字段中填写信息
• 返回序列
  • 恢复机器状态，使得调用过程能够在调用结束之后继续执行
• 一个调用序列中的代码通常被分割到调用过程和被调用过程中。返回序列也是如此

变长数据的存储分配

在编译时刻不能确定大小的对象将被分配在堆区，如果时过程的局部对象，也可以将它们分配在运行时刻栈中。

• 尽量将对象放置在栈区的原因：避免对它们的空间进行垃圾回收，减少开销
• 只有一个数据对象局部于某个过程，且当此过程结束时它变得不可访问，才可以使用栈为这个对象分配空间

非局部数据的访问

一个过程除了可以使用过程自身声明的局部数据以外，还可以使用过程外声明的非局部数据

• 全局数据
• 外围过程定义的数据

无过程嵌套声明的语言

c语言

• 全局变量被分配在静态区，使用静态确定的地址访问它们
• 其他变量一定是栈顶活动的局部变量。可以通过运行时刻栈的top_sp指针访问它们

支持过程嵌套声明的语言

Pascal语言

嵌套深度

• 过程的嵌套深度
  • 不内嵌在任何其他过程中的过程，设其嵌套深度为1
  • 如果一个过程p在一个嵌套深度为i的过程中定义，则其嵌套深度为i+1
• 变量的嵌套深度
  • 将变量声明所在过程的嵌套深度作为该变量的嵌套深度

访问链

• 静态作用域规则
  • 只要过程b的声明嵌套在过程a的声明中，过程b就可以访问过程a中声明的对象
• 可以在相互嵌套的过程的活动记录之间建立一种称为访问链的指针，使得内嵌的过程可以访问外层过程中声明的对象

display表

是一个指针数组d（本质上就是一个邻接表）

• 在任何时刻，d[i]均指向运行栈中最新建立的嵌套深度为i的过程的活动记录
• 如果要访问某个嵌套深度为i的非局部名字x，只要沿着指针d[i]找到x所属过程的活动记录即可

参数传递

传值

Call-by-Value

把实参的值传递给相应的形参

实现方法

• 调用过程把实参的值计算出来，并传递到被调用过程相应的形式单元中
• 在被调用过程中，像引用局部数据一样引用形式参数，直接访问对应的形式单元

传地址

Call-by-Reference

把实参的地址传递给相应的形参

实现方法

• 调用过程把实参的地址传递到被调用过程相应的形式单元中
• 在被调用过程中，对形参的引用或赋值被处理成对形式单元的间接访问

传值结果

Call-by-Value-Result

实现方法

• 每个形参对应两个形式单元
  • 第一个存放实参的地址
  • 第二个存放实参的值
• 在过程体中，对形参的引用或赋值看作对它的第二个形式单元的直接访问
• 过程完成返回前，把第二个单元的内容存放到第一个单元所指的实参单元中

传名

Call-by-Name

相当于把被调用过程的过程体copy到调用出现的地方，但是其中出现的形参都替换成相应的实参。

符号表

符号表用于存放标识符的属性信息的数据结构

• 存储：种属、类型、存储位置、长度、作用域、参数和返回值信息
• 作用：辅助代码生成、一致性检查

主要操作

• 声明语句的翻译：填、查
• 可执行语句的翻译：查

符号表的组织

• 基本属性（直接存放在符号表中）
  • 各种符号均具有的属性，如类型、地址等
• 扩展属性（动态申请内存）— 内情向量
  • 数组：数组的维数、各维的长度
  • 过程：参数个数、参数类型、返回值类型

标识符的基本处理方法

• 当在某一层的声明语句中识别出一个标识符时，依此标识符查相应于本层的符号表
  • 如果查到，报错“id重复声明”
  • 否则，在符号表中加入新登记项，将标识符及有关信息填入
• 当在可执行语句部分扫到标识符时
  • 在该层符号表中查找该id，如果找不到，则到直接外层符号表中去查。一旦找到，则在表中取出有关信息并作相应处理
  • 如果查遍所有外层符号表均未找到该id，则报错“id未声明”