编译原理学习笔记

这东西很早就开始看，但是一直没有一个明晰的思路。说起来最早接触编译器，大概是第一次试着自己写一个计算器的时候吧。那会尝试使用递归来进行表达式的解析，现在想来很像下推自动机。准确来说现在看着像是手写下推自动机

编译器纲要

编译原理的根本目的是将程序设计高级语言翻译成机器硬件控制器可直接执行的二进制代码。自顶向下观测，可以从编译的阶段流程逐步深入学习。

首先是概览，理解每个阶段的输入和输出，从黑箱角度理解每一阶段的编译器组件的功能，参考龙书。简要来说：输入是人类可读的程序语言，然后经过编译器前端和后端两个大层次的多阶段翻译，逐步转换成为语言的单词（token）集合，表示语言结构的抽象语法树，带有更多附加信息的，包含语义的语法树，中间代码（可以是三地址码等等），最终生成符合目标体系架构的原生机器代码。

或者从另一个视角来观察，CPU自身对应的就是一种有限状态模型。因此，编译的过程实质上可以理解为将一种编程模型下的程序翻译成另一种编程模型下的程序。 所以实质上，软件和硬件的分界点是可以变动的，这部分的trade-off和收益暂时不展开。

其次从词法分析开始，介绍词法匹配的方法，进一步深入到本质：正则表达式（三型文法），以及NDFA，以及实质上和NDFA的表达力完全等价的DFA。这里对于自动机的定义，构造和自动机所能识别的语言的介绍，是对于语言和自动机表达力和等价性的重要讨论。

接下来是语法分析，介绍CFG和CSG，以及配套的自动机模型：下推自动机。并且证明：下推自动机PDA和DPDA（确定型下推自动机）的表达力也是一样的，并且识别的语言类型也是相同的。

这部分除了自动机，还有自上而下/自下而上分析法，以及他们下属的各种方法，比如SLR，LALR，LL(0)等方法，以及其中包含的包括跳转表等分析技术。

学到一半的感受是，对于三型文法和二型文法，都有适合他们的识别对应语言的自动机模型。理解这两种文法的识别方法，可以从理解这两种语言的自动机模型开始着手。

另外二型文法对于大多数语言来说确实够用了，一般语言识别最大的问题就是语言结构的嵌套问题，这部分理解了PDA的下推栈之后就能自己动手写出来一些简单的parser了。

语义识别的部分一般是在语法树上的非叶子节点附加操作，以及借助符号表等工具来完成。在完成这部分之后，编译器的前端部分基本就完成了。这时，可以结束开发，转而编写解释器；或者为了追求性能，继续编写以各个平台的处理器为目标产物的编译器。

编译器部分，会涉及到内存分配，链接器，地址回填等操作，算是细节很多，非常偏重实践和工业界的东西。特别是很多优化可以在体系结构无关的三地址/四地址码，以及机器相关的机器码级别完成。优化是一个NP问题，可以一直做下去。近两年也有在优化环节引入AI来进行编译优化的工作。

词法分析，状态机与正则表达式

词法分析是读取输入字符流，并将它转换为

• 字母表 元素构成的集合
• 符号 构成字母表的元素。例如a,b,c是符号
• 符号串 符号的有穷序列。例如symbol。空符号串记作\(\epsilon\)
• 符号串长度 包含符号的个数。例如x=string，则有|x|=6
• 符号串连接 xy表示这两个符号串连接
• 符号串集合的乘积 AB={xy|x∈A,y∈B}
• 符号串的幂运算 同一个符号串的自我连接
• 符号串集合的幂运算 符号串集合的自我乘积
• 符号串集合的正闭包 是集合1到n次幂的并集
• 自反闭包 正闭包和空串集合的并集

通过离散数学的语言描述正则语言。

文法及其分类

简介

• 编译流程：词法分析，语法分析，语义分析，中间代码生成，中间代码优化，目标代码生成六步。
• 编译程序结构：包含上面6个步骤的对应程序，以及表格处理程序，出错处理程序。

按照前后端划分，前面5个步骤属于前端，最后一个步骤属于后端，因为它依赖于特定计算机硬件系统和机器指令。

同时，编译过程也可以分为一遍和多遍。

高级语言的自编译性（自举）：允许这个语言为它自己编写编译器。自展技术可以实现这一点：它把语言分为一个核心部分和数个扩充部分。用机器语言实现核心，再用核心实现扩展功能。

• 编译器移植：改后端为目标机器后端生成器，然后编译生成A上运行的B编译器，再用它编译自己，就得到了B上可用的编译器。

翻译程序编写系统，是编译器/翻译器的开发工具。它也曾被称为自动程序设计系统，这一概念包含规格说明，目标语言，问题范围和采用方法等。采用方法包括知识工程等。

文法分类

根据Chomsky文法分类，可以得到0,1,2,3型文法。数字越大越宽松：

• 0：每个产生式的左部和右部都包含于N和T全并集的闭包中，且至少有一个非终结符
• 1（上下文有关语言CSG）：除了空产生式，均有左侧小于等于右侧
• 2（上下文无关语言CFG）：产生式左部只能是非终结符
• 3（正规语言RG）：产生式右部的非终结符统一出现在最左端/最右端

越强的语法（编号越小）的自动机越难构造。程序设计语言大多是CSG，但是我们一般用CFG描述程序设计语言，将上下文有关的部分单独分离为语义分析的部分。

语法分析

语法分析相比词法分析使用的有穷自动机NDFA/DFA，它使用下推自动机。这种自动机模型更强一些，有部分计数功能。

下推自动机

自动机原型是图灵机。其核心模型是状态转换和状态修改。

在有限状态控制器上添加了一个信息/状态保存栈。因此，它有简单的计数能力。

下推自动机的原理实际上就是给DFA增加了一个数据栈。形式化地说，接受三型文法的DFA的形式化定义如下：

\[ DFA A = A(Q, \Sigma, \delta, q_0, F) \]

其中：

• \(Q\)：状态的有穷集合
• \(\Sigma\)：输入符号的有穷集合
• \(\delta\)：转移函数\(\delta(q, a)\)
• \(q_0\)：自动机的初始状态
• \(F\)：自动机接受状态/终结状态的集合

那么，下推自动机PushDown Automation的形式化定义就是：

\[ PDA P = P(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F) \]

其中：

• \(Q\)：状态的有穷集合
• \(\Sigma\)：输入符号的有穷集合
• \(\Gamma\)：有限的堆栈字符表
• \(\delta\)：转移函数，是三元函数\(\delta(q, a, X)\)，三个变量分别是\(Q\)中的状态，\(\Sigma\)中的输入符号或者空串\(\epsilon\)，\(\Gamma\)中的堆栈符号
• \(q_0\)：自动机的初始状态
• \(Z_0\)：自动机堆栈的初始符号
• \(F\)：自动机接受状态/终结状态的集合

语法分析方法

自上而下语法分析

简单的说，就是不断选取产生式，尝试从根节点推导出和当前串\(w\)匹配的串。

从语法树的根到叶去建立语法树。步骤是试探+回溯，边推导边匹配。对输入序列，使用产生式进行最左推导，直到得到一个合法句子/非法结构。随后从左到右扫描输入序列，自上而下建立语法树。

最大的问题是左递归，即非终结符同时出现在左部和右部左侧，会造成死循环。消除方法为引入新的非终结符进行同义转化。直接消除左递归的方法可以使用通用的算法进行解决。

另一个问题是消除文法二义性。直接的消除方法不适用于自上而下分析方法。

还有一个问题是公共前缀的提取。该行为能有效优化选择速度，提升性能和错误恢复能力。方法是引入新的非终结符来表示公共前缀的推导，再改写原来的产生式。

自下而上语法分析

简而言之就是，从串\(w\)着手，不断在其中寻找能用产生式规约的部分，并不断地进行规约操作。

下面是GPT的介绍：

自下而上语法分析（bottom-up parsing）是一种从输入的最底层符号开始，逐步构造出高层结构的语法分析方法。它的目标是通过合并输入符号和中间结果，最终构造出整个输入的语法树。LR分析器是自下而上语法分析的典型代表之一。

我们用一个简单的例子来说明自下而上语法分析的过程。假设我们有以下的语法规则：

1. S → AB
2. A → a
3. B → b

这里，S、A、B 是非终结符，a、b 是终结符。我们的输入字符串是 “ab”。

我们从输入字符串的第一个符号开始，将每个符号视为一个单独的子树：

初始状态：输入字符串 “ab” 被表示为 [a, b]。

1. 匹配并规约第一部分

我们检查字符串并尝试应用规则 A → a。

• 输入字符串中第一个符号是 a，符合规则 A → a。
• 我们将 a 规约为 A。

此时，输入状态变为 [A, b]。

2. 匹配并规约第二部分

接下来，我们检查字符串并尝试应用规则 B → b。

• 输入字符串中第二个符号是 b，符合规则 B → b。
• 我们将 b 规约为 B。

此时，输入状态变为 [A, B]。

3. 匹配并规约整个字符串

现在，我们尝试应用规则 S → AB。

• 当前输入状态是 [A, B]，符合规则 S → AB。
• 我们将 [A, B] 规约为 S。

此时，输入状态变为 [S]。

此时，输入字符串已被规约为 S，表示输入字符串 “ab” 是该语法的一个有效句子。

根据上述规约过程，我们可以构造出对应的语法树：

    S
   / \
  A   B
 /     \
a       b

有几种基于自上而下的识别方法，比如LALR和SLR。