第 8 章运行时环境

8.1. 概述

运行时环境包含

运行时刻存储空间的管理策略
- 静态
- 栈式
- 堆策略
符号表管理
- 除了编译过程中需要外，有些符号表信息会保存到运行时，如程序的 DEBUG 版本
垃圾回收策略
运行支持库

符号表是编译过程中访问最频繁的操作区域。在词法分析阶段，当遇到一个标识符时，会把标识符的名字登记到符号表，当标识符所关联的语法信息有了明确的定义或说明后，就要在符号表中新增加一个条目（或更改一个条目），将该标识符及其相关的语法信息全部登记到符号表中。

运行时存储空间的管理策略是运行时环境的核心任务之一。

8.2. 符号表

8.2.1. 符号表的结构

	名字	类型	种类	大小	地址偏移
第一项入口	a	int	VAR	4	0
第二项入口	f1	float	VAR	8	4
第三项入口	pa	pointer(int)	VAR	4	12

名字栏是符号表的主栏，查找等操作通常是按名字进行的。由于程序中标识符的名字长短不一，因此通常对名字采取一种间接的方式：专门开辟一个存储区域存放长短不一的名字，然后用一对 $\displaystyle{ \left( x , y \right) }$ 指明名字的位置和长度。

符号表的种类多，常见有：常量表、变量表、标号表、函数名表、数组内情向量子表等。

8.2.2. 符号表的管理

符号表管理涉及到符号表的操作，是对带有作用域名字的符号表的组织和管理。为提高访问符号表的效率，可以针对名字设计一个 Hash 函数，将名字映射到符号表的入口项。

8.2.3. C 语言中的符号表

C 语言符号表是一中典型的栈式符号表组织结构。函数中的变量不仅是局限于函数的，而且是局限于语句块的。

void func()
{
    int i = 0;
    {
        int i = 1;  // 与外部的 i 是两个不同的 i
    }
}

为了反映这种嵌套的变量的作用域，使用栈式符号表进行组织管理。

每个函数都有自己的一张符号表（也可以将所有函数符号表集中在一张大表中管理）使用一个栈 tblptr 来保存当前处于编译状态的函数的符号表。由于 C 语言中一个函数内部不能再定义另一个函数，因此 tblptr 栈通常只有两个元素。

栈顶元素是当前正在处理的函数符号表的指针
栈底元素指向保存在函数外部定义的全局变量或其他函数名字等信息的符号表，即全局符号表

每个函数的符号表都是一个栈，称为栈式符号表。每当编译到一个新的名字，从栈顶向符号表填写。查找时从栈顶向栈底查找。每进入一个新的作用域，则向栈中加入一个间隔。

void f(int x, int y, int z)  // 1
{
    int i = 1;  // 2
    {
        int j = 2;  // 3
        i = i + j;
        {
            int k = 3;  // 4
            i = i + j + k;
        }
        int m = 3;  // 5
    }
    printf("%d\n", i);  // 6
}

如果不知道怎么画，那就对照着程序照着画一遍

8.3. 存储分配策略

8.3.1. 静态存储分配策略

C 语言中有全局变量及 static 局部变量，这些变量在编译时都已知道，而且永远只有一份。具有该特性的变量可以采用静态存储分配策略。

程序运行时，在内存中有一片数据区域，所有的 static 局部变量和所有全局变量集中存储在一起，它们共同构成了程序的静态存储区。

须满足的条件

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

8.3.2. 栈式存储分配策略

对于函数内部的非 static 局部变量采用栈式存储分配策略。C 语言程序中可以直接或间接递归调用，函数中的一个局部变量可能出现多个实例。每递归调用一次都会创建一个局部变量的实例。

C 语言编译程序采用函数的活动记录来实现函数的调用，并在活动记录中实现局部变量空间的分配，活动记录是存在栈中的。

8.3.3. 堆式存储分配策略

C 语言支持指针变量。指针变量所指的空间的大小与位置，有时只有在程序运行时刻才能知道。我们使用 malloc 和 free 来动态的分配和释放空间。

8.4. 存储空间的组织

8.4.1. 运行时内存空间的划分

代码区
静态数据区
栈
↓
…
↑
堆

8.4.2. 函数与活动记录

函数每次调用执行，都会在内存中创建函数内部的局部变量。我们将函数的一次调用执行，称为一个活动。从函数的第一条指令执行到函数的最后一条指令为止，这个过程称为函数的一次活动的生存周期。

两个函数的生存周期，要么是不重叠的，要么是嵌套包含的，不可能是相互交叉的。

函数的一次活动，需要使用许多数据，如接收实参、局部变量空间分配、运行时临时变量等，为了管理函数的活动，也需要一些重要的数据。管理函数的活动所需要的全部信息，称为函数的活动记录。

活动记录包含了管理活动及活动本身运行所需的信息（如实参、局部变量等）。当活动开始时创建活动记录，当活动结束时撤销活动记录，这符合栈的特点。因此活动记录的空间是在栈中分配的。

8.6. C 语言的存储分配

8.6.1. C 语言的活动记录结构

1. C 语言函数调用语句的目标代码

对于过程 p(x, y, z) 生成代码为

param z
param y
param x
call p, 3

设有函数 f

void f(int x, int y, int z) {
    int s = 0;
    s = x + y + z;
    {
        int k = 1;
        s = s + k;
    }
    printf("S=%d\n", s);
}

则调用 f(1, 2, 3) 会产生以下的目标代码

mov     ax, 3
push    ax     ; 3 入栈
mov     ax, 2
push    ax     ; 2 入栈
mov     ax, 1
push    ax     ; 1 入栈
call    f

2. 调用返回到调用者时调用者代码

调用者负责将实参压栈，因此也由调用者负责将实参出栈，只有调用者才知道真实入栈的实参个数。

当调用返回时，即 f(1, 2, 3) 执行完成返回 main 时，main 紧接着的出栈代码是

add     sp, 6  ; 设 int 占 2 字节，3 个实参一共 6 字节

3. 访问形参局部变量

在上述函数 f 调用后，通过上表关于新 BP 的相对地址即可访问局部变量。要获取形参 y 对应的实参值，可通过 word ptr[BP+6] 完成。

word ptr 的含义是将 [BP+6] 处的内容按 word 2 字节进行访问。

动态链表 BP 的作用是，设变量 x 的偏移量是 offset，则用 [BP+offset] 来访问局部变量。

例设有程序

int sum(int n) {
    int s = 0;
    if (n == 0)
        s = 0;
    else
        s = n + sum(n - 1);
}
void main() {
    int s = 0;
    s = sum(10);
    printf("1+2+...+10=%d\n", s);
}

8.6.2. 入口指令的自动生成

在上面两表中，返回地址及实参都是由调用者完成的，那么动态链表 BP 及局部变量的空间分配是如何完成的？

它们是由被调用者函数的入口代码完成的。入口代码的任务是，建立起活动记录的动态链表，并为局部变量分配空间。

入口代码即编译器直接插入到用户的函数体代码之前。

对于 void f(int x, int y, int z) 其入口代码为

push bp      ; 老 BP 入栈。调用者的动态链表保存起来，以后由出口代码恢复
mov  bp, sp  ; 建立自己的活动记录的基地址，通过 BP 访问自己的局部变量
sub  sp, 4   ; 将栈顶指针减 4 字节，为局部变量 s 和 k 分配空间

8.6.3. 出口指令的自动生成

函数的出口代码由编译器直接插入到用户的函数体代码之后（在 ret 指令之前）。出口代码的任务是，恢复调用者的动态链表。

对于函数 f 其出口指令为

mov  sp, bp  ; 将 BP 赋给栈顶指针 SP，使得 SP 指向老的 BP
pop  bp      ; 出栈，自动将老 BP 赋给 BP 寄存器，从而恢复调用者 BP

8.7. 垃圾回收机制

C 语言指针变量所指向的空间，通过堆式存储管理进行分配与回收。

自动垃圾回收机制不需要程序员明确释放指针所指向的空间，由垃圾回收机制自动回收，减轻程序员的负担，并增加程序的健壮性，降低由于内存泄漏而造成的程序崩溃概率。

8.8. 运行库管理

目标程序运行时，需要运行库的支持。编译程序将通用的、经常出现的函数或过程预先编译成运行库，作为编译程序的一部分。我们在程序设计时可以直接调用它们。

一般地，运行库都是以二进制目标代码形式提供，用户程序编译完成后，通过 link 程序与用到的运行库连接在一起运行。

8.9. 连接程序与装配程序

通常，编译程序生成的目标程序是可重定位的。程序调用的库函数中的函数，在目标程序中只是一个符号的引用，并不是真正的函数的目标代码。

当使用连接程序时，将把调用函数的符号引用转换成在库中找到的所调用函数的真正代码，并连接到程序代码中，成为代码的一个组成部分。这种连接方式称为静态连接。

静态连接会加大目标程序的代码体积，现在更多采用的是动态连接。即要调用的函数代码并不连接到程序代码中，而是在调用处生成一个调用链接库中某个函数的调用指令。当程序运行到此处时，系统再将动态链接库装入内存，转入调用那个函数。

由链接程序生成的可重定位的执行程序，其中变量地址一般都是相对地址（由编译程序生成的可重定位属性来标记）。通过装配程序，将目标程序装入到内存的某一区域，这时装配程序每次读入一行代码，将它复制到目标内存区域，并根据重定位属性将指令中所有的相对成分都加上一个常数即可。

第 8 章 运行时环境