1. NFA和DFA是什么编译原理进行到词法分析阶段逃不开两个概念NFA与DFA。简单说它们都是用来描述词法规则的形式化工具但二者的“性格”差别极大。DFA全称是确定性有限自动机一个状态在遇到一个输入符号时下一跳是唯一确定的处理起来非常直白NFA全称是非确定性有限自动机同一状态下同一个输入符号可能跳到多个状态还可能存在不需要任何输入就能跳转的ε转移执行逻辑上天然带“分叉”。这个不确定性带来一个现实问题如果拿NFA直接做词法分析器每读一个字符可能要沿着多路分支去尝试匹配效率完全不可控。因此实际工程里几乎不可能直接拿NFA去跑词法分析而是先构造NFA再把它转换成等价的DFA让每条路径唯一化。等价的含义是两者识别的语言完全一致即能接受的正规式集合完全相同只是DFA的每个状态变成了原来NFA的一个状态集合这个集合被称为“子集”。从正规式到DFA的完整链路是这样的先把正规式解析成一棵语法树再从语法树构造NFA然后通过子集构造算法把NFA转为DFA最后做DFA的最小化压缩。这个流水线里NFA本身不直接面对输入串它是中间产物承上启下。很多人初次学到这里觉得绕是因为没有站在“编译器到底怎么用这几个东西”的角度去理解。词法分析器的目标其实只有一个给定一个输入字符串快速判断它属于哪个token类型比如标识符、关键字、数字、运算符并输出token流。NFA和DFA就是用来承载这个判断逻辑的自动机模型。我给初学者的建议是先抛开教科书里的证明细节把NFA和DFA想象成两套“状态转移图”。NFA像是一张可以走岔路、甚至凭空跳转的地图DFA则是每条路都笔直、每个路口只有一条出口的公路网。这两套图描述的是同一种语言只是表达方式不同DFA更适合机跑NFA更适合人写规则。理解了这一点后面再看子集构造、最小化这些操作就是在讲“怎么把岔路图改成单行道公路网然后顺手把冗余路段删掉”。2. 为什么要先构造NFA再转DFA不直接生成DFA2.1 正规式到NFA的构造是“翻译”不是“设计”接触过正则表达式的人都能感受到写一个正则容易但要直接从正则推导出一个DFA的状态转移表思维负担非常大。因为DFA要求每个状态下每个输入符号都有且仅有一个转移目标但人在写规则时习惯用并集、可选、重复这些灵活的语义这些语义几乎天然就是NFA式的。比如a|b人读起来是“要么a要么b”而转化成自动机就是两条平行的路径这就是一个标准NFA结构。再比如a*表示零个或多个a在NFA里体现为一条从终态回到初态的ε回边。这种结构如果直接设计DFA光是把复杂的嵌套语义拆解成无歧义的单一路径就够折腾一阵子了。所以正规式到NFA的构造方法比如Thompson构造法本质上是机械化的“翻译”步骤。它把每个正规式子结构对应成一个小子图再通过ε转移把这些子图拼成一个完整的NFA。这个过程不需要思考优化完全是按语法结构递归搭积木。四个基本结构的拼法如下连接就是首尾相接并集就是引入一个新开始状态分别用ε跳转到两个子图闭包就是在新子图外面包一层ε回边单个字符就是两个状态之间连一条标着该字符的边。这里有个实用经验写正规式时把结构拆成“字符、连接、并集、闭包”四种原子操作心里就有一本“翻译手册”直接照着拼NFA比苦想DFA省力得多。而且Thompson构造法有个很好的性质——每个新增状态至多有两出边整个NFA状态数和边数与正规式长度线性相关不会爆炸这为后续子集构造提供了健康的输入。2.2 NFA更能保留正则语义的可读性从可维护性的角度说NFA也更贴近人的思维模型。一段正规式如果直接转成DFA状态转移表可能面目全非很难回溯“这到底对应原正则的哪一段语义”。而NFA的子图结构和正规式基本是一一对应的开发者排查问题时可以拿着NFA图对照原正则去检查哪里多了一条边、哪里少了一个状态一目了然。我实际做过一个词法分析器里面有几十个token规则维护时最怕的就是某个状态跳错了。如果直接维护DFA表改一个规则可能要连带改好几个状态。但如果保留NFA作为源模型改完正则重新跑一遍转换流程DFA自动更新人就省心了。这也是很多词法分析器生成器比如lex家族的实现思路内部的工作原理源文件写正则生成器内部构建NFA再统一转成DFA用于匹配。用户看到的接口是正则内部跑的是压缩后的状态机分工清晰。有意思的是还有一类工具比如部分正则引擎会反其道而行直接用优化过的NFA做匹配利用回溯或并行模拟来处理不确定性。但这类方案适用场景有限处理简单的词法规则时性能可能不错一旦规则多、输入长回溯代价就很难控。主流编译器的词法分析器仍然是“NFA构型、DFA执行”这条稳妥路线。2.3 子集构造的“集合语义”能天然处理歧义NFA转DFA的核心算法叫子集构造subset construction思路是把NFA上某个状态在某个输入符号下能抵达的所有状态“打包”成DFA的一个新状态。这个打包动作天然处理了NFA的不确定性多个可能的分支在DFA层面被合并成一个明确的集合不会再出现“同一输入走两条路”的问题。从词法分析角度想这种集合语义还有一个额外的好处真正匹配token时如果NFA中存在多个可接受路径比如某个前缀既能被认成关键字又能被认成标识符压缩成DFA后状态里会同时包含多个接受态我们可以在这些接受态之间定义优先级比如“关键字优先于标识符”。这个处理手法在后续章节讲词法歧义消除时会反复遇到也是工程师必须掌握的实战技巧。所以先NFA后DFA并不是“绕远路”而是把“人的表达”和“机器的执行”之间的鸿沟用两个各擅其场的中间层给填平了。一条从正则到状态机的工程流水线每个环节都有明确的职责缺一则另一侧的工作会变得异常吃力。3. 核心实操NFA转DFA的子集构造全过程3.1 ε闭包(move)和子集构造的基本运算子集构造依赖两个基本函数ε闭包ε-closure和move。理解透这两个函数整个算法就稳了一半。ε闭包的定义是从一个状态集合T出发沿着所有ε边能到达的状态统统并进来包括T自身。它的作用是把“不消耗任何字符就能发生的跳转”全部吸收进当前集合。比如某个NFA状态s有一条ε边指向tt又有一条ε边指向u那么closure({s}) {s, t, u}。这个闭包计算的实现通常用栈或队列做图的深度/广度遍历代码量很小。move函数的定义是从状态集合T出发消耗一个输入符号c所有能到达的状态的集合。注意move不做ε扩展它只找出“直接吃下c字符的下一跳”。实际操作时标准的顺序是先根据当前状态集合计算move(T, c)得到下一跳集合再对这个集合求ε闭包两者合并就是D状态在输入c下跳转的目标状态。我以前入门时写代码容易搞错一个顺序先求闭包再move。这么做会把ε边跨过字符边导致本该等一个具体字符的地方被空跳偷跑了。严谨的步骤永远是“先move后closure”。当然如果整个NFA压根没有ε边那么这个顺序问题就不存在但正规式构造出的NFA几乎不可能没有ε边所以这个坑得非常留意。3.2 一个实例能识别“a|b*c”的NFA如何转DFA我们用一个小例子完整走一遍这样比干背算法步骤要有感觉得多。假设要识别的正规式是 a|b*c。按Thompson构造法先分别构造a子图、b子图和c子图再用并集和连接把它们拼起来。得到的NFA大致有7个状态。为方便叙述设开始状态 S0经过ε可跳到 a 子图的开始也可跳到 b* 子图的开始b* 子图内部S1b循环、S2可ε跳到c子图开始a 子图从S3吃a到S4c 子图从S5吃c到S6S6为最终接受态同时整个NFA最终状态也由此汇合现在开始子集构造。先计算closure({S0})把所有从S0出发的ε边走一遍得到的集合包含{S0, S1, S3, S5}记作D0。这还没完S1后面有到S2的ε边S2又是到S5的ε跳板但S2本身也要进集合所以再扩一轮closure({S0})实际为{S0, S1, S2, S3, S5}。初学者经常在这里漏算S2导致后面状态数不对。看一下输入符号a从D0中各状态出发吃a能到的地方只有S3的a边目标是S4于是move(D0, a){S4}再求closure({S4})没有ε边结果就是D1{S4}。D1是接受态吗不是因为S4不是终态终态是S6。再看输入符号bD0里S1有b回边吃b后回到S1所以move(D0, b){S1}再做closure得到{S1, S2, S5}记为D2。这个集合里的S5是c子图的开始但此时还没吃c所以不能被误判为接受态。很多初学的人看到S5附近有路就以为能接受这不对必须吃到c到S6才算接受。再算输入符号cD0中S2有ε到S5、S5吃c到S6注意移动过程是从S2没吃任何字符就到S5再由S5吃c到S6所以move(D0, c){S6}closure后还是{S6}记为D3D3是接受态。接着对D2按同样的方式计算吃b回到S1再closure回D2自己形成一条回边吃c则从S2/S5走c边到达S6得到D3。最终这个DFA只有四个状态状态转移关系如下DFA状态a输入b输入c输入是否接受D0D1D2D3否D1———否D2—D2D3否D3———是对比NFA转DFA前后的差异NFA在S0处眼见着有去a、b、c三条“候选道路”执行时必须都试一遍DFA的D0遇到这几个字符则各走各的唯一出口完全确定。这就是“编译”带来的效率提升。3.3 实操中的状态标记和终止条件真正实现子集构造时要维护一张“状态对应表”记录D状态编号和它对应的NFA状态集合。算法开始时初始化一个队列把closure({NFA开始状态})塞进去作为第一个D状态然后循环取出队列头的D状态逐个对字母表中的每个符号执行move与closure如果得到的新集合从未出现就新创建一个DFA状态记录转移边并把它加入队列如果已经出现过则只补记一条转移边不再重复创建。终止条件是队列为空意味着所有可达DFA状态都已经被“展开”过一遍。很多人问会不会出现无限循环不会因为NFA状态数量有限D状态集合又是NFA状态集合的子集最多只有2的n次方种组合n为NFA状态数扩张一定会在有限步内停。实际运算时由于正规式结构约束状态数通常远小于这个上界不必太紧张。还有一个容易被忽略的细节哪些DFA状态是接受态规则是凡DFA状态对应的NFA状态集合里包含原NFA的接受态该DFA状态就是接受态。比如前面的D3集合包含S6所以D3是接受态。如果原NFA有多个接受态那么只要集合里出现任意一个这个DFA状态就接受。提示子集构造结果里可能出现“带接受态但不是最终输入结束状态”的情况例如集合既包含某token的终态、又能继续通过字符走到别的状态这在词法分析中叫“最长匹配”问题。后续章节讲词法规则优先级时这种状态会被特别处理一般通过记录最近一次接受的输入位置来解决。4. DFA最小化把状态机压缩到最精简4.1 为什么要做最小化压缩带来什么收益子集构造得到的DFA往往不是最小的里面可能存在大量行为等价的状态。两个状态如果从任意输入串出发要么都接受、要么都拒绝且分别到达的下一状态也互为等价那么它们可以被合并成一个状态。这个合并过程就是DFA最小化也称化简最经典的实现手段是Hopcroft算法也是一个划分细化算法因效率高被广泛使用或教科书上更常见的Moore划分法。最小化的收益有两层第一是节省存储空间状态少了转移表就小。词法分析器通常常驻内存、每次编译都要加载状态数从几百压到几十直接减少内存占用。第二是加快匹配速度虽然DFA每个状态单次跳转已经是O(1)但状态多了会放大缓存miss概率减少状态数对实际运行时间也有微弱但可测的改善。这里有个容易混淆的概念最小化只压缩等价状态绝不改变DFA所识别的语言。也就是说最小化前后的DFA接收的字符串集合完全相同只是地图上少了几条重复路段。这和子集构造不同子集构造是在改变自动机形态最小化是在删冗余。4.2 划分法的运作流程从接受态开始逆推划分法的直观思路是先把所有状态分成两组接受态一组、非接受态一组。这两个集合显然是可区分的一个接受空串一个不接受后续再逐步细化。细化规则是如果两个状态在同一个组里但它们在某个输入符号c下跳转到的状态属于不同的组那么这两个状态必须分开。不断重复“按转移目标划分”的过程直到没有状态组能被进一步细分。以前面得到的四状态DFA为例。全体状态先划分为两个组G1{D0, D1, D2}非接受G2{D3}接受。看G1内部D1在所有输入上都无转移按正规式语义D1吃不到任何继续前进的字符也没有接受标记这跟D0、D2显然不同。D0吃a去D1、吃b去D2、吃c去D3D2吃b回自己、吃c去D3不收a。按字母表逐符号比对D0和D2在字母a上的行为不同D0有a边D2没有且a边的目标D1属于非接受组与D2“无转移”不同所以二者至少应当分开。D0和D2再比b、c时各自跳转目标都在同一大组里看不出区别但由于a行为已经不同划分时就会把它们拆开。这里多说一句等价的定义严格按“是否区分”来。如果存在任意输入串能区分两个状态它们绝不等价必须分开。最终划分结果为 {D0}、{D1}、{D2}、{D3}恰好四组前面这个例子本身已经是最小DFA。现实中很多未化简的DFA会有几十上百个状态被合并到只有几位数的核心状态那个压缩量才明显。4.3 一个常被忽视的技巧处理死状态工程里还有一个和最小化配套的优化叫“死状态合并”。死状态是指一个DFA状态一旦进入就永远不可能到达任何接受态了。更直白地讲它就是一个词法匹配中的黑洞——吃再多字符也不会成功。子集构造生成的DFA里经常有这种状态它们在转移表中占据大量行和列但实际完全没用。正规式的DFA中遇到一个当前token不接受的字符时分析器会回到上一次接受的位置重新开始匹配根本不会踏进这些死状态。因此把死状态统一合并成一个“非接受且所有输入符号都回指自己”的状态可以让转移表更紧凑。这不属于DFA最小化的核心定义但实际做词法生成器时几乎是必做的后处理步骤。我自己的实践经验是不要在子集构造过程中频繁检查死状态这会拖慢算法等子集构造完毕再一次性做死状态合并和划分法最小化代码逻辑清晰且不容易出bug。先后顺序对了很多边界问题会自动消失。5. 动手实现一个简化版词法分析器5.1 数据结构与接口设计用Python实现一个能跑通“正规式→NFA→DFA→最小化→匹配单词”的小工具是理解这套流程的最佳路径。整个代码无需太长几百行内足够但数据结构必须设计清楚。我习惯把NFA表示为状态用整型编号边的集合用三元组源状态、输入字符、目标状态表示其中输入字符为None时表示ε边。开始状态记录为start接受状态集合记录为accepts。DFA则用字典保存转移关系形如transition[(状态, 字符)] 目标状态再加一个accepts集合记录哪些编号是接受态。核心接口只有三个regex_to_nfa(regex)负责把正则字符串解析成NFAsubset_construction(nfa)执行子集构造返回DFAminimize_dfa(dfa)执行划分法最小化。再看一个match(dfa, text)函数输入一个字符串判断整个串是否被词法器识别并返回识别的token类型。这三个接口的顺序就是编译原理词法分析器生成的骨架。5.2 从正规式到NFA的递归构造解析正则时我建议直接用递归下降的方式按结构分解先处理并集再处理连接然后处理闭包最后处理单个字符。这个顺序符合运算符优先级也和平时用正则的习惯一致a|b*先看到的应该是两边的整体a和b*而不是先把b*拆开。构造NFA时用四个辅助函数build_char(c)生成两个状态、一条字符边build_concat(n1, n2)把两个子图首尾相接build_union(n1, n2)新建开始与结束状态用ε边把两个子图并联build_star(n)新建状态在子图前后加ε环回。这里有一点经验构造时不要图省事跳过“新建统一结束状态”这一步。并联和闭包场景里如果不把各个子图的接受态统一到一个汇合状态后续求closure和move时会在接受判定上出各种奇奇怪怪的问题。统一汇合后整个NFA只有一个开始状态和一个接受状态子集构造时不必考虑多个终态逻辑一下子简单很多。5.3 子集构造与最小化的代码骨架我列一段子集构造的伪代码骨架重点展示逻辑顺序。实际的Python实现还要处理字符表枚举、集合转冻结集合用于字典查找这类细节。def epsilon_closure(states, nfa): stack list(states) closure set(states) while stack: s stack.pop() for edge in nfa.edges_from(s): if edge.symbol is None and edge.target not in closure: closure.add(edge.target) stack.append(edge.target) return frozenset(closure) def move(states, symbol, nfa): result set() for s in states: for edge in nfa.edges_from(s): if edge.symbol symbol: result.add(edge.target) return result def subset_construction(nfa, alphabet): start epsilon_closure({nfa.start}, nfa) dfa_states [start] state_map {start: 0} transitions {} accepts set() queue [start] while queue: current queue.pop(0) i state_map[current] if any(s in nfa.accepts for s in current): accepts.add(i) for ch in alphabet: nxt epsilon_closure(move(current, ch, nfa), nfa) if not nxt: continue if nxt not in state_map: state_map[nxt] len(dfa_states) dfa_states.append(nxt) queue.append(nxt) j state_map[nxt] transitions[(i, ch)] j return build_dfa(dfa_states, transitions, accepts)最小化部分的代码核心是维护一个partition列表反复扫描每个组内的状态按照转移目标所在组进行细分。落到实操上每一步细分后要把当前组拆成若干新组如果一个组无法再拆就保留。终止条件是遍历完所有组都没有变化。这里有个实用的工程细节Python里用字典查转移表时键写成(状态, 字符)元组虽然方便但状态多了以后内存翻倍。更好的做法是用嵌套字典transition[状态][字符] 目标状态这样每个状态只维护一条映射目标状态相同的还能共享。小项目无所谓但真拿来生成几千状态的词法器区别很明显。5.4 用一个小例子走通全流程我们用“标识符与关键字”这个小场景走一遍。正规式可以是(a|b|c)(a|b|c|0|1)*即字母开头、后续字母或数字用来匹配简单的变量名。先手算NFA再交给代码转换最后确认很多输入串比如a、abc1、1a的接受情况是否符合预期。用代码跑完子集构造得到的DFA大概3个状态开始状态接受空串吗不接受因为标识符必须至少一个字母第二个状态是吃过首字母后到达的状态第三个状态是吃过数字后的状态如果首字符是数字则直接走向死状态。这个结果和手推一致能帮助我们确认代码路径正确。跑最小化后状态数从3变2是可能的因为“吃完首字母的状态”和“吃完后续字符的状态”在功能上等价——它们都处于“正在匹配标识符”的中间态后续转移行为完全一样。这种等价状态在全手工构造的状态机里很容易被忽略但划分法能一眼识破。6. 常见问题与排查技巧实录6.1 ε闭包算漏状态导致匹配结果偏少或偏多这个坑我见得太多了。初学者写closure时常常只对直接ε边做一次遍历忘了ε边后面还可能缀着更长的ε链。结果DFA状态数偏少某些边界输入串被错误地拒绝或接受。排查思路很简单写一个断言函数对每个正规式生成的NFA先手工算出closure表再和代码跑出来的结果逐项比对。如果发现差异多半是循环退出条件写错了——正确做法是用栈/队列做“不断扩张直到没有新状态加入”的循环而不是用固定层数的for循环。我给初学者的建议是closure函数本质就是一个图遍历务必用visited集合做去重否则还会陷入死循环。6.2 子集构造爆状态数导致内存暴涨虽然理论上DFA状态数可以到2的n次方但实际正规式写得不合理时比如大量嵌套闭包组合状态数依然可能膨胀到不可接受。这种情况通常不是算法错了而是正则本身太复杂。一个实用对策是词法规则拆分。把八十个token类型当作一个巨大的DFA来构造往往一不小心就爆。拆成几十个小DFA每组按优先级排序依次匹配状态总量会小很多。代价是要稍多几次匹配尝试但对大多数语言的词法规则而言这个损换完全可接受。我自己处理复杂语言时甚至会按“关键字”、“标识符与字面量”、“运算符与分隔符”三大类分别生成DFA运行期按token类型分派。6.3 最小化时把不等价状态错并导致识别精度下降最小化算法本身逻辑不复杂出错往往在实现细节上比如比较两个状态的转移时忘记处理“无转移”和“有转移但走向同一组”的差别。严格来说如果一个状态在符号c上没有转移另一个走到了某个组那它们必然不等价必须分开。许多人的实现里把这个情况当成“都无转移”来对待就会产生错误合并。我的建议是在计算转移目标映射时给缺少转移的情况返回一个特殊值比如-1并在比较映射时把它当作一个独立的组来比较。这样“无转移”和“任何具体组”都截然不同不可能被错误地并到一起。写完最小化逻辑后跑一批随机生成的测试串确认最小化前后的接受结果完全一致这是一个性价比非常高的验证手段。6.4 匹配时最长匹配和优先级处理不当词法分析器在实际分析源码时必须采用“最长匹配”策略。例如关键字if和标识符ifx一个词法分析器读到ifx时绝不能在读完if就停下来把它当关键字必须继续吃字符直到无法延伸这时ifx整体才算标识符。自动机本身给出的状态转移并不区分“曾经经过接受态”所以工程实现上要有额外机制扫描过程中记录最近一次接受态的位置和状态遇到死路时回退到该位置做token输出。这种机制在基于DFA的实现里叫“记忆最近接受点”实现上只是几个变量的事但少了它词法分析器就会把ab拆成a、、b期间把a这种非法前缀的错误都暴露出来显然是错的。我带的项目里至少有两位实习同学栽在这个细节上最后都是靠跑一段包含多义前缀的测试用例才发现。建议大家写完匹配函数后用一个带“关键字和标识符重叠”的测试集比如if、iff、if8做回归测试立刻就能看出问题。6.5 工具链中的常见选择与避坑实际工程里不一定非要自己撸完整套转换代码很多开源工具已经封装好了。比如flex家族使用正则规则文件生成C语言的词法分析器内部早已实现NFA转DFA和最小化。用这类工具时最常踩的坑反而是书写规则时的优先级和状态管理。心里有了NFA/DFA这套底子写flex规则时会自然去想“这一条规则和另一条规则在什么输入前缀上会撞车”提前就能调整规则的排列顺序。如果要自己实现教学用的工具我建议别一上来就抄lex语法先用纯Python写一个极简版本跑通主流程。代码量不大遇到问题时便于调试和可视化。等主流程跑通再逐渐扩展成真正的模板生成器。把式样和实现拆分清楚整个项目就不会被工具链的复杂度带偏。提示自己实现时表达NFA时尽量用轻量对象或元组避免过早引入类层次。状态和边的表示一旦复杂化调试成本会成倍上升。宁可写着“不入流”但直白的数据结构先把流程跑通再做面向对象的封装。最后再分享一点个人心得编译原理课程学到词法分析最劝退的地方往往不是概念多而是概念之间的衔接关系不清晰。NFA和DFA这个环节如果只是看书上的定义很容易觉得“不过是个形式化模型而已”但亲手把一个正规式变成DFA状态表再看着它匹配真实的字符串那种“原来编译器是这样认单词”的通透感完全不是看书能替代的。我自己当年入门时是拿一个带几百行规则的真实编程语言做测试把词法部分彻底跑通之后才真正理解为什么教科书要花那么多篇幅讲ε闭包和子集构造——因为这在工业级实现里真的每天都要用到。建议初学者别怕在转换算法上多花时间尽量自己写出完整代码至少跑通一个包含关键字、标识符、整数和运算符的迷你语言。这套工程量不算大但对后续的语法分析、中间代码生成等章节会打下非常扎实的基础。再做一个小推广这套“NFA→DFA→最小化”的流程不仅用于编译器的词法分析器也被广泛应用在正则表达式引擎、网络协议状态机、文本抽取管线里。把自动机的思路吃透你在这些领域看问题的视角会完全不同。如果后续有机会我再写一篇关于词法分析器如何做错误恢复和最长匹配策略的详细文章这些是生成器文档里最少提到、也恰恰是最影响实际体验的部分。