简介一份面向北京邮电大学编译原理课程实验的词法分析器实现资料适合正在学习编译器前端、需要完成Lexer设计与编码的本科生参考。资源围绕词法规则定义、输入字符流处理、符号栈管理与错误恢复等关键环节展开对应编译器构造中的扫描器实现能够帮助读者理解标识符、关键字、常量、运算符等词素的识别流程。压缩包共4个文件包含Lexer.cpp源码、res.h头文件、README说明与test测试文本整体仅10KB结构紧凑便于快速定位核心代码并对照测试样例进行调试。已有1000人学习下载适合作为课程实验的独立完成或排错对照素材。通过阅读源码和测试文件可以直观掌握词法分析器的程序框架与实现细节为后续语法分析、语义分析乃至完整编译器设计打下基础。1. 北邮编译原理课程实验一词法分析器第一关就卡住大半人的地方北邮编译原理课程实验里词法分析器通常是第一个要交的代码物。很多人以为它就是把关键字和数字“查出来”的体力活结果动手才发现自己写的分析器要么最后一个 token 被吞掉要么注释里的关键字被错误识别成词法单元跑遍用例也交不了差。这篇笔记把这类实验拆成“正则转 DFA、表驱动扫描、错误恢复、验证脚本”四块来讲适合正在写编译原理实验的学生也适合想从零补词法分析器实现的人。它解决的是同一个问题让分析器在最长匹配、多状态切换和出错继续扫描的情况下仍然稳定输出正确的 token 流。2. 从正则到 DFA把实验要求拆成能用的状态机2.1 三条实现路线怎么选词法分析器在课程实验里有三种常见做法。第一种是用 flex 这种生成器写正则规则然后自动生成 C 代码快但黑匣子太重老师一旦追问“你的 DFA 在哪”容易卡壳。第二种是手写一个大 switch 判断每个字符简单直观但状态一多就变成意大利面条后续加字符集和注释状态时特别想骂人。第三种是正规做法先为正则表达式构造 NFA再用子集构造法转 DFA最后最小化状态数并生成转移表。我一般会劝选第三种。北邮这类课程实验的验收点往往就是 DFA 状态图、转移表和 Token 流输出你走完第三条路线等于把编译原理第三章的核心算法全部实现了。而且这条路线的每一步都能单独打印出来验证NFA 有多少个状态、DFA 哪些状态被合并、转移表哪一行走向错误态这些是写实验报告的关键素材。对应王生原翻译的《编译原理》第三版第三章课后习题里那些“构造 NFA”“子集构造”“最小化”的题目做完这个实验基本就打通了。三条路线的对比如下。路线学习收益工作量调试难度适合场景flex 生成低重点是学会写正则语法最低低只想跑通流程不关心状态机细节手写 switch中能理解匹配逻辑中状态一多容易乱词法规则很少的迷你语言正则转 NFA 转 DFA高覆盖课内核心算法高中但每步可验证课程验收和后续语法分析衔接2.2 Thompson 构造法与 NFA 节点设计把正则表达式转成 NFA最通用的是 Thompson 构造法。它把每一条正则规则拆成子表达式的拼装两个子 NFA 前后串联、并联和闭包三种组合方式。实现上先定义 NFA 节点结构每个节点包含普通字符转移边、空转移边和一个接受标记。import java.util.*; class NfaState { int id; // 状态编号打印 NFA 图时用 MapCharacter, SetNfaState next; // 普通字符转移键是字符 SetNfaState epsilon; // 空转移集合 boolean isEnd; // 是否为接受状态 public NfaState(int id) { this.id id; this.next new HashMap(); this.epsilon new HashSet(); this.isEnd false; } public void addTransition(char c, NfaState target) { next.computeIfAbsent(c, k - new HashSet()).add(target); } public void addEpsilon(NfaState target) { epsilon.add(target); } }这里的next用Set而不是单个状态原因是 Thompson 构造法会自然产生一个字符出发到多个状态的情况比如并联结构里初始状态同时指向两个分支。epsilon专门存空转移它在子集构造时会成为核心处理对象。调试时把每个状态的id、next和epsilon按行打印出来就能画出一张完整的 NFA 图交实验报告时直接贴这个输出。2.3 子集构造法与状态转移表生成NFA 还不是最终产物真正用于扫描的是 DFA。子集构造法把 NFA 的状态集合映射成 DFA 的单个状态。两个基础操作是空转移闭包和普通字符转移。空转移闭包表示“不消耗字符也能到达的所有状态”普通字符转移表示“吃掉一个字符 c 后能到达的所有状态再取闭包”。// 计算一个 NFA 状态集合的空转移闭包 SetNfaState epsilonClosure(SetNfaState states) { DequeNfaState stack new ArrayDeque(states); SetNfaState closure new HashSet(states); while (!stack.isEmpty()) { NfaState s stack.pop(); for (NfaState t : s.epsilon) { if (closure.add(t)) { stack.push(t); } } } return closure; }这里用栈做遍历是因为空转移会链式出现closure.add(t)返回 true 说明这个状态是第一次被加入需要继续展开它的空转移。写这个函数时最容易漏掉的是初始状态本身也要进闭包所以变量初始化直接把states全部放进去。子集构造的完整流程是对 DFA 的每一个新状态遍历所有字符类别分别计算“当前状态集合中每个状态经过该字符到达的状态集合”的闭包把结果映射成新的 DFA 状态。这一步得到的 DFA 状态数可能不少但接下来最小化会把它压回去。最小化常见做法是先把状态划分成“接受状态”和“非接受状态”两个集合然后反复细化如果某个划分里两个状态对同一个字符类别跳到了不同的划分就把它们拆开。拆到不能再拆为止。这个算法的代码量不大但需要注意把“错误状态”单独列一个集合否则转移表里未定义的行会被错误地映射到普通状态后面扫描的时候越界访问是迟早的事。处理完最小化以后把状态编号 字符类别 下一状态直接写成二维数组就是第 3 章扫描程序的输入了。3. 用 Java 逐行实现词法分析器Token 定义、字符分类与主循环3.1 Token 类型和字符类别映射词法分析器的输出是 Token 流。课程实验要求的 Token 类型一般包括标识符、关键字、数字常量、字符串常量、运算符和分隔符外加一个错误类型。设计枚举时先把类型定下来后面加类型只需要改枚举和查表函数两个地方。enum TokenType { IDENTIFIER, KEYWORD, NUMBER, STRING, OPERATOR, DELIMITER, ERROR } class Token { TokenType type; String lexeme; // 词素文本 int line; // 所在行号 int col; // 所在列号调试排错很好用 public Token(TokenType type, String lexeme, int line, int col) { this.type type; this.lexeme lexeme; this.line line; this.col col; } Override public String toString() { return String.format(%-12s %-20s line%d col%d, type, lexeme, line, col); } }字符分类函数决定扫描器每次读入一个字符时查哪一列转移表。分类越粗DFA 的状态数越少分类越细越能区分运算符和分隔符。课程实验的常见做法是把字符分成九类字母和下划线、数字、空白、运算符、分隔符、双引号、单引号、哨兵字符和非法字符。注意关键字不单独占一个字符类别它由标识符状态匹配完成后查表决定。int charClass(char c) { if (Character.isLetter(c) || c _) return 0; // 字母与下划线 if (Character.isDigit(c)) return 1; // 数字 if (Character.isWhitespace(c)) return 2; // 空白 if (-*/%!|.indexOf(c) 0) return 3; // 运算符 if ((){}[];,.indexOf(c) 0) return 4; // 分隔符 if (c ) return 5; // 双引号 if (c \) return 6; // 单引号 if (c 0) return 7; // 哨兵 return 8; // 非法字符 }这里把c 0单独分一类的目的是为了让扫描循环能统一处理文件末尾。后面主循环会使用“多读一个哨兵字符”的技巧来强制触发最后一次最长匹配这个技巧是避免最后一个 Token 被吞掉的关键。3.2 表驱动主循环最长匹配和向前看一个字符DFA 扫描的核心是一个循环读一个字符查转移表进入下一状态如果某个状态是接受状态就记录下这个位置一旦走到死路就把“最后一次接受的位置”作为当前 Token 的终点。这样保证匹配到的是最长有效子串而不是刚识别到前缀就草草收工。public ListToken scan(String source) { ListToken tokens new ArrayList(); int pos 0; int line 1; int state 0; // DFA 当前状态0 是初始状态 int tokenStart 0; // 当前 Token 的起始位置 int lastAcceptState -1; // 最近一次进入接受状态时的状态编号 int lastAcceptPos -1; // 最近一次接受位置 while (pos source.length()) { char c (pos source.length()) ? source.charAt(pos) : 0; int nextState transition[state][charClass(c)]; if (nextState 0) { state nextState; if (accept[state]) { lastAcceptState state; lastAcceptPos pos 1; // 接受位置是下一个字符的索引 } pos; // 正常推进一个字符 } else { if (lastAcceptState 0) { String lexeme source.substring(tokenStart, lastAcceptPos); tokens.add(makeToken(lastAcceptState, lexeme, line)); pos lastAcceptPos; // 回退到最后一次接受位置的后一位 state 0; tokenStart pos; lastAcceptState -1; lastAcceptPos -1; } else { // 死路且没有接受状态说明是非法字符 tokens.add(new Token(TokenType.ERROR, source.substring(tokenStart, tokenStart 1), line, pos)); pos tokenStart 1; state 0; tokenStart pos; } } } return tokens; }这段循环有两个参数需要特别注意。第一个是transition[state][charClass(c)]的state和charClass(c)前者是之前积累的 DFA 状态后者是当前字符的类别两者共同决定下一个状态。第二个是lastAcceptPos pos 1这里加一是因为pos还没递增pos 1正好是当前字符的下一个位置而substring是左闭右开区间。循环的终止条件是pos source.length()当pos source.length()时读到哨兵字符哨兵在转移表中没有合法转移于是触发最后一次 Token 的截断输出。没有这个哨兵最后一个不带分隔符的标识符或数字就会被永远留在缓冲区里。3.3 标识符和关键字的查表策略标识符匹配到接受状态后并不能直接确定 Token 类型。课程实验的语言里int、return、while这类词虽然长得像普通标识符但语义上是关键字。常见做法是维护一个关键字哈希表先按标识符处理再查表判断是否升级为关键字。private static final MapString, TokenType KEYWORDS new HashMap(); static { KEYWORDS.put(int, TokenType.KEYWORD); KEYWORDS.put(char, TokenType.KEYWORD); KEYWORDS.put(if, TokenType.KEYWORD); KEYWORDS.put(else, TokenType.KEYWORD); KEYWORDS.put(while, TokenType.KEYWORD); KEYWORDS.put(return, TokenType.KEYWORD); } Token makeToken(int state, String lexeme, int line) { if (state IDENT_STATE) { TokenType type KEYWORDS.getOrDefault(lexeme, TokenType.IDENTIFIER); return new Token(type, lexeme, line, 0); } if (state NUMBER_STATE) { return new Token(TokenType.NUMBER, lexeme, line, 0); } // 其余状态按规则映射 return new Token(TokenType.OPERATOR, lexeme, line, 0); }这里的IDENT_STATE和NUMBER_STATE是识别标识符和数字的最终状态编号具体值取决于第 2 章生成的 DFA。把关键字表独立出来的好处是实验要求变严格时可以随时往里加词而转移表完全不用动。我在这个阶段犯过的错误是把关键字处理写死在 accept 状态判断里结果状态一多就分不清哪个状态对应哪个关键字复盘之后才明白查表才是最省事的方案。4. 错误恢复与符号表实验报告里最容易被扣分的两处细节4.1 出错后继续扫描还是立即终止很多第一次写词法分析器的人遇到非法字符就直接System.exit(1)这样在课程验收时很吃亏。老师给的测试用例往往故意包含非法输入期望输出里要有错误提示但后续 Token 仍然正常输出。正确的做法是“吃掉一个字符继续扫描”遇到死路且没有接受状态时把当前字符记为 ERROR 类型的 Token位置向前推进一位然后从初始状态重新开始。一个容易被忽略的细节是错误 Token 的pos更新规则。上面主循环里已经写了pos tokenStart 1但很多实现会顺手写成pos lastAcceptPos这里如果lastAcceptPos是 -1就会死循环或者跳过一个字符。我的习惯是错误恢复时用tokenStart 1而不是pos 1因为tokenStart是本次扫描周期的起点从它加一才能精确跳过非法字符而pos可能已经往前跑了好几个字符。这是写错误恢复函数时最容易翻车的一个地方。4.2 符号表要不要在词法阶段做北邮这类课程内部常见的约定是符号表留到语法分析阶段再实现但词法分析器可以先插入“登记”的接口。原因是标识符、常量和字符串在语法分析阶段会被反复查询类型和作用域如果词法阶段就把表建好语法阶段可以直接继承省掉重新遍历源文件的成本。符号表条目的最小设计是四个字段名字、种类、附加属性和首次出现的行号。这里字段少一点没有关系关键是词法器必须在每次识别完一个标识符后及时登记。class SymbolEntry { String name; // 符号名比如 temp String kind; // 标识符 / 常量 / 字符串 String attr; // 附加信息类型、字面量等 int line; // 首次出现的行号用于报错定位 int count; // 出现次数统计引用频率用 public SymbolEntry(String name, String kind, String attr, int line) { this.name name; this.kind kind; this.attr attr; this.line line; this.count 1; } }登记函数最好放在makeToken里识别到IDENTIFIER类型后执行一次symbolTable.putIfAbsent(name, entry)。需要注意变量名大小写是否敏感课程语言一般默认大小写敏感Count和count是两个不同的符号所以哈希表的键直接使用原始 lexeme不做任何 normalize。关键字不要登记进符号表它在语法分析阶段有单独的分类。4.3 行号与列号维护行号和列号看似简单但多行注释和字符串跨行时经常出问题。最稳的方案是在扫描循环里单独维护两个变量读到\n时line、col 0否则col。问题出在注释状态里换行符的处理上如果你在 DFA 的状态转移表里让注释状态直接跳过任意字符那么遇到换行符时这里只做状态转移不会触发line于是后续所有报错行号全部错位。这块的原理是词法分析器的行号维护必须和字符处理同步不能依赖将来对 Token 内容做二次扫描。更具体的说处理注释、字符串等多行状态时转移表的动作列要单独标记“遇到换行符时 line”。我一般会把行号维护抽成一个advancePosition(char c)小函数在每次读完一个字符后调用而不是混在主体逻辑里。这样一来不管是普通代码、字符串还是注释行号更新逻辑全部走同一个入口实验报告里关于行号准确性的验证截图也很好补。5. 常见问题排查5 个让词法分析器翻车的坑与对策5.1 文件末尾最后一个 Token 被吞掉现象输入int a 10不带分号输出只有int、a、10消失。原因扫描循环用while (pos source.length())作为终止条件最后一个数字读完后再无字符可读死路永远不会触发接受状态里的内容就一直留在缓冲区。解决把循环条件改成pos source.length()并引入哨兵字符让最后一次循环强制走到死路从而截断最后一个 Token。这个坑在第一次写词法器时几乎人人踩调试时用“末尾不带分隔符”的用例单独测一条就能暴露问题。5.2 字符串和注释里的关键字被错误识别现象输入/* int x 1; */输出的 Token 流里出现整段内容甚至int被标记为 KEYWORD。原因扫描器进入注释状态时没有做状态隔离注释内容被当作普通代码走了一遍标识符匹配。解决在状态转移表里把注释状态设计成“从/和*进入遇到*后紧跟/才退出”的独立状态处于该状态时所有字符都不参与普通 Token 匹配。字符串状态同理遇到双引号进入字符串专属状态在字符串内部除了转义字符外不做任何状态判断。这个方案从 DFA 阶段就定下来中途打补丁很容易漏掉转义字符的边界情况。5.3 行号错位报错定位全靠猜现象报错信息显示第 10 行的 Token实际在第 6 行。原因多行注释状态里直接跳过了\n行号计数器没更新。解决如前所述把所有字符处理统一收口到advancePosition函数在读字符循环里每次都对当前字符检查一次是否为换行符。这里要特别强调不仅普通字符需要更新行号注释状态、字符串状态和非法字符状态同样需要更新。把行号更新放在三个分支各自重复一次代码会很难维护统一入口才是正解。5.4 最小化 DFA 状态表越界现象程序运行到某个罕见字符时抛出ArrayIndexOutOfBoundsException。原因最小化 DFA 时没有把错误态单独归类导致转移表的某些行没有定义查表时直接越界。解决子集构造完成后统一把所有未定义转移映射到-1而不是映射到错误状态编号。查表时先判断nextState 0再做状态更新也就是第 3 章主循环里已经写过的处理逻辑。写最小化算法时初始划分必须是{接受状态},{错误态},{普通非接受状态}三个集合任意合并都会埋下越界隐患。5.5 数字溢出被直接丢弃现象输入一个超长整数字面量99999999999999999999程序抛NumberFormatException或者输出负数。原因词法分析阶段直接调Integer.parseInt解析数字。解决识别数字时先判断字符串长度是否超过 10 位十进制 int 上限超过则仍然生成 NUMBER 类型 Token但把attr标记为overflow让语法阶段决定是转成长整型还是报错。解析操作放在makeToken而不是扫描循环里这样即使数字解析失败扫描过程也不会中断。6. 进阶验证用差分测试给词法分析器上一份保险词法分析器的正确性不能靠肉眼盯几段输入来确认一定要做差分测试。思路是用一个可信的参照实现输出 Token 流再把自己的输出规范化后逐行对比。课程实验阶段可以用 flex 生成一个最简单的参照词法器也可以用系统工具配合正则做替换输出。我习惯用 Python 脚本批量跑用例全部通过才算数。先准备一组测试用例文件覆盖空文件、纯注释、不含末尾分隔符的代码、连续运算符、未闭合字符串、非法字符、超长标识符、跨行注释。熟练以后可以再加中文注释和 CRLF 换行。把每个用例输入给两个分析器把两边输出按“类型 词素 行号”的格式统一排版之后再 diff。#!/usr/bin/env python3 import subprocess import sys cases [ , # 空文件 int a 1, # 末尾无分号 /* only comment */, # 纯注释 x a -b;, # 连续运算符 s \unterminated;, # 未闭合字符串 id 123;, # 非法字符 while (i 10) { i; }, # 综合用例 ] for code in cases: with open(/tmp/input.c, w) as f: f.write(code) out_mine subprocess.run([./scanner, /tmp/input.c], capture_outputTrue, textTrue).stdout out_ref subprocess.run([./ref_scanner, /tmp/input.c], capture_outputTrue, textTrue).stdout normalized_mine normalize(out_mine) normalized_ref normalize(out_ref) if normalized_mine ! normalized_ref: print(FAIL on:, repr(code)) print(mine:, normalized_mine) print(ref :, normalized_ref) sys.exit(1) print(all cases passed)差分测试跑通以后还有两个验证习惯值得养成。第一个是把第 2 章生成的转移表和接受状态表打印出来人工抽查几个路径比如int必须走到关键字接受状态10必须走到数字接受状态。第二个是用覆盖率工具统计每个状态是否被用例访问过如果有状态没走到说明测试用例集有空洞要补输入。我当年做这个实验的时候正是靠差分脚本查出多行注释状态的行号不更新问题那一次返工让我意识到词法分析器的坑往往不在工具链深不深而在最长匹配、状态隔离和行号更新这些看起来不起眼的细节上。希望这篇笔记能帮你在同样的地方少走两轮弯路。本文还有配套的精品资源点击获取