编译原理课程总结

本学期学习了编译原理，轮子哥口中的三大浪漫之一，复习期间写这篇文章作为梳理，并且把大作业的 Code 放到了 GitHub 上，希望对学弟学妹有所帮助（逃。

基本概念

编译说白了就是翻译，把高级语言代码翻译成的机器能够执行的机器代码，主流有两种形式：编译器和解释器。前者将源程序翻译成目标程序后再进行运行，后者则是一遍翻译一遍执行。前者典型如 C++，执行效率高，后者如 Python，灵活性好但是效率有所逊色。但实际上，现在的大趋势就是编译和解释的融合，例如 Java 就是编译成字节码后进行由 JVM 来解释执行，带来良好的跨平台性，同时也引入 JIT（just in time）技术在 JVM 执行时提高程序运行的效率。

编译大致可以分成如下几个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化以及目标代码生成，符号表管理和出错处理贯穿整个过程。如果把中间代码以前的阶段称之为前端，而其后的成为后端，便是另外一种角度下的编译器（分析/综合模式），而课程所涉及的也主要是前端部分，后端部分的优化事实上对程序有着重要的作用，希望以后有机会能进一步的探索。接下来就以课程所学的各个阶段为主线来梳理一下内容。

词法分析

词法分析要做的就是把文本序列转换为我们所规定的记号（token），因此其主要工作如下：

1. 处理与平台相关的输入
2. 过滤程序中无用的部分，比如注释
3. 识别输入序列中的记号
4. 调用符号表管理程序和出错管理程序进行相关处理

核心是第三点，而要识别文本序列中的记号，首先我们要定义规则，什么是合法的记号，然后想办法来识别它，这也就是老师常说的立法和执法。

立法：记号的组成

规则：因为记号的组成一般是字符的线性组合，因此可以使用正则表达式来进行描述，这里就不对正则表达式做过多的展开。而这种规则又可以称为模式（pattern）

记号：按照某个模式识别出的元素，一般是指一类，一般我们需要识别出记号的类别和其属性，常见的类别包括关键字、标识符、字面量以及特殊符号（+, - 等）

单词（lexeme）：识别出元素自身的值

举个例子，对于 C++ 中的关键字 const ，我们就需要识别出他的类别是关键字，而对于某个变量名 count 则要识别出类别为 id 并且其 lexeme 为 count 以便后续的符号表登记操作。

执法：识别记号

我们使用有限自动机来识别记号，Why？先来看看自动机 M 的组成：$M = (S, \Sigma, move, s_0, F)$，这个五元组的组成：

1. $S$：有限个状态的集合
2. $\Sigma$：有限个输入字符的集合
3. $move$：状态转移函数，表明某个状态在接收到某个字符会转向下一个状态
4. $s_0$：唯一的初始状态
5. $F$：终态集，代表了可以接受的状态的集合

自动机是一种很好用的工具，根据状态转移来一步一步地建模问题。记号识别正好契合了这种方法，比如你要识别一个邮件的地址，你拿着对应的正则表达式，先识别一系列的字符组合，关键是其中的@ 符号，最后再来形如 qq.com 的后缀完成识别。

有限自动机根据其状态转移函数是否是一对多的，也即同在某个状态下，对于同一个输入字符是否有多个可能的下一状态，分成不确定的有限自动机（NFA）和确定的有限自动机（DFA）。而自动机的编程实现是很简单的，每次读一个字符进行，根据状态转移函数进行状态转移，循环往复执行到最后一个输入即可。而 NFA 因其的不确定性会带来大量的回溯，一般我们都会将其确定化后形成一个 DFA 来进行实现，确定化的方法不展开，核心就是一句话：把状态转移拓展为状态集转移，把状态集之间的转移作为 DFA。

有了正则表达式和自动机，怎么把他们连起来做记号的识别呢？Thompson 可以完成正规式到 NFA 的转换，而再通过确定化 NFA 得到 DFA 即可完成记号的识别。

语法分析

有了词法分析的记号流之后，我们便要从记号流之中提取程序的语言结构，而一般会通过一颗树来表示语言的结构（在 NLP 中一般也是这么干的），这棵树我们称之为语法树；除了提供语法树给下一阶段语义分析以外，语法分析还需要检查一下语法错误，比如我们经常会漏的括号等。对于错误处理，这里对可能出现的错误简单做一下分类：

1. 词法错误：不符合构词规则，一般在词法分析阶段发现
2. 语法错误：语法结构出错，不成句，例如缺少括号等
3. 静态语义错误：类型不一致，参数不匹配等
4. 动态语义错误：死循环，除数为 0 是常见的动态语义错误

从错误中恢复是比较困难的，因此这里不再展开，而实现的时候一般直接报错，并且指出哪里出错即可。回到语法分析，我们还是需要关注亮点：如何描述语言的结构（立法）和有了规则之后如何识别。

立法：上下文无关文法

语言是非常复杂的结构，否则自然语言处理也不会被称为人工智能皇冠上的明珠了，其中包含很多的非线性结构，好在程序语言相对来说更加的精确，我们能够通过形式化的方式来描述它。常用的便是上下文无关文法（Context Free Grammar，CFG），它是一个四元组 $G = (S, N, T, P)$：

1. S：开始符号，所有的句子都从这里开始（Start）
2. N：非终结符的有限集合
3. T：终结符的有限集合
4. P：产生式的有限集合，其形式为 $A\rightarrow\alpha$，$A \in N$ 以及 $\alpha \in N \cup T \cup {\epsilon}$

其中对于 N 和 T 我的理解是：T 是最终我们能在记号流中见到的所有记号的类别，而 N 是描述语言产生时的中间结构，比如常见的运算就可以表示成下面这张图：

有了 CFG 以后，语言是怎么产生的呢？推导，也即利用产生式的右部替换产生式的左部，最终将所有的 N 都换成了 T，得到一个句子，其中推导的时候如果每次都替换最左边的非终结符，就成为最左推导，同理有最右推导，也被称之为规范推导；推导各个步骤中的中间结果称为句型。To be honest，我觉得这些概念没什么记忆的必要，纯粹是为了应付考试，了解大概意思即可。

推导中对于非终结符的替换的选择不是唯一的，因此同一个句子可能得到两颗不一样的语法树，这就是文法的二义性。其本质是文法对优先级和结合性缺少定义。如之前的 NFA 一样，我们不喜欢二义性，消除二义性的方法就是加入优先级和结合性的信息来改写文法。但消除二义性后的文化书写起来比较麻烦，并且因为引入了额外的信息，树的高度变高，也给后续的带来额外的负担。

此外，再对文法做一些展开。和前面的正则表达式相比，CFG 的表达能力是更强的，也即能够描述更丰富的结构，比 CFG 更强的有 CSG（上下文有关文法），一个很明显的例子就是计数问题，正规表达式无法表示有两个相同数量的字母句子，而 CFG 可以，CSG 进一步地可以表示三个相同数量的字母的句子。

执法：识别语言结构

有了规则，下一步就是怎么做，方法大致分成两类：自上而下和自下而上。

自上而下

自上而下分析的核心就是模拟推导的过程，对于任何一个输入序列 $\omega$，从开始符号 $S$ 进行推导，试探着对 $\omega$ 进行匹配。在模拟这一过程之前，我们需要对文法做一些改动，主要包括：消除左递归和消除左因子，避免带来的递归调用爆栈以及回溯。

修改好文法之后，我们就可以来编程了，利用简化的文法写出 DFA，来暴力实现。这种方法称之为递归下降子程序法，适合手动编写简单的语言解释器，我们的大作业便是采用这种方法，但不适合大型的项目和自动生成。因此我们还有另外一种方法：预测分析器。

预测分析器使用一个下推自动机，就是带有数据栈的有限自动机来完成推导的过程。工作方式就是从初始的某个格局开始，经过一系列变化达到最终格局，如果是接收格局那么就 ok 否则报错。格局是一个三元组：（栈内容，当前剩余输入，改变格局的动作）。改变格局的动作分为三类：

1. 匹配终结符：从当前剩余输入中拿出一个终结符吃掉
2. 展开非终结符：模拟推导的过程
3. 成功接收 / 出错

这里的核心是一张预测分析表，来指导下推自动机的工作。预测分析表说的就是：当你栈顶的非终结符看到一个终结符的时候你应该转向哪一个状态（或者说进行哪一步推导）。而如何确定，则是通过计算非终结符的 FIRST 和 FOLLOW 集合来完成这张表的填写，简单来说，FIRST 集合中是该非终结符推导出的所有句子的起始终结符，而 FOLLOW 集合中则是紧跟着该非终结符的终结符，具体的细节也不再赘述。

自下而上

自上而下的思路是模拟推导，从开始符号开始，把非终结符展开，最终得到一个完整的句子；那么反过来，从句子出发，不断地进行推导的逆过程——归约（将终结符变为非终结符），最终得到一个开始符号，也是一种可行的方法。因此，移进-归约分析应运而生。

还是借助一个下推自动机，运用格局和一张分析表来驱动语言结构的识别，关键就在于我怎么知道什么时候该进行归约？又该归约成什么非终结符？

归约（reduce）是推导的逆过程，而如果将某个句型（或则是句子）的分析树画出来，我们可以发现：

每次归约，就是把一个子树的叶子节点减掉，而为了规范，我们一般从最左边的最小子树（高度为2）的开始，这个操作就是剪句柄。想想一下最右推导，我们最后才会把最左边的非终结符展开成终结符，而剪句柄，则是每次都把句子的最左边归约成一个非终结符。最右推导和最左归约互为逆过程，也正好是自上而下和自下而上的体现。

回到归约的下推自动机，其格局类似之前的预测分析器，只不过改变格局的动作由匹配终结符和展开非终结符换成对应的移进和归约。但是还是那两个问题，我怎么知道我现在该移进还是规约？这张分析表的构造的核心在于识别活前缀，即某个句型的开头序列是什么。而要识别活前缀，还是要需要我们的老朋友 DFA 以及项目（带有已经见到部分标记的产生式）来完成。这里不再展开，因为我觉得这个属于技术细节，核心的东西在于前面的思想，搞清楚了思想剩下的就是模拟机器执行的过程，没必要过于纠结。

语义分析

拿到了语法分析产生的语法树，到了语义分析阶段我们就可以为所欲为做一些跟最终结果相关的工作了。而对于一个解释器来说，在拿到语法树之后，就可以执行相应的语义动作了，这也是我们在最终大作业一个简单绘图语言的解释器中所采用的做法，就是把对应的图给画出来。

一般的编译器在语义分析阶段需要完成的工作是：检测表达的语义是否合法以及执行相应的语义动作——生成中间代码。

中间代码，前面也提到了，是连接前端和后端的桥梁。主要的形式有树、后缀式以及三地址码。树和后缀式之前在数据结构都有接触过，而三地址码则是形如 a := 1 这样形式的代码，和汇编非常的接近，一般可以用一个四元组 (op, arg1, arg2, result) 来表示，拿 a = 1 + 2 来说，就会生成 (+, 1, 2, T1) 以及 (:=, , T1, T2) 这样两条代码。同样的还有三元组，把存放结果的第四个 result 参数省略而通过三元式的位置来确定存储位置，毫无疑问，这样做会给后面的代码优化带来很大的麻烦，因此多用四元式。

执行语义动作除了生成中间代码以外，一般还会在对应的文法符号（比如非终结符上）记录一些信息，称作属性。属性可以分为继承属性和综合属性，前者需要父结构的信息，而后者需要子结构的信息。属性的计算方案根据抽象程度不同可以分为语法制导定义和翻译方案，这二者就类似算法和具体的代码，前者是一个框架流程，后者则是关系到具体的平台和语言实现。

总的来说，语义分析做的事情就是拿着语法树执行动作，而还有一些内容比较零散，我就挑一些我觉得比较重要的来说。

嵌套

变量或者过程嵌套的原则：静态作用域原则和就近嵌套原则。这两个原则其实我们已经很习惯了，但单独拿出来说是想说明一下实现的思路。栈，后进先出，和这个嵌套的关系刚好契合，每次我们遇到一个作用域和其中的变量（过程同理），就可以把它压栈，查找的时候沿着栈顶向里查找即可。

过程调用方式

这就是我们之前经常遇到的 C 语言中的 swap 函数遇到的问题：值传递还是引用传递。在编译原理中，我们强调了左值和右值的区别，左值是一个有存储空间的变量，是一个容器，而右值则是内容，比如常见的字面量 1、123。值传递是右值的传递（将实参的内容交给形参），引用传递则是左值（将实参的地址填到形参的地址中），所以后者在函数/过程内部修改形参也会对实参产生影响。此外复写-调用方式是二者的一个结合，在函数体内部是值传递，而在函数返回的时候会把形参的值传回的实参。

拉链-回填技术

在翻译一些控制语句的时候，例如 if / while 等，我们需要考虑的一个核心问题就是：下一条在哪里？例如，对于 if x > 0 then x := a + 1 else x := 2 这样一条语句，在一遍自上而下的扫描的过程中，我们看到当前的语句 if x > 0 能确定的是条件为真时要转向 then x:= a + 1 （可以认为是紧接着的下一条指令），但是为假的出口并不能马上确定，因为then 语句中可能做很多操作，不是简单的下一条，必须要到我们看到 else 的时候才能确定。而延迟这种条件转向语句的填写的技术就是拉链回填技术。说白了，就是我现在不知道，先记着，到了合适的时候再回过头来的填之前的漏。而如何设计回填的时机是比较 tricky 的，比如前面的看到 else 我们就知道这里可能需要回填一波之前的条件为假的出口，设计的时候需要仔细的考虑。

总结

一开始学编译原理，觉得是非常高大上的一门课，而随着抽丝剥茧把前端各个阶段分开来，一点一点学起来，还是非常有趣的。并且亲手写了一个简单的解释器，成就感还是爆棚的。此外，也切实感受到软件工程的重要性，如果不能够把任务分解成可实现的小块，而是一上来丢给你一个写一个解释器的大目标，是很难有信心完成它的。

另外，明天就考试了，祝自己好运！