如果你正在啃词法分析这一块那么NFA和DFA这两个缩写迟早会出现在你面前。它们的全称是非确定有限自动机和确定有限自动机名字拗口但核心问题只有一个如何让程序在输入流上自动判断出“下一个字符序列属于哪个token”。上一篇笔记从正则表达式讲起讲了字符类、连接、选择和闭包但正则表达式说到底只是给人看的规则机器没法直接执行。这篇笔记我重点把NFA和DFA讲透它们是什么、有什么区别、怎么从正则表达式一步一步手工构造出来以及最终怎么落到能跑的词法分析器上。如果你正在学编译原理或者打算动手写一个小型词法分析器这篇应该能省你不少绕路的时间。1. 把词法规则变成一台能跑的机器1.1 现实场景为什么表达式没法直接吃输入我看过不少初学者的疑问既然正则表达式已经把标识符、数字、关键字的规则写清楚了为什么不直接在字符串上跑正则表达式非要引入NFA和DFA这两个看起来更抽象的概念原因其实很朴素。正则表达式描述的是“一类字符串长什么样”但它本身不告诉你“给你一个具体字符流时下一步该看谁”。比如规则letter(letter|digit)*它表达的意义是“字母开头后面跟任意个字母或数字”。可当你读到第三个字符、发现它不是一个合法字符时表达式并不会告诉你当前已经积累了多少、是否已构成一个完整token。真正要逐字符判断、记录接受位置、决定回退多少的是一台能在字符流上“跑起来”的机器。编译原理教材里给这台机器起了个名字有限自动机。有限自动机的基本构件特别简单若干个状态、状态之间的带标签转移边、一个开始状态、若干接受状态。它读一个字符就沿着对应标签的边换一个状态如果下一步没有可走的边这个输入片段就不再匹配如果最终停在某个接受状态就说明这个片段符合对应的词法规则。整个词法分析过程本质上就是把这个状态机放到输入流上面跑一遍。1.2 为什么流程偏偏是“先NFA后DFA”如果直接让人来画DFA大多数情况下是灾难。人脑很难同时维护“所有可能的分支、所有可能的嵌套重复”很容易漏掉一条边界情况。但反过来正则表达式本身有非常清晰的递归结构拼接、选择、闭包都是固定的组合方式。所以实际做法是先把正则表达式用一套机械规则展开成NFA这个展开过程几乎不可能出错然后用一个叫“子集构造”的算法把NFA变成DFA最后再把DFA最小化减少状态数。这个流程看起来绕了一点却非常符合工程习惯从容易验证的结构出发用机械算法逐步转换到高效可执行的结构。我当年刚接触时也想过“不转DFA直接让NFA跑不行吗”后来才明白问题不在能不能跑而在跑的代价。NFA每读一个字符可能需要同时存在于多个状态也就是要维护一个状态集合即便做了预处理直接解释执行NFA的成本也比DFA高一个量级。而DFA在任何时刻只有一个当前状态查表就能得到下一个状态这才是词法分析器真正希望得到的形态。1.3 这篇笔记适合谁看如果你正在准备编译原理考试这篇能把“构造NFA”“子集构造”“DFA最小化”这几个高频考点串成一条线如果你是想手写一个几百行的词法分析器这篇的构造过程、状态表、最长匹配代码骨架可以直接照着改哪怕你只是想把正则表达式背后的自动机原理弄明白我觉得本文也不会让你觉得在背定义。后面每一节我都会用同一个正则例子走完全程这样你拿一张纸一支笔就能跟着推一遍。2. NFA与DFA的本质差异确定性、ε边与状态数2.1 判定确定性的三条标准很多教材把NFA和DFA分开定义NFA允许一个状态对同一个输入符号有多条转移边也允许空转移DFA要求每个状态对每个符号最多只有一条边并且不允许空转移。这里“最多一条”很关键如果再严格一点有些教材要求“恰好一条”也就是要把所有没有定义的转移指向一个死状态。判断一个自动机是确定的我心里有三条问句同一状态、同一符号会不会出现两条不同的边存不存在不消费字符就能走的ε边每个状态下每个输入符号的行为是不是唯一的只要有一条回答“是”它就是NFA。这里的“唯一”指的是状态转移结果唯一不是路径唯一。DFA的好处在于运行时只需记录一个整数状态编号不需要开集合、不需要做并集运算所以几乎所有工业级词法分析器内部最终都是用DFA表驱动的。2.2 ε边到底代表了什么ε边是让初学者最容易懵的地方。它的名字叫“空转移”意思是从某个状态可以不读任何字符直接跳到另一个状态。你完全可以把它理解成“免费的通道”程序走到某个状态后先通过这些通道把能到达的状态全部收集起来然后再看真正的输入字符。为什么需要ε边因为在构造NFA时选择、拼接、闭包这些“结构性动作”都需要一些不占字符的连接线。比如a|b要对同一个开始状态引出两条边分别标a和b但状态本身并不知道自己接下来要分支还是要汇合于是用ε边搭出“分叉”和“汇合”的骨架。用生活里的例子说ε边就像地铁换乘通道换乘通道本身不消耗你的“里程”但它决定你能到达哪些站台。2.3 一张表看清NFA与DFA的差异维度NFADFA状态转移同一符号可有多条边允许ε边同一符号最多一条边不允许ε边运行方式可能同时处在多个状态需要维护状态集合每个时刻只有一个当前状态接受条件存在一条从开始到接受状态的完整路径即可当前状态恰好是接受状态状态数由构造规则直接生成通常较大可能比NFA少也可能指数级扩大执行效率需要处理状态集合较慢单状态查表很快构造难度可从正则表达式机械化展开直接人工构造容易出错这张表里最容易误导人的是“DFA状态数可能比NFA少也可能指数级扩大”。很多人以为子集构造一定让状态变多其实不一定。比如本文后面示例a(b|c)*dNFA有9个状态转成DFA后只有4个状态最小化后只剩3个。但某些嵌套闭包、复杂交集类正则会触发指数膨胀这是自动机理论的经典结论。实际工程中遇到状态爆炸多数来自过度复杂的正则写法而不是算法本身的问题。2.4 常见的三个误解第一个误解NFA比DFA表达能力更强。不对。正则语言、NFA、DFA三者描述的语言类完全一样。差别只在效率和构造便利性不在表达能力。第二个误解NFA运行时要“回溯”像带记忆的搜索算法。其实NFA的语义是“并行状态集合”不是回溯。你要是用递归回溯去模拟NFA最坏情况确实会指数时间但正规做法是每次读入符号后对状态集合做并集这样是线性时间。第三个误解DFA一旦画出来就能直接当词法分析器。还差得远。词法分析器里多个规则并存、最长匹配、保留字优先级、错误恢复这些都是在DFA之上额外处理的。第5节我会详细讲这部分。3. 从正则表达式到NFA经典三规则的逐步构造实战3.1 单字符、拼接、选择、闭包的基础片段NFA构造的核心思想是递归每个正则子表达式对应一个小的NFA片段片段只有一个入口和一个出口。这样一来无论表达式嵌套多深都能像搭积木一样一层层组合。基础规则有四条我习惯叫它“四件套”。单个字符a画两个状态入口通过标记为a的边连到出口。拼接r1 r2把r1的出口和r2的入口用一条ε边连起来。整体入口是r1的入口整体出口是r2的出口。选择r1|r2新建一个入口状态分别用ε边连到r1的入口和r2的入口再把r1的出口和r2的出口分别用ε边连到一个新建的出口状态。闭包r*新建入口状态和出口状态。入口状态用ε边连到新出口表示“直接跳过整个子表达式”入口状态同时用ε边连到r的入口r的出口用ε边连回r的入口表示循环r的出口还用ε边连到新出口表示“循环若干次后退出”。如果正则里有可选符号?可以把r?当成“空串与r的选择”也就是构造一个选择片段其中一个分支是空串不过实际做的时候我会直接画成“跳过或进入”两个ε边思路都是等价的。这四件套里最容易漏的是闭包的两个出口一个是给“循环继续”用的回头ε边一个是给“循环结束”用的退出ε边。画漏任何一个*的语义就错了。3.2 逐步示例a(b|c)*d为了不让构造过程停留在抽象规则上我挑一个稍微复杂点的例子a(b|c)*d。意思是开头必须有一个a中间可以有任意多个b或c最后必须有一个d。空串形式的(b|c)*允许存在所以ad也在这个语言里。第一步构造单字符a的片段。我记作状态S0到S1边上的标签是a。第二步构造选择b|c。新建入口S2新建出口S5。S2通过ε边分别连到S3和S4S3有b边连到S5S4有c边连到S5。这里有个细节S3和S4是“内部状态”S5是选择的出口不是闭包最终出口。第三步构造(b|c)*。在刚才选择片段的外面包一层闭包骨架新建入口S6和出口S7。S6用ε边连到S2S6用ε边直接连到S7S5用ε边连回S2S5用ε边连到S7。这样(b|c)*的入口就是S6出口就是S7。第四步把a片段和(b|c)*拼接。按拼接规则S1用ε边连到S6。第五步构造d片段与前面的整体拼接。这一步在草稿上最容易乱。我习惯把(b|c)*的出口S7当成拼接点S7用d边直接连到新接受状态S9。严格按四件套来说也可以新建一个d子图的入口再用ε边把S7连过去。两种写法等价示例里直接连线更省状态。最终状态表如下状态ε转移abcdS0无S1无无无S1S6无无无无S2S3, S4无无无无S3无无S5无无S4无无无S5无S5S2, S7无无无无S6S2, S7无无无无S7无无无无S9S9无无无无无开始状态是S0接受状态是S9。3.3 构造完之后的检查清单画完NFA后别急着转DFA先做三件检查。第一确认每个正则子表达式都有“一进一出”。入口多了说明某个拼接边漏了出口多了说明某个选择或闭包没有统一汇合。第二检查闭包的退路。S6必须能直接到S7否则(b|c)*无法匹配空串。S5必须能回到S2否则无法循环第二次。第三用几个短字符串在图上走一遍。我当时会拿ad、abd、acd、abdcd这四个测试串手动模拟。ad应该走“跳过闭包”的路径abd应该走“进入闭包一次后退出”的路径。走不通就赶紧回头查ε边。如果你在纸上画建议把ε边用虚线、字符边用实线不然状态一多虚线连成一片自己都看得头昏。我早期画图时吃过这个亏后来坚持两种线型分开排查速度快很多。4. 从NFA到DFA子集构造法的表格演算全过程4.1 ε闭包其实就是“原地可达”子集构造法这个名字听着吓人操作起来就是一个反复计算状态集合的过程。两个操作要先搞明白。ε-closure(T)从集合T中任意状态出发只靠ε边能到达的所有状态的集合。可以理解为“不读任何字符站在原地能换到的所有站台”。move(T, c)从集合T中任意状态出发只走标签为c的边一步能到达的所有状态的集合。子集构造的核心就是反复执行对当前DFA状态它其实是NFA状态集合和每个输入符号先做move再做ε-closure结果就是下一个DFA状态。如果一个DFA状态中至少包含一个NFA接受状态那么这个DFA状态就是接受状态。实际计算时ε闭包我习惯写成一边入栈一边收集的算法。下面给一段我常用的思路示例def epsilon_closure(states): stack list(states) closure set(states) while stack: s stack.pop() for t in eps_table[s]: if t not in closure: closure.add(t) stack.append(t) return closure闭包计算的本质是一个深度优先遍历遍历的只可能是ε边所以复杂度不高。真正容易犯错的是忘记把初始状态自己也放进闭包结果里。ε-closure({S0})不等于“从S0出发能到达的别处”必须包含S0本身。4.2 子集构造的伪代码如果你打算以后用代码实现可以先保存下面这段流程。它非常短但细节都在顺序里def subset_construction(): start epsilon_closure({nfa_start}) dfa_states [start] marked [False] while not all(marked): i marked.index(False) marked[i] True current dfa_states[i] for sym in alphabet: nxt epsilon_closure(move(current, sym)) if not nxt: continue if nxt not in dfa_states: dfa_states.append(nxt) marked.append(False) transitions[(i, sym)] dfa_states.index(nxt) return dfa_states, transitions这里有个细节值得多说一句dfa_states是一个集合的列表集合本身不可哈希所以我用“是否已在列表里”来判断而不是直接放进字典。实际工程可以把每个状态集合编码成位图或排序后的字符串这样查找更快。我第一次写的时候没注意这一点结果每次判断“新状态是否已经存在”都得做全表扫描状态一多就慢得离谱。4.3 手工跑一遍转移表继续用上一节的NFA。初始DFA状态来自ε-closure({S0})结果只有{S0}记为T0。从T0读入amove({S0}, a)得到{S1}ε-closure({S1})从S1出发经ε边到S6再到S2和S7S2又到S3、S4。所以得到状态集合{S1, S2, S3, S4, S6, S7}记为A。从A读入b状态里能走b的只有S3得到{S5}再算ε-closure({S5})从S5可以回到S2再由S2到S3、S4也可以直接到S7。结果{S2, S3, S4, S5, S7}记为B。从A读入c只有S4能走c到S5闭包结果和上面完全一样仍然是B。从A读入d只有S7能走d到S9ε-closure({S9})是{S9}记为C。继续处理B。B中能走b的仍然是S3能走c的仍然是S4闭包后都回到B。B中能走d的仍然是S7闭包后到C。最后处理C。C里只有S9没有出边所以所有输入的move都为空集按约定不再生成新状态。完整DFA转移表如下DFA状态包含的NFA状态abcd是否接受T0{S0}A死死死否A{S1,S2,S3,S4,S6,S7}死BBC否B{S2,S3,S4,S5,S7}死BBC否C{S9}死死死死是这里“死”意味着没有转移边。DFA里的缺失转移在词法分析中有着非常重要的用途它表示当前识别片段到此结束需要回溯到最近一次接受位置。很多书本会把缺失转移统一画成一个死状态我正在做的时候发现手工演算保留缺失转移反而更直观因为它能直接映射到代码里的break条件。4.4 接受状态判定和死状态接受状态的判定不看DFA状态叫什么只看它对应的NFA状态集合里有没有接受状态。C包含S9所以是接受状态。A和B都不包含S9所以不是。死状态要不要显式画出来取决于应用场景。画出来DFA更完整、更符合教科书定义不画在词法分析器里反而方便表示“匹配失败、立即回退”。我自己的笔记里会写下一条经验考试和手工演算时建议保留死状态因为后续最小化算法要对所有符号做划分缺失转移很容易让人漏算工程实现时则倾向于不显式建死状态用None或-1表示无转移。两套思路没有对错但要清楚自己在做什么。5. DFA最小化与词法分析器落地状态表、最长匹配和调试5.1 划分细化哪些状态可以合并刚才得到的DFA有4个状态但直觉告诉我A和B太像了它们除了b、c输入时转到的目标不同其实A转到BB转到Bd输入时都转到C。能不能合并关键看行为是否等价对任意剩余输入串两个状态最终会落到同样类型的接受或非接受情况。最小化算法的起点很简单把所有状态分成两组一组是接受状态一组是非接受状态。本例就是{C}和{T0, A, B}。然后反复做细化。对每个分组观察组内每个状态在某个符号下的转移目标属于哪个分组。如果组内状态对同一符号的转移目标分布不一致就把这个组拆开。第一步看非接受组{T0, A, B}在a下的转移只有T0有到A的转移A和B都没有a转移。这明显不一致于是把T0单独拆出来剩下{A, B}。第二步看{A, B}。对bA转到BB也转到B都在同一组对c同样如此对d都转到C。一致所以A和B可以合并成一个状态M。最终最小化DFA状态abcd是否接受T0M死死死否M死MMC否C死死死死是这个结果完全符合a(b|c)*d的语言直觉先等一个a然后在b/c上循环任意次最后等一个d。状态从4个降到3个。手工做划分细化时最大的坑是忘了一开始就要划分“接受/非接受”。没有这个初始划分后续合并会把接受状态和非接受状态混在一起语义就崩了。5.2 从DFA到词法分析状态表和最长匹配DFA画好、最小化完成接下来就是把它变成词法分析器的核心驱动结构。最常见的形式是一张二维状态转移表行是DFA状态列是输入符号或字符类单元格是下一个状态编号。需要接受信息时再给每个状态附一个“是否为接受状态、对应哪个token类型”的标记。扫描循环有一个关键机制叫“最长匹配”。简单说词法分析器不能看到一个可接受状态就立刻停下因为当前已匹配的片段可能只是一个更长合法token的前缀。比如关键字if和标识符ifx放在一起输入ifx时读完i、f后状态可能是关键字的接受状态但接着读到x会发现还能继续走。如果立即停止就会错误地把if当关键字留下孤零零的x。正确的做法是记录“最近一次经过接受状态的位置和token类型”一直走到没有转移为止然后回退到那个位置。这个循环的骨架大致如下pos 0 while pos input长度: state 开始状态 last_accept 无 i pos while i input长度: state 转移(state, input[i]) if 无转移: break if state 是接受状态: last_accept i 1 记录当前token类型 i i 1 if last_accept 为空: 报告词法错误 输出从 pos 到 last_accept 的token pos last_accept这段代码里最容易写错的是边界的开闭。last_accept记录的是“接受位置之后的下标”而不是最后一个字符的下标。我用i1而不是i是为了让切片input[pos:last_accept]直接包含所有已接受字符。如果你喜欢用“最后一个字符下标”就要在切片时做1两种约定都行但必须全文统一否则会莫名其妙多吞一个字符或少吐一个字符。5.3 多token与保留字冲突实际词法分析器不可能只识别一个正则。标识符、数字、运算符、关键字全都对应各自的DFA。工程设计上通常把多个DFA合并成一个大的DFA每个状态可以同时属于多个token类型。比如匹配到if时该状态可能既是标识符DFA的接受状态又是关键字token的接受状态。出现这种冲突时词法规则决定优先级关键字优先于标识符。处理保留字还有一个更常见的做法先把所有标识符统一识别为“标识符token”然后在返回前查一张保留字表把if、while、return这些字符串映射成关键字token类型。这种做法简单直接状态数也不会因为关键字数量增加而膨胀。两种方案都能工作取舍点是如果你构建的是合并大DFA状态数和维护成本都会上升如果你用查表方案词法规则里几乎不用为每个关键字单独画分支。我在小型项目里更倾向后者。另一个容易出问题的是空白符和注释。它们严格来说也算合法token只是不需要往外传递。处理方式是在主扫描循环里跳过这类token。需要注意的是跳过逻辑不能破坏最长匹配否则一个注释结束符号可能被误读成普通运算符。我踩过这个坑注释结束符在当前DFA里也有对应转移跳过逻辑判断“碰到注释开头就一路找结束符”结果把结束符后面的一个合法字符也吞了。后来统一改成“先按最长匹配规则识别整个token再判断类型是否是空白/注释是则丢弃”问题就消失了。5.4 调试经验让自动机可视化手算NFA和DFA是一回事写成代码又是另一回事。代码跑起来状态多了以后直接在终端打印转移表非常反人类。我调试时最常用的办法是输出文本格式的点图描述文件然后交给可视化工具渲染成图形。格式不难每个状态一个节点每条转移边一行ε边和字符边用不同样式区分。这样一眼就能看出是哪条边漏了、哪个状态被错误合并了。针对子集构造我还会额外打印每个DFA状态对应的NFA状态集合把它一起写进节点标签里。原因很简单只看编号看不出问题看到A {S1,S2,S3,S4,S6,S7}就能快速核对闭包是否算漏。后来我把这个输出习惯带到了所有自动机相关代码里排查效率提升非常明显。最后分享一个我自己反复强调的小经验NFA和DFA学的时候不要只背定义、只跑算法一定要拿一个手工例子从头推到尾。例子不用复杂像digit、a(b|c)*d这类就够。多推两遍之后再看词法分析器生成的报错信息、状态转移表、为什么某个输入被回退到某个位置很多逻辑会自动在脑子里连起来。到了这一步编译原理里这块比较磨人的骨头才算是真正啃下来了。