编译原理词法分析器：手写Java状态机与避坑指南

简介：这份压缩包提供了一份编译原理课程中词法分析器的C++实现，面向正在学习编译原理、需要完成相关实验或深入理解词法分析整体流程的高校学生。程序支持启动后输入测试程序名，自动对源码进行词法分析，并以单词二元式序列输出结果；同时针对SAMPLE字符集之外的非法字符、字符常数缺少右单引号、注释缺少结尾界符*/等典型错误，能够准确指出错误性质和出现位置。压缩包内含1个.cpp源文件，大小约2KB，代码量不大但覆盖了词法分析的核心逻辑，便于逐行研读和在此基础上扩展。目前已有4264人学习下载，适合作为词法分析实验的参考模板，帮助读者理解关键字与标识符识别、状态转换、错误处理机制以及二元式输出格式设计等关键环节。

1. 编译原理词法分析器，为什么是课程设计里唯一能拿满分的模块

编译原理词法分析器看着只是把源码切成 Token，好像没什么技术含量，实际上整条编译链路里报错行号准不准、关键字串不串味、注释会不会吞掉代码，全在这一步定型。很多用 Java 写编译原理实验的同学都有这种体会：语法分析器写了三周没崩，词法分析器的缓冲区先崩了。这篇文章把我做词法分析器用的 Token 设计、状态转换图、手写代码和排错经验串一遍，给正在做编译原理实验的读者一条能照抄的落地路径，也适合想回看底层状态机的从业者。

2. 先定 Token 种别再写代码：状态转换图与正规式的对应关系

词法分析器做的事一句话：读字符流，吐出 Token 流。Token 流就是一组{种别, 单词, 行号, 列号}记录。这一步不关心if后面有没有括号、声明合不合法，它只负责把sum切成一个标识符，把10.5切成一个实数，然后遇到@这种字符时给你一个明确的词法错误。听起来简单，但真正动手时，第一个问题往往是：我到底要识别多少种东西？

我一般的做法是，先别打开编辑器，拿一张纸把这门语言里所有合法的"词"列出来。列出来的过程就是设计 Token 种别表的过程。

2.1 Token 种别表：种别码定多少位，正规式怎么写

Token 种别表的常见格式是：种别、种别码、正规式、示例。种别码在课程设计里通常就是一个整数常量，后续语法分析器靠这个整数判断当前读到的是什么东西。下面是我常用的一张最小表，覆盖大多数编译原理实验要求：

表格里最需要动脑子的是"关键字到底算不算独立的种别"。很多同学会把if、else、while各编一个种别码，结果种别表瞬间膨胀到三四十项。更常见且更省事的方案是：所有关键字共用一个种别码KEYWORD，具体是哪个关键字靠text字段区分。这样正规式只写一个标识符规则，扫描时先按标识符把整个词读出来，再去查一张关键字哈希表决定它到底是IDENTIFIER还是KEYWORD。

这种方法的好处在于，标识符的正规式和关键字的正规式天然就是同一个，不会出现"ifx被拆成if和x"这种经典错误。后续我会在避坑章节专门讲这个坑。

2.2 从正规式到状态转换图：标识符、整数、字符串的三条转化链

种别表定完，下一步就是把每个正规式变成状态转换图。状态转换图不是摆设，它直接决定代码里switch怎么分叉。以标识符为例：正规式是letter ( letter | digit )*，状态图就是三个状态——起始状态读到一个字母，进入"标识符中"状态；在"标识符中"状态读到字母或数字，留在原地；读到其他字符，结束并吐出 Token。

整数[0-9]+的状态图更简单：起始状态读数字，进"整数中"状态；继续读数字留在原地；读到小数点且后面有数字，进"实数中"状态；读到其他字符，结束。这里有一个细节：如果到了结束位置才去判断"到底是整数还是实数"，就需要在状态里记一个isReal标志。我写的代码里是用一个布尔变量在读取过程中随时翻转。

字符串"..."的状态图稍微复杂一点，因为它允许空白和特殊字符出现在两个引号之间，还要处理换行（未闭合的字符串要报错）。所以字符串的状态转移条件是：进入字符串状态后，读了非引号、非换行的字符就留在原地；读引号结束；读换行或 EOF 就报"未闭合字符串"。

状态转换图里的每个节点，最终都对应代码里的一个if分支或循环体。节点少的问题可以在纸上画，节点一旦超过二十个，我建议直接考虑使用工具生成，这部分放到第 4 章。

2.3 最长匹配原则与单字符回溯：状态机可靠的底层逻辑

词法分析器有一个默认约定：只要当前状态合法，就尽量多读字符。这就是最长匹配原则。>=必须被识别成一个运算符，而不是>再加一个=；10.5必须被识别成一个实数，而不是10加一个.加5。实现这个原则靠的是"看一个字符再决定"的 peek 策略，而不是先拆开再拼回去。

具体到代码里，peek 策略长这样：在识别数字的过程中，读到小数点时，先看一眼下一个字符是不是数字，是才把小数点并进当前 Token，否则宁可结束当前 Token，把小数点留给下一轮当作单独运算符。这种"超前扫描一个字符"的做法不会真的回溯——因为你看完没采用的那个字符，下一轮nextToken()会从那个位置重新开始读，所以它等于被留在缓冲区里了。理解这一条，后面调试1..2这种输入时会省很多力气。

3. 用 Java 手写词法分析器：核心扫描流程与三个关键代码块

手写词法分析器，我推荐用 Java 而不是 C，原因不是性能，而是字符串和动态数组在 Java 里是现成的，省去手动管理缓冲区的精力，让你把注意力放在状态转移上。下面这套代码是一个可以在编译原理实验中直接跑通的最小实现，支持关键字、标识符、整数、实数、字符串、注释、单/双字符运算符和基本的错误报告。

3.1 类怎么拆：TokenType、Token、Lexer 三类划分

三个类的边界很明确。TokenType是枚举，定义所有种别；Token是产出物，携带类型、单词文本、行号、列号；Lexer是扫描器，只负责把字符串变成Token。主函数写一段包含各类词的源码，方便你直接看输出。

import java.util.*; enum TokenType { KEYWORD, IDENTIFIER, INTEGER, REAL, STRING, OPERATOR, DELIMITER, EOF, ERROR } class Token { TokenType type; String text; int line; int column; Token(TokenType type, String text, int line, int column) { this.type = type; this.text = text; this.line = line; this.column = column; } @Override public String toString() { return String.format("%-10s | %-14s | line=%d col=%d", type, text, line, column); } }

Token里保存line和column不是可选项，而是刚需。语法分析器在报"这里缺个分号"的时候，依赖的就是这个行列号；你自己调试 Token 流时，没有行列号根本没法对着源码定位。另外，toString()故意用String.format固定列宽，是为了在终端里一眼看出哪一行出了问题。

3.2 核心扫描循环：跳空白后识别标识符与数字

Lexer的核心是nextToken()方法，每次调用吐出下一个 Token。它做的第一件事是跳过空白，包括空格、制表符、换行，然后根据当前字符的类型进入不同的读取分支。看代码：

class Lexer { private final String input; private int pos = 0; private int line = 1; private int column = 1; private static final Set<String> KEYWORDS = new HashSet<>(Arrays.asList( "if", "else", "while", "for", "return", "int", "float", "string", "void" )); Lexer(String input) { this.input = input; } Token nextToken() { skipWhitespace(); if (pos >= input.length()) { return new Token(TokenType.EOF, "", line, column); } int startLine = line; int startCol = column; char c = input.charAt(pos); if (isLetter(c) || c == '_') { return readIdentifier(startLine, startCol); } if (isDigit(c)) { return readNumber(startLine, startCol); } if (c == '"') { return readString(startLine, startCol); } if (c == '/') { if (pos + 1 < input.length() && input.charAt(pos + 1) == '/') { skipLineComment(); return nextToken(); } if (pos + 1 < input.length() && input.charAt(pos + 1) == '*') { if (skipBlockComment()) { return nextToken(); } else { return new Token(TokenType.ERROR, "unterminated block comment", startLine, startCol); } } } Token multi = tryReadMultiCharOp(startLine, startCol); if (multi != null) { return multi; } if ("+-*/%<>=!;,.()[]{}".indexOf(c) >= 0) { pos++; column++; TokenType tt = ",;()[]{}".indexOf(c) >= 0 ? TokenType.DELIMITER : TokenType.OPERATOR; return new Token(tt, String.valueOf(c), startLine, startCol); } pos++; column++; return new Token(TokenType.ERROR, "illegal char: " + c, startLine, startCol); } private void skipWhitespace() { while (pos < input.length()) { char c = input.charAt(pos); if (c == ' ' || c == '\t') { pos++; column++; } else if (c == '\r') { if (pos + 1 < input.length() && input.charAt(pos + 1) == '\n') { pos++; } pos++; line++; column = 1; } else if (c == '\n') { pos++; line++; column = 1; } else { break; } } } private Token readIdentifier(int startLine, int startCol) { StringBuilder sb = new StringBuilder(); while (pos < input.length() && (isLetter(input.charAt(pos)) || isDigit(input.charAt(pos)) || input.charAt(pos) == '_')) { sb.append(input.charAt(pos)); pos++; column++; } String word = sb.toString(); TokenType tt = KEYWORDS.contains(word) ? TokenType.KEYWORD : TokenType.IDENTIFIER; return new Token(tt, word, startLine, startCol); } private Token readNumber(int startLine, int startCol) { StringBuilder sb = new StringBuilder(); while (pos < input.length() && isDigit(input.charAt(pos))) { sb.append(input.charAt(pos)); pos++; column++; } if (pos < input.length() && input.charAt(pos) == '.' && pos + 1 < input.length() && isDigit(input.charAt(pos + 1))) { sb.append('.'); pos++; column++; while (pos < input.length() && isDigit(input.charAt(pos))) { sb.append(input.charAt(pos)); pos++; column++; } return new Token(TokenType.REAL, sb.toString(), startLine, startCol); } return new Token(TokenType.INTEGER, sb.toString(), startLine, startCol); } private boolean isLetter(char c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } private boolean isDigit(char c) { return c >= '0' && c <= '9'; } }

这段代码的skipWhitespace单独处理了\r\n组合，Windows 换行符不会把\r当成非法字符，这个细节很多教材代码都没写。readIdentifier先完整读出一个词，再查预定义的关键字集合，而不是在读的过程中逐个匹配关键字，这保证ifx不会被拆成if+x。readNumber里判断小数点时用了一个pos + 1的 peek，只有后面确认为数字才吞掉小数点，否则1..2会得到一个1的整数和一个单独的点号，而不是把1.并进去。

3.3 注释、字符串与多字符运算符的独立方法

字符串和注释的处理要单独拆方法，因为它们内部允许出现的字符和普通代码完全不同。字符串里可以出现空格和大多数运算符字符，注释里可以出现任何字符直到终止符，这些状态如果塞进nextToken()主分支里，代码会乱成一团。

private Token readString(int startLine, int startCol) { pos++; column++; StringBuilder sb = new StringBuilder(); while (pos < input.length() && input.charAt(pos) != '"' && input.charAt(pos) != '\n') { char ch = input.charAt(pos); if (ch == '\\' && pos + 1 < input.length()) { pos++; column++; ch = input.charAt(pos); } sb.append(ch); pos++; column++; } if (pos < input.length() && input.charAt(pos) == '"') { pos++; column++; return new Token(TokenType.STRING, sb.toString(), startLine, startCol); } return new Token(TokenType.ERROR, "unterminated string: \"" + sb, startLine, startCol); } private void skipLineComment() { while (pos < input.length() && input.charAt(pos) != '\n') { pos++; column++; } } private boolean skipBlockComment() { pos += 2; column += 2; while (pos + 1 < input.length() && !(input.charAt(pos) == '*' && input.charAt(pos + 1) == '/')) { if (input.charAt(pos) == '\n') { line++; column = 1; } else { column++; } pos++; } if (pos + 1 < input.length()) { pos += 2; column += 2; return true; } pos = input.length(); return false; } private Token tryReadMultiCharOp(int startLine, int startCol) { if (pos + 1 >= input.length()) { return null; } String two = input.substring(pos, pos + 2); if (two.equals("==") || two.equals("!=") || two.equals("<=") || two.equals(">=") || two.equals("&&") || two.equals("||")) { pos += 2; column += 2; return new Token(TokenType.OPERATOR, two, startLine, startCol); } return null; } }

readString里的转义处理是简化版：遇到反斜杠就把下一个字符当普通字符吞掉，不做\n、\t的语义转换。对词法分析器来说这已经够用，转义字符的语义解释是语法分析或语义分析阶段的事。skipBlockComment里最容易被忽略的是换行——每读到一个\n必须更新line并重置column，否则注释后面所有报错的行号都会偏移。这也是老生常谈的"注释导致行号雪崩"问题，第 5 章再展开。

主函数用一个包含各种 Token 的源码串验证：

public class TestLexer { public static void main(String[] args) { String src = "int sum = 0;\n" + "for (int i = 0; i < 10; i++) {\n" + " sum += i; // 累加\n" + "}\n" + "string name = \"rx\";\n" + "/* block comment */\n" + "if (sum >= 10.5) { return 0; }\n"; Lexer lexer = new Lexer(src); Token t; do { t = lexer.nextToken(); System.out.println(t); } while (t.type != TokenType.EOF); } }

这段主函数输出结果时，你可以对照源码逐行看行列号是否准确。特别注意：// 累加后面的内容没有输出任何 Token，块注释里的内容也没有，这说明注释被正确跳过了。如果{ return 0; }附近的行号比实际多或少，问题基本都出在注释或换行处理上。

4. 手写还是上 Flex/JFlex：两条路径怎么选，参数怎么给

不少编译原理实验允许或者鼓励用工具生成词法分析器。工具派最常用的是 Flex（C/C++ 生态）和 JFlex（Java 生态）。工具的好处是正规式写得快，几行就声明完所有规则，但代价是你要接受一套额外的 DSL 语法，出了问题排查起来比手写代码更玄学。我见过太多同学在.lex文件里漏了一个%或者括号不匹配，卡一个晚上。

4.1 JFlex/Flex 三步走：.lex 文件的正则段、动作段和辅助段

JFlex 的输入文件通常分三段：用户代码段（可选）、选项与词法规则段、用户辅助代码段。三段用%%分隔。一个最小的simple.flex文件长这样：

%% %class SimpleLexer %line %column Digit = [0-9] Letter = [a-zA-Z_] %% {Letter}({Letter}|{Digit})* { return new Token(TokenType.IDENTIFIER, yytext(), yyline, yycolumn); } {Digit}+ { return new Token(TokenType.INTEGER, yytext(), yyline, yycolumn); } "==" | "!=" | "<=" | ">=" | "&&" | "||" { return new Token(TokenType.OPERATOR, yytext(), yyline, yycolumn); } [ \t\n\r]+ { /* skip whitespace */ } "//"[^\n]* { /* skip line comment */ }

第一行%%前是选项区，%class指定生成的类名，%line和%column让 JFlex 自动维护yyline与yycolumn变量。规则区每条规则由正规式和动作组成，动作就是在{}里写 Java 代码。yytext()返回当前匹配到的字符串，这三个变量组合起来，刚好能生成和手写版本完全一致的 Token。

需要说明的是，这种.flex文件的细节在不同版本之间略有差异，比如有的版本要求%class写在%{ %}里，有的直接写。用工具的正确姿势是：先跑通一个空文件，再逐步加规则，不要一次性写全。

4.2 手写还是工具：缓冲区控制、错误定位和实验要求三个维度

选择手写还是工具，我一般看三个维度。第一是实验要求，很多学校的编译原理实验明确标注"手工构造词法分析器"，这种情况下用工具会被判抄袭或至少拿不到过程分。第二是 Token 种类的规模，20 种以内的 Token 手写完全可控，超过 40 种就建议工具；课程设计的规模一般不会超过 25 种，手写的代码量其实不大。第三是错误定位的精细度，手写状态机里你可以在任何状态下做自定义错误处理，工具生成的 DFA 对非法字符的恢复策略相对固定。

这里有个容易被忽视的点：用工具时正则规则命中的优先级取决于规则在文件中的顺序。比如关键字规则必须写在标识符规则前面，否则if会被当成标识符；手写方案则不同，它是先按标识符读完整词再查关键字表，天然避免了这个顺序问题。

4.3 行号列号与最长匹配的默认参数：工具和手写都要对齐

无论哪条路，最终产出的 Token 流格式必须对齐，否则后面语法分析器没法统一对接。我最常遇到的"参数没对齐"是：手写版本的column从 1 开始计数，JFlex 的yycolumn也从 1 开始，两者一致；但有些同学的column是从 0 开始，导致所有报错位置差一格。

另一个参数是缓冲区大小。手写版本用input.charAt(pos)配合input.length()天然没有缓冲区溢出的问题，但如果你改写成逐字节读取的 C 语言版本，就得自己处理缓冲区边界。工具生成的版本内部自带缓冲区管理，但你传入的 Reader 需要正确包装。总之，输出格式统一、行列号起点统一、Token 类型命名统一，这三个"统一"能避免后面一半以上的联调问题。

5. 词法分析器避坑指南：五个让实验翻车的常见问题与排查方法

代码写完了不代表能跑通，跑通了也不代表所有输入都正确。我自己在辅导编译原理实验时，见过最多的翻车现场集中在下面五类问题，每一条都是真实踩过的，按"现象 → 原因 → 解决"写清楚。

5.1 非法字符没报错反而被吞：错误行号永远差一列

现象：输入里有一个@，词法分析器没吐 ERROR Token，而是把它当成空白或者某个界符的一部分，后面所有报错位置全部向右偏一列。

原因：在skipWhitespace()或者单字符分派时，把未知字符误放进了白名单；或者column的递增发生在当前位置判断之后，导致报错时列号还停留在上一个字符。

解决：给所有pos++的路径配上对应的column++，唯一让column重置为 1 的地方只有换行处理。你可以统一封装一个advance()方法，内部同时更新pos和column，这样就不会漏。排查时打印每个 Token 的line和column，对着源码数一下，很快就能找出是哪一步少加了一次。

5.2 ifile 被拆成 if 和 ile：关键字比对的顺序问题

现象：输入ifile，输出两个 Token：KEYWORD if和IDENTIFIER ile。但语义上ifile应该是一个单独的标识符。

原因：这是最典型的"贪心失配"。有的实现在读取标识符时，每读一个字母就去匹配关键字表，结果读到if就急着吐 Token，完全没有遵循最长匹配原则。

解决：先按标识符的正规式读完整个词，再查关键字集合决定种别。我的代码里readIdentifier就是先StringBuilder收完所有字母数字，再KEYWORDS.contains(word)判断。这样ifile必然整个进标识符分支，不会被拆开。这也是手写方案比工具方案更不容易踩的顺序坑。

5.3 块注释里的换行丢了：从注释后面开始行号全错

现象：源码里有跨多行的/* ... */注释，注释之后的每个 Token 的line都比实际小，而且错误的行数恰好等于注释跨过的行数减一。

原因：skipBlockComment()里只判断了注释结束符*/，没有对\n做line++和column = 1。注释里的换行被当成普通字符跳过，行号计数器自然落后。

解决：在跳过注释内容的循环里，遇到\n就更新line并重置column，代码见第 3.3 节的skipBlockComment。这块逻辑也可以在 C 语言版本里用一个共同的readChar()函数统一管理，避免注释、字符串、普通代码三处各写一套。

5.4 Windows 换行符崩了：CRLF 让最后一个 Token 消失

现象：代码文件在 Windows 上保存，\r\n结尾。词法分析器把\r报成非法字符，或者文件末尾的行数据莫名少一行。

原因：很多教材代码只处理\n，没处理\r。\r单独出现在字符流中时，被当成了未定义的普通字符，进入错误分支。

解决：在skipWhitespace()里把\r\n作为一组换行处理，见 3.2 节代码。如果是 C 语言逐字节读入，处理方式是在读到\r时再读一个\n确认，不要直接把\r丢给错误分支。另外，文件末尾不带换行符时，pos >= input.length()的判断要能正常返回 EOF Token，不要把最后一个有效 Token 吞掉。

提示：如果你把源码从 Windows 拷到 Linux 上跑，\r会变成^M字符，这也是很多"我本机好好的，服务器上就崩"的元凶。

5.5 缓冲区截断长标识符：Token 内容莫名少一截

现象：一个 20 个字符的标识符，输出时只有前 10 个字符，而且后面紧跟的 Token 奇妙地错乱了。

原因：用固定大小缓冲区（比如char buf[1024]）逐段读入源码时，没有处理跨缓冲区的 Token。标识符前半段在缓冲区末尾，后半段在下一个缓冲区开头，如果当前缓冲区的边界被当成词法边界，Token 就被截断了。

解决：Java 版直接用String或Reader读完整份源码，绕开这个坑。C 语言版需要在缓冲区填满时，把未读完的字符搬到缓冲区头部继续拼接。这个细节在课程设计里注意事项里经常被提到，但真正动手时特别容易被忽略，因为它只在长标识符或长字符串时暴露。

6. 把 Token 流接给语法分析之前：测试用例、状态表与调试习惯

词法分析器写完后，先别急着写语法分析器。用几分钟做一下验证，能省下后面以小时计的调试时间。

6.1 五个测试用例覆盖全部 Token 分支：用断言而不是肉眼

我建议准备一段固定源码，里面包含五种场景：普通标识符和关键字混合、整数和小数、注释跳过、字符串读入、非法字符报错。用 JUnit 或简单的断言跑一遍：

List<Token> tokens = lexAll(src); assertEquals(TokenType.IDENTIFIER, tokens.get(0).type); assertEquals("sum", tokens.get(0).text); assertEquals(TokenType.INTEGER, tokens.get(1).type); assertEquals("0", tokens.get(1).text); assertEquals(TokenType.REAL, tokens.get(5).type); assertEquals("10.5", tokens.get(5).text); assertEquals(6, tokens.get(5).line); assertEquals(14, tokens.get(5).column);

肉眼扫终端输出很容易放过一些边界问题，断言则把预期的行列号固定下来。我习惯把这份测试源码存成一个文件，以后每次改词法分析器代码，跑一遍老测试，确保没有把以前能过的 Case 弄坏。

6.2 种别码常量与 Token 流接口：给语法分析器留好位置

语法分析器需要的不是Token对象，而是种别码和单词文本。建议在TokenType枚举上直接定义int code()方法，让KEYWORD.code()返回 1，IDENTIFIER.code()返回 2，这样语法分析器里写switch (currentToken.type.code())就行，不用到处用魔法字符串。接口也要统一成Token nextToken()+Token peekToken()。课程设计里往往要求 LL(1) 解析，peekToken至少要看一个 lookahead，词法分析器这一层预留好接口，语法分析器才能写得干净。

6.3 调试习惯：打开 TRACE，对着状态转换图逐 Token 核

加一个private boolean debug开关，在nextToken()每个返回语句前打印token内容，是我最常用的调试手段。关键不是打印本身，而是把输出和手绘的状态转换图对照。如果某条路径输出的 Token 不符合预期，先在图上找对应的状态，再回代码里查那个状态对应的if分支，通常几分钟就能定位。

我每次写完词法分析器，都会把这份测试样例和 TRACE 开关留下来，后面写语法分析器时继续用。这个习惯救过我很多次，希望帮到你。

本文还有配套的精品资源，点击获取