自动机理论（Automata）

本章属于词法分析专题。总览见 词法分析；词法用正则描述见 正则表达式；如何从正则构造自动机见 构建自动机。

自动机的本质是一个有向图，节点为状态编码，而边为输入符号，自动机根据当前节点和对应的输入符号寻找状态转移，从而在进入到不同状态时触发对应动作。而根据自动机的确定性与否，又可以划分为确定有限自动机（DFA）和非确定有限自动机（NFA）。对于DFA而言，每个状态对于一个输入，有且仅有一个目标状态，即任意节点A连出的边中，不会有重复的符号。而对于NFA，则可以有多个不同的目标状态，即一个节点，可以有多个连出边都是同一个符号。

DFA和NFA其实功能上是等价的，因为任意NFA，都可以通过子集构造法来转换到一个对应的新DFA上，当然，往往新构造的DFA会比原NFA大很多，甚至有时是指数增长的。子集构造的具体步骤见 构建自动机；多规则场景见 自动机合并；状态压缩见 自动机最小化。

有限状态自动机（FSM）

有限状态自动机（FSM）是一种抽象的计算模型，它包含一组状态和一组能够在这些状态上执行的转移。在任何时刻，自动机都处于其中的一个状态，而它所处的这个状态，称为当前状态。自动机根据输入的转移，从一个状态转移到另一个状态。这个转移可以是确定的，也可以是不确定的。自动机的状态和转移可以用图来表示，这种图称为状态图。

初始态 即自动机开始的状态，如下面示例中1状态。

终结态 自动机的结束状态，在图中用双圆圈表示，遇到终结态，自动机可以结束。如下图中4状态。但要注意，不同的自动机匹配模式有可能并不会一遇到终结态就立即结束，有时会选择当自动机无法进行转移，并且当前处于终结态时才结束，以获得可行的最长匹配。

下图左被称为自动机的状态转移图，我们通过指针上面标记的符号，来确定拿个符号下，转移到哪个目标状态。例如，下图就显示了1状态在遇到a输入后转移到了2状态。下图右被称为自动机的状态转移表，我们通过表格中的行和列来确定下一个状态。例如，下表第二行就显示了2状态，当输入列是b时，会转移到3状态。

一般来说，有限状态自动机有两种类型：

• 确定性自动机：在任何状态，自动机都只有一个转移可以选择，这种自动机称为确定性自动机（DFA）。
• 非确定性自动机：存在一个状态，自动机在遇到一个输入时有多个转移可以选择，这种自动机称为非确定性自动机（NFA）。

这两种自动机都非常常用，上面的示例就是一个典型的DFA，因为其每个状态遇到一个输入都只能转移到一个状态。如果是NFA，在状态转移表中，一个单元格中会有多个不同可能的转移到的目标状态。

词法分析器通常跑的是 DFA（或等价实现）。如何从 正则表达式 得到它，见 构建自动机；回到总览：词法分析。

下推自动机 (PDA)

有限状态自动机只有有限个状态，因此记忆能力也是有限的：它认得出「固定模式」的串（正则语言），却认不出需要「数清配对」的结构。经典反例是 $\{a^n b^n \mid n \ge 0\}$：任意长的一串 a 后面必须跟同样多的 b。DFA 无法为每一个 $n$ 单独记一笔账——状态再多也是常数，而 $n$ 可以任意大。括号任意嵌套同理：((())) 合法，)( 不合法，中间要记得「还欠几个右括号」。

下推自动机（Pushdown Automaton，PDA） 就是在有限状态之上再加一个栈：控制仍由有限状态转移驱动，但每一步还可以根据栈顶符号决定做什么，并弹出 / 压入若干栈符号。栈深度不封顶，于是就能记住任意长的「未匹配前缀」。直观配置是三元组：

• 当前控制状态
• 尚未读完的输入
• 当前栈内容（栈顶朝上）

转移往往写成：在状态 $p$、读输入 $a$（也可 $\varepsilon$ 不读）、栈顶为 $X$ 时，转到状态 $q$，并把栈顶换成串 $\gamma$（$\gamma=\varepsilon$ 表示只弹不压）。

小例子：识别 $a^n b^n$。 思路是「先把每个 a 记在栈里，再靠 b 一一销账」：

1. 读 a：压入一个标记（比如 A），留在「还在读 a」的状态。
2. 读到第一个 b：转入「开始销账」；之后每个 b 弹出一个 A。
3. 输入读完且栈空（或只剩约定的栈底符）则接受；中途栈空却还来 b、或还剩 A 却已无输入，则拒绝。

括号匹配同理：遇 ( 压栈，遇 ) 弹栈；结束时空栈才合法。FSM 做不到「任意深度」的配对，PDA 可以。

和编译前端的对应关系很直接：

阶段	语言类（直觉）	机器直觉
词法分析	正则	DFA / NFA（无栈）
语法分析	上下文无关	PDA（有分析栈）

真正的编译器里，很少手写一台抽象 PDA，而是用 LL / LR 的表驱动过程：分析栈里压的是文法符号或状态，移进、归约就是在对栈做约定好的操作。细节见 LL、LR。

补充一句：非确定 PDA 与上下文无关文法能力相当；确定 PDA 更弱一些。语法分析器追求的是确定性的、可高效实现的一类文法（如 LL(1)、LALR），那是语法章的主题；简单来说词法分析靠有限状态机，语法分析则需要栈。