简介这份资源是北京邮电大学编译原理课程实验一的词法分析器实现包面向正在学习编译原理、需要完成词法分析实验的高校学生与自学者。词法分析器是编译器前端的关键模块负责将源代码字符流切分为标识符、关键字、常量、运算符等词素本包可帮助读者理解词法规则定义、输入处理、分词逻辑与错误恢复的完整实现思路。压缩包共4个文件以cpp源代码与h头文件为核心辅以txt格式的说明与测试用例整体约10KB体量轻便便于快速阅读与本地编译调试。目前已有1000人学习下载说明其在课程实验场景中具有一定参考价值。读者可从中获取词法分析器的代码框架、词法规则组织方式以及测试输入样例对照理解LEX/Flex等工具背后的扫描器原理为后续语法分析与语义分析实验打下基础。1. 北邮编译原理课程实验一词法分析器从零手写到能过验收的完整路径如果你正在搜「北邮编译原理课程实验一词法分析器.zip」大概率是两种情况一是实验一刚布置下来对着 Lex 或手写扫描器的要求不知道从哪下手二是已经写了一半被正则、DFA、最长匹配这些概念绕晕想找一份能跑通的参考实现对照着看。词法分析器是整个编译原理实验链条的第一环它把源代码字符流切成一个个有意义的 Token后面语法分析、语义分析全都吃它的输出。这个实验看起来简单但真正动手你会发现坑不少标识符和关键字的区分、浮点数的状态机设计、注释和空白怎么跳过、出错时行号怎么维护。这篇笔记按「先搞懂原理 → 再动手实现 → 最后避坑」的顺序把北邮这门课实验一从设计到验收的完整路径讲清楚适合刚接触编译原理的本科生也适合想用 Java 重写一遍练手的同学。2. 词法分析器的核心原理与选型为什么不能只靠正则2.1 从字符流到 Token 流词法分析到底在做什么词法分析器的输入是一串字符输出是一个 Token 序列。每个 Token 至少包含两部分信息类型比如 IDENTIFIER、NUMBER、PLUS、IF和值比如变量名count、数字3.14。编译器前端后续的语法分析器只认 Token不认原始字符所以词法分析器的职责就是「把没有结构的字符流变成有结构的 Token 流」。听起来简单但有几个关键约束决定了实现方式。第一是最长匹配遇到ifelse时不能切成ifelse得整体识别为一个标识符。第二是优先级关键字和标识符的字符模式完全一样必须先查关键字表再判定标识符。第三是回溯问题读到123abc时数字部分读到123就该停但下一个字符a已经读进来了得想办法「退回去」。这三点决定了你不能简单地用一串 if-else 顺序判断必须有一个能记录状态、支持回退的扫描机制。常见做法有两种一是用正则表达式配合工具如 Lex/Flex/JFlex自动生成二是手写一个确定有限自动机DFA。北邮实验一通常要求手写目的是让你理解 DFA 的工作过程而不是调库。2.2 手写 DFA vs 工具生成实验场景下怎么选工具生成的优点是快写几条正则规则就能出结果但缺点是黑匣子——你不知道它内部怎么处理最长匹配、怎么回退、怎么维护行号。实验验收时老师往往会追问「你这个标识符识别是怎么实现的」如果只会调工具就答不上来。手写 DFA 的核心思路是为每一类 Token 定义一个状态转移过程。比如识别标识符状态机是「读到字母或下划线 → 进入标识符状态 → 继续读字母数字下划线 → 读到其他字符就结束」。识别数字则更复杂要区分整数、小数、科学计数法。手写的好处是每一步都在你掌控中行号维护、错误恢复、回退逻辑都能自己设计。我一般建议的做法是先用状态转移图把每类 Token 画清楚再翻译成代码。状态图不用画得多漂亮关键是每个状态的「入口条件」和「出口条件」要明确。下面这张表是我做实验时常用的 Token 分类和对应的识别规则Token 类型正则模式优先级备注关键字if|else|while|int|float...最高先查表再判标识符标识符[a-zA-Z_][a-zA-Z0-9_]*高最长匹配数字常量[0-9](.[0-9])?高注意小数点后必须有数字运算符|-|*|/||!|...中双字符优先于单字符分隔符( ) { } ; ,中单字符直接匹配注释//... 或 /.../低跳过不产生 Token空白空格、制表、换行最低跳过但换行要维护行号这张表的关键在于优先级顺序关键字 标识符 数字 运算符 分隔符 注释 空白。实际扫描时每读一个字符先判断它可能属于哪几类再按优先级和最长匹配原则决定最终 Token 类型。2.3 状态机设计把正则翻译成可执行代码以数字识别为例一个完整的数字状态机需要处理这几种情况纯整数123、小数3.14、以小数点开头的小数.5有些语言支持、科学计数法1.2e-3。状态转移如下初始状态 S0读到数字 → S1读到.→ S2S1整数部分读到数字 → S1读到.→ S3读到e/E→ S4其他 → 接受回退S2小数点后读到数字 → S3其他 → 报错S3小数部分读到数字 → S3读到e/E→ S4其他 → 接受回退S4指数符号读到/-→ S5读到数字 → S6其他 → 报错S5指数符号后读到数字 → S6其他 → 报错S6指数部分读到数字 → S6其他 → 接受回退这个状态机看起来有 7 个状态但翻译成代码其实就是一个 switch-case 加一个循环。关键是要有一个peek()方法能看下一个字符但不消费以及一个retract()方法能回退一个字符。这两个方法是手写扫描器的核心工具。3. 用 Java 实现词法分析器从 Token 类到主扫描循环3.1 Token 类与符号表的设计先定义 Token 类。一个 Token 至少要有类型、值、行号、列号四个字段。类型用枚举表示值用字符串存原始文本。行号和列号用于报错时定位。public class Token { public enum Type { KEYWORD, IDENTIFIER, NUMBER, OPERATOR, DELIMITER, EOF, ERROR } private Type type; private String value; private int line; private int column; public Token(Type type, String value, int line, int column) { this.type type; this.value value; this.line line; this.column column; } // getter 方法省略 Override public String toString() { return String.format(%s, %s, line%d, col%d, type, value, line, column); } }关键字表用一个HashSetString存初始化时把所有关键字加进去。标识符识别出来后先查这个表命中就是 KEYWORD否则是 IDENTIFIER。运算符表类似但要注意双字符运算符、!、、、、||的优先级高于单字符。private static final SetString KEYWORDS new HashSet(Arrays.asList( if, else, while, for, int, float, double, char, return, void, break, continue, main )); private static final SetString DOUBLE_OPERATORS new HashSet(Arrays.asList( , !, , , , ||, , -- ));符号表在实验一里不是必须的但建议顺手加上。符号表用来存标识符的属性类型、作用域等后面实验二语法分析会用到。最简单的符号表就是一个HashMapString, SymbolInfo键是标识符名字值是属性对象。3.2 主扫描循环peek、advance 与回退机制主扫描循环是词法分析器的心脏。它的逻辑是每次循环开始时跳过空白和注释然后根据当前字符判断进入哪个识别分支识别完一个 Token 后把位置指针推到 Token 末尾继续下一轮。public ListToken tokenize() { ListToken tokens new ArrayList(); while (pos input.length()) { skipWhitespaceAndComments(); if (pos input.length()) break; char c input.charAt(pos); int startLine line; int startCol col; if (Character.isLetter(c) || c _) { tokens.add(readIdentifierOrKeyword(startLine, startCol)); } else if (Character.isDigit(c)) { tokens.add(readNumber(startLine, startCol)); } else if (isOperatorStart(c)) { tokens.add(readOperator(startLine, startCol)); } else if (isDelimiter(c)) { tokens.add(new Token(Token.Type.DELIMITER, String.valueOf(c), startLine, startCol)); advance(); } else { tokens.add(new Token(Token.Type.ERROR, String.valueOf(c), startLine, startCol)); advance(); } } tokens.add(new Token(Token.Type.EOF, , line, col)); return tokens; }advance()方法负责消费一个字符并更新行列号private void advance() { if (pos input.length()) { char c input.charAt(pos); pos; if (c \n) { line; col 1; } else { col; } } }peek()方法看下一个字符但不消费private char peek() { return pos input.length() ? input.charAt(pos) : \0; } private char peekNext() { return pos 1 input.length() ? input.charAt(pos 1) : \0; }回退机制在数字识别里特别重要。比如读到123后下一个字符是这个已经通过peek()看到了但还没消费所以不需要回退。但如果用advance()消费了才发现数字结束了就得回退。我一般用peek()代替advance()来做判断只在确认属于当前 Token 时才advance()这样就不需要显式回退。3.3 标识符、数字、运算符的识别分支标识符识别分支private Token readIdentifierOrKeyword(int line, int col) { StringBuilder sb new StringBuilder(); while (pos input.length() (Character.isLetterOrDigit(input.charAt(pos)) || input.charAt(pos) _)) { sb.append(input.charAt(pos)); advance(); } String value sb.toString(); Token.Type type KEYWORDS.contains(value) ? Token.Type.KEYWORD : Token.Type.IDENTIFIER; return new Token(type, value, line, col); }数字识别分支要处理小数和科学计数法private Token readNumber(int line, int col) { StringBuilder sb new StringBuilder(); boolean hasDot false; boolean hasExp false; while (pos input.length()) { char c input.charAt(pos); if (Character.isDigit(c)) { sb.append(c); advance(); } else if (c . !hasDot !hasExp) { hasDot true; sb.append(c); advance(); } else if ((c e || c E) !hasExp) { hasExp true; sb.append(c); advance(); if (pos input.length() (input.charAt(pos) || input.charAt(pos) -)) { sb.append(input.charAt(pos)); advance(); } } else { break; } } return new Token(Token.Type.NUMBER, sb.toString(), line, col); }运算符识别分支要优先匹配双字符private Token readOperator(int line, int col) { char c input.charAt(pos); char next peekNext(); String twoChar c next; if (DOUBLE_OPERATORS.contains(twoChar)) { advance(); advance(); return new Token(Token.Type.OPERATOR, twoChar, line, col); } advance(); return new Token(Token.Type.OPERATOR, String.valueOf(c), line, col); }这三个分支覆盖了大部分 Token 类型。注释和空白的跳过逻辑放在skipWhitespaceAndComments()里遇到//就跳到行尾遇到/*就跳到*/遇到空格换行就advance()。3.4 测试用例与输出验证写完扫描器后用一段包含各种 Token 的测试代码跑一遍public static void main(String[] args) { String source int main() {\n int count 0;\n float pi 3.14;\n // 这是注释\n while (count 10) {\n count count 1;\n }\n return 0;\n }; Lexer lexer new Lexer(source); ListToken tokens lexer.tokenize(); for (Token t : tokens) { System.out.println(t); } }预期输出应该包含 KEYWORD(int)、IDENTIFIER(main)、DELIMITER(()、DELIMITER())、DELIMITER({)、KEYWORD(int)、IDENTIFIER(count)、OPERATOR()、NUMBER(0)、DELIMITER(;) 等等。重点检查3.14是否被识别为一个完整的 NUMBER 而不是3和.14两个 Tokencount 10里的是否被识别为 OPERATOR注释是否被正确跳过行号是否在换行后递增。4. 避坑与排查词法分析器最容易翻车的 5 个地方4.1 现象ifelse被切成if和else两个 Token原因标识符识别时没有坚持最长匹配原则读到if就急着查关键字表返回了。解决标识符识别必须一直读到非字母数字下划线为止拿到完整字符串后再查关键字表。关键字表只用于判定类型不用于截断识别过程。4.2 现象3.14被识别成3和.14或者3.被当成合法数字原因数字状态机设计不完整没有处理小数点后必须跟数字的约束或者读到小数点后没有继续读后续数字。解决在数字识别分支里读到.后必须检查下一个字符是否是数字如果不是就报错或回退。科学计数法同理e后面必须跟数字或正负号加数字。4.3 现象行号在注释或字符串里换行后不准确原因advance()方法只在主循环里被调用跳过注释时用了pos直接移动指针没有更新行号。解决所有移动指针的操作都必须走advance()包括跳过注释和空白。如果注释跨多行advance()会自动处理换行计数。4.4 现象被识别成两个或者被识别成和原因运算符识别时没有先检查双字符组合直接按单字符返回了。解决读运算符时先用peekNext()看下一个字符拼成双字符字符串查表命中就消费两个字符否则消费一个字符。4.5 现象程序遇到非法字符如、#直接崩溃或死循环原因主循环的 else 分支没有消费当前字符导致pos不前进无限循环。解决else 分支必须advance()消费掉非法字符并生成一个 ERROR 类型的 Token。后续语法分析可以选择跳过 ERROR Token 或直接报错终止。5. 进阶技巧用表驱动法重构扫描器与验收自查清单手写 if-else 分支的扫描器能跑通但代码冗长、扩展性差。如果实验要求支持更多 Token 类型或者你想让代码更优雅可以试试表驱动法。核心思路是把每个 Token 类型的识别规则抽象成一个对象主循环只负责查表和调度。interface TokenReader { Token tryRead(Lexer lexer, int line, int col); boolean canStart(char c); } class IdentifierReader implements TokenReader { public boolean canStart(char c) { return Character.isLetter(c) || c _; } public Token tryRead(Lexer lexer, int line, int col) { // 识别逻辑 } }然后把所有 Reader 放进一个列表主循环遍历列表找到第一个canStart返回 true 的 Reader 来执行。这样新增 Token 类型只需要加一个 Reader 类不用改主循环。验收前用这份清单自查检查项通过标准关键字识别if、while、int等被识别为 KEYWORD 而非 IDENTIFIER最长匹配ifelse识别为一个 IDENTIFIER不是两个 KEYWORD数字格式3.14、1e-5、0.5都能正确识别3.报错双字符运算符、!、、不被拆成两个单字符注释跳过//和/* */内的内容不产生 Token行号维护换行后行号递增报错信息里的行号准确非法字符遇到、#等生成 ERROR Token不崩溃不死循环EOF输入结束后生成 EOF Token主循环正常退出最后说一个我自己的习惯每次改完扫描器先拿一段只有 3 行的小代码跑一遍看 Token 序列对不对再拿完整的测试用例跑。不要一上来就测几百行的代码出了问题定位成本太高。词法分析器是编译原理实验里最容易拿分的一环只要状态机设计清楚、边界情况覆盖到验收基本不会翻车。希望帮到你。本文还有配套的精品资源点击获取