从零手写词法生成器：DFA原理与代码实现-北京尧图网络

1. 从零手写词法生成器为什么第一步是DFA编译原理这门课很多人学到词法分析就开始发懵。教材上正则表达式、NFA、DFA、子集构造法一路推下来公式写得满满当当但真让你动手写一个能跑的词法生成器往往不知道从哪下手。我当时做这个实验的时候也一样盯着“确定有穷状态机”这几个字看了半天心想这玩意儿到底怎么变成代码。后来想通了词法分析器的本质就是一台状态机。你给它一串字符它一个字符一个字符地吃进去每吃一个就根据当前状态和这个字符决定下一步跳到哪个状态。如果最后停在一个“接受状态”那就说明识别出了一个合法的单词Token。所谓“自己写一个词法生成器”第一步就是把这台状态机用代码实现出来让它能根据你定义的状态转移规则正确地跑完整个输入串。这个实验适合正在学编译原理、需要完成课程实验的同学也适合任何想理解“正则表达式引擎底层怎么工作”的开发者。哪怕你以后不做编译器状态机这套思路在协议解析、输入校验、游戏AI行为树里都用得上。我下面会从设计思路讲到代码实现再到调试过程中踩过的坑尽量把每一步的“为什么”说清楚让你看完能直接动手复现。2. 整体设计DFA到底该怎么用代码表达2.1 先搞清楚DFA的数学定义和代码映射DFA在教材上的标准定义是一个五元组状态集合Q、字母表Σ、转移函数δ、初始状态q0、接受状态集合F。刚看这个定义的时候觉得挺抽象但把它翻译成代码其实非常直接。状态集合Q就是一组整数或者枚举值比如0、1、2、3。字母表Σ就是你能识别的字符范围比如数字0-9、字母a-z。转移函数δ是核心它接收“当前状态”和“输入字符”两个参数返回“下一个状态”。初始状态q0就是程序启动时所在的默认状态。接受状态集合F就是那些“走到这里就算识别成功”的状态。用代码表达最直观的方式是用一个二维数组或者哈希表来存转移关系。假设状态用整数编号字符用ASCII码那转移表就是一个int transition[状态数][字符数]的二维数组。查表的时候直接next transition[current][ch]O(1)时间非常高效。但这里有个问题ASCII码有128个字符如果状态多的话二维数组会很大而且大部分格子是空的因为很多字符在当前状态下根本没有转移。所以实际写的时候我倾向于用哈希表嵌套外层key是当前状态内层是一个mapkey是字符value是下一个状态。这样只存有意义的转移节省空间查起来也不慢。2.2 为什么不用NFA直接跑教材里讲词法分析一般会先讲NFA非确定有穷状态机再讲如何通过子集构造法转成DFA。那为什么不直接实现NFA呢NFA的问题是“非确定”——同一个状态面对同一个输入字符可能有多个下一状态甚至可以不读字符就跳转ε转移。这意味着你的程序需要做回溯或者并行搜索实现复杂度高而且运行效率低。DFA则是“确定”的每个状态面对每个字符最多只有一个下一状态程序就是一个简单的循环读字符、查表、跳状态。没有回溯没有分支爆炸代码写起来清爽跑起来也快。所以工程上做词法分析器标准做法都是先把正则表达式转成NFA再用子集构造法转成DFA最后把DFA的转移表固化到代码或者数据文件里。这个实验的第一步就是先把DFA这个“运行时引擎”写好。后面你再加正则解析、NFA构造、子集构造都是往这个引擎里灌数据而已。2.3 状态机的输入输出设计一个DFA引擎需要什么输入至少需要转移规则状态转移表、初始状态、接受状态集合、待分析的字符串。输出是什么通常是“是否接受该字符串”或者更进一步“在哪个位置接受了什么Token”。对于词法生成器来说我们最终要的不是简单的“接受/拒绝”而是要把输入串切分成一个个Token。所以DFA引擎的设计要支持“最长匹配”从当前位置开始不断吃字符、跳状态每到达一个接受状态就记录一下当前位置直到无法继续转移为止然后回退到最后一个接受状态的位置输出一个Token再从那个位置继续下一轮。这个“最长匹配”逻辑是词法分析器的核心行为。比如输入if123你希望识别出if这个关键字然后123作为数字而不是把if123整个当成一个标识符。最长匹配加上优先级规则关键字优先于标识符才能正确处理。3. 核心细节转移表的构建与状态编码3.1 状态编号与接受状态的标记状态编号我习惯从0开始0固定作为初始状态。接受状态用一个布尔数组或者集合来标记比如accepting {2, 5, 7}表示状态2、5、7是接受状态。这里有个细节一个状态可以同时是接受状态也可以继续往外转移。比如识别标识符的时候读到第一个字母进入状态1状态1是接受状态因为单个字母也是合法标识符但同时状态1读到更多字母或数字还要继续跳到状态1自身。这种“接受且可继续”的状态在词法分析里非常常见。状态编码的时候我建议把不同Token类型的状态分开编号比如0初始状态1-9标识符/关键字相关状态10-19数字相关状态20-29运算符相关状态30-39分隔符相关状态这样调试的时候看状态编号就能大概知道在识别什么日志也好读。3.2 转移表的两种存法对比前面提到二维数组和哈希表两种方式这里详细对比一下。存储方式优点缺点适用场景二维数组查询O(1)内存连续缓存友好稀疏时浪费空间字符集大时数组巨大状态少、字符集小如ASCII哈希嵌套只存有效转移节省空间查询有哈希开销实现稍复杂状态多、字符集大、转移稀疏邻接表灵活易扩展查询需要遍历最坏O(n)转移极少、状态极多对于课程实验级别的词法生成器状态数一般几十个ASCII字符128个二维数组也就几十乘一百多完全能接受。而且二维数组写起来简单查表快调试直观。所以我第一版就用二维数组用-1表示“无转移”。#define MAX_STATES 100 #define MAX_CHARS 128 int transition[MAX_STATES][MAX_CHARS]; // 初始化全部为-1 memset(transition, -1, sizeof(transition)); // 添加转移状态0遇到字母跳到状态1 transition[0][a] 1;用-1表示无转移有个好处查表后判断next -1就知道卡住了逻辑清晰。3.3 字符分类与预处理直接拿原始字符去查转移表有个问题如果字母表很大转移表会爆炸。比如你要识别所有字母难道要把transition[0][a]到transition[0][z]一个个写一遍太蠢了。标准做法是先做字符分类。把字符分成若干类字母、数字、空白、运算符字符等。然后转移表是基于“字符类”而不是“具体字符”来建的。这样转移表的列数就从128降到几类大大缩小。int charClass(char c) { if (c a c z) return 0; // 字母 if (c 0 c 9) return 1; // 数字 if (c || c \t || c \n) return 2; // 空白 // ... 其他类别 return 3; // 其他 }然后转移表变成transition[状态][字符类]。查表时先算字符类再查表。多了一步分类但转移表小了一个数量级值得。注意字符分类函数要处理好边界比如大写字母、下划线、各种括号和运算符别漏了。漏一个字符可能导致某个Token识别失败而且这种bug很难查因为大部分输入都正常只有特定字符才触发。4. 实操过程从零写出可运行的DFA引擎4.1 定义Token类型和状态转移规则先明确我们要识别哪些Token。以一个简化版的C语言子集为例标识符、整数、加号、减号、乘号、除号、左括号、右括号、分号、空白。对应的正则定义大概是标识符[a-zA-Z_][a-zA-Z0-9_]*整数[0-9]运算符、-、*、/分隔符(、)、;空白[ \t\n]通常跳过然后手工构造DFA。状态设计如下状态0初始状态状态1正在识别标识符接受状态2正在识别整数接受状态3识别到接受状态4识别到-接受状态5识别到*接受状态6识别到/接受状态7识别到(接受状态8识别到)接受状态9识别到;接受状态10正在识别空白接受但通常跳过转移规则用文字描述状态0遇到字母或下划线跳到状态1遇到数字跳到状态2遇到跳到状态3遇到-跳到状态4遇到*跳到状态5遇到/跳到状态6遇到(跳到状态7遇到)跳到状态8遇到;跳到状态9遇到空白跳到状态10。状态1遇到字母、数字或下划线留在状态1其他字符则停止回退。状态2遇到数字留在状态2其他字符停止回退。状态3到状态10都是单字符Token读入一个字符后立即接受不需要继续。把这些规则填进转移表// 字符类0字母/下划线, 1数字, 2空白, 3其他 void initTransition() { memset(transition, -1, sizeof(transition)); // 状态0的转移 transition[0][0] 1; // 字母/下划线 - 标识符 transition[0][1] 2; // 数字 - 整数 transition[0][2] 10; // 空白 - 空白状态 // 运算符和分隔符需要单独处理因为它们不是字符类能覆盖的 // 这里为了简化把运算符也归入其他类然后在状态0特殊判断 }等等这里有个问题运算符和分隔符每个都是不同的字符如果都归入“其他”类状态0遇到“其他”类就不知道该跳哪个状态了。所以字符分类不能太粗运算符和分隔符需要单独分类或者干脆在状态0对具体字符做特判。我实际写的时候是这么处理的字符类分得细一点把每个运算符和分隔符都单独作为一类。虽然类多了但转移表还是比128列小得多。int charClass(char c) { if (isalpha(c) || c _) return 0; if (isdigit(c)) return 1; if (c || c \t || c \n) return 2; if (c ) return 3; if (c -) return 4; if (c *) return 5; if (c /) return 6; if (c () return 7; if (c )) return 8; if (c ;) return 9; return 10; // 其他未识别字符 }这样转移表的列数就是11状态数11总共121个格子非常小。4.2 实现最长匹配的扫描循环核心扫描函数大概长这样Token nextToken(char *input, int *pos) { int currentState 0; int lastAcceptState -1; int lastAcceptPos *pos; int i *pos; while (input[i] ! \0) { int cls charClass(input[i]); int nextState transition[currentState][cls]; if (nextState -1) { break; // 无法继续转移 } currentState nextState; i; if (isAccepting(currentState)) { lastAcceptState currentState; lastAcceptPos i; } } if (lastAcceptState -1) { // 没有接受任何Token报错或跳过 // 这里简单处理跳过当前字符 (*pos); return makeErrorToken(input[*pos - 1]); } // 回退到最后一个接受位置 *pos lastAcceptPos; return makeToken(lastAcceptState, input, lastAcceptPos); }这段代码的关键点第一lastAcceptState和lastAcceptPos记录最近一次到达接受状态的位置。因为DFA可能走过接受状态后继续走了一段但最后卡在非接受状态这时候要回退到最后一个接受状态。第二循环条件是input[i] ! \0遇到字符串结束就停。但实际词法分析器通常是在一个字符流上工作不是以\0为界这里为了实验简单用字符串。第三如果从头到尾都没到达过接受状态说明当前字符无法识别需要报错。报错策略可以是跳过、可以是终止看你的需求。4.3 接受状态的判定与Token生成isAccepting函数就是查一个布尔数组int accepting[MAX_STATES] {0}; // 初始化时标记 accepting[1] 1; // 标识符 accepting[2] 1; // 整数 accepting[3] 1; // // ... 以此类推makeToken根据接受状态反推Token类型并从输入中截取对应的字符串Token makeToken(int state, char *input, int endPos) { Token t; t.end endPos; switch (state) { case 1: t.type TOKEN_ID; break; case 2: t.type TOKEN_INT; break; case 3: t.type TOKEN_PLUS; break; // ... } return t; }这里有个细节标识符状态1既可能是普通标识符也可能是关键字如if、while。通常的做法是在识别出标识符后再查一张关键字表如果匹配就改成关键字Token。这个步骤放在Token生成之后做不影响DFA本身。4.4 主循环与测试主函数就是一个循环不断调用nextToken直到输入结束int main() { char input[] int x 123 456;; int pos 0; initTransition(); initAccepting(); while (input[pos] ! \0) { Token t nextToken(input, pos); printToken(t, input); } return 0; }测试用例要覆盖各种情况纯标识符、纯数字、标识符数字混合、各种运算符、空白、非法字符。我建议每加一条转移规则就写一个对应的测试别等全部写完再测不然出了bug你都不知道是哪条规则的问题。5. 常见问题与排查技巧实录5.1 状态转移表填错了怎么快速定位这是最常见的bug。表现是某个Token识别不出来或者识别成了错误的类型。排查方法在扫描循环里加日志打印每次状态转移的currentState、输入字符、nextState。然后拿一个最小复现输入跑一遍看状态跳转是否符合预期。比如输入ab预期是状态0 - 状态1 - 状态1最后接受为标识符。如果日志显示状态0 - 状态1 - 状态-1那说明状态1遇到字母b的转移没填。回去检查转移表初始化代码补上transition[1][0] 1。我踩过的坑是字符分类函数里把下划线忘了导致_foo这种标识符识别失败。这种bug很隐蔽因为大部分标识符不以_开头。所以字符分类函数一定要对着ASCII表仔细过一遍。5.2 最长匹配回退逻辑写错的典型表现回退逻辑写错通常有两种表现一是Token被截断比如abc123只识别出abc123丢了二是Token被吞并比如if把if整个当成一个标识符。第一种情况通常是lastAcceptPos没有在每次到达接受状态时更新或者更新了但回退时用错了变量。第二种情况通常是接受状态标记错了把不该接受的状态标成了接受。排查方法打印每次接受状态更新时的lastAcceptState和lastAcceptPos以及最终回退的位置。对比预期就能看出是哪一步出了问题。5.3 空白和注释的处理策略空白字符空格、制表符、换行通常不作为Token返回而是直接跳过。但跳过的逻辑要小心不能简单地在主循环里if (isspace(c)) continue;因为空白可能出现在Token中间虽然正常代码里不会但输入可能不规范。更稳妥的做法是把空白也作为一个DFA状态识别到空白Token后直接丢弃继续下一轮。注释的处理更复杂因为注释有单行//和多行/* */两种。单行注释相对简单识别到//后一直吃到换行。多行注释需要跨行匹配状态机要能处理/*和*/的配对。这个实验如果只要求基础词法可以先不做注释后面再扩展。5.4 常见问题速查表问题现象可能原因排查方法解决方案某类Token完全识别不出转移表对应列全为-1检查字符分类函数和转移表初始化补上对应转移Token被截断lastAcceptPos未更新或回退错误打印接受状态更新日志修正回退逻辑Token被吞并接受状态标记过多检查accepting数组只标记真正的接受状态程序死循环状态转移形成环且无接受状态打印状态序列确保每个环上至少有一个接受状态或加最大步数限制非法字符导致崩溃未处理无转移情况检查nextState -1分支添加错误处理跳过或报错实操心得调试DFA最好的工具就是日志。别嫌日志多状态机这种确定性系统只要日志够详细bug基本一眼就能看出来。我习惯在开发阶段把每次状态转移都打出来上线前再关掉。6. 从DFA到完整词法生成器的扩展思路DFA引擎跑通之后下一步就是让它“自动生成”。现在的转移表是手工填的状态和规则都是硬编码的。真正的词法生成器应该支持输入正则表达式自动构造NFA再转成DFA最后生成转移表。这个扩展路径大概是正则表达式 - 语法树 - NFAThompson构造法 - DFA子集构造法 - 最小化DFA - 生成转移表。每一步教材上都有详细算法实现起来工作量不小但有了DFA引擎这个基础后面就是往里面灌数据。另一个扩展方向是支持更复杂的Token类型比如浮点数、字符串字面量、多字符运算符、!、。这些只需要增加状态和转移规则DFA引擎本身不用改。这也体现了DFA设计的优势引擎和规则分离扩展规则不影响引擎。我在实际做这个实验的时候最大的体会是别一上来就想着写完整的词法生成器。先把DFA引擎写扎实用几个简单规则测通确保最长匹配、回退、接受状态判定这些核心逻辑没问题。然后再逐步加规则、加Token类型。这样每一步都有反馈不会写到一半发现底层有bug要推倒重来。最后分享一个小技巧转移表可以用脚本生成。你用一个简单的文本格式描述状态转移规则写个Python脚本读进去生成C数组代码比手工填表靠谱得多。状态一多手工填表必出错而且改起来痛苦。用脚本生成改规则就是改文本重新生成一下就行。

从零手写词法生成器：DFA原理与代码实现

相关推荐

2026 AI编程工具选型指南：33款主流工具六大场景实测推荐

Ubuntu下迁移Conda环境

挂载mount

更多资讯

biliTickerBuy 抢票辅助工具：扫码登录到一键开抢的完整上手指南

Unity 构建序列化：level0、sharedassets、resources.assets

从裸机到内核：操作系统实验核心机制与避坑实战

Mhvtl虚拟带库+TSM搭建Oracle Rman备份与异机恢复实战

IDEA中Tomcat启动成功但页面404的三大根源与修复

AtlasOS 驱动与中断优化指南：从诊断到回滚的实操教程

今日更新

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？