从零实现DFA：编译原理词法分析器核心实战

1. 从“能跑就行”到“状态清晰”为什么词法分析的第一步是DFA很多人第一次接触编译原理实验看到“词法生成器”四个字第一反应是打开搜索引擎找一段现成的正则表达式引擎代码或者干脆用std::regex把token切出来交差。我当年也动过这个念头但真正动手写完之后才明白实验一让你先实现一个确定有穷状态机DFA不是为了折腾你而是因为词法分析器的本质就是一个被高度优化过的DFA。你后面要写的词法生成器无论是手写状态转移还是用自动机工具生成底层跑的都是同一个东西。DFA这个东西说穿了特别朴素它有一组有限的状态一个输入字符集一个转移函数一个初始状态以及若干个接受状态。每读入一个字符就根据当前状态和这个字符决定跳到哪个状态如果跳到一个接受状态就说明刚才读入的那段字符构成了一个合法的词素。就这么简单。但简单不等于好写尤其是当你需要处理标识符、关键字、数字常量、运算符、界符这些混杂在一起的情况时状态的数量和转移关系会迅速膨胀手写if-else或者switch-case很快就会变成一坨难以维护的代码。所以这篇内容的核心目标很明确带你从零实现一个结构清晰、可扩展、可调试的DFA并用它完成一个简化版词法分析器的字符识别任务。适合正在做编译原理实验的同学也适合任何想理解“正则表达式引擎底层到底在干什么”的开发者。我不会只给你一段代码就完事而是会把设计决策、状态编码、转移表的组织方式、调试技巧、以及我踩过的坑全部摊开讲。你跟着走一遍后面写完整的词法生成器时会发现自己对状态的理解完全不一样了。提示本文假设你至少写过C或Java知道结构体和数组的基本用法。如果你用的是Python思路完全一样只是转移表的表达方式更灵活。2. 状态机建模先把“词”拆成状态再谈代码2.1 词法单元的状态抽象从正则到状态图在写任何代码之前必须先把你要识别的词法单元用状态图描述出来。假设我们的实验要求识别以下几类token标识符以字母或下划线开头后跟字母、数字或下划线。无符号整数以数字开头后跟数字。关键字if、else、while、return等本质上和标识符共享同一套字符规则但需要在识别后查表区分。运算符、-、*、/、、、!、、、、。界符(、)、{、}、;、,。空白字符空格、制表符、换行通常跳过。把这些规则画成状态图你会发现标识符和关键字可以共用一条路径从初始状态出发遇到字母或下划线进入“标识符主体”状态继续读字母数字下划线就留在该状态读到其他字符就接受并回退。数字同理。运算符稍微麻烦一点因为和、和、和、!和!存在前缀关系需要多一个状态来区分“只读到一个字符”和“读到两个字符”的情况。这里有一个关键设计决策是否把所有token的识别塞进同一个DFA。我的建议是实验一阶段先分开做每个token类型一个独立的DFA函数比如scanIdentifier()、scanNumber()、scanOperator()。这样做的好处是调试极其方便你可以单独测试每个函数确认状态转移正确后再考虑合并。合并成一个大DFA虽然理论上是等价的但调试成本会指数级上升尤其是当某个状态转移写错时你很难定位到底是哪条规则出了问题。2.2 状态编码用枚举还是整数常量状态怎么表示最直观的方式是用枚举enum class State { START, IN_ID, IN_NUM, IN_OP, IN_OP_EQ, DONE, ERROR };枚举的好处是代码可读性高调试时打印状态名一目了然。但如果你后面要写一个通用的词法生成器状态数量是动态的枚举就不适用了得用整数索引加转移表。实验一阶段我建议先用枚举把逻辑跑通等理解透了再改成表驱动。转移函数怎么写最朴素的方式是switch-caseState transition(State current, char ch) { switch (current) { case State::START: if (isalpha(ch) || ch _) return State::IN_ID; if (isdigit(ch)) return State::IN_NUM; if (isOperatorChar(ch)) return State::IN_OP; return State::ERROR; case State::IN_ID: if (isalnum(ch) || ch _) return State::IN_ID; return State::DONE; // ... 其他状态 } }这种写法在状态少的时候没问题但状态一多switch会变得非常长而且每个状态的处理逻辑散落在不同的case里修改起来容易漏。更好的方式是用二维数组做转移表行是状态列是字符类别值是下一个状态。字符类别需要预先归类比如把所有字母归为一类所有数字归为一类把单独归为一类等等。// 字符类别索引 enum CharClass { CC_LETTER, // 字母或下划线 CC_DIGIT, // 数字 CC_EQ, // CC_LT, // CC_GT, // CC_BANG, // ! CC_OTHER, // 其他字符 CC_COUNT }; // 转移表trans[当前状态][字符类别] 下一个状态 State trans[STATE_COUNT][CC_COUNT] { // START行 { State::IN_ID, State::IN_NUM, State::IN_OP, State::IN_OP, State::IN_OP, State::IN_OP, State::ERROR }, // IN_ID行 { State::IN_ID, State::IN_ID, State::DONE, State::DONE, State::DONE, State::DONE, State::DONE }, // ... 其他行 };表驱动的好处是状态转移关系一目了然你可以直接对着状态图填表填完之后检查每一行是否覆盖了所有字符类别。而且后面如果要增加新的token类型只需要增加状态和对应的行不需要改动转移逻辑的代码结构。这是从“手写状态机”到“词法生成器”的关键一步。2.3 接受状态与回退为什么需要“多看一个字符”DFA的一个核心特性是它不知道什么时候该停下来。比如识别标识符abc你读到a进入IN_ID读到b还在IN_ID读到c还在IN_ID读到空格时发现空格不属于标识符字符集此时你才知道标识符结束了。但问题是空格已经被你读进来了它不属于标识符你需要把它“退回去”让下一个token的扫描从空格开始。这就是所谓的**回退retract**机制。实现方式很简单维护一个输入指针pos每次读取字符时pos如果需要回退就pos--。但要注意回退只能回退一个字符因为DFA每次只多看一个字符就能确定当前token是否结束。这也是DFA相对于NFA的优势之一不需要回溯多个字符效率高。char getChar() { if (pos input.size()) return input[pos]; return \0; // EOF } void retract() { if (pos 0) pos--; }在实际写代码时我习惯把“读取-判断-回退”封装成一个循环State state State::START; std::string lexeme; while (true) { char ch getChar(); State next trans[state][charClass(ch)]; if (next State::ERROR || next State::DONE) { retract(); break; } lexeme ch; state next; }这里有一个容易踩的坑EOF的处理。当getChar()返回\0时charClass应该把它归为CC_OTHER这样从IN_ID状态会转移到DONE然后回退。但回退之后pos指向的是\0的位置下一次循环又会读到\0如果不做特殊处理可能会陷入死循环。我的做法是在主循环里判断pos是否已经到达输入末尾如果是且当前状态是START就直接结束。注意回退操作在表驱动DFA里是必须的但如果你用的是“最长匹配”策略回退逻辑需要更小心。实验一阶段建议先用最简单的“读到一个不属于当前token的字符就回退”策略等跑通了再考虑优化。3. 从状态表到可运行代码一个极简DFA的完整落地3.1 字符分类函数的实现细节字符分类是DFA的入口分类错了后面全错。我见过不少同学直接写if (ch a ch z)这样写本身没错但可移植性差而且容易漏掉大写字母和下划线。更稳妥的方式是用标准库函数isalpha、isdigit、isalnum但要注意这些函数对char参数有符号性问题最好先转成unsigned char。int charClass(char ch) { if (isalpha(static_castunsigned char(ch)) || ch _) return CC_LETTER; if (isdigit(static_castunsigned char(ch))) return CC_DIGIT; switch (ch) { case : return CC_EQ; case : return CC_LT; case : return CC_GT; case !: return CC_BANG; default: return CC_OTHER; } }这里有一个设计上的取舍是否把、、、!单独分类。如果你把它们都归为CC_OTHER那么从START状态遇到这些字符时你无法区分到底是哪个运算符需要额外读取字符来判断。单独分类的好处是转移表可以直接根据字符类别决定下一个状态不需要在转移函数里再做判断。代价是字符类别数量增加转移表的列数变多。实验一阶段我倾向于单独分类因为这样转移表的逻辑更清晰调试时也更容易看出问题。3.2 转移表的填充与验证转移表填完之后必须做验证。验证的方法很简单手动模拟几个典型输入看状态转移是否符合预期。比如输入abc123从START开始遇到aCC_LETTER转到IN_ID遇到b还在IN_ID遇到c还在IN_ID遇到1CC_DIGIT还在IN_ID遇到2还在IN_ID遇到3还在IN_ID遇到EOFCC_OTHER转到DONE回退接受。整个过程状态序列是START - IN_ID - IN_ID - IN_ID - IN_ID - IN_ID - IN_ID - DONE词素是abc123。再比如输入从START遇到CC_EQ转到IN_OP再遇到CC_EQ转到IN_OP_EQ遇到EOF转到DONE接受词素是。如果输入是后面跟一个字母比如a从START遇到转到IN_OP遇到aCC_LETTER时IN_OP行对应的CC_LETTER列应该是什么应该是DONE因为本身就是一个合法的运算符遇到字母说明运算符结束了需要回退。所以IN_OP行的CC_LETTER列填DONECC_EQ列填IN_OP_EQ其他列填DONE。这种手动模拟虽然笨但非常有效。我建议你在纸上画一个表格行是状态列是字符类别把每个格子填上目标状态然后逐个检查。填完之后用几个边界情况测试空输入、只有空白字符、只有单个运算符、标识符后直接跟运算符如ab、数字后直接跟字母如123abc这应该报错还是识别为两个token取决于你的实验要求。3.3 主循环与Token输出主循环的逻辑是跳过空白字符然后根据当前字符决定调用哪个扫描函数扫描完成后输出token类型和词素继续下一轮。std::vectorToken tokenize(const std::string input) { std::vectorToken tokens; size_t pos 0; while (pos input.size()) { // 跳过空白 while (pos input.size() isspace(static_castunsigned char(input[pos]))) pos; if (pos input.size()) break; char ch input[pos]; if (isalpha(static_castunsigned char(ch)) || ch _) { tokens.push_back(scanIdentifier(input, pos)); } else if (isdigit(static_castunsigned char(ch))) { tokens.push_back(scanNumber(input, pos)); } else { tokens.push_back(scanOperator(input, pos)); } } return tokens; }每个scan函数的内部逻辑就是前面说的DFA循环。以scanIdentifier为例Token scanIdentifier(const std::string input, size_t pos) { State state State::START; std::string lexeme; while (pos input.size()) { char ch input[pos]; State next trans[state][charClass(ch)]; if (next State::DONE || next State::ERROR) break; lexeme ch; pos; state next; } // 查关键字表 TokenType type isKeyword(lexeme) ? TokenType::KEYWORD : TokenType::IDENTIFIER; return Token(type, lexeme); }注意这里没有显式的回退操作因为我们在循环里先判断next如果是DONE或ERROR就不消费当前字符pos保持不变相当于自动回退了。这种写法比先消费再回退更简洁也不容易出错。提示关键字识别不要用一堆if-else用一个std::unordered_setstd::string或者std::map查表代码更干净扩展也方便。4. 调试DFA时最容易翻车的几个地方4.1 状态转移表的行列错位这是最隐蔽的bug。你填表的时候可能把某一行的列顺序记错了比如把CC_EQ和CC_LT的顺序搞反了结果被识别成。这种错误在代码里不会报错只会导致token类型错误而且往往要到测试阶段才发现。我的建议是在转移表旁边写注释标明每一列对应的字符类别并且在初始化时用static_assert检查列数是否匹配。// trans[state][charClass] // 列顺序CC_LETTER, CC_DIGIT, CC_EQ, CC_LT, CC_GT, CC_BANG, CC_OTHER State trans[STATE_COUNT][CC_COUNT] { ... }; static_assert(sizeof(trans[0]) / sizeof(trans[0][0]) CC_COUNT, 列数不匹配);另外每次修改转移表后重新跑一遍所有测试用例不要只跑你正在调试的那个。我吃过这个亏改了一个状态转移结果另一个不相关的token识别挂了排查了半天才发现是表填错了。4.2 回退逻辑与EOF的边界情况回退逻辑在输入末尾特别容易出问题。假设输入是abc没有换行符。扫描标识符时读到c之后pos已经等于input.size()下一次循环pos input.size()为假直接退出词素是abc正确。但如果输入是abc末尾有空格扫描到空格时next是DONE不消费空格pos指向空格返回标识符。主循环下一轮跳过空格pos到达末尾结束。看起来没问题。但如果你在scanIdentifier里用了getChar()和retract()的写法就要小心EOF的处理。getChar()在pos input.size()时返回\0retract()会把pos减一如果pos已经是0减一就变成负数了。所以retract()里必须加if (pos 0)的判断。这个bug在输入为空或者只有一个字符时特别容易触发。4.3 关键字与标识符的优先级关键字和标识符共享同一套字符规则区别只在于识别完成后查表。这里有一个常见的错误在DFA内部就把关键字识别出来。比如在IN_ID状态里判断当前词素是否是关键字如果是就转到KEYWORD状态。这样做的问题是关键字表是动态的而且DFA的状态应该只负责字符层面的识别不应该掺杂语义判断。正确的做法是DFA只负责识别出“这是一个标识符形状的词素”然后在外层查关键字表决定是IDENTIFIER还是KEYWORD。这个设计原则在后面写词法生成器时非常重要DFA只做字符识别语义分析交给外层。这样DFA的转移表可以保持稳定增加关键字不需要修改状态机。4.4 运算符的前缀匹配问题和、和、和、!和!这几组运算符存在前缀关系。处理方式有两种一种是最长匹配即尽可能读入更多字符直到无法构成更长的运算符为止另一种是优先匹配短运算符即读到就立即返回不检查下一个字符是否是。显然最长匹配才是正确的因为是一个独立的运算符不能被拆成两个。实现最长匹配的关键是在IN_OP状态遇到时不要立即接受而是转到IN_OP_EQ状态继续读下一个字符。如果下一个字符不是则回退接受IN_OP状态的词素即单个。如果下一个字符是则接受IN_OP_EQ状态的词素即。这个逻辑在转移表里体现为IN_OP行的CC_EQ列填IN_OP_EQIN_OP_EQ行的所有列填DONE因为已经是最长的了后面跟任何字符都说明运算符结束。但这里有一个细节!单独出现时通常不是合法运算符除非你的语言支持逻辑非所以!后面必须跟才是合法的!。如果输入是!a应该报错。这个逻辑需要在转移表里体现IN_OP状态遇到!转到IN_OP_BANG状态IN_OP_BANG状态遇到转到IN_OP_NEQ状态遇到其他字符转到ERROR。这样!a就会在IN_OP_BANG状态遇到a时转到ERROR报错。注意实验一阶段如果你的实验要求不涉及!可以简化处理把!单独作为一个运算符或者直接报错。但理解这个前缀匹配的逻辑对后面写完整的词法分析器非常重要。5. 从实验一延伸到词法生成器DFA只是起点5.1 表驱动DFA的通用化改造实验一你写的是一个针对特定token集合的DFA。但词法生成器的目标是给定一组正则表达式自动生成DFA。这意味着你不能把状态和转移关系硬编码在代码里而应该把它们作为数据结构的输入。改造的思路是把状态定义、字符类别定义、转移表、接受状态集合、每个接受状态对应的token类型全部用数据结构表示。然后写一个通用的runDFA函数接收这些数据结构和输入字符串输出token序列。struct DFADefinition { int stateCount; int startState; std::vectorint acceptStates; std::vectorstd::vectorint transitionTable; // [state][charClass] std::vectorTokenType acceptTypes; // 每个接受状态对应的token类型 };这样当你后面用正则表达式构造NFA、再转换成DFA时只需要生成这个DFADefinition结构然后交给通用的runDFA执行即可。实验一的手写DFA本质上是在手动填充这个结构理解了这个映射关系后面的自动化生成就顺理成章了。5.2 从DFA到NFA再到正则反向理解词法生成器如果你已经理解了DFA的工作方式下一步可以反过来想给定一个正则表达式怎么构造出对应的DFA标准的路径是正则表达式 - NFAThompson构造法 - DFA子集构造法 - DFA最小化 - 生成转移表。实验一你写的是最后一步的“执行”部分而词法生成器的核心是前面的“构造”部分。我建议你在完成实验一之后尝试手动把一个简单的正则表达式比如[a-z][a-z0-9]*转换成NFA再用子集构造法转换成DFA最后和实验一里手写的标识符DFA对比。你会发现子集构造法生成的DFA状态可能比你手写的多但经过最小化之后状态数量会减少到和你手写的差不多。这个过程能让你真正理解“为什么DFA是最优的”。5.3 性能考量DFA为什么比正则表达式引擎快很多人会问既然std::regex已经能匹配正则表达式了为什么还要自己写DFA答案很简单性能。std::regex通常是基于回溯的NFA实现最坏情况下时间复杂度是指数级的。而DFA的时间复杂度是线性的每个字符只需要一次状态转移没有回溯。对于编译器这种需要处理大量源代码的场景DFA的效率优势非常明显。当然DFA也有缺点状态爆炸。当正则表达式的数量很多时DFA的状态数量可能急剧增加。这就是为什么实际的词法生成器如Flex会提供DFA最小化和表压缩的选项。实验一阶段你不需要考虑这些但理解这个权衡对你后面选择工具和优化代码很有帮助。提示如果你对DFA最小化感兴趣可以看看Hopcroft算法。它的核心思想是把状态划分成等价类然后合并等价状态。实验一阶段可以先跳过等词法生成器跑通了再回头优化。6. 一些让我少走弯路的实操习惯写DFA代码的时候我养成了几个习惯后来发现非常省时间。第一个习惯是先画状态图再写代码。状态图不用很漂亮用纸笔或者画图工具都行关键是每个状态的含义、每条转移的条件、哪些是接受状态必须清清楚楚。我见过太多同学直接上手写switch-case写到一半发现状态不够用又回头改改着改着就乱了。第二个习惯是为每个状态写一个测试用例。比如START状态测试空输入、测试单个字母、测试单个数字、测试单个运算符IN_ID状态测试字母后跟字母、字母后跟数字、字母后跟运算符、字母后跟EOF。每个测试用例不需要很复杂但必须覆盖该状态的所有出边。这样一旦某个转移写错测试会立刻告诉你。第三个习惯是打印状态转移日志。在DFA循环里加一行调试输出打印当前状态、读入字符、下一个状态。跑测试的时候打开日志一眼就能看出状态转移是否符合预期。这个习惯在调试复杂的DFA时特别有用因为你可以看到完整的转移路径而不是只看到最终结果。#ifdef DEBUG std::cerr State: stateName(state) , Char: ch , Next: stateName(next) std::endl; #endif最后一个习惯是保持转移表的单一数据源。状态定义、字符类别定义、转移表这三者必须保持一致。我通常会把它们放在同一个头文件里用枚举定义状态和字符类别用二维数组定义转移表然后在代码里只通过枚举名访问不直接写数字。这样即使后面增加状态或字符类别编译器也会帮你检查数组维度是否匹配。这些习惯看起来琐碎但在我后来写词法生成器的时候它们帮我节省了大量调试时间。DFA本身不复杂复杂的是状态之间的交互和边界情况。把状态图、测试用例、日志、单一数据源这四件事做好你就能把DFA写得又快又稳。