有限自动机（进阶）
复习
- 正则表达式：用组合规则描述词法模式
- 手写词法分析器：本质是一个状态机
- 语言与文法：用规则描述语言
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 有限自动机是只有有限状态的识别机器
- 它逐字符读入，依据当前状态转移
- 正则表达式可以机械地转成有限自动机
- 它正是“自动生成词法分析器”的原理
正文
上一章说，正则表达式很适合描述词法规则。可正则毕竟是“描述”，计算机要真正识别一个字符串符不符合正则，还得把它变成一台能运转的机器。这台机器，就是有限自动机（finite automaton，FA）。
一台只有有限状态的机器
有限自动机由几样东西组成：
- 一组状态（数量有限）
- 一组转移规则：在某个状态读到某个字符，就跳到某个状态
- 一个起始状态和若干接受状态
它从起始状态出发，逐个读入字符，按转移规则改变状态。读完整个输入后，如果停在接受状态，就说明这个字符串“被接受”，属于所描述的语言。
这也解释了它名字里的“有限”：它只能靠有限个状态来“记住”信息，没有无限的记忆能力。 正因如此，它识别不了“任意嵌套的括号”——那需要数不清的层数，超出有限状态的表达力。
两类：DFA 与 NFA
有限自动机有两种常见形式：
- 确定性（DFA）：每个状态对每个字符，只有唯一一条转移，走法是确定的
- 非确定性（NFA）：同状态下、同一字符，可能有多条转移，甚至可以不读字符就“空跳”
直觉上 NFA 更灵活、更难直接执行，但有个漂亮的结果：任何 NFA 都能转成等价的 DFA。
从正则到自动机
更有意思的是：任何正则表达式，都能机械地转成一台有限自动机。 连接、选择、重复这些运算，各自都有对应的构造方式；NFA 再转成 DFA，就得到一台可以直接运行的识别机器。
这条流水线的意义非同小可：你只要把词法规则写成正则，程序就能自动生成词法分析器。 这比手写省力得多，也不容易出错。
于是，正则在“描述”和“执行”之间，由有限自动机架起了一座桥。一层负责声明规则，一层负责落实执行——又是分层的思路。
到这里，字符已经能可靠地变成一个个词法单元了。下一组，我们要回答更大的问题：怎样把这些词，组织成有结构的语法树？
思考题 1
有限自动机为什么叫“有限”？它最多能记住多少信息？
思考题 2
把正则表达式转成有限自动机，对自动生成词法分析器有什么意义？
小结
知识点
- 有限自动机由有限状态、转移、起始与接受状态构成
- 它逐字符读入并转移，按结束状态判断是否接受
- 分 DFA（确定）与 NFA（非确定）
- 任何正则表达式都可转成等价的有限自动机
参考资料
- Wikipedia(zh)：有限自动机：有限状态的字符串识别机器
- Wikipedia(zh)：确定有限自动机：每个状态转移唯一的自动机
思考题答案（仅供参考）
思考题 1
“有限”指它的状态数量是有限的，因此能记住的信息也有限（本质上只是“当前处于哪个状态”）。它无法记录任意大的计数或任意深的嵌套，所以识别不了需要无限记忆的语言。
思考题 2
因为正则表达式可以机械地转成有限自动机，而有限自动机是可以直接执行的识别机器。于是只需把词法规则写成正则，程序就能自动生成词法分析器，省去手写，既高效又不易出错。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪