• 编译器一般结构
• 词法分析
  • 非确定有限自动机（NFA）
  • 确定有限自动机（DFA）
  • 相关
• 语法分析
  • 上下文无关文法（可以用BNF语言表示）
  • 怎样设计文法
  • 自顶向下语法分析
  • 自底向上的语法分析
  • 语法制导翻译
  • 相关
• 中间代码生成
• 运行时刻环境
• 代码生成和优化
• 参考资料

编译器一般结构

1. 词法分析（Lexical Analysis or Scanning）：将字符序列转化为单词（token）序列，给出单词的类别和一些相关属性值属性值放在公用的符号表（Symbol Table）中，词法分析过程返回单词的属性值存放的地址
2. 语法分析（Syntax Analysis）：在分词的基础上建立语法分析树
3. 语义分析（Semantic Analysis）：类型检查和类型转换
4. 中间代码生成（Intermediate Code Generation）
5. 代码优化（Code Optimization）：优化中间代码
6. 代码生成（Code Generation）

词法分析

所有程序设计语言的单词都可以用正则语言（正则表达式定义的语言）表示（或者说应该这样设计），因此只讨论如何识别正则语言

非确定有限自动机（NFA）

• 构建方法是，为每种类型的正则表达式单元（例如或、星号等）构建结点或结点组，并构建起始结点和终结点，然后将它们通过\(\epsilon\)符号连起来。
• 如何用来识别语言：通过\(\epsilon\text{-}closure\)实现，从初始结点的\(\epsilon\text{-}closure\)开始，每读入一个字符就计算转移到的结点集合的\(\epsilon\text{-}closure\)，重复这个过程直到读入所有字符，如果终结点在最后得到的\(\epsilon\text{-}closure\)中就判断成功否则失败。

确定有限自动机（DFA）

构建方法是：

• 从NFA到DFA：类似直接用NFA识别语音的过程，把\(\epsilon\text{-}closure(s_0)\)作为一个确定状态（其中\(s_0\)是初始的NFA状态），对每个状态和每个符号，找到该状态通过该转移符号可达的所有结点，并算出其\(\epsilon\text{-}closure\)作为新的状态。重复此过程直到没有新的状态为止。缺点是这个转换可能导致状态空间的指数增长，例如与\((a\vert b)^*a(a\vert b)^{n-1}\)的NFA等价的状态书不少于\(2^n\)。

• 直接生成DFA：把正则表达式转换为语法树，为每个结点\(p\)计算函数\(nullable(p)\)并用其计算\(firstpos(p)\)，然后计算\(lastpos(p)\)并用其和\(firstpos(p)\)计算\(followpos(p)\)。生成DFA时，初始状态为\(firstpos(root)\)，每次取一个未处理过的状态，并为其对每个符号通过该状态的每个\(p\)对应的\(followpos(p)\)作转移生成新的结点集作为一个新状态。一直重复直到没有更多新状态产生为止。计算方法：

  Node \(n\)	\(nullable(n)\)	\(firstpos(n)\)	\(lastpost(n)\)	\(followpos(n)\)
  Leaf \(\varepsilon\)	\(true\)	\(\varnothing\)	\(\varnothing\)
  Leaf \(i\)	\(false\)	\(\{i\}\)	\(\{i\}\)
  Root of \((c_1\vert c_2)\)	\(nullable(c_1) \vert\vert nullable(c_2)\)	\(firstpos(c_1)\cup firstpos(c_2)\)	\(lastpos(c_1)\cup lastpos(c_2)\)
  Root of \((c_1 c_2)\)	\(nullable(c_1) \&\& nullable(c_2)\)	if \(nullable(c_1)\) then \(firstpos(c_1)\cup firstpos(c_2)\) else \(firstpos(c_1)\)	if \(nullable(c_2)\) then \(lastpos(c_1)\cup lastpos(c_2)\) else \(lastpos(c_2)\)	\(\forall i\in lastpos(c_1)\), \(firstpos(c_2)\subset followpos(i)\)
  Root of \(c_1*\)	\(true\)	\(firstpos(c_1)\)	\(lastpos(c_1)\)	\(\forall i\in lastpos(c_1)\), \(firstpos(c_1)\subset followpos(i)\)

• 最小化DFA的状态数：一个DFA的两个状态称为可区分的，如果存在某个字符序列，使得能且只能从其中的一个状态出发沿着该字符序列可以达到终结状态。如果两个状态是不可区分的，说明以该其中一个状态为初始状态、原终结状态为终结状态的子DFA与另一个子DFA识别相同的语言，因此该两个状态可以合并为同一个（初始状态）。根据这个思想的最小化算法：初始化时把所有状态分为两类（终结状态和非终结状态，注意一个DFA中终结状态可以有多个），然后每次把每个类分为多个子类并将原类替换掉，分类的规则是所有同一个子类的状态对每个字符都转移到同一个其他类（或自身）；重复此过程直到无法再分出更多的类为止。

  问：上面直接生成DFA的方法是否总是能使生成的DFA的状态数最小？答：不能。例子：

相关

• 定理：NFA、DFA和正则表达式三者的描述能力是一样的。

  问：从正则表达式到NFA/DFA可以构造证明，反方向怎么证明？

• 局限：例如，正则表达式无法计数，如无法构造一个有限自动机接受语言\(L=\{a^n b^n\vert n\ge1\}\)。

  问：如何证明？

• 工具：lex、flex可以用来生成一个scanner，用来识别指定类型的token。例如可以通过正则表达式定义需要识别的token形式以及相应的动作（怎样处理，例如print出来），将其输入flex可以生成一个c源程序，编译之得到一个c可执行程序，可用来处理包含需要识别的token的文件并在每次识别成功时都进行相应的处理。

语法分析

上下文无关文法（可以用BNF语言表示）

• 文法的每条规则叫作一个产生式；推导就是用产生式右端的一项取代左端的过程；最左推导（每步推导都替换最左边的非终端符号）和最右推导
• 正则语言用来定义每个单词（token），上下文无关文法用来定义一个程序语句（statement）。而程序语句由单词（下面也成为符号）组成。
• 文法二义性：存在一个句子使得该文法存在两种产生不同分析树的推导
• 文法二义性是不可判定问题（无法给出一个通用算法可以判定所有上下文无关文法的二义性）

  问：如何证明？参考维基百科

• 正则语言可以转换为上下文无关文法（通过所谓“右线性文法”）。实际上，所有能用左/右线性文法表示的语言都能用正则语言表示

  问：如何证明？

怎样设计文法

• （手动）消除二义性
• 左递归（存在形如\(A\to Aa\)的产生式，或通过推导能产生上述产生式）。消除左递归的思想就是消除所有形如\(A_i\to A_j\gamma\)的产生式（将其对\(A_j\)展开，如果展开式还是这样的产生式就再展开直到不是），但这要求输入的文法没有环（即必须是一个DAG），而且输出可能包含\(\epsilon\)产生式。

  问：如何消除环？如何消除\(\epsilon\)产生式？

• 提取左公因子（关于同一个非终结符号的两个或多个不同产生式的右端如果有同样的前缀，改写该组产生式，把公共前缀提出来作为新的产生式）

自顶向下语法分析

• 对于消除了左递归产生式后的文法，可以通过回溯法来解析，但是太慢
• 定义\(FIRST(A)\)（可以作为非终结符\(A\)的第一个符号的终结符）和\(FOLLOW(A)\)（可以作为紧接\(A\)之后第一个符号的终结符）
• LL(1)文法：对于关于任意\(A\)的两个产生式\(A\to \alpha\vert\beta\)，\(FIRST(\alpha)\)和\(FIRST(\beta)\)交集为空，且若\(\epsilon\)在\(FIRST(\beta)\)中则\(FIRST(\alpha)\)和\(FOLLOW(A)\)交集为空（反之亦然）。LL(1)足以满足大部分程序设计语言的构造；左递归文法和二义性文法都不是LL(1)的。
• LL(1)文法可以不用回溯，因为只需往前看一个符号（单词）就能知道选择哪个产生式。
• 如何分析一个LL(1)文法：
  • 先构造一个预测分析表\(M\)，其中\(M[A,a]\)表示如果当前所在的非终结符是\(A\)且下一个输入符号（单词）是\(a\)要选择的产生式
  • 给定一个句子，把该表看成一个状态转移表来根据当前的符号（单词）来决定每次选择的产生式，来生成语法分析树的结点

自底向上的语法分析

• LR(k)文法是LL(k)文法的真超集，因此能够表示比LL(k)更多的语言
• 不同的LR分析法具有相同的LR分析程序，不同之处在于用不同的方法构造出不同的ACTION表和GOTO表
• 几种LR分析法包括（表达能力从小到大排序；具体算法略过，只看了一下大体思路）：
  • LR(0)：见到\(FIRST\)集就移进，否则就归约。对于不能用LR(0)解析的文法却用LR(0)进行解析时可能出现移进-归约冲突（即在某个状态可以移进也可以归约）或归约-归约冲突（即在某个状态有多个归约选项）
  • SLR：见到\(FIRST\)集就移进，否则先看\(FOLLOW\)集，与\(FOLLOW\)集对应的项目归约，其它报错。
  • LALR：即LookAhead-LR，为了解决LR(1)太多状态的问题
  • LR(1)

语法制导翻译

• 实质就是在定义上下文无关文法的同时为每条产生式的定义一些属性值（例如对于一个数值结点可以有一个属性表示这个数值的类型，是整数还是浮点数什么的；还可以用来生成中间代码，即属性定义为中间代码字符串），然后在构建语法分析树的时候如何计算这些属性值（例如对分析树进行后序遍历）。
• 综合属性（简单来说就是由子节点定义的属性）、继承属性（简单来说就是从父节点或兄弟结点继承的属性）
• \(S\)属性（如果一个文法的所有属性都是综合属性）的文法可以通过LR分析器求解、\(L\)属性（如果每个属性要么是综合属性，要么只依赖于父结点或左边兄弟结点的属性值且不存在依赖环）可以通过递归下降法或LL分析器求解

相关

• 工具：YACC、Bison可以用来生成语法分析程序。用法是通过BNF语法定义出一个上下无关文法的语法结构，然后用c定义出各个AST（抽象语法树）的节点类型，然后在该语法结构中指定如果解析到对应的语法结构要怎样做（例如，怎样用c创建一个AST的结点）。详见这里。

中间代码生成

• 基本上就是通过语法制导翻译方法来产生中间代码，还要进行类型检查、地址回填（例如if-else语句生成的goto语句的地址无法即时给出，要处理了之后的语句才知道）等等操作

运行时刻环境

• 编译器维护一个运行时刻环境，提供诸如自动垃圾回收（如Java）等的机制来管理虚拟内存。

代码生成和优化

• 主要解决问题：指令集选取、寄存器分配、指令排序
• 基本流程：把中间代码转化为基本块，以基本块为结点建立控制流图。
• 两种优化方法：
  • 局部优化（适用于单个基本块）：如公共子表达式消除、死代码消除、常量折叠、代数等价变换
  • 全局优化（整个控制流）：如活性分析（例如连续的多次赋值只有最后一次有效）
• 寄存器分配：重写中间代码使得使用的寄存器不多于目标系统的寄存器个数。方法：建立一个无向图，顶点为中间代码变量，边表示其两个端点会在同一时刻处于活的状态；转化为图着色问题。这是一个NP-Hard问题，现实中常用一些启发式方法。

参考资料

• 自动机理论：https://zhuanlan.zhihu.com/pikanote