1. 词法分析器在编译流程中的位置为什么值得单独拿出来读前阵子把某本编译原理教材的前两章又从头翻了一遍读到第二章“词法分析”时我明显比第一遍有耐心。因为自己动手写过几个小前端之后才意识到词法分析器看上去平平无奇但它处在编译器最靠前的位置任何偷懒和接口失误都会顺着 token 流一直传导到语法分析、错误恢复和符号表管理。第二章读起来容易真到选型时才发现不少坑。词法分析器要回答的问题很简单怎样从原始字符流里切出一个个有意义的 token。但“简单”是建立在所有细节都对的前提下。这一章把词法分析器独立出来讲是因为它的输入输出边界非常明确理论工具也非常成熟正则表达式描述模式有限自动机实现匹配。你可以在完全不考虑语法分析实现方式的前提下先把词法这一层做到足够好。从工程角度来看我在这本书里收获最大的不是某个具体算法而是它始终在提醒我词法分析器不只是“匹配字符串”它应该成为一个设计良好的模块让后面的语法分析器拿到的是干净、可信、带位置信息的 token 流。1.1 token、lexeme、pattern 三个词必须先分清楚原书开篇就强调了三个概念我第一次读时觉得它们像同义反复后来写代码出问题才明白它们在说不同的事pattern是规则也就是用正则表达式写出的“长什么样算一个标识符”lexeme是输入字符串中被匹配到的那个具体片段token是抽象类别比如“这是一个 ID”“这是一个关键字”。举个例子规则[a-zA-Z_][a-zA-Z0-9_]*是 pattern输入里的foo123是 lexeme语法分析器拿到的ID(foo123)里的ID才是 token。实际编码时token 通常是一个结构体包含类别、文本、行号、列号。很多人误以为 token 就是字符串本身这会在后面做符号表、做错误定位时吃大亏。1.2 词法分析器为什么值得单独成章编译器教科书通常会把词法分析器放得很靠前有些人觉得它“太基础”草草翻过。但我自己的经验是词法分析器的独立性恰恰是它的优点它可以用生成器自动构建也可以手写选型空间大它不依赖语法分析的细节但你若先把 token 设计错了后面几乎没法无痛修改它的理论部分正则表达式、NFA、DFA在文本处理、协议解析、日志分析里照样通用。这本教材把词法分析器的输出定义成“token 流”而不是“字符串”我觉得这是很多人没绷住的地方。表面上只是取一个名字实际上决定了你后面能不能高效处理空白、注释、宏展开、行号追踪等一系列问题。等真的开始写语法分析器时你就会感谢这一章里的这些细节。1.3 词法层面对接口设计的启示这一章让我最受用的地方是它对接口的思考词法分析器不应当只返回一个字符串而应该返回携带充分上下文的 token。行号、列号不是语法分析器需要的但却是错误报告、调试器和编辑器集成需要的。很多人在实验性项目里会偷懒只返回(类别, 文本)这样的二元组。等到编译器报错时只能显示出“语法错误”连出现在哪一行都不知道再回头给所有 token 加位置信息改动量会顺着语法分析树的构建扩散得到处都是。原书把这个设计问题放在词法这一章讲我后来觉得非常有道理位置信息在最小的那一层顺手加上后面的每一层都是免费的。2. 用正则表达式定义词法简写背后的工程折衷词法分析器为什么不直接用上下文无关文法来描述 token这是第二章里我最常被问到的问题。答案可以说得很抽象词法层面的单词结构足够规则用正则语言描述刚刚好也可以用一句大白话说杀鸡用牛刀只会让识别逻辑越来越复杂而且正则语言本身就有足够成熟的机械构造方法。书里介绍的思路是把每个 token 类别写成一条正则表达式然后把所有模式合并起来构造一个词法分析器。这套路听起来简单但“合并”比想象中麻烦。不同模式可能匹配到同一段输入这时候需要定义冲突解决规则通常是“最长匹配优先”和“先声明优先”这一点后面细说。2.1 为什么是正则语言而不是上下文无关语言词法单元没有一个封闭层级不需要嵌套结构。标识符的规则是“字母开头后面跟着字母数字”数字字面量的规则是“一串数字可能有小数点”它们都可以用正则表达式表达。但如果你试图用上下文无关文法去描述“所有合法标识符”虽然也能做到却平白引入了递归下降或者 LALR 分析那一整套机制对词法层来说完全没有必要。正则语言的优点在于它有确定的自动机模型而且从正则表达式到自动机的转换是机械的。这意味着你可以让工具自动完成构造不需要手工设计状态图。另一个优点是效率对 DFA 而言匹配一个字符只需查一次转移表匹配长度为 n 的输入就是 O(n) 时间这在编译器前端是完全可以接受的。2.2 常用简写和它们在构造上的“去糖”方式实际写正则表达式时我们不会只用“并、连接、闭包”这三种基本运算。书里也介绍了字符类、.、?、、{m,n}这类扩展。比如[a-z]本质是a|b|c|...|z的一种简写ab?本质是a(ε|b)a本质是aa*.本质是“除了换行符以外任意字符”的字符类。我在自己实现词法分析器时习惯先把这些扩展“去糖”转成基本运算。因为自动机构造算法只认基本运算简写越多状态生成逻辑越容易乱。去糖的过程不会改变语言本身只是把表达形式统一了后续代码能少写很多分支。值得留意的是书中在处理诸如-转义、字符类求补时也给了一套相当工程化的处理方案先把字符类展开成一系列字符区间再对区间做拆分最后统一转换成基本运算。比如[^a]并不是“所有不等于 a 的字符”那么简单它要在给定的字符集范围内求补。如果没这种细节纯靠直觉写出的字符类实现会在输入换行、转义符、Unicode 字符时各种翻车。2.3 正则表达式是规格说明不是实现方案我见过不少人把“写正则”和“实现词法分析器”划等号谈到性能优化就开始争论“这个正则引擎为什么那么慢”。在词法分析这个场景里最关键的是把正则当成一份规格说明书真正跑起来的是经过构造得到的 DFA。这带来了一个认知转换正则表达式本身不直接执行它先变成 NFA再变成 DFA然后才是查表匹配。我用这本书里的思路重新审视一些问题比如之前觉得正则表达式里(a|b)*abb的括号嵌套很难读但自动机构造过程根本不关心你读不读得懂它只关心语言是否等价。手工优化正则表达式的匹配顺序很多时候是在和一个根本不存在的解释器较劲。3. Thompson 构造法把正则 AST 机械地翻成 NFA正则表达式到 NFA 的转换一般叫 Thompson 构造法。它的核心思想非常简单把每个正则表达式子结构看成一个带“开始状态”和“接受状态”的小零件然后把小零件按运算符拼起来。因为转换是完全递归的所以代码写起来很直白。我第一次学这个构造法时总觉得它绕为什么要引入那么多 ε 转移后来明白ε 边在这里起的作用是“装配时的胶水”。它不消耗字符只负责把不同的自动机片段连接起来让构造过程可以递归进行。3.1 构造规则记忆法书里的构造规则我用四句话就能记住单个字符a从状态 s 出发通过标号a到达状态 e连接AB把 A 的接受状态和 B 的开始状态用 ε 边连起来选择A|B新增开始状态分别 ε 到 A 和 B 的开始状态再用 ε 把 A 和 B 的接受状态汇入同一个新接受状态闭包A*新增开始和接受状态要能跳过 A也要能从 A 的接受状态回到 A 的开始状态。只要把这四件事做对构造出来的 NFA 一定正确。这里的关键是“递归”两个字A 和 B 不是裸字符串而是各自已经构造好的完整自动机片段。如果不能把一个片段内部的状态完美封装起来拼接时就容易互相污染。3.2 一个小实现要点装箱与状态编号如果自己动手写一次我建议用这样的数据结构每个状态只有一个编号边用数组或者邻接表存放。构造时一个Fragment只需要记住开始状态和接受状态不需要记住中间所有状态。class Fragment: def __init__(self, start, accept): self.start start self.accept accept def thompson(node): if node.kind char: s new_state() e new_state() add_edge(s, node.value, e) return Fragment(s, e) elif node.kind cat: left thompson(node.left) right thompson(node.right) add_edge(left.accept, , right.start) return Fragment(left.start, right.accept) elif node.kind alt: s new_state() e new_state() left thompson(node.left) right thompson(node.right) add_edge(s, , left.start) add_edge(s, , right.start) add_edge(left.accept, , e) add_edge(right.accept, , e) return Fragment(s, e) elif node.kind star: s new_state() e new_state() inner thompson(node.child) add_edge(s, , inner.start) add_edge(s, , e) add_edge(inner.accept, , inner.start) add_edge(inner.accept, , e) return Fragment(s, e)我把这段代码放在笔记里因为它是理解后面子集构造的最佳起点。你不需要背代码甚至不需要真的实现它但必须理解每个add_edge在干什么。尤其star构造里的add_edge(s, , e)那条边它专门用来匹配空串很多人画状态图时容易漏掉结果导致a*无法匹配空输入。3.3 构造时的常见疏忽我在手工推演和写实现时撞到过几个问题写出来帮你避坑连接构造时左右片段的接受状态可能不唯一。很多实现里用Fragment只存一个接受状态如果遇到多接受状态的片段就会出错。正常构造里每个片段只有一个接受状态但如果你手工改过某个结构就要小心ε 边不要画到接受状态之外。star里循环边要从内层片段的接受状态连回内层开始状态不要连到外层接受状态上否则闭包会吃掉后面拼接的内容构造顺序影响状态编号但不影响语言。做子集构造时编号不同会导致中间集合不同但最后识别出的语言是一样的。3.4 为什么 Thompson 构造法适合工程NFA 本身不是用来直接运行的因为它的 ε 边和“同一字符可能有多条出边”会让匹配过程充满回溯。Thompson 构造法的价值在于它把一个逻辑上很复杂的任务变成了简单递归你不需要动脑设计状态图只要照着语法树走一遍。这也解释了为什么大部分词法分析器生成工具都采用“正则表达式 → NFA → DFA”这条路线。直接手工构造 DFA 很容易出错尤其是当模式有交叉和重叠时。把复杂度交给中间层换来的是可验证性和可维护性。4. 子集构造法NFA 的“三心二意”变成 DFA 的“从一而终”NFA 匹配时最大的槽点是同一状态下同一个输入字符可能要么走 ε 边要么走多条标号相同的边这让“到底该走哪条路”变成一个需要探索的问题。子集构造法把“所有可能同时活跃的 NFA 状态”打包成一个 DFA 状态从而彻底去掉不确定性。第一次学这个算法的人往往被 ε-闭包绊住。ε-闭包就是从一个状态出发只走 ε 边能到达的所有状态的集合。它不是一步能算完的因为一条 ε 边可能通往另一个还有 ε 边的状态必须做传递闭包。4.1 ε-闭包先想清楚我建议先画一个只有 ε 边的小例子。比如从状态 1 出发有 ε 边到状态 2从状态 2 又有 ε 边到状态 3。那么ε-closure({1})就是{1,2,3}。看起来简单但有些书上的图会把 ε 边画成环这时就要注意闭包可能包含很多状态也可能包含接受状态。实现里我习惯用栈或队列来做闭包计算先把初始集合全部压入然后不断弹出一个状态对它所有的 ε 边目标做并集直到没有新状态加入。这个过程时间复杂度是线性的关键是别用递归去处理否则遇到环会崩。4.2 手工推演 (a|b)*abb书里有一个经典例子(a|b)*abb我几乎是靠它才彻底把子集构造法吃透的。下面是我自己手动编号后得到的一个 NFA 转移关系因为手工编号方式和原书不一样你重点看集合的变化不要纠结状态名。按顺序编号 NFA 状态后DFA 的转移表大概长这样DFA 状态代表的 NFA 状态集合包含关键成员输入 a输入 b是否接受A{1,2,4,6,8,9}BC否B{2,3,4,6,7,8,9}DC否C{2,4,5,6,7,8,9}DC否D{2,3,4,6,7,8,9,10,11}DE否E{2,4,5,6,7,8,9,12,13}DF否F{2,4,5,6,7,8,9,14}DC是注意最后一行F 状态是接受状态因为它对应的 NFA 集合里包含编号 14 这个接受状态。从转移表可以看到前面几个状态基本都在“a 和 b 之间循环”只有走到abb的尾巴时才沿着 D、E、F 一路走下去。这和我手工推(a|b)*abb时的心智模型完全一致。如果你跟着自己做一遍会发现一个很有意思的地方DFA 里某些状态集合很大看起来好像“很多状态同时活着”。这其实正是 NFA 并行匹配的体现。DFA 的一个状态就是 NFA 的一次“可能性快照”它把可能的探索路径全部记录在了状态里。4.3 实现层面的表示选择子集构造实现时最自然的表示是用一个长整数或位数组来代表“NFA 状态集合”因为每个状态在集合里只有“有/无”两种情况。位集做并集、判断是否包含速度都非常快。另一个关键点是不要把每个 DFA 状态对应的完整 NFA 状态集长期保留。很多教程会建一个巨大的表把所有集合都存下来但工程里我们真正需要的是“转移表 是否接受 对应的 token 类型”。原始集合信息在构造完成后就可以丢掉否则内存占用会非常难看。4.4 计算复杂度和实际差异子集构造最坏情况是指数级的一个 n 状态的 NFA 可能产生 2^n 个 DFA 状态。但我在实际场景里几乎从没见过真正爆掉的情况。因为从正则表达式构造出的 NFA 结构非常规整可达状态远少于理论上限。这本书里也提到类似观点DFA 状态数往往比想象中少很多除非你在正则里拼命叠加导致高度歧义的结构。如果真的需要控制状态数量可以一边构造一边做可达性检查只把从开始状态能到达的集合加进 DFA避免把所有集合都枚举一遍。这种“惰性构造”对内存非常友好。5. 状态化简与 token 优先级扫描器落地前的两道关键加工从 NFA 到 DFA我们已经得到了确定性的自动机但直接拿它当词法分析器还差两步化简和优先级处理。这两步在原书里看着轻描淡写实际工程中它们决定了一个扫描器是“能跑”还是“好维护”。5.1 最小化的目的减少表的膨胀DFA 状态化简的目标是去掉等价状态。两个状态如果从它们出发接受未来输入的行为完全一致它们就可以合并。为什么需要合并因为扫描器最终要编译成一张转移表每多一个状态匹配时判断分支就多一份生成的代码也会更臃肿。更重要的是化简后的 DFA 更容易理解和调试。以语言ab|ac为例先构造出大概 4 个 DFA 状态开始状态 A读 a 后到 BB 读 b 到 CB 读 c 到 D其中 C 和 D 都是接受状态并且没有后续转移。C 和 D 行为完全一致可以合并成一个状态。这样ab|ac的最小 DFA 只需要 3 个状态。精简出来的那一步就是状态化简的直观收获。5.2 课堂式划分的细化具体算法分两步走。第一步先把状态分成两个大组接受状态一组非接受状态一组。第二步反复细化对每个组按照“输入某个字符后落入哪个组”来把组拆开。比如某两个状态都在非接受组但状态 X 在输入 a 后跳到接受组状态 Y 在输入 a 后留在非接受组那它们一定不等价必须拆开。重复这个过程直到所有组都不能再拆每个组里的状态就都是等价状态了。这个算法我之前老是记不住后来找了个方法每次划分时只看“转移目标所在组”不要死死盯住状态编号。等价状态的定义原本就是“未来行为一致”而未来的行为完全体现在转移目标的分组上。这么想算法就顺了。5.3 token 匹配优先级最长匹配和书写顺序词法分析器面对的不只是一个 token 模式而是很多个。比如关键字if和标识符规则同时存在输入里出现ifx两个模式都能匹配前缀。如果不做优先级规定词法分析器会无所适从。工程上的标准做法是两条最长匹配优先谁匹配到的输入更长谁赢如果长度一样先声明的那条规则赢。书上把“最长匹配”讲得比较细。具体实现时扫描器不是每读一个字符就立刻决定 token而是记录下“最近一次命中的接受状态和对应位置”然后继续往下读直到完全无法转移为止。最后回退到最近命中位置输出 token。这里有一个细节词法分析器必须保存“最近一次命中”的双指针一个记录命中状态一个记录命中位置。如果输入很长而中途没有接受状态最终只能报错误如果一直有接受状态则不断更新。很多人写手写词法分析器时只记得当前状态忘了记住最近命中点结果遇到“前缀能匹配但不能完整匹配”的输入时就傻了。5.4 合并多个模式后的接受状态处理把多个正则表达式合并成一个 DFA 时每个接受状态都必须带上“命中了哪个 token 类别”的信息同时还要带上优先级。如果某个状态通过不同模式都能到达它就是冲突点合并时要用“最长匹配”和“书写顺序”来定夺。实际编码时我习惯于把转移表里的“接受”字段从布尔值扩展成整数 token 类型。这样在匹配过程中一旦进入接受状态就能顺手拿到 token 编号而不需要额外查一次规则表。原书里没有太强调这个数据布局问题但实现过一遍的人都知道这关系到热路径上的内存访问次数。6. 关键字、标识符、错误恢复最容易在读书时一带而过的地方词法分析器主题里有两个角落我觉得是读书时最容易忽略但实际中避免不了的关键字与标识符的区分以及错误恢复。它们不像 NFA、DFA 那样“高深”却能真实决定一个扫描器好不好用。6.1 关键字分类不是词法分析器的“独立模式”有朋友问我关键字和标识符的词法规则写得不一样是不是应该给if、else各写一条正则从文法角度看关键字确实是语言里的保留字但工程上很少为每个关键字单独画一条 DFA 路径因为那会让状态爆炸。更常见的做法是把关键字和普通标识符合并到一条规则里例如[a-zA-Z_][a-zA-Z0-9_]*统一识别出来然后在接受状态下查一张哈希表看这个文本是不是关键字。是就返回关键字的 token 类别不是就返回标识符。这种做法的好处是DFA 状态数不随关键字数量增长新增一个关键字只是往哈希表里加一条记录。书中虽然讲的是“每个 token 一条正则”的组合方式但在实际代码里把关键字作为标识符的子集处理几乎是不假思索的选择。理解了这一点再看ifx为什么被识别成标识符因为ifx作为一个整体长度是 3而if只有 2最长匹配优先规则让ifx胜出。6.2 最大咀嚼在实词中的体现最长匹配规则有时候会带来一点“反直觉”的结果。比如输入if (x)词法分析器会先匹配if然后因为遇到空格而停下来这是因为空格不是标识符规则的一部分。如果输入是if(x)也就是左括号紧跟在if后面词法分析器在读if后还想继续读左括号但左括号不属于标识符字符集于是回退到最近命中位置还是输出if和(。如果把最长匹配应用到数字上会更有意思。输入123abc数字规则[0-9]会先匹配123但后面跟着字母导致它想继续尝试却失败于a。此时扫描器回退到123的结束位置输出数字 token然后从a重新开始。这个回退行为是“最长匹配”的自然结果不是额外 hack 出来的。书里把这个过程称作“最近命中回退”我读第一遍时没太在意后来写手写词法分析器时才发现自己漏掉了对最近命中点的保存输出结果经常多吞一个字符。这是“读书笔记”里最值得划重点的一句话回退位置必须和接受状态一起记录缺一不可。6.3 错误恢复和位置追踪错误恢复在词法层面的目标不是“分析出错误”而是“尽量不至于让整个编译器因为一个坏字符就崩溃”。常见做法是遇到无法匹配任何模式的字符时跳过它并记录错误然后继续扫描。这种做法被很多教材当成小事但它对后续的错误报告质量影响巨大。位置追踪是我特别想强调的一点。token 里的行号和列号必须在词法分析阶段生成。因为只有在这一层编译器还“看得到”原始字符位置等 token 流进入语法分析后位置信息已经变成不可逆的抽象。如果你要写带错误定位的编译器那么词法分析器里的line和col字段会是你最值得投入的代码。处理换行符时有个细节不要踩Windows 的换行是\r\n如果用\n来计数行号行号没问题列号会把\r多算一格。很多人在词法层纠结半天最后发现是换行符没处理干净。6.4 读书之后我对实现选择的重新思考读完这一章我对“什么时候该手写扫描器”有了更明确的想法。如果只是做一个小型玩具语言模式数量还不算太多手写一个递归的状态机其实很快而且错误恢复和位置追踪都能按自己的需要定制。但如果词法规则有一二十条而且还会不断调整我会更倾向于用自动化工具生成 DFA。最让我感慨的不是哪个方案更“高级”而是这本书把一件事讲透了词法分析器的本质是把你对“文本长什么样”的直觉转化为可验证、可移植、可合并的表驱动自动机。正则表达式负责表达意图Thompson 构造法负责线性翻译子集构造法负责确定化最小化负责压缩优先级规则负责消除歧义。这一整套流程走通后你再回头读任何正则表达式相关的文档都会有“原来它内部长这样”的踏实感。如果在读第二章时你有和我一样的困惑建议你一定要亲手把(a|b)*abb的 NFA 和 DFA 都画一遍然后再把关键字表、最近命中回退和位置追踪加到自己的扫描器里。做完这三件事词法分析器对你来说就不再是一个“被生成工具包办的黑盒”了。 
长河君 · 2026/10/14 7:05:51 · 阅读 1.2k 深入理解词法分析器：从正则表达式到DFA的编译前端核心
1. 词法分析器在编译流程中的位置为什么值得单独拿出来读前阵子把某本编译原理教材的前两章又从头翻了一遍读到第二章“词法分析”时我明显比第一遍有耐心。因为自己动手写过几个小前端之后才意识到词法分析器看上去平平无奇但它处在编译器最靠前的位置任何偷懒和接口失误都会顺着 token 流一直传导到语法分析、错误恢复和符号表管理。第二章读起来容易真到选型时才发现不少坑。词法分析器要回答的问题很简单怎样从原始字符流里切出一个个有意义的 token。但“简单”是建立在所有细节都对的前提下。这一章把词法分析器独立出来讲是因为它的输入输出边界非常明确理论工具也非常成熟正则表达式描述模式有限自动机实现匹配。你可以在完全不考虑语法分析实现方式的前提下先把词法这一层做到足够好。从工程角度来看我在这本书里收获最大的不是某个具体算法而是它始终在提醒我词法分析器不只是“匹配字符串”它应该成为一个设计良好的模块让后面的语法分析器拿到的是干净、可信、带位置信息的 token 流。1.1 token、lexeme、pattern 三个词必须先分清楚原书开篇就强调了三个概念我第一次读时觉得它们像同义反复后来写代码出问题才明白它们在说不同的事pattern是规则也就是用正则表达式写出的“长什么样算一个标识符”lexeme是输入字符串中被匹配到的那个具体片段token是抽象类别比如“这是一个 ID”“这是一个关键字”。举个例子规则[a-zA-Z_][a-zA-Z0-9_]*是 pattern输入里的foo123是 lexeme语法分析器拿到的ID(foo123)里的ID才是 token。实际编码时token 通常是一个结构体包含类别、文本、行号、列号。很多人误以为 token 就是字符串本身这会在后面做符号表、做错误定位时吃大亏。1.2 词法分析器为什么值得单独成章编译器教科书通常会把词法分析器放得很靠前有些人觉得它“太基础”草草翻过。但我自己的经验是词法分析器的独立性恰恰是它的优点它可以用生成器自动构建也可以手写选型空间大它不依赖语法分析的细节但你若先把 token 设计错了后面几乎没法无痛修改它的理论部分正则表达式、NFA、DFA在文本处理、协议解析、日志分析里照样通用。这本教材把词法分析器的输出定义成“token 流”而不是“字符串”我觉得这是很多人没绷住的地方。表面上只是取一个名字实际上决定了你后面能不能高效处理空白、注释、宏展开、行号追踪等一系列问题。等真的开始写语法分析器时你就会感谢这一章里的这些细节。1.3 词法层面对接口设计的启示这一章让我最受用的地方是它对接口的思考词法分析器不应当只返回一个字符串而应该返回携带充分上下文的 token。行号、列号不是语法分析器需要的但却是错误报告、调试器和编辑器集成需要的。很多人在实验性项目里会偷懒只返回(类别, 文本)这样的二元组。等到编译器报错时只能显示出“语法错误”连出现在哪一行都不知道再回头给所有 token 加位置信息改动量会顺着语法分析树的构建扩散得到处都是。原书把这个设计问题放在词法这一章讲我后来觉得非常有道理位置信息在最小的那一层顺手加上后面的每一层都是免费的。2. 用正则表达式定义词法简写背后的工程折衷词法分析器为什么不直接用上下文无关文法来描述 token这是第二章里我最常被问到的问题。答案可以说得很抽象词法层面的单词结构足够规则用正则语言描述刚刚好也可以用一句大白话说杀鸡用牛刀只会让识别逻辑越来越复杂而且正则语言本身就有足够成熟的机械构造方法。书里介绍的思路是把每个 token 类别写成一条正则表达式然后把所有模式合并起来构造一个词法分析器。这套路听起来简单但“合并”比想象中麻烦。不同模式可能匹配到同一段输入这时候需要定义冲突解决规则通常是“最长匹配优先”和“先声明优先”这一点后面细说。2.1 为什么是正则语言而不是上下文无关语言词法单元没有一个封闭层级不需要嵌套结构。标识符的规则是“字母开头后面跟着字母数字”数字字面量的规则是“一串数字可能有小数点”它们都可以用正则表达式表达。但如果你试图用上下文无关文法去描述“所有合法标识符”虽然也能做到却平白引入了递归下降或者 LALR 分析那一整套机制对词法层来说完全没有必要。正则语言的优点在于它有确定的自动机模型而且从正则表达式到自动机的转换是机械的。这意味着你可以让工具自动完成构造不需要手工设计状态图。另一个优点是效率对 DFA 而言匹配一个字符只需查一次转移表匹配长度为 n 的输入就是 O(n) 时间这在编译器前端是完全可以接受的。2.2 常用简写和它们在构造上的“去糖”方式实际写正则表达式时我们不会只用“并、连接、闭包”这三种基本运算。书里也介绍了字符类、.、?、、{m,n}这类扩展。比如[a-z]本质是a|b|c|...|z的一种简写ab?本质是a(ε|b)a本质是aa*.本质是“除了换行符以外任意字符”的字符类。我在自己实现词法分析器时习惯先把这些扩展“去糖”转成基本运算。因为自动机构造算法只认基本运算简写越多状态生成逻辑越容易乱。去糖的过程不会改变语言本身只是把表达形式统一了后续代码能少写很多分支。值得留意的是书中在处理诸如-转义、字符类求补时也给了一套相当工程化的处理方案先把字符类展开成一系列字符区间再对区间做拆分最后统一转换成基本运算。比如[^a]并不是“所有不等于 a 的字符”那么简单它要在给定的字符集范围内求补。如果没这种细节纯靠直觉写出的字符类实现会在输入换行、转义符、Unicode 字符时各种翻车。2.3 正则表达式是规格说明不是实现方案我见过不少人把“写正则”和“实现词法分析器”划等号谈到性能优化就开始争论“这个正则引擎为什么那么慢”。在词法分析这个场景里最关键的是把正则当成一份规格说明书真正跑起来的是经过构造得到的 DFA。这带来了一个认知转换正则表达式本身不直接执行它先变成 NFA再变成 DFA然后才是查表匹配。我用这本书里的思路重新审视一些问题比如之前觉得正则表达式里(a|b)*abb的括号嵌套很难读但自动机构造过程根本不关心你读不读得懂它只关心语言是否等价。手工优化正则表达式的匹配顺序很多时候是在和一个根本不存在的解释器较劲。3. Thompson 构造法把正则 AST 机械地翻成 NFA正则表达式到 NFA 的转换一般叫 Thompson 构造法。它的核心思想非常简单把每个正则表达式子结构看成一个带“开始状态”和“接受状态”的小零件然后把小零件按运算符拼起来。因为转换是完全递归的所以代码写起来很直白。我第一次学这个构造法时总觉得它绕为什么要引入那么多 ε 转移后来明白ε 边在这里起的作用是“装配时的胶水”。它不消耗字符只负责把不同的自动机片段连接起来让构造过程可以递归进行。3.1 构造规则记忆法书里的构造规则我用四句话就能记住单个字符a从状态 s 出发通过标号a到达状态 e连接AB把 A 的接受状态和 B 的开始状态用 ε 边连起来选择A|B新增开始状态分别 ε 到 A 和 B 的开始状态再用 ε 把 A 和 B 的接受状态汇入同一个新接受状态闭包A*新增开始和接受状态要能跳过 A也要能从 A 的接受状态回到 A 的开始状态。只要把这四件事做对构造出来的 NFA 一定正确。这里的关键是“递归”两个字A 和 B 不是裸字符串而是各自已经构造好的完整自动机片段。如果不能把一个片段内部的状态完美封装起来拼接时就容易互相污染。3.2 一个小实现要点装箱与状态编号如果自己动手写一次我建议用这样的数据结构每个状态只有一个编号边用数组或者邻接表存放。构造时一个Fragment只需要记住开始状态和接受状态不需要记住中间所有状态。class Fragment: def __init__(self, start, accept): self.start start self.accept accept def thompson(node): if node.kind char: s new_state() e new_state() add_edge(s, node.value, e) return Fragment(s, e) elif node.kind cat: left thompson(node.left) right thompson(node.right) add_edge(left.accept, , right.start) return Fragment(left.start, right.accept) elif node.kind alt: s new_state() e new_state() left thompson(node.left) right thompson(node.right) add_edge(s, , left.start) add_edge(s, , right.start) add_edge(left.accept, , e) add_edge(right.accept, , e) return Fragment(s, e) elif node.kind star: s new_state() e new_state() inner thompson(node.child) add_edge(s, , inner.start) add_edge(s, , e) add_edge(inner.accept, , inner.start) add_edge(inner.accept, , e) return Fragment(s, e)我把这段代码放在笔记里因为它是理解后面子集构造的最佳起点。你不需要背代码甚至不需要真的实现它但必须理解每个add_edge在干什么。尤其star构造里的add_edge(s, , e)那条边它专门用来匹配空串很多人画状态图时容易漏掉结果导致a*无法匹配空输入。3.3 构造时的常见疏忽我在手工推演和写实现时撞到过几个问题写出来帮你避坑连接构造时左右片段的接受状态可能不唯一。很多实现里用Fragment只存一个接受状态如果遇到多接受状态的片段就会出错。正常构造里每个片段只有一个接受状态但如果你手工改过某个结构就要小心ε 边不要画到接受状态之外。star里循环边要从内层片段的接受状态连回内层开始状态不要连到外层接受状态上否则闭包会吃掉后面拼接的内容构造顺序影响状态编号但不影响语言。做子集构造时编号不同会导致中间集合不同但最后识别出的语言是一样的。3.4 为什么 Thompson 构造法适合工程NFA 本身不是用来直接运行的因为它的 ε 边和“同一字符可能有多条出边”会让匹配过程充满回溯。Thompson 构造法的价值在于它把一个逻辑上很复杂的任务变成了简单递归你不需要动脑设计状态图只要照着语法树走一遍。这也解释了为什么大部分词法分析器生成工具都采用“正则表达式 → NFA → DFA”这条路线。直接手工构造 DFA 很容易出错尤其是当模式有交叉和重叠时。把复杂度交给中间层换来的是可验证性和可维护性。4. 子集构造法NFA 的“三心二意”变成 DFA 的“从一而终”NFA 匹配时最大的槽点是同一状态下同一个输入字符可能要么走 ε 边要么走多条标号相同的边这让“到底该走哪条路”变成一个需要探索的问题。子集构造法把“所有可能同时活跃的 NFA 状态”打包成一个 DFA 状态从而彻底去掉不确定性。第一次学这个算法的人往往被 ε-闭包绊住。ε-闭包就是从一个状态出发只走 ε 边能到达的所有状态的集合。它不是一步能算完的因为一条 ε 边可能通往另一个还有 ε 边的状态必须做传递闭包。4.1 ε-闭包先想清楚我建议先画一个只有 ε 边的小例子。比如从状态 1 出发有 ε 边到状态 2从状态 2 又有 ε 边到状态 3。那么ε-closure({1})就是{1,2,3}。看起来简单但有些书上的图会把 ε 边画成环这时就要注意闭包可能包含很多状态也可能包含接受状态。实现里我习惯用栈或队列来做闭包计算先把初始集合全部压入然后不断弹出一个状态对它所有的 ε 边目标做并集直到没有新状态加入。这个过程时间复杂度是线性的关键是别用递归去处理否则遇到环会崩。4.2 手工推演 (a|b)*abb书里有一个经典例子(a|b)*abb我几乎是靠它才彻底把子集构造法吃透的。下面是我自己手动编号后得到的一个 NFA 转移关系因为手工编号方式和原书不一样你重点看集合的变化不要纠结状态名。按顺序编号 NFA 状态后DFA 的转移表大概长这样DFA 状态代表的 NFA 状态集合包含关键成员输入 a输入 b是否接受A{1,2,4,6,8,9}BC否B{2,3,4,6,7,8,9}DC否C{2,4,5,6,7,8,9}DC否D{2,3,4,6,7,8,9,10,11}DE否E{2,4,5,6,7,8,9,12,13}DF否F{2,4,5,6,7,8,9,14}DC是注意最后一行F 状态是接受状态因为它对应的 NFA 集合里包含编号 14 这个接受状态。从转移表可以看到前面几个状态基本都在“a 和 b 之间循环”只有走到abb的尾巴时才沿着 D、E、F 一路走下去。这和我手工推(a|b)*abb时的心智模型完全一致。如果你跟着自己做一遍会发现一个很有意思的地方DFA 里某些状态集合很大看起来好像“很多状态同时活着”。这其实正是 NFA 并行匹配的体现。DFA 的一个状态就是 NFA 的一次“可能性快照”它把可能的探索路径全部记录在了状态里。4.3 实现层面的表示选择子集构造实现时最自然的表示是用一个长整数或位数组来代表“NFA 状态集合”因为每个状态在集合里只有“有/无”两种情况。位集做并集、判断是否包含速度都非常快。另一个关键点是不要把每个 DFA 状态对应的完整 NFA 状态集长期保留。很多教程会建一个巨大的表把所有集合都存下来但工程里我们真正需要的是“转移表 是否接受 对应的 token 类型”。原始集合信息在构造完成后就可以丢掉否则内存占用会非常难看。4.4 计算复杂度和实际差异子集构造最坏情况是指数级的一个 n 状态的 NFA 可能产生 2^n 个 DFA 状态。但我在实际场景里几乎从没见过真正爆掉的情况。因为从正则表达式构造出的 NFA 结构非常规整可达状态远少于理论上限。这本书里也提到类似观点DFA 状态数往往比想象中少很多除非你在正则里拼命叠加导致高度歧义的结构。如果真的需要控制状态数量可以一边构造一边做可达性检查只把从开始状态能到达的集合加进 DFA避免把所有集合都枚举一遍。这种“惰性构造”对内存非常友好。5. 状态化简与 token 优先级扫描器落地前的两道关键加工从 NFA 到 DFA我们已经得到了确定性的自动机但直接拿它当词法分析器还差两步化简和优先级处理。这两步在原书里看着轻描淡写实际工程中它们决定了一个扫描器是“能跑”还是“好维护”。5.1 最小化的目的减少表的膨胀DFA 状态化简的目标是去掉等价状态。两个状态如果从它们出发接受未来输入的行为完全一致它们就可以合并。为什么需要合并因为扫描器最终要编译成一张转移表每多一个状态匹配时判断分支就多一份生成的代码也会更臃肿。更重要的是化简后的 DFA 更容易理解和调试。以语言ab|ac为例先构造出大概 4 个 DFA 状态开始状态 A读 a 后到 BB 读 b 到 CB 读 c 到 D其中 C 和 D 都是接受状态并且没有后续转移。C 和 D 行为完全一致可以合并成一个状态。这样ab|ac的最小 DFA 只需要 3 个状态。精简出来的那一步就是状态化简的直观收获。5.2 课堂式划分的细化具体算法分两步走。第一步先把状态分成两个大组接受状态一组非接受状态一组。第二步反复细化对每个组按照“输入某个字符后落入哪个组”来把组拆开。比如某两个状态都在非接受组但状态 X 在输入 a 后跳到接受组状态 Y 在输入 a 后留在非接受组那它们一定不等价必须拆开。重复这个过程直到所有组都不能再拆每个组里的状态就都是等价状态了。这个算法我之前老是记不住后来找了个方法每次划分时只看“转移目标所在组”不要死死盯住状态编号。等价状态的定义原本就是“未来行为一致”而未来的行为完全体现在转移目标的分组上。这么想算法就顺了。5.3 token 匹配优先级最长匹配和书写顺序词法分析器面对的不只是一个 token 模式而是很多个。比如关键字if和标识符规则同时存在输入里出现ifx两个模式都能匹配前缀。如果不做优先级规定词法分析器会无所适从。工程上的标准做法是两条最长匹配优先谁匹配到的输入更长谁赢如果长度一样先声明的那条规则赢。书上把“最长匹配”讲得比较细。具体实现时扫描器不是每读一个字符就立刻决定 token而是记录下“最近一次命中的接受状态和对应位置”然后继续往下读直到完全无法转移为止。最后回退到最近命中位置输出 token。这里有一个细节词法分析器必须保存“最近一次命中”的双指针一个记录命中状态一个记录命中位置。如果输入很长而中途没有接受状态最终只能报错误如果一直有接受状态则不断更新。很多人写手写词法分析器时只记得当前状态忘了记住最近命中点结果遇到“前缀能匹配但不能完整匹配”的输入时就傻了。5.4 合并多个模式后的接受状态处理把多个正则表达式合并成一个 DFA 时每个接受状态都必须带上“命中了哪个 token 类别”的信息同时还要带上优先级。如果某个状态通过不同模式都能到达它就是冲突点合并时要用“最长匹配”和“书写顺序”来定夺。实际编码时我习惯于把转移表里的“接受”字段从布尔值扩展成整数 token 类型。这样在匹配过程中一旦进入接受状态就能顺手拿到 token 编号而不需要额外查一次规则表。原书里没有太强调这个数据布局问题但实现过一遍的人都知道这关系到热路径上的内存访问次数。6. 关键字、标识符、错误恢复最容易在读书时一带而过的地方词法分析器主题里有两个角落我觉得是读书时最容易忽略但实际中避免不了的关键字与标识符的区分以及错误恢复。它们不像 NFA、DFA 那样“高深”却能真实决定一个扫描器好不好用。6.1 关键字分类不是词法分析器的“独立模式”有朋友问我关键字和标识符的词法规则写得不一样是不是应该给if、else各写一条正则从文法角度看关键字确实是语言里的保留字但工程上很少为每个关键字单独画一条 DFA 路径因为那会让状态爆炸。更常见的做法是把关键字和普通标识符合并到一条规则里例如[a-zA-Z_][a-zA-Z0-9_]*统一识别出来然后在接受状态下查一张哈希表看这个文本是不是关键字。是就返回关键字的 token 类别不是就返回标识符。这种做法的好处是DFA 状态数不随关键字数量增长新增一个关键字只是往哈希表里加一条记录。书中虽然讲的是“每个 token 一条正则”的组合方式但在实际代码里把关键字作为标识符的子集处理几乎是不假思索的选择。理解了这一点再看ifx为什么被识别成标识符因为ifx作为一个整体长度是 3而if只有 2最长匹配优先规则让ifx胜出。6.2 最大咀嚼在实词中的体现最长匹配规则有时候会带来一点“反直觉”的结果。比如输入if (x)词法分析器会先匹配if然后因为遇到空格而停下来这是因为空格不是标识符规则的一部分。如果输入是if(x)也就是左括号紧跟在if后面词法分析器在读if后还想继续读左括号但左括号不属于标识符字符集于是回退到最近命中位置还是输出if和(。如果把最长匹配应用到数字上会更有意思。输入123abc数字规则[0-9]会先匹配123但后面跟着字母导致它想继续尝试却失败于a。此时扫描器回退到123的结束位置输出数字 token然后从a重新开始。这个回退行为是“最长匹配”的自然结果不是额外 hack 出来的。书里把这个过程称作“最近命中回退”我读第一遍时没太在意后来写手写词法分析器时才发现自己漏掉了对最近命中点的保存输出结果经常多吞一个字符。这是“读书笔记”里最值得划重点的一句话回退位置必须和接受状态一起记录缺一不可。6.3 错误恢复和位置追踪错误恢复在词法层面的目标不是“分析出错误”而是“尽量不至于让整个编译器因为一个坏字符就崩溃”。常见做法是遇到无法匹配任何模式的字符时跳过它并记录错误然后继续扫描。这种做法被很多教材当成小事但它对后续的错误报告质量影响巨大。位置追踪是我特别想强调的一点。token 里的行号和列号必须在词法分析阶段生成。因为只有在这一层编译器还“看得到”原始字符位置等 token 流进入语法分析后位置信息已经变成不可逆的抽象。如果你要写带错误定位的编译器那么词法分析器里的line和col字段会是你最值得投入的代码。处理换行符时有个细节不要踩Windows 的换行是\r\n如果用\n来计数行号行号没问题列号会把\r多算一格。很多人在词法层纠结半天最后发现是换行符没处理干净。6.4 读书之后我对实现选择的重新思考读完这一章我对“什么时候该手写扫描器”有了更明确的想法。如果只是做一个小型玩具语言模式数量还不算太多手写一个递归的状态机其实很快而且错误恢复和位置追踪都能按自己的需要定制。但如果词法规则有一二十条而且还会不断调整我会更倾向于用自动化工具生成 DFA。最让我感慨的不是哪个方案更“高级”而是这本书把一件事讲透了词法分析器的本质是把你对“文本长什么样”的直觉转化为可验证、可移植、可合并的表驱动自动机。正则表达式负责表达意图Thompson 构造法负责线性翻译子集构造法负责确定化最小化负责压缩优先级规则负责消除歧义。这一整套流程走通后你再回头读任何正则表达式相关的文档都会有“原来它内部长这样”的踏实感。如果在读第二章时你有和我一样的困惑建议你一定要亲手把(a|b)*abb的 NFA 和 DFA 都画一遍然后再把关键字表、最近命中回退和位置追踪加到自己的扫描器里。做完这三件事词法分析器对你来说就不再是一个“被生成工具包办的黑盒”了。