1. 从零理解“无符号数的自动机识别”第一次看到“无符号数的自动机识别”这个标题很多人脑子里冒出来的第一个念头大概是这到底是在讲编译原理还是在讲数字电路其实两者都沾边。简单来说它研究的是这样一个问题——给定一串字符比如123、0、007、42abc我们怎么用一台“抽象机器”自动判断它是不是一个合法的无符号数并且把合法的部分识别出来。这件事听起来好像用一行正则表达式就能搞定但真正动过手的人都知道正则表达式背后的理论模型就是有限状态自动机。你写[0-9]的时候引擎内部其实就是在跑一个状态机。所以“无符号数的自动机识别”本质上是一个把词法规则转化为状态转移图的经典练习它既是编译原理课程里词法分析器的最小可用原型也是理解 DFA确定性有限自动机和 NFA非确定性有限自动机区别的绝佳切入点。这篇文章适合谁看如果你正在学编译原理、形式语言与自动机或者你是个写代码的想搞清楚“为什么正则引擎能识别数字却不能识别括号配对”那这篇内容就是给你准备的。我会从设计思路讲起把状态机的构造过程一步步拆开再给出可以直接跑的代码实现最后把我自己踩过的坑和排查技巧一并倒出来。整篇内容不依赖任何特定教材你拿一张纸一支笔就能跟着推。需要提前说明的是无符号数在不同语境下定义略有差异。有的场景只允许纯数字串有的场景允许前导零有的场景还允许小数点。为了把问题讲透我下面会以“纯整数无符号数”为主线同时在扩展部分讨论带小数点和前导零的情况。这样你既能掌握核心方法又能根据实际需求做调整。2. 核心设计思路与方案选型拆解2.1 为什么用自动机而不是正则表达式很多人会问识别一个无符号数我直接写个循环判断每个字符是不是0到9不就行了为什么要搬出自动机这套理论这个问题问得好答案在于可扩展性和形式化验证。当你只识别纯数字时循环确实够用。但词法分析器要识别的可不止数字还有标识符、运算符、关键字、注释等等。如果每种 token 都写一个独立的循环代码会迅速膨胀成一团乱麻。而自动机的好处是所有 token 的识别可以统一到一个状态转移框架里每个 token 对应一组接受状态扫描一遍字符流就能完成全部词法分析。这就是为什么几乎所有编译器前端都采用自动机驱动的词法分析。另一个原因是形式化。自动机是一个数学对象你可以证明它识别的语言恰好是某个正则语言也可以用它做等价性判定、最小化化简。循环代码做不到这些。所以从工程角度自动机是“一次投入、长期受益”的基础设施。2.2 DFA 与 NFA 的取舍逻辑构造无符号数识别器时你会面临第一个选择用 DFA 还是 NFANFA 的构造更直观。比如“一个或多个数字”你可以画成起始状态遇到数字进入接受状态接受状态遇到数字继续留在接受状态。这个描述天然就是 NFA 的思路因为“一个或多个”隐含了选择。但 NFA 有个麻烦同一时刻可能处于多个状态实现时需要维护状态集合还要处理空转移。对于无符号数这种简单规则用 NFA 属于杀鸡用牛刀反而增加实现复杂度。DFA 的每个状态对每个输入符号最多只有一个后继实现起来就是一个二维表或者一组 switch 分支跑起来是 O(n) 的确定性扫描没有任何回溯。所以我个人的选择是先把 NFA 画出来帮助理解再手工确定化为 DFA最后用 DFA 写代码。这样既保证了思路清晰又保证了运行效率。2.3 状态设计的关键考量设计状态时核心问题是我需要几个状态才能区分“合法”和“非法”对于纯整数无符号数最少需要三个状态起始状态 S还没读到任何字符。接受状态 A已经读到了至少一个数字当前串是合法的。死状态 D读到了非数字字符且不可能再恢复。转移规则也很简单S 遇到数字去 A遇到其他去 DA 遇到数字留在 A遇到其他去 DD 遇到任何字符留在 D。这里有个细节值得注意死状态是否必要。理论上如果你在扫描到非法字符时直接返回失败可以不要死状态。但在完整的词法分析器里死状态是有用的因为它能告诉你“这个 token 在哪里结束”。比如输入123abc扫描到a时进入死状态此时你知道数字部分是123a属于下一个 token。所以死状态的存在让 token 边界判定变得自然。还有一个容易忽略的点空串的处理。无符号数至少有一位数字所以起始状态不能是接受状态。如果你把起始状态也设为接受那空串就会被误判为合法数字。这个坑我在早期实现里踩过后面会详细说。3. 核心细节解析与实操要点3.1 状态转移表的构建方法把状态机写成代码最直接的方式是建一张状态转移表。行是状态列是输入字符类别单元格是下一个状态。对于无符号整数字符类别可以简化为两类数字0-9和非数字。转移表如下当前状态输入为数字输入为非数字S起始ADA接受ADD死DD这张表就是整个识别器的核心。实现时你可以用一个二维数组表示也可以用字典嵌套。用数组的话状态编号 0、1、2 分别对应 S、A、D输入类别 0 表示数字、1 表示非数字那么table[0][0]1、table[0][1]2以此类推。构建这张表的过程其实就是把状态图“翻译”成数据结构。我建议你手动画一遍状态图再填表这样不容易漏掉转移。特别是死状态的自环很多人画图时会忘记导致代码里出现未定义行为。3.2 接受状态的判定时机一个关键细节是什么时候判断接受。有两种常见做法。第一种是扫描完整个输入后看最终状态是否是接受状态。这种做法适合输入就是一个完整 token 的场景。第二种是每读一个字符就检查当前状态如果进入接受状态就记录位置扫描到死状态时回退到最后一个接受位置。这种做法适合从连续字符流中切分 token。两种做法的区别在于对123abc这种输入的处理。第一种会直接判定整个串非法第二种会识别出123并停在a之前。实际词法分析器用的是第二种因为源代码里 token 是连续排列的你必须知道每个 token 的边界。实现第二种做法时需要维护一个lastAccept变量每次进入接受状态就更新它。当扫描到死状态或者输入结束时如果lastAccept有值就说明识别成功token 是从起点到lastAccept的子串。3.3 前导零与边界情况处理纯数字识别看起来简单但边界情况不少。我列几个实际会遇到的问题前导零007算不算合法无符号数从自动机角度它完全合法因为每个字符都是数字。但从语义角度有些场景不允许前导零。这属于词法规则之外的约束自动机本身不负责需要在识别后额外判断。空输入空串不是合法无符号数因为起始状态不是接受状态。这一点前面提过但实现时容易因为初始化逻辑写错而放行。超长数字自动机本身不关心数值大小但识别后如果要转成整数就要考虑溢出。这是识别之后的事但设计接口时要预留处理空间。正号123算不算无符号数严格来说不算因为不是数字。但有些场景允许可选正号这时状态机需要增加一个状态来处理后的数字。这些边界情况说明一个道理自动机识别的是语法形式不是语义约束。你要清楚自己的需求边界在哪里再决定状态机设计到什么程度。提示如果你的场景需要允许前导零但禁止全零以外的多位数前导零那已经超出正则语言的能力范围需要引入计数或额外逻辑。别试图用状态机硬扛那样状态数会爆炸。4. 实操过程与核心环节实现4.1 手写一个 DFA 识别器下面我用 Python 实现一个完整的无符号整数识别器。选择 Python 是因为它读起来接近伪代码方便你理解逻辑移植到其他语言也很容易。先定义状态和转移表# 状态编号 S, A, D 0, 1, 2 # 转移表table[state][char_type] # char_type: 0 表示数字1 表示非数字 table [ [A, D], # S [A, D], # A [D, D], # D ] def char_type(ch): if 0 ch 9: return 0 return 1然后是核心扫描函数采用“记录最后接受位置”的策略def recognize_unsigned_int(text): state S last_accept -1 for i, ch in enumerate(text): state table[state][char_type(ch)] if state A: last_accept i if state D: break if last_accept 0: return True, text[:last_accept 1] return False, 这段代码的逻辑是从头扫描每进入接受状态就记录位置。一旦进入死状态就停止。最后如果记录过接受位置就返回成功和对应的子串。测试几个用例print(recognize_unsigned_int(123)) # (True, 123) print(recognize_unsigned_int(007)) # (True, 007) print(recognize_unsigned_int(123abc)) # (True, 123) print(recognize_unsigned_int(abc)) # (False, ) print(recognize_unsigned_int()) # (False, )结果符合预期。123abc被正确切分为123空串和纯字母被拒绝。4.2 从整数扩展到带小数点的无符号数实际场景里无符号数往往还包括小数比如3.14、0.5。这时状态机需要扩展。新的规则是数字序列可选地后跟一个小数点再加数字序列。注意小数点前后都必须有数字所以.5和5.都不合法。状态设计变成四个S起始A整数部分已有至少一位数字B刚读到小数点等待小数部分C小数部分已有至少一位数字接受状态D死状态转移表当前状态数字小数点其他SADDAABDBCDDCCDDDDDD实现时把char_type扩展为三类转移表变成三列。核心扫描逻辑不变仍然是记录最后接受位置。这样3.14会一路走到 C3.会停在 B 然后因为输入结束而回退到 A识别出3。这个行为是否符合预期取决于你的需求如果要求小数点后必须有数字那3.识别出3是合理的因为3本身是合法整数。4.3 用状态机驱动一个简易词法分析器单个识别器只能处理一种 token。要体现自动机的真正价值可以把它扩展成一个能同时识别数字、标识符和运算符的简易词法分析器。思路是把所有 token 的状态机合并成一个大状态机每个接受状态标记它对应的 token 类型。扫描时每进入一个接受状态就记录位置和类型遇到死状态就回退输出最后一个接受的 token然后从该位置继续扫描。这种“最长匹配”策略是词法分析的标准做法。比如输入abc123标识符状态机会一直匹配到末尾输出标识符abc123而不是先输出abc再输出123。这就是为什么关键字和标识符的识别要放在一起靠最长匹配和优先级来区分。实现时状态表会变大但核心逻辑还是那套转移、记录、回退、继续。你会发现一旦框架搭好增加新 token 类型只是往表里加行加列的事这就是自动机方案的可扩展性优势。5. 常见问题与排查技巧实录5.1 状态机实现中的典型 bug我在实现和教学过程中见过太多相似的错误这里整理成一张速查表问题现象可能原因排查方法空串被判定为合法起始状态被误设为接受状态检查接受状态集合是否包含 S123abc整体被拒绝没有记录最后接受位置只看最终状态改为记录 lastAccept 策略死状态后程序崩溃转移表缺少死状态的自环补全 table[D][*] D小数点后无数字仍接受小数点状态被误设为接受检查接受状态是否只包含 C超长数字识别后溢出识别与转换未分离先识别字符串再单独处理转换这些问题的共同点是状态设计阶段的疏忽会在实现阶段放大。所以我的建议是动手写代码之前先在纸上把状态图画完整包括所有转移和接受状态标记然后再翻译成代码。这一步花十分钟能省掉后面一小时的调试。5.2 性能与可读性的平衡状态转移表用二维数组实现查询是 O(1)性能很好。但状态多了以后数组会变得难以阅读因为你看不出table[3][2]到底代表什么。我的经验是状态少的时候用数组状态多的时候用字典加枚举。比如用State.S、CharType.DIGIT这样的命名代码可读性会大幅提升性能损失可以忽略。如果确实对性能敏感可以在初始化时把字典编译成数组兼顾两者。另一个技巧是把转移表写成数据文件或者用代码生成这样修改规则时不用动核心逻辑。这在需要支持多种数字格式的场景下特别有用。5.3 自动机方案的适用边界最后说一个容易被忽视的问题自动机不是万能的。它能识别的是正则语言也就是不需要计数就能描述的模式。无符号数恰好属于这一类所以自动机很合适。但如果你要识别的是“括号配对”“嵌套结构”“缩进敏感的语言”自动机就无能为力了因为那些需要栈或者计数器。这时候你需要下推自动机或者更强大的模型。搞清楚这个边界能帮你避免在错误的方向上浪费时间。注意不要试图用状态机去解析 JSON 或 XML 的嵌套结构那是语法分析器的活。词法分析器只负责把字符流切成 token嵌套关系交给语法分析阶段处理。我在实际项目里遇到过一个案例有人想用正则表达式匹配嵌套的括号写了上百行的模式还是漏掉边界情况。后来换成递归下降解析器二十行代码就解决了。这个教训说明选对工具比硬扛重要得多。6. 从识别器到可复用组件的封装思路6.1 接口设计要点把识别器封装成可复用组件时接口设计决定了它好不好用。我倾向于暴露三个东西一个初始化函数、一个扫描函数、一个结果结构。初始化函数接收配置比如是否允许小数点、是否允许前导零。扫描函数接收字符串和起始位置返回识别结果和下一个位置。结果结构包含是否成功、识别的子串、token 类型。这样的接口既适合单次识别也适合嵌入更大的词法分析循环。关键是不要把状态机的内部细节暴露出去调用方只关心“给我一个串告诉我是不是数字到哪里结束”。6.2 测试用例的设计自动机的测试用例要覆盖三类正常路径、边界情况、非法输入。正常路径包括0、9、123、999999。边界情况包括空串、单个数字、超长数字、前导零。非法输入包括纯字母、字母数字混合、只有小数点、小数点开头、小数点结尾。我习惯把这些用例写成一个表每行是输入和期望输出跑一遍就能验证。这种表驱动测试的好处是增加新规则时只需加行不用改测试逻辑。6.3 与其他模块的协作在完整的编译器或解释器里无符号数识别器只是词法分析器的一部分。它需要和标识符识别器、运算符识别器协同工作共享字符流和位置信息。协作的关键是最长匹配和优先级。比如123既可以被数字识别器接受也可以被标识符识别器接受如果标识符允许数字开头。这时需要约定优先级通常数字优先因为123更自然地解释为数字。另一个协作点是错误恢复。当所有识别器都失败时词法分析器需要报告错误并跳过当前字符继续扫描。这个逻辑不属于单个识别器但识别器需要提供足够的信息让上层做决策。7. 我个人的实操体会与建议回过头看无符号数的自动机识别虽然是个小题目但它把形式语言的核心概念串了一遍状态、转移、接受、确定化、最长匹配。把这套东西吃透再看词法分析器、正则引擎、协议解析器会发现底层逻辑是相通的。我的建议是不要满足于“能跑就行”。动手画状态图手工推几个输入再写代码验证。遇到不符合预期的结果先回去检查状态图而不是急着改代码。状态图对了代码自然对状态图错了代码怎么调都是补丁摞补丁。另外如果你打算把这个识别器用在真实项目里记得把识别和转换分开。识别器只负责判断“这是不是一个合法数字串”转换器负责把字符串变成整数或浮点数。这样职责清晰测试也容易写。我见过太多把两者混在一起的代码最后溢出、精度、前导零的问题搅成一团改都改不动。最后分享一个小技巧在状态机的转移函数里加一个可选的日志开关每次转移时打印当前状态、输入字符、下一个状态。调试复杂状态机时这个日志比断点还好用因为它能让你看到完整的转移路径一眼就能定位到哪一步走错了。这个习惯我保持了多年几乎每个状态机项目都会加上。 
长河君 · 2026/10/15 10:18:09 · 阅读 1.2k 无符号数自动机识别：从DFA设计到词法分析器实现
1. 从零理解“无符号数的自动机识别”第一次看到“无符号数的自动机识别”这个标题很多人脑子里冒出来的第一个念头大概是这到底是在讲编译原理还是在讲数字电路其实两者都沾边。简单来说它研究的是这样一个问题——给定一串字符比如123、0、007、42abc我们怎么用一台“抽象机器”自动判断它是不是一个合法的无符号数并且把合法的部分识别出来。这件事听起来好像用一行正则表达式就能搞定但真正动过手的人都知道正则表达式背后的理论模型就是有限状态自动机。你写[0-9]的时候引擎内部其实就是在跑一个状态机。所以“无符号数的自动机识别”本质上是一个把词法规则转化为状态转移图的经典练习它既是编译原理课程里词法分析器的最小可用原型也是理解 DFA确定性有限自动机和 NFA非确定性有限自动机区别的绝佳切入点。这篇文章适合谁看如果你正在学编译原理、形式语言与自动机或者你是个写代码的想搞清楚“为什么正则引擎能识别数字却不能识别括号配对”那这篇内容就是给你准备的。我会从设计思路讲起把状态机的构造过程一步步拆开再给出可以直接跑的代码实现最后把我自己踩过的坑和排查技巧一并倒出来。整篇内容不依赖任何特定教材你拿一张纸一支笔就能跟着推。需要提前说明的是无符号数在不同语境下定义略有差异。有的场景只允许纯数字串有的场景允许前导零有的场景还允许小数点。为了把问题讲透我下面会以“纯整数无符号数”为主线同时在扩展部分讨论带小数点和前导零的情况。这样你既能掌握核心方法又能根据实际需求做调整。2. 核心设计思路与方案选型拆解2.1 为什么用自动机而不是正则表达式很多人会问识别一个无符号数我直接写个循环判断每个字符是不是0到9不就行了为什么要搬出自动机这套理论这个问题问得好答案在于可扩展性和形式化验证。当你只识别纯数字时循环确实够用。但词法分析器要识别的可不止数字还有标识符、运算符、关键字、注释等等。如果每种 token 都写一个独立的循环代码会迅速膨胀成一团乱麻。而自动机的好处是所有 token 的识别可以统一到一个状态转移框架里每个 token 对应一组接受状态扫描一遍字符流就能完成全部词法分析。这就是为什么几乎所有编译器前端都采用自动机驱动的词法分析。另一个原因是形式化。自动机是一个数学对象你可以证明它识别的语言恰好是某个正则语言也可以用它做等价性判定、最小化化简。循环代码做不到这些。所以从工程角度自动机是“一次投入、长期受益”的基础设施。2.2 DFA 与 NFA 的取舍逻辑构造无符号数识别器时你会面临第一个选择用 DFA 还是 NFANFA 的构造更直观。比如“一个或多个数字”你可以画成起始状态遇到数字进入接受状态接受状态遇到数字继续留在接受状态。这个描述天然就是 NFA 的思路因为“一个或多个”隐含了选择。但 NFA 有个麻烦同一时刻可能处于多个状态实现时需要维护状态集合还要处理空转移。对于无符号数这种简单规则用 NFA 属于杀鸡用牛刀反而增加实现复杂度。DFA 的每个状态对每个输入符号最多只有一个后继实现起来就是一个二维表或者一组 switch 分支跑起来是 O(n) 的确定性扫描没有任何回溯。所以我个人的选择是先把 NFA 画出来帮助理解再手工确定化为 DFA最后用 DFA 写代码。这样既保证了思路清晰又保证了运行效率。2.3 状态设计的关键考量设计状态时核心问题是我需要几个状态才能区分“合法”和“非法”对于纯整数无符号数最少需要三个状态起始状态 S还没读到任何字符。接受状态 A已经读到了至少一个数字当前串是合法的。死状态 D读到了非数字字符且不可能再恢复。转移规则也很简单S 遇到数字去 A遇到其他去 DA 遇到数字留在 A遇到其他去 DD 遇到任何字符留在 D。这里有个细节值得注意死状态是否必要。理论上如果你在扫描到非法字符时直接返回失败可以不要死状态。但在完整的词法分析器里死状态是有用的因为它能告诉你“这个 token 在哪里结束”。比如输入123abc扫描到a时进入死状态此时你知道数字部分是123a属于下一个 token。所以死状态的存在让 token 边界判定变得自然。还有一个容易忽略的点空串的处理。无符号数至少有一位数字所以起始状态不能是接受状态。如果你把起始状态也设为接受那空串就会被误判为合法数字。这个坑我在早期实现里踩过后面会详细说。3. 核心细节解析与实操要点3.1 状态转移表的构建方法把状态机写成代码最直接的方式是建一张状态转移表。行是状态列是输入字符类别单元格是下一个状态。对于无符号整数字符类别可以简化为两类数字0-9和非数字。转移表如下当前状态输入为数字输入为非数字S起始ADA接受ADD死DD这张表就是整个识别器的核心。实现时你可以用一个二维数组表示也可以用字典嵌套。用数组的话状态编号 0、1、2 分别对应 S、A、D输入类别 0 表示数字、1 表示非数字那么table[0][0]1、table[0][1]2以此类推。构建这张表的过程其实就是把状态图“翻译”成数据结构。我建议你手动画一遍状态图再填表这样不容易漏掉转移。特别是死状态的自环很多人画图时会忘记导致代码里出现未定义行为。3.2 接受状态的判定时机一个关键细节是什么时候判断接受。有两种常见做法。第一种是扫描完整个输入后看最终状态是否是接受状态。这种做法适合输入就是一个完整 token 的场景。第二种是每读一个字符就检查当前状态如果进入接受状态就记录位置扫描到死状态时回退到最后一个接受位置。这种做法适合从连续字符流中切分 token。两种做法的区别在于对123abc这种输入的处理。第一种会直接判定整个串非法第二种会识别出123并停在a之前。实际词法分析器用的是第二种因为源代码里 token 是连续排列的你必须知道每个 token 的边界。实现第二种做法时需要维护一个lastAccept变量每次进入接受状态就更新它。当扫描到死状态或者输入结束时如果lastAccept有值就说明识别成功token 是从起点到lastAccept的子串。3.3 前导零与边界情况处理纯数字识别看起来简单但边界情况不少。我列几个实际会遇到的问题前导零007算不算合法无符号数从自动机角度它完全合法因为每个字符都是数字。但从语义角度有些场景不允许前导零。这属于词法规则之外的约束自动机本身不负责需要在识别后额外判断。空输入空串不是合法无符号数因为起始状态不是接受状态。这一点前面提过但实现时容易因为初始化逻辑写错而放行。超长数字自动机本身不关心数值大小但识别后如果要转成整数就要考虑溢出。这是识别之后的事但设计接口时要预留处理空间。正号123算不算无符号数严格来说不算因为不是数字。但有些场景允许可选正号这时状态机需要增加一个状态来处理后的数字。这些边界情况说明一个道理自动机识别的是语法形式不是语义约束。你要清楚自己的需求边界在哪里再决定状态机设计到什么程度。提示如果你的场景需要允许前导零但禁止全零以外的多位数前导零那已经超出正则语言的能力范围需要引入计数或额外逻辑。别试图用状态机硬扛那样状态数会爆炸。4. 实操过程与核心环节实现4.1 手写一个 DFA 识别器下面我用 Python 实现一个完整的无符号整数识别器。选择 Python 是因为它读起来接近伪代码方便你理解逻辑移植到其他语言也很容易。先定义状态和转移表# 状态编号 S, A, D 0, 1, 2 # 转移表table[state][char_type] # char_type: 0 表示数字1 表示非数字 table [ [A, D], # S [A, D], # A [D, D], # D ] def char_type(ch): if 0 ch 9: return 0 return 1然后是核心扫描函数采用“记录最后接受位置”的策略def recognize_unsigned_int(text): state S last_accept -1 for i, ch in enumerate(text): state table[state][char_type(ch)] if state A: last_accept i if state D: break if last_accept 0: return True, text[:last_accept 1] return False, 这段代码的逻辑是从头扫描每进入接受状态就记录位置。一旦进入死状态就停止。最后如果记录过接受位置就返回成功和对应的子串。测试几个用例print(recognize_unsigned_int(123)) # (True, 123) print(recognize_unsigned_int(007)) # (True, 007) print(recognize_unsigned_int(123abc)) # (True, 123) print(recognize_unsigned_int(abc)) # (False, ) print(recognize_unsigned_int()) # (False, )结果符合预期。123abc被正确切分为123空串和纯字母被拒绝。4.2 从整数扩展到带小数点的无符号数实际场景里无符号数往往还包括小数比如3.14、0.5。这时状态机需要扩展。新的规则是数字序列可选地后跟一个小数点再加数字序列。注意小数点前后都必须有数字所以.5和5.都不合法。状态设计变成四个S起始A整数部分已有至少一位数字B刚读到小数点等待小数部分C小数部分已有至少一位数字接受状态D死状态转移表当前状态数字小数点其他SADDAABDBCDDCCDDDDDD实现时把char_type扩展为三类转移表变成三列。核心扫描逻辑不变仍然是记录最后接受位置。这样3.14会一路走到 C3.会停在 B 然后因为输入结束而回退到 A识别出3。这个行为是否符合预期取决于你的需求如果要求小数点后必须有数字那3.识别出3是合理的因为3本身是合法整数。4.3 用状态机驱动一个简易词法分析器单个识别器只能处理一种 token。要体现自动机的真正价值可以把它扩展成一个能同时识别数字、标识符和运算符的简易词法分析器。思路是把所有 token 的状态机合并成一个大状态机每个接受状态标记它对应的 token 类型。扫描时每进入一个接受状态就记录位置和类型遇到死状态就回退输出最后一个接受的 token然后从该位置继续扫描。这种“最长匹配”策略是词法分析的标准做法。比如输入abc123标识符状态机会一直匹配到末尾输出标识符abc123而不是先输出abc再输出123。这就是为什么关键字和标识符的识别要放在一起靠最长匹配和优先级来区分。实现时状态表会变大但核心逻辑还是那套转移、记录、回退、继续。你会发现一旦框架搭好增加新 token 类型只是往表里加行加列的事这就是自动机方案的可扩展性优势。5. 常见问题与排查技巧实录5.1 状态机实现中的典型 bug我在实现和教学过程中见过太多相似的错误这里整理成一张速查表问题现象可能原因排查方法空串被判定为合法起始状态被误设为接受状态检查接受状态集合是否包含 S123abc整体被拒绝没有记录最后接受位置只看最终状态改为记录 lastAccept 策略死状态后程序崩溃转移表缺少死状态的自环补全 table[D][*] D小数点后无数字仍接受小数点状态被误设为接受检查接受状态是否只包含 C超长数字识别后溢出识别与转换未分离先识别字符串再单独处理转换这些问题的共同点是状态设计阶段的疏忽会在实现阶段放大。所以我的建议是动手写代码之前先在纸上把状态图画完整包括所有转移和接受状态标记然后再翻译成代码。这一步花十分钟能省掉后面一小时的调试。5.2 性能与可读性的平衡状态转移表用二维数组实现查询是 O(1)性能很好。但状态多了以后数组会变得难以阅读因为你看不出table[3][2]到底代表什么。我的经验是状态少的时候用数组状态多的时候用字典加枚举。比如用State.S、CharType.DIGIT这样的命名代码可读性会大幅提升性能损失可以忽略。如果确实对性能敏感可以在初始化时把字典编译成数组兼顾两者。另一个技巧是把转移表写成数据文件或者用代码生成这样修改规则时不用动核心逻辑。这在需要支持多种数字格式的场景下特别有用。5.3 自动机方案的适用边界最后说一个容易被忽视的问题自动机不是万能的。它能识别的是正则语言也就是不需要计数就能描述的模式。无符号数恰好属于这一类所以自动机很合适。但如果你要识别的是“括号配对”“嵌套结构”“缩进敏感的语言”自动机就无能为力了因为那些需要栈或者计数器。这时候你需要下推自动机或者更强大的模型。搞清楚这个边界能帮你避免在错误的方向上浪费时间。注意不要试图用状态机去解析 JSON 或 XML 的嵌套结构那是语法分析器的活。词法分析器只负责把字符流切成 token嵌套关系交给语法分析阶段处理。我在实际项目里遇到过一个案例有人想用正则表达式匹配嵌套的括号写了上百行的模式还是漏掉边界情况。后来换成递归下降解析器二十行代码就解决了。这个教训说明选对工具比硬扛重要得多。6. 从识别器到可复用组件的封装思路6.1 接口设计要点把识别器封装成可复用组件时接口设计决定了它好不好用。我倾向于暴露三个东西一个初始化函数、一个扫描函数、一个结果结构。初始化函数接收配置比如是否允许小数点、是否允许前导零。扫描函数接收字符串和起始位置返回识别结果和下一个位置。结果结构包含是否成功、识别的子串、token 类型。这样的接口既适合单次识别也适合嵌入更大的词法分析循环。关键是不要把状态机的内部细节暴露出去调用方只关心“给我一个串告诉我是不是数字到哪里结束”。6.2 测试用例的设计自动机的测试用例要覆盖三类正常路径、边界情况、非法输入。正常路径包括0、9、123、999999。边界情况包括空串、单个数字、超长数字、前导零。非法输入包括纯字母、字母数字混合、只有小数点、小数点开头、小数点结尾。我习惯把这些用例写成一个表每行是输入和期望输出跑一遍就能验证。这种表驱动测试的好处是增加新规则时只需加行不用改测试逻辑。6.3 与其他模块的协作在完整的编译器或解释器里无符号数识别器只是词法分析器的一部分。它需要和标识符识别器、运算符识别器协同工作共享字符流和位置信息。协作的关键是最长匹配和优先级。比如123既可以被数字识别器接受也可以被标识符识别器接受如果标识符允许数字开头。这时需要约定优先级通常数字优先因为123更自然地解释为数字。另一个协作点是错误恢复。当所有识别器都失败时词法分析器需要报告错误并跳过当前字符继续扫描。这个逻辑不属于单个识别器但识别器需要提供足够的信息让上层做决策。7. 我个人的实操体会与建议回过头看无符号数的自动机识别虽然是个小题目但它把形式语言的核心概念串了一遍状态、转移、接受、确定化、最长匹配。把这套东西吃透再看词法分析器、正则引擎、协议解析器会发现底层逻辑是相通的。我的建议是不要满足于“能跑就行”。动手画状态图手工推几个输入再写代码验证。遇到不符合预期的结果先回去检查状态图而不是急着改代码。状态图对了代码自然对状态图错了代码怎么调都是补丁摞补丁。另外如果你打算把这个识别器用在真实项目里记得把识别和转换分开。识别器只负责判断“这是不是一个合法数字串”转换器负责把字符串变成整数或浮点数。这样职责清晰测试也容易写。我见过太多把两者混在一起的代码最后溢出、精度、前导零的问题搅成一团改都改不动。最后分享一个小技巧在状态机的转移函数里加一个可选的日志开关每次转移时打印当前状态、输入字符、下一个状态。调试复杂状态机时这个日志比断点还好用因为它能让你看到完整的转移路径一眼就能定位到哪一步走错了。这个习惯我保持了多年几乎每个状态机项目都会加上。