哈工大编译原理 | 7.运行时存储分配

发布于：2025-05-29 ⋅ 阅读:(18) ⋅ 点赞:(0)

运行时存储分配

视频地址：哈工大编译原理（最新精讲版）

文章目录


image-20250509194112941

基本知识

活动记录

image-20250509194430717

活动记录：在程序运行时为每个过程或函数调用分配的内存区域，用来保存该调用期间所需的各种信息。其实就是函数栈帧

编译器通常以过程为单位分配存储空间。过程执行一次，编译器就为它分配一块连续存储区，这就是活动记录

活动记录的一般形式

image-20250509195034564

  • 控制链：指向调用者的活动记录，用于恢复上一个活动记录的环境
  • 访问链：指向定义当前过程的直接外围函数的活动记录。在支持嵌套函数的语言中（函数内部还能定义函数），内层函数可以访问外层函数的局部变量。这些外层变量在运行时并不在当前函数的活动记录中，而是在外围函数的栈帧中，编译器需要用访问链来访问这些外层变量

存储分配策略

image-20250509200826316

编译器为每个数据对象分配地址（偏移量），并生成访问该地址的指令。它会为每个数据对象选择合适的存储分配策略。例如，一个函数内定义的局部变量，编译器会知道其生命周期短、只在函数调用期间有效，于是选择 栈分配。如果是 malloc 或 new 创建的对象，则编译器会插入堆分配的运行库调用

存储分配策略分为两类：

  • 静态存储分配：在编译时刻为数据对象分配存储空间
  • 动态存储分配：在运行时刻为数据对象分配空间，在编译时仅产生各种必要的信息

静态存储分配通常用于全局变量、静态变量、常量等，它们通常存放在数据段、BSS段中。静态分配的变量在程序整个生命周期内都会存在，它们的内存地址在编译时就被确定并且保持不变

动态存储分配通常用于局部变量、动态数据结构，它们通常被存放在栈上（局部变量）或 堆上（动态数据结构）。动态分配的变量的地址在运行时刻可以改变，由程序需求动态分配内存

静态存储分配

image-20250509202748790

这里说的是，如果一个语言满足这些条件，则它可以只使用静态存储分配策略 就能完成运行时存储分配，然而更多情况下，我们需要结合静态存储分配和动态存储分配策略

栈式存储分配

image-20250509203554611

动态存储分配分为两类：

  • 栈式存储分配：当一个过程被调用时，编译器会将该过程的活动记录压入栈中。当过程执行完毕并返回时，对应的活动记录会被从栈中弹出。编译器通过生成指令，在调用函数（例如call a）之前，使用push将相关信息压入栈中，并在a函数返回之前，通过调整栈指针（sp）来释放该函数的栈帧，最终通过ret指令完成返回操作
  • 堆式存储分配：显式地调用malloc，在堆上寻找一个空间用于分配。编译器通过生成call malloc这样的指令来实现堆式存储分配

这里主要研究栈式存储分配

活动树

image-20250510112758449

  • 活动 是对一个过程的一次具体调用，是运行时的一个实例

  • 过程 只是一段可以被调用的代码，是静态的（有点像进程和程序的定义）

活动树中的每个节点表示一次过程的活动。若节点 p 表示某个过程的活动，那么 p 的子节点表示在该活动期间被调用的各个过程的活动，并按照它们的调用顺序从左到右排列

根节点通常对应主过程main。在程序运行过程中，兄弟节点所代表的活动不会同时处于活跃状态，即它们的活动记录不会同时位于控制栈中

例子

以快速排序程序的活动树为例

image-20250510113353430

main依次调用了readArray()和quicksort(1, 9)，在活动树中，根节点main的孩子节点 从左到右为：readArray和quicksort(1, 9)

控制栈保存了当前活跃的所有活动记录，按照调用顺序从栈底到栈顶，依次对应活动树中从根节点到当前活动节点的一条路径上的各个活动

image-20250510113909508

当前的调用链：main -> q(1, 9) -> q(1, 3) -> p(1, 3)。可以看到，控制栈中保存了这些过程的活动记录

image-20250510114518305

实际上，控制栈中保存的是对活动树的后序遍历的结果：只有节点的所有子节点都访问完了，这个节点的活动记录才出栈。后序遍历的栈中，各个节点可以组成一条从根节点到当前节点的路径，因此 控制栈中全部活动记录的序列 对应于 在活动树中从根节点到达当前活动节点的路径，也就是当前的调用链

活动记录

image-20250510115003887

活动记录的设计有以下特点：

  • 栈指针 top_sp 通常指向当前活动记录中局部变量区域的开始位置，而不是整个栈的顶端。这么做是为了以 top_sp 为基地址，配合符号表中记录的偏移量 offset来访问局部变量
  • 调用者与被调用者之间传递的参数和返回值，统一放置在被调用者活动记录的起始位置。这样调用者在调用前可以将实参压入栈顶，而被调用者也能从栈顶附近读取参数。同时，调用者也能在调用结束后从相同区域获取返回值
  • **控制链、访问链和保存的机器状态（调用者栈顶、返回地址、部分寄存器的值）**被放置在活动记录的中间部分。这些内容大小固定，是过程调用管理所必须的，用于支持嵌套调用与过程返回

其实就是函数栈帧的结构

img

有些地方不太一样（返回地址放置在活动记录的中间），但是基本内容都是相同的

调用序列和返回序列

image-20250510120215170

  • 调用序列

    image-20250510120338536

    实现过程调用的代码段。调用序列由调用者和被调用者分别执行，共同完成活动记录的分配和字段的填写：

    • 调用者压入参数的值，将返回地址存放到机器状态字段中，将原栈顶指针top_sp的值存放到控制链字段中，对于嵌套调用的语言，调用者还会填写访问链字段。之后，调用者增加top_sp的值，使它指向被调用者局部数据开始的位置
    • 被调用者将部分寄存器值（被调用者保存寄存器）和其它状态信息 存放到 机器状态字段中，然后初始化其局部数据并开始执行

  • 返回序列

    image-20250510120801498

    实现过程返回的代码。同样地，返回序列由调用者和被调用者分别执行，完成返回值的传输，返回到调用者，恢复上下文

    • 被调用者将返回值放置到返回值字段处，然后恢复top_sp和其它寄存器，接着跳转到返回地址处，回到调用者
    • 调用者可以通过返回值 相对于top_sp的偏移量 来使用返回值

image-20250510121540020

  • 对于参数和返回值，调用者填写参数，被调用者填写返回值
  • 对于保存的机器状态，调用者填写返回地址，被调用者填写部分寄存器的值（被调用者保存寄存器）和其它状态
  • top_sp由调用者保存到控制链字段中，然后更新；被调用者从控制链字段中读取原top_sp的值并恢复

变长数据的存储分配

image-20250510122011944

对于只局部于某个过程，且当此过程结束时变得不可访问的变长数据对象，可以使用栈为它分配空间。链表就不满足条件，仍要分配到堆上。这里我们认为动态数组满足这个条件，可以在控制栈中为它分配空间

image-20250510122303390

活动p定义了动态数组a、b、c。由于动态数组的大小只能在运行时确定，因此在p的活动记录中，我们只存放了指向a、b、c的指针，而不直接为数组分配空间。程序运行时，在控制栈中为数组a、b、c分配空间

注意到，p的活动记录中不包含这些数组的实际内存空间，而是通过指针来访问各个数组。可以从符号表中获得数组的基地址并赋给各个指针

非局部数据的访问

image-20250510145958845

对于允许嵌套函数定义的语言，例如Pascal，对于一个函数，它的变量访问权限和函数调用权限：

  • 变量的访问权限

    一个过程可以访问它自己内部定义的变量，可以访问所有外层过程的变量（直接外层、间接外层、全局变量），但是不能访问它的内层函数定义的变量（内层作用域对上层不可见）

  • 函数调用权限

    一个函数可以调用它的直接内层函数，可以调用所有外层函数（包括直接外层、间接外层、全局函数），可以调用同一作用域的兄弟函数

举个例子

image-20250510151754682

这个例子中，

  • sort的深度为1

  • readarray、exchange、quicksort的深度为2，是sort的直接内层函数。它们都使用了sort中定义的a

  • partition的深度为3，是quicksort的直接内层函数。它调用了exchange函数，并且使用了sort中定义的a和quicksort中定义的v

可以看到，sort函数不能直接调用partition函数，它只能通过调用quicksort实现间接调用。同时，外层过程也不能使用内层过程中定义的变量

image-20250510153007398

我们主要关注嵌套函数定义语言中数据对象的访问。无论是访问链还是display表，它们都是用于访问非局部数据的

访问链

访问链被称为静态链，是相对于控制链而言的，控制链也被称为动态链。原因如下：

  • 控制链与函数的调用动态关系密切相关，其变化依赖于程序的执行流程和控制流。随着函数的调用和返回，控制链会动态地调整。
  • 访问链的设置基于嵌套的结构，并且在编译时就可以确定。编译器能够分析每个函数的嵌套深度，在程序运行时，每个活动记录的访问链都指向直接外层函数的活动记录。这一关系不受函数调用情况或控制流的影响，因此它在运行时是静态不变的
访问链的建立

image-20250510154022021

一个活动记录的访问链 总是指向 它的直接外层过程的活动记录，具体来说，访问链指向的是 活动记录中局部数据开始的位置。注意到，这与函数调用是两回事，调用者不一定是被调用者的直接外层过程。我们可以从程序代码中获得各个过程的直接外层过程和嵌套深度，根据嵌套深度表来建立访问链

访问链的建立方法

调用序列中包含了 建立访问链 的代码

  1. 首先，在编译时，编译器通过解析程序代码，建立了嵌套深度表，记录了各个过程和对应的嵌套深度

    image-20250510154419633

  2. 在程序运行时，结合嵌套深度表，按照以下的规则来建立访问链：假设嵌套深度为nx的过程x调用嵌套深度为ny的过程y（x->y）

    • nx < ny

      image-20250510154648290

      按照调用权限，一定是过程x调用它的直接内层过程y，例如quicksort调用partition函数。此时，只需要在y的访问链中放置一个指向x的活动记录的指针

      例如，sort调用了它的直接内层过程readArray，则readArray的访问链 指向 sort的活动记录：

      image-20250510155613330

    • nx = ny

      image-20250510155752165

      一个函数可以调用与它在同一个作用域下定义的兄弟函数，它们的活动记录的访问链会指向同一个直接外层过程的活动记录。因此，被调用者的活动记录的访问链与调用者的活动记录的访问链是相同的，被调用者的访问链可以直接复制调用者的访问链

      例如，quicksort递归调用自己，可以直接将前一个quicksort活动记录的访问链 复制给 后一个quicksort，它们都是指向sort的活动记录：

      image-20250510160858449

    • nx > ny

      image-20250510164001979

      内层过程x调用了外层过程y。由函数调用权限，调用者x必定嵌套在某个过程z中，而z中直接定义了被调用者y。因此，从x的活动记录开始，沿着访问链经过nx - ny + 1步可以找到离栈顶最近的z的活动记录，y的访问链指向这个活动记录

      例如，深度为3的partition函数调用了深度为2的exchange函数。partition嵌套在sort中，而sort直接定义了exchange，因此需要从partition的访问链开始，经过 3 - 2 + 1 = 2步后，到达sort的活动记录，令exchange指向这个活动记录

      image-20250510163920775

display表

image-20250510164025519

访问链方法需要为每个活动记录都设置访问链字段，当需要寻找某个外部过程声明的变量时（不一定是直接外层过程），需要沿着访问链来回寻找，效率很低

display表 是一个指针数组d，d[i]指向运行栈中最新建立的，嵌套深度为i的过程的活动记录

实际上，display表可被看成多个链表的索引入口：每个嵌套深度对应一个链表，由所有该深度的活动记录组成，d[i]就指向由嵌套深度为i的活动记录组成的链表的头部。每个活动记录中包含一个额外的字段，指向前一个相同嵌套深度的活动记录，从而将这些记录串联起来

例子

以快速排序为例，展示display表的修改过程

image-20250510151754682

image-20250510164822168

sort的深度为1，d[1]指向sort的活动记录

image-20250510164900025

readArray的深度为2，d[2]指向r的活动记录

image-20250510165432828

  • quicksort调用了partition，partiton深度为3，d[3]指向partition的活动记录

  • partition又调用了深度为2的exchange，d[2]当前指向quicksort，这需要将exchange的活动记录作为链表节点添加到链表头部，即quicksort的前面，形成d[2] -> exchange -> quicksort，因此exchange的活动记录中需要保存quicksort的活动记录的位置，这可以从d[2]中复制过来，然后修改d[2]，令d[2]指向exchange的活动记录

image-20250510165446841

当exchange过程执行完毕后，需要更新display表，将exchange的活动记录从d[2]指向的链表中删除：将exchange保存的原d[2]值（quicksort的活动记录指针） 赋给d[2]

image-20250510165657170

同理，quicksort递归调用，则在d[2]链表中插入新建立的quicksort的活动记录，方法同上

image-20250510165756068

display表的维护

image-20250510165857712

display表中 活动记录的添加和删除 与 链表中节点的添加和删除类似：

  • 每次建立一个新的活动记录都需要修改display表，将新活动记录添加到d[i]的头部
  • 当一个活动结束时，需要恢复display表的状态，从d[i]中删除这个节点，并恢复d[i]的原值

d[i]始终指向当前活跃的那个活动记录

符号表

image-20250510202753005

image-20250510202822038

我们将语句分为两类：

  • 声明语句：声明基本变量、数组、过程、结构体
  • 可执行语句：引用数据对象，表达式计算，赋值语句，控制流语句，过程调用

对符号表的操作都嵌入到SDT的语义动作中，在声明语句中需要查找（避免出现重复定义）并填写符号表，记录语义信息。在可执行语句中需要查找符号表，获得变量的类型、地址，过程的参数个数、参数类型等信息，用于生成中间代码以及检查语义错误

单个符号表的组织

image-20250510203248477

针对不同属性采取不同的存储策略，属性即指名字、类型、地址、数组内情向量、参数信息：

  • 对于基本属性，如名字、类型、地址、偏移量，将它直接存放在符号表中
  • 对于扩展属性，如数组的维数、各维的长度（内情向量），过程的参数个数、参数类型，额外申请一块内存用于存放它们，符号表中只需要保存指向这块内存空间的指针

image-20250510203830951

多个过程符号表的组织

一个变量的实际地址 = 定义该变量的活动记录的基地址 + 该变量在活动记录中的偏移地址，具体来说：

  • 需要通过访问链来寻找活动记录，然后获得活动记录的基地址
  • 需要在符号表中查找该向量的offset属性，从而获得变量在活动记录中的偏移地址

为了刻画过程之间的嵌套关系并避免命名冲突，通常为每个过程建立一个独立的符号表，并维护符号表之间的层级关联。这样，编译器在查找变量信息时，可以在当前符号表及其外层符号表中逐级查找，从而确定变量的定义层级以及其在活动记录中的偏移地址，以便通过访问链定位该变量所在的活动记录的基地址

具体来说，各个过程的符号表的组织方式为：

image-20250510205142058

对符号表进行分析：

  • 符号表头部

    符号表头部中包含两个字段：该过程声明的局部变量所需的总空间大小以及指向其 直接外层过程的符号表的指针。以readarray为例，它定义了一个int型的变量i，因此其符号表中记录的局部变量总大小为 4 字节；sort是readarray的直接外层过程，因此readarray 的符号表头部将包含一个指向 sort 的符号表的指针

  • 符号表条目

    符号表条目分为两类：变量声明条目（包括基本变量、数组、结构体）以及过程声明条目

    • 对于变量声明条目，按照单个符号表的组织方式存储语义信息，即直接存储基本属性（名字、种属、偏移地址），并保存存储了扩展属性的内存空间的地址
    • 对于过程声明条目，符号表条目中有一个指向 该过程 对应符号表的指针

在构建符号表过程中，我们需要设置好 符号表头部 和 各个符号表条目，SDT中的语义动作将实现符号表的建立

符号表的建立

image-20250510210427831

这就是说，当遇到当前过程中定义的内层过程时，我们需要递归地进入内层过程中构造它的符号表，因此需要暂时挂起对当前过程声明语句的处理。我们可以借助栈来完成分析

嵌套过程的SDT

文法中规定 声明语句 会放置在 所有可执行语句之前，且声明语句的翻译是创建符号表，而可执行语句的翻译是查找并使用符号表，因此我们对这两个语句的SDT分别进行分析以区分不同类型的语义动作

声明语句的SDT

image-20250510211540175

D：声明语句，包括对变量的声明 以及 对过程的声明（对应符号表中两类条目）

S：可执行语句

符号表的创建过程

  • 预定义过程

    在编译器设计中，为了统一处理最外层过程的作用域，通常引入一个预定义过程作为最外层过程的外层过程。这样，原本最外层的过程（如 sort）就变成了被嵌套的过程，其嵌套深度为 1，而预定义过程的深度为0

    可以认为，sort 是被嵌套在一个虚构的预定义过程中的，等价于如下结构：

    program 预定义过程;
    program sort(input, output);
    ... // 原 sort 过程的所有内容

    在这种设计下：

    • 预定义过程仅声明了一个过程 sort；
    • 它的符号表中只包含 sort 的过程声明条目；

    因此，预定义过程的符号表也就构成了整个程序的全局符号表

  • 符号表栈 和 偏移地址栈

    在编译过程中，为了支持嵌套过程的语义分析，编译器通常使用两种栈结构：符号表栈和偏移地址栈，分别用于管理当前作用域的信息

    • 符号表栈（tblptr）
      用于保存 正在翻译的各个过程的符号表指针。栈顶始终指向当前正在翻译过程的符号表。
      • 当遇到一个新的过程声明时，编译器会为其创建一个符号表，并将其指针压入栈顶；
      • 当该过程翻译完毕后，该符号表指针会从栈顶弹出，并作为一个过程声明条目插入到当前外层过程的符号表中。
    • 偏移地址栈（offset）
      用于记录当前过程声明的局部变量在活动记录中的偏移量。栈顶值表示当前过程的下一个可用偏移地址。
      • 当翻译一个变量声明时，会使用栈顶的偏移量作为该变量在活动记录中的地址，并更新栈顶值；
      • 当过程翻译结束时，对应的偏移地址也会从栈中弹出。

    这两个栈始终保持同步：每进入或退出一个过程，符号表栈和偏移地址栈都会同时压入或弹出，从而确保栈顶元素始终对应当前正在翻译的过程

  • 函数

    • mktable(previous)

      创建一个新的符号表，并返回指向新表的指针，参数previous指向先前创建的符号表，它一定是直接外层过程的符号表

    • addwidth(table, width)

      向符号表table的头部插入过程中所声明的局部变量的总存储空间大小width

    • enter(table, name, type, offset)

      向符号表table中插入一个变量声明的条目，包括变量名字、种属、偏移地址

    • enterproc(table, name, newtable)

      向符号表table中插入一个过程声明的条目，包括过程名字、指向该过程符号表的指针

接下来对各个产生式的语义动作进行分析：

image-20250510211540175

  • P->M D

    这对应 预定义过程的翻译。在翻译 过程声明D之前，我们需要先创建一个全局符号表：在D之前插入一个非终结符D，它包含了创建全局符号表的语义动作：

    • t = mktable(nil)，这创建了全局符号表，符号表的头部指针设置为空
    • push(t, tblptr)，push(0, offset)，将全局符号表的指针压入到符号表栈tblptr中，将预定义过程的可用偏移量0压入到偏移量栈offset中。这些动作都是 新创建一个符号表后必须做的
    M->ε
{
	t = mktable(nil);
    push(t, tblptr);
    push(0, offset);
}

    在翻译完过程声明D后，当前栈顶对应的是预定义过程的符号表指针 和 可用偏移量，此时需要向全局符号表的头部插入 预定义过程中声明的局部变量的总存储大小，然后清空栈，完成翻译：

    P->M D
{
    addwidth(tblptr), top(offset);
    pop(tblptr);
    pop(offset);
}

  • D-> D1 D2

    D是一个声明序列，可以包含多个变量/过程声明。递归翻译就可以了

  • Dp -> proc id N D1 S

    这是过程声明语句：过程名为id，它包含子声明D1，过程体为S

    首先，为过程id创建一个符号表，该符号表要指向当前tblptr栈顶的符号表，因为这个符号表对应的过程 一定是过程id的直接外层过程。同样地，需要执行压栈动作：

    N->ε
{
    t = mktable(top(tblptr));
    push(t, tblptr);
    push(0, offset);
}

    在翻译完D1和S之后，需要设置过程id的符号表的头部，并向它的直接外层过程的符号表中插入过程id的声明条目：

    Dp->proc id N D1 S
{
    t = top(tblptr);	// 过程id的符号表指针
    addwidth(t, top(offset));	// 设置过程id符号表的头部字段
    pop(tblptr);
    pop(offset);
    enterproc(top(tblptr), id.lexeme, t);	// 当过程id的符号表出栈后，当前栈顶是它的直接外层过程的符号表，这里将过程id的声明条目插入到其直接外层过程的符号表中
}

  • Dv->id: T;

    这是变量声明语句：变量名字为id，变量类型为T。变量是在某个过程中声明的，首先将该变量的声明信息插入到过程的符号表中（变量名字、种属、偏移地址），然后还需要更新这个过程的可用偏移地址

    栈顶对应 当前正在翻译的过程，因此直接从栈顶获得过程的符号表和可用偏移地址：

    Dv->id: T;
{
    enter(top(tblptr), id.lexeme, T.type, top(offset));
    top(offset) = top(offset) + T.width;
}
例子

image-20250510230118028

已经翻译完了readarray过程，在readarray符号表中填入变量i的信息，设置符号表的头部offset字段，然后在sort符号表中填入readarray过程的声明条目

image-20250510230424120

image-20250510230456341

image-20250510230521426

image-20250510230532003

最终翻译完了sort过程，将sort过程的声明条目插入到全局符号表中，同时设置全局符号表的头部offset字段

可执行语句的SDT

image-20250510230714055

在可执行语句中引用了变量id，首先在该层符号表中查找该id，若找不到，再到直接外层符号表中查找。找到id的声明后，返回id(层号, 偏移地址)。根据返回的层号，我们可以计算 声明id的活动记录 与 当前活动记录的深度差，然后从当前活动记录开始，沿着访问链 走 Δ \Delta Δ步可以到达声明id的活动记录，从而获得声明变量id的活动记录的基地址

例子

image-20250510231122146

quicksort过程中引用了a和v，其中

  • a是在sort过程中声明的，层号为1，偏移地址为0
  • v是在quicksort过程中声明的，层号为2，偏移地址为4

image-20250510231246053

从quicksort的活动记录开始，沿着访问链走2 - 1 = 1步，我们可以到达声明变量a的sort过程的活动记录，从而获得sort活动记录的基地址

访问链的建立是 从调用者的活动记录开始，沿着访问链走ny - nx + 1步；访问链的使用是 从当前活动记录开始，沿着访问链走 Δ \Delta Δ步，到达定义变量x的活动记录，其中 Δ \Delta Δ = 定义非局部变量x的活动记录的深度 - 当前活动记录的深度

记录和类中的字段

image-20250510231540760

image-20250510232447585

符号表的另一种组织方式

image-20250510231651534

image-20250510231704510

关键在于如何区分每个条目 属于哪个过程、位于哪个层

在语义翻译过程中，每遇到一个过程声明，编译器就会为其在过程表 btab 中分配一个条目，用于记录该过程的静态信息。而 display 表则用于在运行时快速定位某个嵌套层级上最近激活的过程的活动记录，从而支持变量地址计算和非局部数据的访问

为了能快速提取出每个过程在 nametab 中的所有名字条目，设置以下两个字段：

  • btab.last：指向过程中最后一个名字在nametab中的位置，这是过程符号表的结束边界
  • nametab.link：指向同一过程中定义的上一个名字在nametab中的位置

我们可以从 btab.last 开始，通过 nametab.link 链接依次回溯，获取该过程的所有条目

对于带有形式参数的过程，还需设置字段：

  • btab.lastptr：指向该过程最后一个形参 在 nametab 中的位置。例如，过程 quicksort 有两个形参 m 和 n，其中 n 是最后一个参数，它在 nametab 中的位置为 11，则 quicksort.lastptr = 11

image-20250510232257708

我们使用 display 表来记录各个过程（块）在不同嵌套层级上的活动记录信息。其中，d[i] 表示当前嵌套深度为 i 的过程中，btab 表中序号最大的那个过程的活动记录地址。也就是说，d[i] 总是指向运行栈中嵌套深度为 i 的最新过程所对应的活动记录

例子

例子见PPT的P72页

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布