简介面向编译原理初学者与课程实验需求这份北京邮电大学词法分析器实验包围绕编译器前端扫描器的设计与实现展开适合正在学习词法规则、记号识别与错误处理的学生对照实践。压缩包共4个文件以2个txt说明与测试文本、1个h头文件和1个cpp源文件为主整体约10KB体量轻便便于快速查看核心代码与实验材料。已有1000人学习下载。内容覆盖词法规则定义、输入处理、分词逻辑、符号栈管理及错误处理等关键环节附带的说明与测试文本可用于验证标识符、关键字、常量、运算符等词素的识别效果。读者可借助源代码理解从词法规则到扫描算法的落地方式梳理实验实现思路并对照测试用例排查边界情况与异常输入为后续语法分析学习打基础。1. 课程实验的真相一个词法分析器到底要跑通哪几步“编译原理”这门课最劝退的时刻不是推文法而是实验一那天下午——你打开压缩包里面躺着一份能直接编译运行的词法分析器源码、一组 .c 风格的测试用例而实验指导书只有三页。这份课程实验资源干的事很具体把一段类 C 源程序切成一串 Token每个 Token 带上类型、原始词素和行列号交给后面的语法分析器直接消费。它适合两类人被实验一卡住、想先跑通再回头啃原理的以及自己写完了但输出格式对不上、想找份参考实现做对照的。词法分析器看着简单真正拉开分数的往往是关键字表顺序、最长匹配回退、注释与换行处理这些边角玄学得很。2. 项目结构与技术选型C 手写扫描器 正则到 DFA 的两条路线拿到包先别急着 make先把目录摊开看。这类实验项目通常有两条并行的实现路线一条是纯手写的扫描器一个字符一个字符往前啃边啃边判断另一条是把词法规则写成正则表达式走 Thompson 构造 → 子集构造 → DFA 最小化的标准流水线最终生成一张状态转移表来驱动扫描。两条路线通常共用同一套 Token 定义和测试用例方便你在实验报告里做对比。2.1 目录结构src 放实现rules 放规则test 放验收我按常见组织方式把目录梳理成下面这样你对照自己包里的文件应该能一一对上lexer-lab/ ├── src/ │ ├── main.cpp # 入口读文件、循环取 token、按格式打印 │ ├── scanner.h/.cpp # 手写扫描器最长匹配 回退 │ ├── regex_parser.h/.cpp # 正则表达式解析成后缀形式 │ ├── nfa.h/.cpp # Thompson 构造正则 - NFA │ ├── dfa.h/.cpp # 子集构造 Hopcroft 最小化 │ └── token.h # Token / TokenType 定义全项目共用 ├── rules/ │ └── tokens.rules # 词法规则表名字 正则 ├── test/ │ ├── case01_basic.c │ ├── case02_keywords.c │ ├── case03_comment.c │ └── expected/ # 每个 case 对应的期望 token 流 ├── Makefile └── README.mdsrc/里最容易被忽略的是token.h——它是整个项目的契约扫描器、DFA 生成器、打印逻辑全都要 include 它。rules/tokens.rules是可扩展性的关键规则写成一行一条的形式改词法不用动 C 代码重新跑一遍生成流程即可。test/expected/是验收标准很多同学跑出来“看着像对的”一比对 expected 就发现行列号差了一位。提示动手前先find . -name *.rules -o -name *.l确认项目用的是自定义规则文件还是 lex/flex 的 .l 文件这决定你后面改规则的方式完全不同。2.2 核心数据结构Token、TokenType 与符号表整个项目的数据流就围绕一个结构体转。先把类型枚举写清楚后面所有逻辑都是围绕它做的分派// src/token.h #pragma once #include string enum class TokenType { KW_INT, KW_IF, KW_ELSE, KW_WHILE, KW_RETURN, // 关键字 ID, // 标识符 NUM, // 整数字面量 FLOAT_LIT, // 浮点字面量 STR_LIT, // 字符串字面量 OP, // 运算符 - * / 等 DELIM, // 分隔符 ( ) { } ; , COMMENT, // 注释可选大部分实现直接丢弃 ERROR, // 非法字符 END_OF_FILE // 文件结束 }; struct Token { TokenType type; // 词法单元类型 std::string lexeme; // 原始词素保留原样便于报错 int line; // 起始行号从 1 开始 int column; // 起始列号从 1 开始 };lexeme存原始字符串而不是自己再拼一遍是为了报错时能原样打印“第 7 行第 12 列附近出现非法字符 #”而不是让用户猜。line/column记的是词素的起始位置不是结束位置——语法分析器报错时更关心“这个词从哪开始的”。标识符还要过一道符号表重复出现的名字复用同一个 id这样实验二建符号表时能直接接上// 扫描器内部维护用于标识符去重 class SymbolTable { public: // 返回该标识符的稳定编号第一次见就分配新号 int intern(const std::string name) { auto it table_.find(name); if (it ! table_.end()) return it-second; int id static_castint(table_.size()); table_.emplace(name, id); return id; } private: std::unordered_mapstd::string, int table_; };参数说明intern的入参是识别出来的完整标识符字符串返回值是稳定编号。用unordered_map而不是map是因为这里不需要有序遍历只查不遍历平均 O(1) 比红黑树的 O(log n) 划算。如果你后面要按字典序输出符号表再换回map就行。2.3 输入输出约定从 .c 源文件到 token 流输入是普通文本文件输出是逐行打印的 token 流格式必须和test/expected/完全一致否则 diff 不过。常见格式是类型, 词素, 行:列KW_INT, int, 1:1 ID, a, 1:5 OP, , 1:7 NUM, 1, 1:9 DELIM, ;, 1:10 END_OF_FILE, , 1:11主流程就是一个 while 循环直到拿到END_OF_FILE为止// src/main.cpp int main(int argc, char** argv) { if (argc 2) { std::cerr usage: lexer source-file\n; return 1; } std::ifstream in(argv[1], std::ios::binary); if (!in) { std::cerr cannot open argv[1] \n; return 2; } std::string src((std::istreambuf_iteratorchar(in)), std::istreambuf_iteratorchar()); Scanner scanner(src); // 一次性把源文件吞进内存 for (;;) { Token tok scanner.nextToken(); // 每调用一次吐一个 token printToken(tok); // 按约定格式输出 if (tok.type TokenType::END_OF_FILE) break; } return 0; }逻辑说明用std::istreambuf_iterator一次读完整个文件比逐行 getline 简单因为词法分析需要跨行看块注释、字符串里的换行。ios::binary是为了避免某些平台上文本模式的换行转换把列号算歪这一点在跨平台交作业时是血泪经验。Scanner构造时保存源串nextToken()内部维护pos_每次从当前位置往前扫描扫完推进指针——下一节就拆这个函数。3. 核心链路拆解正则表达式怎么变成一个能跑的 DFA这一章是项目的技术核心。规则文件里写的ID [a-zA-Z_][a-zA-Z0-9_]*这种正则最终要变成一张二维状态转移表trans[state][char] - state扫描时查表即可。整条链路四步正则转后缀、后缀建 NFA、NFA 子集构造转 DFA、DFA 最小化。少一步也能跑但实验报告里少一步就少一分。3.1 规则文件怎么变成内存里的 NFAThompson 构造正则先要被解析成后缀表达式也叫逆波兰式因为后缀形式没有括号、不需要回溯用栈就能一步步建出 NFA。解析器部分不贴全重点看构造Thompson 构造的核心思想是每种正则运算对应一小块固定的图然后用 epsilon 边把小块拼起来。状态节点定义如下// src/nfa.h constexpr char EPS \0; // 用 \0 表示 epsilon 转移 struct NFAState { char trans EPS; // 转移字符EPS 表示空转移 int next1 -1; // 第一条出边 int next2 -1; // 第二条出边epsilon 分叉时用 }; int newState(std::vectorNFAState g) { g.emplace_back(); return static_castint(g.size()) - 1; }三个基本构造块分别是单字符、连接、闭包// 单字符 as --a-- e std::pairint,int buildChar(char c, std::vectorNFAState g) { int s newState(g), e newState(g); g[s].trans c; g[s].next1 e; return {s, e}; } // 连接 AB把 A 的接受态用 epsilon 连到 B 的起始态 std::pairint,int buildConcat(std::pairint,int a, std::pairint,int b, std::vectorNFAState g) { g[a.second].trans EPS; g[a.second].next1 b.first; return {a.first, b.second}; } // 闭包 A*新增起止态配四条 epsilon 边 std::pairint,int buildStar(std::pairint,int a, std::vectorNFAState g) { int s newState(g), e newState(g); g[s].trans EPS; g[s].next1 a.first; g[s].next2 e; g[a.second].trans EPS; g[a.second].next1 a.first; // 回到子图起点实现重复 g[a.second].next2 e; // 或者直接跳过零次匹配 return {s, e}; }逻辑说明buildStar里那四条 epsilon 边是 Thompson 构造的固定套路——新起点可以进子图匹配一次以上也可以直接到新终点匹配零次子图终点可以回子图起点继续匹配也可以到新终点结束。参数上每个函数都返回{起始态, 接受态}这样一对下标方便上层继续拼接。选择法A|B同理新建起点用两条 epsilon 分别指向 A、B 的起点A、B 的接受态再用 epsilon 汇到同一个新终点。3.2 NFA 到 DFA子集构造把状态数压下来NFA 有个致命问题一个状态读一个字符可能跳到多个状态运行时得随时回溯写起来容易翻车。子集构造把“状态集合”打包成一个 DFA 状态从而做到确定性——每个状态读每个字符只有唯一去向。先写 epsilon 闭包这是整个算法的地基// 求状态集合的 epsilon 闭包能零成本到达的所有状态 std::setint epsilonClosure(const std::setint states, const std::vectorNFAState g) { std::setint closure states; std::vectorint work(states.begin(), states.end()); while (!work.empty()) { int s work.back(); work.pop_back(); if (g[s].trans ! EPS) continue; // 只有 epsilon 边才继续走 for (int nxt : {g[s].next1, g[s].next2}) { if (nxt 0 !closure.count(nxt)) { closure.insert(nxt); work.push_back(nxt); } } } return closure; }参数说明入参states是一组 NFA 状态返回它们加上所有 epsilon 可达状态的并集。用setint而不是unordered_set因为后面要把集合当作 DFA 状态的唯一键需要稳定有序才能比较和哈希。接着是move和主循环// 从集合 T 出发读字符 c 能到达的 NFA 状态集合 std::setint move(const std::setint T, char c, const std::vectorNFAState g) { std::setint result; for (int s : T) if (g[s].trans c g[s].next1 0) result.insert(g[s].next1); return result; // 注意这里还没做 epsilon 闭包 } // 子集构造主循环 void subsetConstruction(const std::vectorNFAState nfa, int nfaStart, const std::setint nfaAccept, DFA out) { std::mapstd::setint, int stateMap; // NFA 集合 - DFA 状态号 std::queuestd::setint work; auto start epsilonClosure({nfaStart}, nfa); stateMap[start] 0; work.push(start); while (!work.empty()) { auto cur work.front(); work.pop(); int curId stateMap[cur]; if (std::includes(cur.begin(), cur.end(), nfaAccept.begin(), nfaAccept.end())) out.accept.insert(curId); // 含接受态则标为接受 for (char c : alphabet) { // alphabet 是规则里出现的所有字符 auto nxt epsilonClosure(move(cur, c, nfa), nfa); if (nxt.empty()) continue; if (!stateMap.count(nxt)) { stateMap[nxt] static_castint(stateMap.size()); work.push(nxt); } out.trans[curId][c] stateMap[nxt]; } } }逻辑说明move只找一步直达epsilonClosure补上零成本路径两者组合才是完整的转移。alphabet是规则里所有出现过的字符的并集一般用std::setchar存别偷懒用 256 全字符表——虽然不出错但会生成大量无效边最小化时白白多跑几轮。out.accept记录哪些 DFA 状态是接受态扫描时命中即产出 token。3.3 DFA 最小化合并等价状态去掉冗余跳转子集构造出来的 DFA 经常有几十个状态但真正“行为不同”的可能只有十来个。最小化的思路是划分先按“接受态 / 非接受态”分成两组然后反复检查同一组内的状态读同一字符是否跳到同一组不是就拆开直到划分稳定。// Hopcroft 划分的简化版反复按转移目标分组 void minimize(DFA dfa) { // 初始划分接受态一组非接受态一组 std::mapint,int group; // 状态 - 组号 for (int s : dfa.allStates()) group[s] dfa.accept.count(s) ? 1 : 0; bool changed true; while (changed) { changed false; std::mapstd::pairint,std::vectorint, int sig; // 签名 - 新组号 std::mapint,int nextGroup; for (int s : dfa.allStates()) { std::vectorint row; for (char c : alphabet) row.push_back(group.count(dfa.trans[s][c]) ? group[dfa.trans[s][c]] : -1); auto key std::make_pair(group[s], row); if (!sig.count(key)) sig[key] static_castint(sig.size()); nextGroup[s] sig[key]; } if (nextGroup ! group) { group nextGroup; changed true; } } dfa.rebuildFrom(group); // 按组号重建转移表去掉重复状态 }逻辑说明sig里存的是“当前组号 每一个字符跳到的目标组号”组成的签名签名相同说明两个状态在所有输入下的行为完全一致可以合并。changed控制迭代划分只减不增最多迭代状态数次就收敛。参数上dfa.trans用二维表或mapint, mapchar,int都行前者查询快后者省内存。注意最小化时千万不要把不同类型的接受态合到一组。ID的接受态和NUM的接受态在“接受”这一点上相同但产出 token 类型不同合并了就会把标识符识别成数字——这个坑我在实验报告里踩过一次输出里全是NUM, abc。3.4 手写扫描器最长匹配 指针回退才是真功夫DFA 建好了驱动扫描其实很短但有两个细节必须写对最长匹配和回退。比如输入ab读到a后面跟扫描器要能确定属于下一个 token不能贪心地把a当成标识符的一部分。Token Scanner::nextToken() { skipWhitespaceAndComment(); // 跳过空白与注释 if (pos_ src_.size()) return Token{TokenType::END_OF_FILE, , line_, col_}; int start pos_; int startLine line_, startCol col_; int state dfa_.start; int lastAccept -1, lastAcceptPos -1; // 最近一次命中的接受态 TokenType lastType TokenType::ERROR; while (pos_ src_.size()) { char c src_[pos_]; auto it dfa_.trans[state].find(c); if (it dfa_.trans[state].end()) break; // 无路可走停 state it-second; advance(c); // 推进 pos_ 并维护行列号 if (dfa_.accept.count(state)) { // 记下当前最优命中 lastAccept state; lastAcceptPos pos_; lastType dfa_.typeOf(state); // 接受态对应的 token 类型 } } if (lastAccept -1) { // 一个字符都没匹配上 char bad src_[pos_]; advance(bad); return Token{TokenType::ERROR, std::string(1, bad), startLine, startCol}; } // 回退到最近一次成功匹配的位置实现最长匹配语义 rewindTo(lastAcceptPos, startLine, startCol); std::string lex src_.substr(start, lastAcceptPos - start); return Token{lastType, lex, startLine, startCol}; }逻辑说明lastAccept和lastAcceptPos是这段代码的灵魂。DFA 一路上可能经过好几个接受态比如if和iff但只有最后那个才是最长匹配的合法 token所以每命中一次接受态就记一次位置走不通时回退到那个位置。advance负责推进pos_同时更新line_/col_遇到\n就把行号加一、列号归零。skipWhitespaceAndComment单独抽出来因为它还涉及块注释跨行逻辑比想象中长。rewindTo实现上不建议真的“重置整个扫描器”而是记下start和lastAcceptPos两个下标直接把pos_设回lastAcceptPos行列号用起始行加词素里换行符个数重算void Scanner::rewindTo(int newPos, int startLine, int startCol) { pos_ newPos; line_ startLine; col_ startCol; for (int i 0; i newPos - lastStart_; i) if (src_[lastStart_ i] \n) { line_; col_ 1; } else col_; }这段看着像个事后补丁但它是“最长匹配”能成立的地方。很多同学的实现里if之后紧跟字母会直接报错就是因为没做回退扫描器走到死路时不知道退到哪里。4. 编译与运行三个命令把实验跑起来代码看懂了接下来是让它跑起来。这类实验项目通常提供一个 Makefile把扫描器和 DFA 生成器拆成两个可执行目标跑测试用例用脚本或手敲命令都行。4.1 编译一条 make 与三个可执行目标CXX g CXXFLAGS -stdc17 -Wall -Wextra -O2 -g SRC $(wildcard src/*.cpp) OBJ $(SRC:.cpp.o) all: lexer gen_dfa lexer: $(OBJ) $(CXX) $(CXXFLAGS) -o $ $^ gen_dfa: src/gen_dfa.o src/nfa.o src/dfa.o src/regex_parser.o $(CXX) $(CXXFLAGS) -o $ $^ %.o: %.cpp $(CXX) $(CXXFLAGS) -c $ -o $ test: lexer ./run_tests.sh clean: rm -f $(OBJ) lexer gen_dfa三个目标各管一件事make编出扫描器lexer和 DFA 生成器gen_dfamake test跑全部测试用例做 diffmake clean清干净。-stdc17是必须的enum class和std::optional在里面-Wall -Wextra别省能挡掉一批“忘记 return”的低级错误。如果包里的 Makefile 用的是CXXFLAGS -stdc11改成 17 一般不会破坏什么但如果你机器上的老编译器不支持回退到 11 也行代码里没用太新的特性。编译命令按顺序敲make clean # 清掉上次的产物避免半新半旧的 .o 混在一起 make -j4 # 四个核一起编快了不止一点 ./gen_dfa rules/tokens.rules build/dfa.txt # 先验证规则能生成 ./lexer test/case01_basic.c # 再跑扫描第二条-j4对于这个体量的项目属于锦上添花但make clean那步不能省——改了token.h之后增量编译可能漏掉依赖它的 .cpp症状是“我明明改了枚举输出还是旧的”这种玄学问题一半出在这里。4.2 用测试用例跑出第一份 token 流test/case01_basic.c一般是最小用例就几行声明int a 1; int b a 2;跑完之后应该得到KW_INT, int, 1:1 ID, a, 1:5 OP, , 1:7 NUM, 1, 1:9 DELIM, ;, 1:10 KW_INT, int, 2:1 ID, b, 2:5 OP, , 2:7 ID, a, 2:9 OP, , 2:11 NUM, 2, 2:13 DELIM, ;, 2:14 END_OF_FILE, , 3:1对照 expected 做 diff./lexer test/case01_basic.c /tmp/out.txt diff -u test/expected/case01_basic.txt /tmp/out.txtdiff无输出才算过。如果有输出先看是不是行号列号差一位再看着是不是某个关键字被识别成了ID。这套流程跑通一个用例剩下的基本是重复劳动直接写个循环for f in test/case*.c; do name$(basename $f .c) ./lexer $f /tmp/$name.out if diff -q test/expected/$name.txt /tmp/$name.out /dev/null; then echo PASS $name else echo FAIL $name; diff -u test/expected/$name.txt /tmp/$name.out fi done4.3 输出格式与常见报错定位跑不通的时候报错信息往往比 diff 更有用。项目里建议在printToken里对ERROR类型特殊处理直接打到 stderr现象大概率原因定位方法输出为空进程直接退出文件读入失败ifstream判断没走到在main开头打印argv[1]和src.size()全是ERROR单字符 token规则文件没被gen_dfa正确加载先单独跑./gen_dfa看 DFA 状态数是否合理关键字全变成ID关键字规则在标识符规则之后匹配或被合并检查规则文件顺序和接受态的 token 类型映射行列号整体偏 1行列号从 0 开始计统一改成从 1 开始起点初始化成line_ 1, col_ 1块注释后面的内容全丢注释未闭合时一直扫到 EOF 没报错在skipWhitespaceAndComment里对 EOF 做显式判断gen_dfa单独能跑是个重要设计它把“规则写错”和“扫描器写错”两类问题分开了。DFA 生成不出来就是规则写错了生成出来但扫描结果不对才是扫描器的问题。5. 避坑与排查那些让我在机房里坐到熄灯的坑实验一看着简单坑全在边角。下面五条是我自己和周围同学反复踩过的每条按“现象 → 原因 → 解决”写对着症状直接查。5.1 扫描阶段的三个坑坑一关键字识别成标识符。现象是int a 1;输出ID, int而不是KW_INT, int。原因通常是关键字表和标识符共用一条规则只在产出 token 前做一次查表但查表时用的lexeme还在扫描缓冲区里没截断或者查表的大小写没统一。解决办法是在buildIdentifier出口处做一次精确匹配且映射表用const std::unordered_mapstd::string, TokenType静态初始化别每个字符都重建一次static const std::unordered_mapstd::string, TokenType kKeywords { {int, TokenType::KW_INT}, {if, TokenType::KW_IF}, {else, TokenType::KW_ELSE}, {while, TokenType::KW_WHILE}, {return, TokenType::KW_RETURN}, }; TokenType classify(const std::string lex) { auto it kKeywords.find(lex); return it ! kKeywords.end() ? it-second : TokenType::ID; }坑二ab死循环或提前截断。现象是扫描到这个表达式时程序卡住或者输出a、、、b这类奇怪切分。原因是贪心匹配后没有回退指针已经越过了合法边界却不知道退。解决办法就是 3.4 节里那套lastAcceptPos记录加rewindTo凡是往前走一步之前先确认这一步走完还能不能回到最近的接受态。坑三CRLF 换行把列号算错。现象是在 Windows 上编辑过的测试文件跑出来行号对、列号对不上。原因是\r被当成普通字符消耗掉但没更新列号逻辑或者把\r\n当成了一个换行算两次。解决办法是在advance里显式处理void Scanner::advance(char c) { pos_; if (c \r) { /* 若下一个是 \n等它来处理换行 */ } else if (c \n) { line_; col_ 1; } else { col_; } }或者更省事读入文件后先做一次\r\n→\n的归一化整篇源串处理一次后面所有逻辑都不用特殊判断。我一般选后者改一行胜过改十处。5.2 自动机构造阶段的两个坑坑四最小化之后接受态合并错。现象是某些标识符被识别成数字或关键字而且只在特定前缀下出问题。原因是划分算法只按“是不是接受态”分了两组没把“接受态对应的 token 类型”算进签名。解决办法是在初始划分或签名里带上类型// 初始划分时按 token 类型分组而不是简单二分 for (int s : dfa.allStates()) { if (dfa.accept.count(s)) group[s] 100 static_castint(dfa.typeOf(s)); // 每类接受态一组 else group[s] 0; }坑五epsilon 闭包写成了普通 BFS漏掉分叉。现象是某些带*或|的规则匹配不到比如[a-z]匹配单字符可以多个字符就断。原因是epsilonClosure里只沿着next1走忘了 epsilon 状态有两条出边。解决办法是把next1、next2都入栈入栈前判重别让它无限循环。这个 bug 特别隐蔽因为单元测试用单字符能过一到真实源码就翻车。注意DFA 生成器最好能打印每个状态的编号、是否为接受态、出边数跟规则文件一起对着看。我在状态数超过 40 之后基本靠这张表定位问题纯看代码根本看不出哪条边接歪了。6. 二次开发从课程实验到能用的词法分析器跑通之后这个项目真正的价值在“能改”。实验一的代码骨架其实和很多真实项目里的 lexer 同构区别只在规则规模和健壮性。下面三件事是我每次基于这类项目做二次开发时必做的。6.1 扩一条词法规则要改哪三个地方不少人加个新运算符比如、-会改半天其实涉及的地方固定改动点文件具体动作规则rules/tokens.rules加一行OP_PLUS_ASSIGN \枚举src/token.hTokenType里加对应枚举值映射src/gen_dfa.cpp或规则动作把接受态关联到新的TokenType改完重新make ./gen_dfa rules/tokens.rules build/dfa.txt再跑一遍全量测试。如果新规则是前缀冲突型和确认最长匹配逻辑能正确处理——a 1应该出而不是加。这里有个容易忽略的点规则文件里必须转义因为它在正则里是量词不转义会解析成“前一个字符重复一次以上”编译能过、运行结果完全不对。6.2 错误恢复与位置信息让后面的语法分析器少骂人课程实验里遇到非法字符直接吐ERROR就完事但要做二次开发就得考虑错误恢复。我在自己的实现里加了一条规则遇到非法字符不中断记录位置和字符跳过它继续扫最后统一汇总所有错误一次性报出来。语法分析阶段拿到干净的 token 流比中途因为一个#断掉舒服太多。具体做法是把nextToken里的ERROR返回改成“填充到错误列表并递归调用自己”Token Scanner::nextToken() { // ... 前面逻辑不变 if (lastAccept -1) { char bad src_[pos_]; errors_.push_back({startLine, startCol, bad}); // 收集而非抛出 advance(bad); return nextToken(); // 跳过坏字符继续找下一个 token } // ... }errors_用std::vectorLexError存main结束时检查非空就打到 stderr但 token 流照常输出。这样一份带小错的源文件也能扫出完整结果便于对照 expected 找差异。一个小提醒递归调用要考虑极端情况比如整个文件全是非法字符把递归改成循环更稳这里为了可读性保留递归形式。6.3 怎么验证你改完没改坏改完词法分析器最怕“新功能能用、老功能坏了”。我的习惯是做三层验证第一层跑原有全部测试用例一个 diff 都不能有第二层拿几份真实风格的源文件自己手写的几百行即可跑一遍人工扫一眼 token 流是否合理第三层写个随机输入生成器随机拼字符、括号、引号看程序会不会卡死或崩溃这层专治指针回退类的 bug# 随机生成 200 份脏输入只要进程超时或非零退出就记一笔 for i in $(seq 1 200); do head -c 4096 /dev/urandom | tr -dc a-zA-Z0-9_-*/();{}\n \ /tmp/fuzz_$i.c timeout 2 ./lexer /tmp/fuzz_$i.c /dev/null 21 || echo BAD $i donetimeout 2是防死循环的关键tr -dc只保留合法字符集和少量标点模拟“看起来像源码但语法全错”的输入。只要有一份超时就说明某条路径下的回退没写对。最后说个教训。我最早写这类项目时习惯改完直接拿case01跑一下看见有输出就交结果在case03_comment上被块注释未闭合的 EOF 判断坑了一整晚——扫描器在文件末尾死等*/pos_越界[]访问到std::string的\0还在继续走最后是靠 gdb 单步才定位到。从那以后我每次改完nextToken相关代码都强制走一遍“全量 diff 三份脏输入 一份随机垃圾”的流程哪怕只是改了一个字符常量的分类分支。希望这套流程能帮到你少在机房里多坐两个小时。本文还有配套的精品资源点击获取 
长河君 · 2026/10/23 18:20:23 · 阅读 1.2k 编译原理课程实验：C++词法分析器正则转DFA与最长匹配
简介面向编译原理初学者与课程实验需求这份北京邮电大学词法分析器实验包围绕编译器前端扫描器的设计与实现展开适合正在学习词法规则、记号识别与错误处理的学生对照实践。压缩包共4个文件以2个txt说明与测试文本、1个h头文件和1个cpp源文件为主整体约10KB体量轻便便于快速查看核心代码与实验材料。已有1000人学习下载。内容覆盖词法规则定义、输入处理、分词逻辑、符号栈管理及错误处理等关键环节附带的说明与测试文本可用于验证标识符、关键字、常量、运算符等词素的识别效果。读者可借助源代码理解从词法规则到扫描算法的落地方式梳理实验实现思路并对照测试用例排查边界情况与异常输入为后续语法分析学习打基础。1. 课程实验的真相一个词法分析器到底要跑通哪几步“编译原理”这门课最劝退的时刻不是推文法而是实验一那天下午——你打开压缩包里面躺着一份能直接编译运行的词法分析器源码、一组 .c 风格的测试用例而实验指导书只有三页。这份课程实验资源干的事很具体把一段类 C 源程序切成一串 Token每个 Token 带上类型、原始词素和行列号交给后面的语法分析器直接消费。它适合两类人被实验一卡住、想先跑通再回头啃原理的以及自己写完了但输出格式对不上、想找份参考实现做对照的。词法分析器看着简单真正拉开分数的往往是关键字表顺序、最长匹配回退、注释与换行处理这些边角玄学得很。2. 项目结构与技术选型C 手写扫描器 正则到 DFA 的两条路线拿到包先别急着 make先把目录摊开看。这类实验项目通常有两条并行的实现路线一条是纯手写的扫描器一个字符一个字符往前啃边啃边判断另一条是把词法规则写成正则表达式走 Thompson 构造 → 子集构造 → DFA 最小化的标准流水线最终生成一张状态转移表来驱动扫描。两条路线通常共用同一套 Token 定义和测试用例方便你在实验报告里做对比。2.1 目录结构src 放实现rules 放规则test 放验收我按常见组织方式把目录梳理成下面这样你对照自己包里的文件应该能一一对上lexer-lab/ ├── src/ │ ├── main.cpp # 入口读文件、循环取 token、按格式打印 │ ├── scanner.h/.cpp # 手写扫描器最长匹配 回退 │ ├── regex_parser.h/.cpp # 正则表达式解析成后缀形式 │ ├── nfa.h/.cpp # Thompson 构造正则 - NFA │ ├── dfa.h/.cpp # 子集构造 Hopcroft 最小化 │ └── token.h # Token / TokenType 定义全项目共用 ├── rules/ │ └── tokens.rules # 词法规则表名字 正则 ├── test/ │ ├── case01_basic.c │ ├── case02_keywords.c │ ├── case03_comment.c │ └── expected/ # 每个 case 对应的期望 token 流 ├── Makefile └── README.mdsrc/里最容易被忽略的是token.h——它是整个项目的契约扫描器、DFA 生成器、打印逻辑全都要 include 它。rules/tokens.rules是可扩展性的关键规则写成一行一条的形式改词法不用动 C 代码重新跑一遍生成流程即可。test/expected/是验收标准很多同学跑出来“看着像对的”一比对 expected 就发现行列号差了一位。提示动手前先find . -name *.rules -o -name *.l确认项目用的是自定义规则文件还是 lex/flex 的 .l 文件这决定你后面改规则的方式完全不同。2.2 核心数据结构Token、TokenType 与符号表整个项目的数据流就围绕一个结构体转。先把类型枚举写清楚后面所有逻辑都是围绕它做的分派// src/token.h #pragma once #include string enum class TokenType { KW_INT, KW_IF, KW_ELSE, KW_WHILE, KW_RETURN, // 关键字 ID, // 标识符 NUM, // 整数字面量 FLOAT_LIT, // 浮点字面量 STR_LIT, // 字符串字面量 OP, // 运算符 - * / 等 DELIM, // 分隔符 ( ) { } ; , COMMENT, // 注释可选大部分实现直接丢弃 ERROR, // 非法字符 END_OF_FILE // 文件结束 }; struct Token { TokenType type; // 词法单元类型 std::string lexeme; // 原始词素保留原样便于报错 int line; // 起始行号从 1 开始 int column; // 起始列号从 1 开始 };lexeme存原始字符串而不是自己再拼一遍是为了报错时能原样打印“第 7 行第 12 列附近出现非法字符 #”而不是让用户猜。line/column记的是词素的起始位置不是结束位置——语法分析器报错时更关心“这个词从哪开始的”。标识符还要过一道符号表重复出现的名字复用同一个 id这样实验二建符号表时能直接接上// 扫描器内部维护用于标识符去重 class SymbolTable { public: // 返回该标识符的稳定编号第一次见就分配新号 int intern(const std::string name) { auto it table_.find(name); if (it ! table_.end()) return it-second; int id static_castint(table_.size()); table_.emplace(name, id); return id; } private: std::unordered_mapstd::string, int table_; };参数说明intern的入参是识别出来的完整标识符字符串返回值是稳定编号。用unordered_map而不是map是因为这里不需要有序遍历只查不遍历平均 O(1) 比红黑树的 O(log n) 划算。如果你后面要按字典序输出符号表再换回map就行。2.3 输入输出约定从 .c 源文件到 token 流输入是普通文本文件输出是逐行打印的 token 流格式必须和test/expected/完全一致否则 diff 不过。常见格式是类型, 词素, 行:列KW_INT, int, 1:1 ID, a, 1:5 OP, , 1:7 NUM, 1, 1:9 DELIM, ;, 1:10 END_OF_FILE, , 1:11主流程就是一个 while 循环直到拿到END_OF_FILE为止// src/main.cpp int main(int argc, char** argv) { if (argc 2) { std::cerr usage: lexer source-file\n; return 1; } std::ifstream in(argv[1], std::ios::binary); if (!in) { std::cerr cannot open argv[1] \n; return 2; } std::string src((std::istreambuf_iteratorchar(in)), std::istreambuf_iteratorchar()); Scanner scanner(src); // 一次性把源文件吞进内存 for (;;) { Token tok scanner.nextToken(); // 每调用一次吐一个 token printToken(tok); // 按约定格式输出 if (tok.type TokenType::END_OF_FILE) break; } return 0; }逻辑说明用std::istreambuf_iterator一次读完整个文件比逐行 getline 简单因为词法分析需要跨行看块注释、字符串里的换行。ios::binary是为了避免某些平台上文本模式的换行转换把列号算歪这一点在跨平台交作业时是血泪经验。Scanner构造时保存源串nextToken()内部维护pos_每次从当前位置往前扫描扫完推进指针——下一节就拆这个函数。3. 核心链路拆解正则表达式怎么变成一个能跑的 DFA这一章是项目的技术核心。规则文件里写的ID [a-zA-Z_][a-zA-Z0-9_]*这种正则最终要变成一张二维状态转移表trans[state][char] - state扫描时查表即可。整条链路四步正则转后缀、后缀建 NFA、NFA 子集构造转 DFA、DFA 最小化。少一步也能跑但实验报告里少一步就少一分。3.1 规则文件怎么变成内存里的 NFAThompson 构造正则先要被解析成后缀表达式也叫逆波兰式因为后缀形式没有括号、不需要回溯用栈就能一步步建出 NFA。解析器部分不贴全重点看构造Thompson 构造的核心思想是每种正则运算对应一小块固定的图然后用 epsilon 边把小块拼起来。状态节点定义如下// src/nfa.h constexpr char EPS \0; // 用 \0 表示 epsilon 转移 struct NFAState { char trans EPS; // 转移字符EPS 表示空转移 int next1 -1; // 第一条出边 int next2 -1; // 第二条出边epsilon 分叉时用 }; int newState(std::vectorNFAState g) { g.emplace_back(); return static_castint(g.size()) - 1; }三个基本构造块分别是单字符、连接、闭包// 单字符 as --a-- e std::pairint,int buildChar(char c, std::vectorNFAState g) { int s newState(g), e newState(g); g[s].trans c; g[s].next1 e; return {s, e}; } // 连接 AB把 A 的接受态用 epsilon 连到 B 的起始态 std::pairint,int buildConcat(std::pairint,int a, std::pairint,int b, std::vectorNFAState g) { g[a.second].trans EPS; g[a.second].next1 b.first; return {a.first, b.second}; } // 闭包 A*新增起止态配四条 epsilon 边 std::pairint,int buildStar(std::pairint,int a, std::vectorNFAState g) { int s newState(g), e newState(g); g[s].trans EPS; g[s].next1 a.first; g[s].next2 e; g[a.second].trans EPS; g[a.second].next1 a.first; // 回到子图起点实现重复 g[a.second].next2 e; // 或者直接跳过零次匹配 return {s, e}; }逻辑说明buildStar里那四条 epsilon 边是 Thompson 构造的固定套路——新起点可以进子图匹配一次以上也可以直接到新终点匹配零次子图终点可以回子图起点继续匹配也可以到新终点结束。参数上每个函数都返回{起始态, 接受态}这样一对下标方便上层继续拼接。选择法A|B同理新建起点用两条 epsilon 分别指向 A、B 的起点A、B 的接受态再用 epsilon 汇到同一个新终点。3.2 NFA 到 DFA子集构造把状态数压下来NFA 有个致命问题一个状态读一个字符可能跳到多个状态运行时得随时回溯写起来容易翻车。子集构造把“状态集合”打包成一个 DFA 状态从而做到确定性——每个状态读每个字符只有唯一去向。先写 epsilon 闭包这是整个算法的地基// 求状态集合的 epsilon 闭包能零成本到达的所有状态 std::setint epsilonClosure(const std::setint states, const std::vectorNFAState g) { std::setint closure states; std::vectorint work(states.begin(), states.end()); while (!work.empty()) { int s work.back(); work.pop_back(); if (g[s].trans ! EPS) continue; // 只有 epsilon 边才继续走 for (int nxt : {g[s].next1, g[s].next2}) { if (nxt 0 !closure.count(nxt)) { closure.insert(nxt); work.push_back(nxt); } } } return closure; }参数说明入参states是一组 NFA 状态返回它们加上所有 epsilon 可达状态的并集。用setint而不是unordered_set因为后面要把集合当作 DFA 状态的唯一键需要稳定有序才能比较和哈希。接着是move和主循环// 从集合 T 出发读字符 c 能到达的 NFA 状态集合 std::setint move(const std::setint T, char c, const std::vectorNFAState g) { std::setint result; for (int s : T) if (g[s].trans c g[s].next1 0) result.insert(g[s].next1); return result; // 注意这里还没做 epsilon 闭包 } // 子集构造主循环 void subsetConstruction(const std::vectorNFAState nfa, int nfaStart, const std::setint nfaAccept, DFA out) { std::mapstd::setint, int stateMap; // NFA 集合 - DFA 状态号 std::queuestd::setint work; auto start epsilonClosure({nfaStart}, nfa); stateMap[start] 0; work.push(start); while (!work.empty()) { auto cur work.front(); work.pop(); int curId stateMap[cur]; if (std::includes(cur.begin(), cur.end(), nfaAccept.begin(), nfaAccept.end())) out.accept.insert(curId); // 含接受态则标为接受 for (char c : alphabet) { // alphabet 是规则里出现的所有字符 auto nxt epsilonClosure(move(cur, c, nfa), nfa); if (nxt.empty()) continue; if (!stateMap.count(nxt)) { stateMap[nxt] static_castint(stateMap.size()); work.push(nxt); } out.trans[curId][c] stateMap[nxt]; } } }逻辑说明move只找一步直达epsilonClosure补上零成本路径两者组合才是完整的转移。alphabet是规则里所有出现过的字符的并集一般用std::setchar存别偷懒用 256 全字符表——虽然不出错但会生成大量无效边最小化时白白多跑几轮。out.accept记录哪些 DFA 状态是接受态扫描时命中即产出 token。3.3 DFA 最小化合并等价状态去掉冗余跳转子集构造出来的 DFA 经常有几十个状态但真正“行为不同”的可能只有十来个。最小化的思路是划分先按“接受态 / 非接受态”分成两组然后反复检查同一组内的状态读同一字符是否跳到同一组不是就拆开直到划分稳定。// Hopcroft 划分的简化版反复按转移目标分组 void minimize(DFA dfa) { // 初始划分接受态一组非接受态一组 std::mapint,int group; // 状态 - 组号 for (int s : dfa.allStates()) group[s] dfa.accept.count(s) ? 1 : 0; bool changed true; while (changed) { changed false; std::mapstd::pairint,std::vectorint, int sig; // 签名 - 新组号 std::mapint,int nextGroup; for (int s : dfa.allStates()) { std::vectorint row; for (char c : alphabet) row.push_back(group.count(dfa.trans[s][c]) ? group[dfa.trans[s][c]] : -1); auto key std::make_pair(group[s], row); if (!sig.count(key)) sig[key] static_castint(sig.size()); nextGroup[s] sig[key]; } if (nextGroup ! group) { group nextGroup; changed true; } } dfa.rebuildFrom(group); // 按组号重建转移表去掉重复状态 }逻辑说明sig里存的是“当前组号 每一个字符跳到的目标组号”组成的签名签名相同说明两个状态在所有输入下的行为完全一致可以合并。changed控制迭代划分只减不增最多迭代状态数次就收敛。参数上dfa.trans用二维表或mapint, mapchar,int都行前者查询快后者省内存。注意最小化时千万不要把不同类型的接受态合到一组。ID的接受态和NUM的接受态在“接受”这一点上相同但产出 token 类型不同合并了就会把标识符识别成数字——这个坑我在实验报告里踩过一次输出里全是NUM, abc。3.4 手写扫描器最长匹配 指针回退才是真功夫DFA 建好了驱动扫描其实很短但有两个细节必须写对最长匹配和回退。比如输入ab读到a后面跟扫描器要能确定属于下一个 token不能贪心地把a当成标识符的一部分。Token Scanner::nextToken() { skipWhitespaceAndComment(); // 跳过空白与注释 if (pos_ src_.size()) return Token{TokenType::END_OF_FILE, , line_, col_}; int start pos_; int startLine line_, startCol col_; int state dfa_.start; int lastAccept -1, lastAcceptPos -1; // 最近一次命中的接受态 TokenType lastType TokenType::ERROR; while (pos_ src_.size()) { char c src_[pos_]; auto it dfa_.trans[state].find(c); if (it dfa_.trans[state].end()) break; // 无路可走停 state it-second; advance(c); // 推进 pos_ 并维护行列号 if (dfa_.accept.count(state)) { // 记下当前最优命中 lastAccept state; lastAcceptPos pos_; lastType dfa_.typeOf(state); // 接受态对应的 token 类型 } } if (lastAccept -1) { // 一个字符都没匹配上 char bad src_[pos_]; advance(bad); return Token{TokenType::ERROR, std::string(1, bad), startLine, startCol}; } // 回退到最近一次成功匹配的位置实现最长匹配语义 rewindTo(lastAcceptPos, startLine, startCol); std::string lex src_.substr(start, lastAcceptPos - start); return Token{lastType, lex, startLine, startCol}; }逻辑说明lastAccept和lastAcceptPos是这段代码的灵魂。DFA 一路上可能经过好几个接受态比如if和iff但只有最后那个才是最长匹配的合法 token所以每命中一次接受态就记一次位置走不通时回退到那个位置。advance负责推进pos_同时更新line_/col_遇到\n就把行号加一、列号归零。skipWhitespaceAndComment单独抽出来因为它还涉及块注释跨行逻辑比想象中长。rewindTo实现上不建议真的“重置整个扫描器”而是记下start和lastAcceptPos两个下标直接把pos_设回lastAcceptPos行列号用起始行加词素里换行符个数重算void Scanner::rewindTo(int newPos, int startLine, int startCol) { pos_ newPos; line_ startLine; col_ startCol; for (int i 0; i newPos - lastStart_; i) if (src_[lastStart_ i] \n) { line_; col_ 1; } else col_; }这段看着像个事后补丁但它是“最长匹配”能成立的地方。很多同学的实现里if之后紧跟字母会直接报错就是因为没做回退扫描器走到死路时不知道退到哪里。4. 编译与运行三个命令把实验跑起来代码看懂了接下来是让它跑起来。这类实验项目通常提供一个 Makefile把扫描器和 DFA 生成器拆成两个可执行目标跑测试用例用脚本或手敲命令都行。4.1 编译一条 make 与三个可执行目标CXX g CXXFLAGS -stdc17 -Wall -Wextra -O2 -g SRC $(wildcard src/*.cpp) OBJ $(SRC:.cpp.o) all: lexer gen_dfa lexer: $(OBJ) $(CXX) $(CXXFLAGS) -o $ $^ gen_dfa: src/gen_dfa.o src/nfa.o src/dfa.o src/regex_parser.o $(CXX) $(CXXFLAGS) -o $ $^ %.o: %.cpp $(CXX) $(CXXFLAGS) -c $ -o $ test: lexer ./run_tests.sh clean: rm -f $(OBJ) lexer gen_dfa三个目标各管一件事make编出扫描器lexer和 DFA 生成器gen_dfamake test跑全部测试用例做 diffmake clean清干净。-stdc17是必须的enum class和std::optional在里面-Wall -Wextra别省能挡掉一批“忘记 return”的低级错误。如果包里的 Makefile 用的是CXXFLAGS -stdc11改成 17 一般不会破坏什么但如果你机器上的老编译器不支持回退到 11 也行代码里没用太新的特性。编译命令按顺序敲make clean # 清掉上次的产物避免半新半旧的 .o 混在一起 make -j4 # 四个核一起编快了不止一点 ./gen_dfa rules/tokens.rules build/dfa.txt # 先验证规则能生成 ./lexer test/case01_basic.c # 再跑扫描第二条-j4对于这个体量的项目属于锦上添花但make clean那步不能省——改了token.h之后增量编译可能漏掉依赖它的 .cpp症状是“我明明改了枚举输出还是旧的”这种玄学问题一半出在这里。4.2 用测试用例跑出第一份 token 流test/case01_basic.c一般是最小用例就几行声明int a 1; int b a 2;跑完之后应该得到KW_INT, int, 1:1 ID, a, 1:5 OP, , 1:7 NUM, 1, 1:9 DELIM, ;, 1:10 KW_INT, int, 2:1 ID, b, 2:5 OP, , 2:7 ID, a, 2:9 OP, , 2:11 NUM, 2, 2:13 DELIM, ;, 2:14 END_OF_FILE, , 3:1对照 expected 做 diff./lexer test/case01_basic.c /tmp/out.txt diff -u test/expected/case01_basic.txt /tmp/out.txtdiff无输出才算过。如果有输出先看是不是行号列号差一位再看着是不是某个关键字被识别成了ID。这套流程跑通一个用例剩下的基本是重复劳动直接写个循环for f in test/case*.c; do name$(basename $f .c) ./lexer $f /tmp/$name.out if diff -q test/expected/$name.txt /tmp/$name.out /dev/null; then echo PASS $name else echo FAIL $name; diff -u test/expected/$name.txt /tmp/$name.out fi done4.3 输出格式与常见报错定位跑不通的时候报错信息往往比 diff 更有用。项目里建议在printToken里对ERROR类型特殊处理直接打到 stderr现象大概率原因定位方法输出为空进程直接退出文件读入失败ifstream判断没走到在main开头打印argv[1]和src.size()全是ERROR单字符 token规则文件没被gen_dfa正确加载先单独跑./gen_dfa看 DFA 状态数是否合理关键字全变成ID关键字规则在标识符规则之后匹配或被合并检查规则文件顺序和接受态的 token 类型映射行列号整体偏 1行列号从 0 开始计统一改成从 1 开始起点初始化成line_ 1, col_ 1块注释后面的内容全丢注释未闭合时一直扫到 EOF 没报错在skipWhitespaceAndComment里对 EOF 做显式判断gen_dfa单独能跑是个重要设计它把“规则写错”和“扫描器写错”两类问题分开了。DFA 生成不出来就是规则写错了生成出来但扫描结果不对才是扫描器的问题。5. 避坑与排查那些让我在机房里坐到熄灯的坑实验一看着简单坑全在边角。下面五条是我自己和周围同学反复踩过的每条按“现象 → 原因 → 解决”写对着症状直接查。5.1 扫描阶段的三个坑坑一关键字识别成标识符。现象是int a 1;输出ID, int而不是KW_INT, int。原因通常是关键字表和标识符共用一条规则只在产出 token 前做一次查表但查表时用的lexeme还在扫描缓冲区里没截断或者查表的大小写没统一。解决办法是在buildIdentifier出口处做一次精确匹配且映射表用const std::unordered_mapstd::string, TokenType静态初始化别每个字符都重建一次static const std::unordered_mapstd::string, TokenType kKeywords { {int, TokenType::KW_INT}, {if, TokenType::KW_IF}, {else, TokenType::KW_ELSE}, {while, TokenType::KW_WHILE}, {return, TokenType::KW_RETURN}, }; TokenType classify(const std::string lex) { auto it kKeywords.find(lex); return it ! kKeywords.end() ? it-second : TokenType::ID; }坑二ab死循环或提前截断。现象是扫描到这个表达式时程序卡住或者输出a、、、b这类奇怪切分。原因是贪心匹配后没有回退指针已经越过了合法边界却不知道退。解决办法就是 3.4 节里那套lastAcceptPos记录加rewindTo凡是往前走一步之前先确认这一步走完还能不能回到最近的接受态。坑三CRLF 换行把列号算错。现象是在 Windows 上编辑过的测试文件跑出来行号对、列号对不上。原因是\r被当成普通字符消耗掉但没更新列号逻辑或者把\r\n当成了一个换行算两次。解决办法是在advance里显式处理void Scanner::advance(char c) { pos_; if (c \r) { /* 若下一个是 \n等它来处理换行 */ } else if (c \n) { line_; col_ 1; } else { col_; } }或者更省事读入文件后先做一次\r\n→\n的归一化整篇源串处理一次后面所有逻辑都不用特殊判断。我一般选后者改一行胜过改十处。5.2 自动机构造阶段的两个坑坑四最小化之后接受态合并错。现象是某些标识符被识别成数字或关键字而且只在特定前缀下出问题。原因是划分算法只按“是不是接受态”分了两组没把“接受态对应的 token 类型”算进签名。解决办法是在初始划分或签名里带上类型// 初始划分时按 token 类型分组而不是简单二分 for (int s : dfa.allStates()) { if (dfa.accept.count(s)) group[s] 100 static_castint(dfa.typeOf(s)); // 每类接受态一组 else group[s] 0; }坑五epsilon 闭包写成了普通 BFS漏掉分叉。现象是某些带*或|的规则匹配不到比如[a-z]匹配单字符可以多个字符就断。原因是epsilonClosure里只沿着next1走忘了 epsilon 状态有两条出边。解决办法是把next1、next2都入栈入栈前判重别让它无限循环。这个 bug 特别隐蔽因为单元测试用单字符能过一到真实源码就翻车。注意DFA 生成器最好能打印每个状态的编号、是否为接受态、出边数跟规则文件一起对着看。我在状态数超过 40 之后基本靠这张表定位问题纯看代码根本看不出哪条边接歪了。6. 二次开发从课程实验到能用的词法分析器跑通之后这个项目真正的价值在“能改”。实验一的代码骨架其实和很多真实项目里的 lexer 同构区别只在规则规模和健壮性。下面三件事是我每次基于这类项目做二次开发时必做的。6.1 扩一条词法规则要改哪三个地方不少人加个新运算符比如、-会改半天其实涉及的地方固定改动点文件具体动作规则rules/tokens.rules加一行OP_PLUS_ASSIGN \枚举src/token.hTokenType里加对应枚举值映射src/gen_dfa.cpp或规则动作把接受态关联到新的TokenType改完重新make ./gen_dfa rules/tokens.rules build/dfa.txt再跑一遍全量测试。如果新规则是前缀冲突型和确认最长匹配逻辑能正确处理——a 1应该出而不是加。这里有个容易忽略的点规则文件里必须转义因为它在正则里是量词不转义会解析成“前一个字符重复一次以上”编译能过、运行结果完全不对。6.2 错误恢复与位置信息让后面的语法分析器少骂人课程实验里遇到非法字符直接吐ERROR就完事但要做二次开发就得考虑错误恢复。我在自己的实现里加了一条规则遇到非法字符不中断记录位置和字符跳过它继续扫最后统一汇总所有错误一次性报出来。语法分析阶段拿到干净的 token 流比中途因为一个#断掉舒服太多。具体做法是把nextToken里的ERROR返回改成“填充到错误列表并递归调用自己”Token Scanner::nextToken() { // ... 前面逻辑不变 if (lastAccept -1) { char bad src_[pos_]; errors_.push_back({startLine, startCol, bad}); // 收集而非抛出 advance(bad); return nextToken(); // 跳过坏字符继续找下一个 token } // ... }errors_用std::vectorLexError存main结束时检查非空就打到 stderr但 token 流照常输出。这样一份带小错的源文件也能扫出完整结果便于对照 expected 找差异。一个小提醒递归调用要考虑极端情况比如整个文件全是非法字符把递归改成循环更稳这里为了可读性保留递归形式。6.3 怎么验证你改完没改坏改完词法分析器最怕“新功能能用、老功能坏了”。我的习惯是做三层验证第一层跑原有全部测试用例一个 diff 都不能有第二层拿几份真实风格的源文件自己手写的几百行即可跑一遍人工扫一眼 token 流是否合理第三层写个随机输入生成器随机拼字符、括号、引号看程序会不会卡死或崩溃这层专治指针回退类的 bug# 随机生成 200 份脏输入只要进程超时或非零退出就记一笔 for i in $(seq 1 200); do head -c 4096 /dev/urandom | tr -dc a-zA-Z0-9_-*/();{}\n \ /tmp/fuzz_$i.c timeout 2 ./lexer /tmp/fuzz_$i.c /dev/null 21 || echo BAD $i donetimeout 2是防死循环的关键tr -dc只保留合法字符集和少量标点模拟“看起来像源码但语法全错”的输入。只要有一份超时就说明某条路径下的回退没写对。最后说个教训。我最早写这类项目时习惯改完直接拿case01跑一下看见有输出就交结果在case03_comment上被块注释未闭合的 EOF 判断坑了一整晚——扫描器在文件末尾死等*/pos_越界[]访问到std::string的\0还在继续走最后是靠 gdb 单步才定位到。从那以后我每次改完nextToken相关代码都强制走一遍“全量 diff 三份脏输入 一份随机垃圾”的流程哪怕只是改了一个字符常量的分类分支。希望这套流程能帮到你少在机房里多坐两个小时。本文还有配套的精品资源点击获取