编译原理笔记

第 05 讲 ~ 第 07 讲：符号表管理技术、运行时的存储组织及管理、源程序的中间形式

第 05 讲 符号表管理技术

  • 符号表：编译程序为了记录源程序中标识符以及相关的信息时所用到的表格。其中的每一个登记项都填入了标识符的种类、类型、特征、存储单元地址等信息。

符号表的概念

  • 在多遍编译程序中，符号表在词法分析时创建，当检测到标识符单词时就添加一个符号表的项和对应索引；符号表在语义分析时才填入项的其他信息，因为只有这时才能根据标识符上下文分析出标识符的相关属性。

如果在语法分析时就对符号表进行填写会导致某些信息的缺失，或在错误的阶段产生了信息，导致编译程序耦合度过高，工程性下降。

image-20230924222017786

  • 在单遍编译程序中，程序则在语义分析阶段才创建符号表，之前的阶段和符号表是完全无关的，这样可以降低耦合度，同时简化符号表和程序之间的交互

image-20230924222250119

符号表的作用

  • 源程序中，标识符的每一次出现都需要从符号表中查询对应的项，有则获取信息，无则添加条目；不同声明类型的语言在查表时的操作也存在差异
  • 符号表的表项会随着标识符的存在、创建和删除而做出动态的修改，也就是说符号表是一个动态表，编译程序需要时刻对其进行管理
  • 符号表在编译过程中，主要提供标识符的名称、类型和存储地址空间等关键信息，访问量大

符号表的操作

最常见的操作是插入、查询，插入操作与声明类型相关。

  • 显式声明语言：插入和查询是可以区分的，插入时理论上不需要查表，可以直接插入；而查询时则正常查询
  • 隐式声明语言：无法区分插入与查询，无论是插入还是查询都需要进行查表的工序，然后再进行插入或获取信息
  • 在实际的编译器中，大部分符号表都采用排序后的方式进行存储，那么显式声明语言在插入之前也需要找到自己需要插入的位置，说到底还得做一次查询的操作，这样一来两类语言的两种操作区别就不是很明显了

除了两类基本操作外，还有定位、重定位两类操作，它们在分程序结构语言的符号表中也经常使用，当检测到分程序的开始时执行定位，结束时则执行重定位。具体的操作将在第 4 小节中进行介绍。

  • 分程序结构语言是指其模块可以包含能嵌套的子模块，每个子模块都能包含独立的标识符和函数参数，在查表时，程序会递归地查找所有自己之上的所有符号表，直到找到标识符或无定义报错，C 语言就具有分程序结构
  • 定位：当子模块开始时，编译器创建一块新的子符号表，在新模块中出现的所有标识符都放置在这个子符号表中；所有的子符号表都可以嵌套新的符号表
  • 重定位：当子模块结束时，编译器对该模块的符号表进行销毁，清空其中的所有标识符，归还空间（允许后续的模块对其进行覆盖）

需要注意的是，在查找分程序结构的符号表时可以允许不同的符号表（模块）中包含相同的定义（局部变量），但是不允许同一符号表中有相同的定义（重复定义）

符号表的组织与内容

符号表的结构

符号表由一系列行组成，每行类似于一条记录，包含了指定富豪的相关属性，通常包含以下信息：

  • 名称：标识符的名称
  • 类型：整型、字符串等
  • 分配的内存地址
  • 声明、使用行
  • 链域：如若使用链式符号表，则会存在一个指向下一个标识符的链域

符号表的组织方式

通常符号表有以下三种组织方式：

  • 统一符号表：对所有标识符都填入结构相同的符号表中，符号表查表会比较方便，但浪费空间
  • 按种类符号表：将属性相同的符号组织在一起，形成多张符号表，空闲的域少，空间效率高，但是查表等操作的时间复杂度高
  • 折中办法：将大部分共同信息组合成一个符号表，再将多余的信息拉一个链域单独存放

对于符号表中标识符名称的存放方式有两种：定长空间（能够快速存取，但是空间浪费），包含标识符起始位置和长度的字符串描述符（字符紧密排列，但是效率低）

非分程序结构语言的符号表组织

标识符的作用和基本处理方法

  • 对非分程序结构语言而言，每个程序单元都不包含子模块，声明的所有标识符都属于这个模块
  • 全局变量和局部变量需要分别存放，声明变量时需要存入局部变量表中，如果已经出现重复定义则需报错
  • 执行时查表顺序为局部表 → 全局表，如果都没找到则说明未声明
  • 局部表在程序段结束后则应该释放

符号表的组织方式

分为无序符号表、有序符号表和散列符号表，无序符号表查表复杂，管理简单；有序符号表因为插入之前要先比查找，所以导致插入较慢，但查询相对而言更快

散列符号表则将符号进行 hash 处理，以 hash 值进行符号的存储和访问。

散列函数有一些常用的备选选项：中平方散列法、折叠法和长度相关法。

  • 中平方散列法：选取中间几位数进行平方操作，最后取模
  • 折叠法：将值按位数拆成几个固定位数的值再相加，最后取模
  • 长度相关法：将第一个和最后一个字符的编码相加，再加上 16 倍的符号长度，最后取模

分程序结构语言的符号表组织

主要涉及到了定位和重定位操作，至于链表法符号表的具体方法不如找一个题目进行应用

第 06 讲 运行时的存储组织及管理

编译程序替程序员管理了符号变量等的内存地址，这些地址需要编译程序主动进行分配，本章介绍静态存储分配、动态存储分配和内存垃圾回收三部分内容，其中静态存储分配适用于静态定义的数据结构，而动态存储分配更实用于管理分程序结构语言内存。

静态存储分配

如果在编译时能确定数据所需存储空间的大小，并分配固定的存储空间，这种分配方式就叫静态存储分配。换句话说当遇到可变长串、动态数组，甚至递归过程时，都不能使用静态存储分配。

我们可以很容易填写静态分配下符号表所含有的地址信息，只需要将变量按照指定的大小紧密地线性排列即可

  • 数据区：一个非分程序结构的程序模块在采用静态存储分配时的数据区分为三部分：隐式参数、形式参数和程序变量
    • 隐式参数：与调用模块间进行通信，调用程序时的跳转地址
    • 形式参数：存放实参的地址和值
    • 程序变量：编译过程中需要的变量等

动态存储分配

动态存储的分配方式主要基于堆栈的思想实现，程序会为每一个程序段创建一个自己的数据区域，并占用一定空间，当程序调用子模块时就延伸这个堆栈，程序结束时就弹出这部分栈，这部分占用的专用数据区被称为活动记录

活动记录包含局部数据区、参数区和 display 区三部分

  • 局部数据区：为局部变量的存储提供空间
  • 参数区：保存隐式参数和显式参数
  • display 区：一系列指针

参数区

参数区用于保存隐式参数和显式参数。隐式参数包含返回调用者时的地址、指向上一级活动记录的指针（prevabp）、当前模块结束后的返回值

在值调用的方案中，实参值一般赋值给形式参数，并且放置在显式参数区。具体的参数传递机制在第 10 章会进行学习

display 区

display 区为访问外部变量提供了重要方式。display 区存放了一系列指针，每一个指针都指向某一级活动记录，这些活动记录逐级调用，都是当前区域的调用者（间接调用者）。他们的变量等对于当前模块都是可见的，或者说全局的。换句话说，子模块的 display 区需要包含所有父模块的活动记录基地址指针

image-20230927213001590

这是一个程序的调用过程

  • 首先顶层模块的活动记录 AR1 包含局部数据区，不需要参数区和 display 区；
  • 其次调用了一个子模块，活动记录 AR2 包括正常的三个分区，参数区含有 prevabp（指向 AR1），子程序结束后的返回地址；display 区含有父模块的活动记录指针，这里还是 AR1 的指针
  • 随后在退出 AR2 后，主程序又调用了子程序，在子模块 AR3 的参数区中，prevabp 此时也指向父模块 AR1
  • 接着在 AR3 中又调用了 AR4，它的 prevabp 指向 AR3，并且 display 区中含有指向 AR3、AR1 的指针

运行时地址计算

假设现在要访问某一个模块中偏移量为 $ON$ 的变量（模块位于栈的第 $BL$ 层），假设当前位于该模块的子程序中，计算地址的方式如下：
$$
ADDR=display[BL] + BL-1 + nip +ON
$$

  • $nip$ 指隐式参数的数目，$BL-1+nip$ 可以看作 display 区的大小
  • 实际上是选出了 display 区中第 BL 层的活动记录的基地址，再加上 display 区的大小，最后加上变量在局部数据区的地址偏移，实际操作要比虚空推导好得多

内存垃圾回收器

内存垃圾回收器是一种自动内存管理机制，可以对动态分配的内存空间进行自动回收，它需要从编译器、操作系统、芯片中获得一些信息才能达成自动回收的目的。

  • 变量根集：程序运行时运行栈上的所有变量集合+全局变量、静态变量

如果一个对象不能被根集出发的指针遍历到，那么就相当于不可达对象，那么就可以当成垃圾进行回收

引用计数

为每个对象都设置一个计数器，它记录当前有多少引用指向当前对象，类似于操作系统中的页引用，当引用为 0 时就可以释放物理页内存。

当回收对象前，要对它的每个指针进行检查，再回收后要检查其他的对象引用计数，这样就带来了较大的开销。

标记和清除垃圾回收器

标记和清除垃圾回收器是跟踪型回收器的一种，它不移动对象。

  • 首先从对象根集遍历指针关系图，对可以到达的对象进行标记
  • 遍历所有内存，对所有未被标记的对象进行回收，此刻回收的都是不可抵达的对象

由于清理过程中不会移动对象，于是会产生内存碎片，内碎片问题严重

在空闲空间分配新对象后，不同生命周期的对象共用一个页面，导致换页频繁，程序运行效率低

标记紧缩算法

标记紧缩算法修正了标记清除回收器的碎片化、分配效率低的问题

  • 标记阶段：标记所有可达的对象
  • 紧缩阶段：对内存空间进行多次扫描，对空间进行滑动紧凑，修改指针的引用值，将空闲空间转化为连续的空间

这样的紧缩操作对于后续的访问有较大的收益，但是紧缩操作本身开销较大，如果大部分变量都不需要清理的话，多次修改大量变量的指针开销会很大

拷贝回收算法

拷贝回收算法和标记紧缩算法相似，但是拷贝回收算法不关心垃圾对象的清理工作，只将活对象移动到连续空间中。它将内存空间一分为二，并线性地分配内存，一旦内存分配至边界线处，就开始拷贝回收，将所有的活对象拷贝到当前空闲的半块内存，并将空闲的内存转化为工作状态，当前的内存转为空闲状态。

缺点就在内存的使用率上，一分为二的思想注定了内存的使用率不能超过 50%。

分代垃圾回收器

目前 Java 常用的垃圾回收机制。有点复杂不想写了就先放着了）

第 07 讲 源程序的中间形式

  • 源程序的中间形式，即编译程序将高级语言程序翻译为汇编语言或机器代码过程中产生的一种内部表示形式。
  • 优点是移植性强、优化处理容易，缺点是效率低，需要二次翻译

波兰表示

前缀表示和后缀表示被称为前缀、后缀表示，后缀被称为逆波兰表示。由于前缀表达式不常使用，所以后缀表示也可以称为波兰表示

波兰表示的语言结构

波兰表示除了可以表示一般的表达式、赋值语句外，也可以通过扩充操作符来表示其他较为复杂的语言结构

对于 if 语句而言，可以进行如下的形式转换：
$$
ifthenelse\ 转换为\
BZBR
$$

N 元表示

在 N 元表示中，每一条指令由 $n$ 个域组成，第一个域代表操作符，后续的域代表操作数

三元式

  • 三元表示：$<操作符>,\ <操作数1>,\ <操作数2>$

对复杂的表达式，可以用一组三元式表示，例如 $W*X+(Y+Z)$ 可表示成下式：
$$
1)\ *,\ W,\ X\
2)\ +,\ Y,\ Z\
3)\ +,\ 1),\ 2)
$$
类似的，条件语句也可以进行转换：
$$
\begin{align}
& if\ X>Y\
& then\ Z:=X\
& else\ Z:=Y+1
\end{align}
$$
转换成三元式则如下：
$$
\begin{align}
& 1)\ -,\ X,\ Y\
& 2)\ BMZ,\ 1),\ 5)\
& 3)\ :=,\ Z,\ X\
& 4)\ BR,\ \ ,\ 7)\
& 5)\ +,\ Y,\ 1\
& 6)\ :=, Z, 5)\
& 7)\ left\ content
\end{align}
$$

  • 这里的 $BMZ$ 代表小于等于 $0$ 转移，条件语句在第二个域中，跳转标签在第三个域中；
  • $BR$ 代表无条件转移

四元式

与三元式类似，四元式也有相应的域和运算规则，具体而言域的含义如下：
$$
<操作符>,\ <操作数1>,\ <操作数2>,\ <结果>
$$
四元式的每次运算后后会产生一个临时变量，这个临时变量可以参与后续的运算，效果和三元式中的标签类似

  • 四元式便于对程序进行优化处理，因此在介绍优化的章节中会使用四元式作为中间代码形式

抽象语法树

抽象语法树是另一种常用的源代码中间形式，树结构中的非叶节点代表操作符，而叶节点代表操作数，对于表达式 $(A+BC)/(DE-(F+G)/(H+I))$ 而言，构造的抽象语法树如下：

image-20231010131143194
  • 树中的编号代表分析器自底向上创建树节点的顺序
  • 遍历抽象语法树能够获得语法式的波兰表达式，整个树也可以由多个三元式进行组合表示，要注意最后一个三元式与树的根节点相关，每一个三元式都代表树中的一个子树