简介这份压缩包面向学习编译原理、准备课程实验或课程设计的学生与教师聚焦词法分析阶段的动手实现。它提供一套可完整运行的 Java 类C词法分析器源码并配有基于 SWING 的图形界面可在 MyEclipse 中导入调试帮助读者把有限状态自动机、词法规则定义、逐字符读取、token 流生成与错误处理等抽象概念落到代码层面。包内共 5 个文件均为 java 源文件压缩包约 5KB体量轻便便于直接阅读和二次修改源码含注释界面可直观呈现分词过程与结果。已有 526 人学习适合需要对照实现理解词法分析流程、完成编译原理实验或课程设计的读者参考。1. 词法分析的真相界面里那行彩色代码是状态机吐出来的 token 流很多人对编译原理的第一印象是界面右边那一栏五颜六色的 token 列表。左边贴进一段源文件点一下按钮右边刷出一排KEYWORD、IDENTIFIER、NUMBER还带着行列号看起来像个玩具版编辑器插件。真正决定这套东西能不能用的不是配色方案而是背后那台状态机它在同一遍扫描里同时干完切词、分类、定位、报错四件事而且必须一个字符都不多吃、一个字符都不落下。值得把这件事拆开看的原因很实在。词法分析是整个编译链路里唯一一处“输入是任意字节、输出必须是规整结构”的地方后面的语法分析、语义分析全都建立在它给出的 token 流之上。它错一位报错行号就偏一行界面高亮就串色学生调试时盯着源码找半天找不到问题血泪经验基本都出在这一层。下面从最长匹配原则讲到扫描主循环的代码再到界面层怎么和词法器划清边界最后落到几个真实踩过的坑。2. 最长匹配与状态机为什么ab必须被切成ab2.1 正则表达式能描述词法但直接拿正则引擎跑会出事教科书上一句话就带过了词法规则可以用正则表达式描述。这句话没错正则语言是上下文无关语言的子集任何 token 的形态都能写成一条正则。问题出在“多条正则怎么组合”上——单个正则能描述一个 token但它不负责决定“什么时候该用哪条”。假设规则表这么写if、int这类关键字一条条列出来标识符是[A-Za-z_][A-Za-z0-9_]*然后按顺序尝试匹配。输入ifx如果关键字规则排在前面第一轮就把if匹配走了剩下x变成一个新标识符。编译器认为你写了“关键字 if 加一个变量 x”可你明明只想声明一个叫ifx的变量。这类错误在语法分析阶段会表现成莫名其妙的“意外的标识符”排查起来极其反直觉。要修它就得引入两条不成文但所有实现都遵守的规则第一条是最长匹配也叫 maximal munch。在任何起点上取所有能匹配的规则里长度最长的那个。ifx上标识符规则能匹配 3 个字符关键字规则只能匹配 2 个标识符胜出。第二条是规则优先级。长度相同时按声明顺序定胜负。if这个位置上关键字规则和标识符规则都能匹配 2 个字符这时关键字优先于是if被判成关键字。这两条规则合起来才是完整的词法规范。手写扫描器的所有结构本质上都是在廉价地实现这两条。直接用正则引擎跑还有两个更现实的问题。一是回溯把几十条规则拼成一个巨大的交替式(kw1|kw2|...|ident|number|...)糟糕的引擎在长行上会反复回溯输入几千字符的源码就明显卡顿。二是错误定位正则引擎失败时只告诉你“从第 N 个字符开始不匹配”而你需要的是“第 3 行第 17 列有一个未闭合的字符串字面量”。这两个信息量级完全不同。2.2 手写扫描器的等价物一个带前瞻的 switch 状态机手写扫描器听起来土但它是把 DFA 摊平写进代码里。DFA 的“状态”在这份代码里不是变量而是“当前执行到哪个扫描函数”——进了scanNumber就等价于处在“数字态”进了scanString就等价于处在“字符串态”函数返回就等价于回到起始态。这样写出来的东西没有状态转移表但转移逻辑一条不少。真正需要显式维护的只有两样位置指针和前瞻能力。起始态下看第一个字符决定走哪条分支这就是一次 lookahead两个字符的运算符需要看两位那就是 lookahead(2)。理论上词法分析的 lookahead 只需要常数个字符实践中也很少超过 2所以整个扫描器可以做到严格 O(n)、零回溯——唯一一次“回滚”出现在数字后面跟e却不是指数的时候回滚距离也是常数。对照一下两种实现形态维度状态转移表 驱动器手写扫描函数状态在哪显式二维数组隐含在函数调用栈/代码位置加一条规则改表可能要重算 DFA加一个if分支或一个函数错误信息只能报“状态 X 下遇到字符 c”可以精确到“字符串未闭合”可读性表是黑匣子逻辑一眼看穿性能一次查表稳定分支预测友好通常更快教学项目和中小型语言实现几乎都选右边这列。不是因为左边不好而是因为左边把“为什么这么切”这个信息彻底藏进了表里调试时你只能看表看不到意图。2.3 Token 数据结构为什么 offset 不能省token 长什么样直接决定了上层能做什么。最偷懒的写法是只存(type, lexeme)两个字段能打印、能喂给语法分析器看起来够用。但只要涉及界面立刻不够。界面要高亮就得知道这个 token 在原文里的绝对偏移区间要报错就得知道行号和列号要做“点 token 跳转到源码位置”还得有偏移。所以一个够用的 token 至少是五个字段public final class Token { public final TokenType type; // 分类KEYWORD / IDENTIFIER / NUMBER / ... public final String lexeme; // 原文切片保留引号和转义界面高亮要用 public final int offset; // 在源字符串中的起始下标0-based public final int line; // 1-based给人看的 public final int column; // 1-based按字符计不是按显示宽度 public Token(TokenType type, String lexeme, int offset, int line, int column) { this.type type; this.lexeme lexeme; this.offset offset; this.line line; this.column column; } public int endOffset() { return offset lexeme.length(); // 仅当源文本已做换行规范化时成立 } }注意lexeme和“值”是两回事。字符串字面量a\nb的 lexeme 是带引号带反斜杠的 6 个字符它的语义值才是 3 个字符。扫描阶段只负责切出 lexeme解转义可以顺手做存一个value字段也可以留给后面的阶段。但高亮和定位必须用 lexeme因为界面上显示的是原文不是解转义之后的值。offset还有个隐性要求它必须和界面拿到的那个字符串是同一个字符串。如果界面在送进词法器之前做了什么预处理——去 BOM、把\r\n换成\n、trim 首尾空白——那么词法器返回的 offset 就和界面上的文本对不上了高亮会整体偏移。这是后面第 5 章要展开的坑之一。3. 扫描主循环字符缓冲区是怎么被一格格吃掉的3.1 peek / advance三个原语撑起整个词法器整个词法器只需要三个原子操作剩下所有扫描函数都是它们的组合public final class Lexer { private final String src; private int pos 0; private int line 1; private int col 1; private final ListToken tokens new ArrayList(); private final ListLexError errors new ArrayList(); public Lexer(String src) { this.src src; } private boolean isAtEnd() { return pos src.length(); } private char peek() { return isAtEnd() ? \0 : src.charAt(pos); } private char peek(int k) { int i pos k; return i src.length() ? \0 : src.charAt(i); } // 唯一推进指针的地方行列号在这里同步累加别处一律不许改 pos private char advance() { char c src.charAt(pos); if (c \n) { line; col 1; } else { col; } return c; } private void emit(TokenType t, int start, int startLine, int startCol) { tokens.add(new Token(t, src.substring(start, pos), start, startLine, startCol)); } }关键约束是pos只允许在advance()里加一line和col只允许跟着advance()变。把这三个变量锁死在一个函数里行列号就永远不会算错——这不是代码洁癖而是唯一能保证“报错位置永远和实际位置一致”的办法。我见过太多实现喜欢在扫描函数里直接pos 2跳过两个字符结果那一行的列号从此开始偏移报错全部偏一位排查时完全看不出规律。peek()在越界时返回\0这是个约定。好处是所有扫描函数写while (peek() ! !isAtEnd())时不会抛异常坏处是如果源文件里真的出现\0行为会有点微妙。教学过程里这个约定足够用工业级实现一般改用返回int并用-1表示结束。主循环本身非常短短到容易让人低估它的重要性public Result scan() { while (!isAtEnd()) { char c peek(); if (c || c \t || c \r || c \n) { advance(); continue; } if (c / peek(1) /) { skipLineComment(); continue; } if (c / peek(1) *) { skipBlockComment(); continue; } if (isDigit(c)) { scanNumber(); continue; } if (isIdentStart(c)) { scanIdentifier(); continue; } if (c ) { scanString(); continue; } scanOperatorOrDelimiter(); // 兜底分支同时也是错误处理入口 } tokens.add(new Token(TokenType.EOF, , pos, line, col)); return new Result(tokens, errors); }这个结构叫“分发器 子扫描器”。分发器只看第一个字符就决定去向子扫描器负责吃满整个 token 并emit。注意每次continue之后pos一定前进了至少一格这是循环能终止的硬保证。如果某个分支写错导致pos没动程序会立即死循环——这类 bug 在界面上表现为一点按钮就卡死非常典型。3.2 标识符与关键字为什么必须“先扫完再查表”这是最长匹配原则最直接的落地。正确做法只有一种先把整个标识符吃满再拿这个词去关键字表里查。private static final SetString KEYWORDS new HashSet(Arrays.asList( if, else, while, for, return, break, continue, int, float, double, char, void, const )); private void scanIdentifier() { int start pos, sl line, sc col; while (!isAtEnd() isIdentPart(peek())) advance(); String word src.substring(start, pos); // 查表在吃满之后保证 ifx 判成 IDENTIFIER 而不是 if x TokenType t KEYWORDS.contains(word) ? TokenType.KEYWORD : TokenType.IDENTIFIER; tokens.add(new Token(t, word, start, sl, sc)); } private boolean isIdentStart(char c) { return Character.isLetter(c) || c _; // 允许中文标识符看语言规范 } private boolean isIdentPart(char c) { return isIdentStart(c) || Character.isDigit(c); }反例值得写出来警醒一下。有人为了避免扫两遍写成“边吃边判”// 错误示范这是 prefix 匹配不是最长匹配 for (String kw : KEYWORDS) { if (src.startsWith(kw, pos)) { emit(TokenType.KEYWORD, ...); pos kw.length(); return; } }这段代码在if、int上完全正常测试用例全过一上线遇到ifx、integer、forEach就翻车。而且因为forEach这种写法在别的语言里很常见写测试的人很容易忽略。核心差异在于startsWith判断的是“从这里开始能不能匹配”词法分析要的是“从这里开始最长能匹配多少”。查表本身用哈希集合O(1)和标识符长度无关。有些实现用排序数组加二分或者干脆按首字母分桶性能差别在几十个关键字的规模下可以忽略但哈希表写法最短最不容易出错。3.3 数字与字符串字面量的边界到底在哪断数字扫描的坑集中在小数点上。1..5在支持区间语法的语言里表示从 1 到 5如果扫描数字时看到.就无脑吃下去会得到1.和.5两个畸形 token语法分析器直接懵。正确判据是小数点和后面的数字必须同时存在才归入当前 token。private void scanNumber() { int start pos, sl line, sc col; while (!isAtEnd() isDigit(peek())) advance(); // 只有 . 后紧跟数字时才吃小数点否则 1..5 的第一个点会留给上层 if (peek() . isDigit(peek(1))) { advance(); while (!isAtEnd() isDigit(peek())) advance(); } // 指数部分允许回滚1e 后面不是数字时e 其实是标识符的开头 if (peek() e || peek() E) { int savePos pos, saveLine line, saveCol col; advance(); if (peek() || peek() -) advance(); if (isDigit(peek())) { while (!isAtEnd() isDigit(peek())) advance(); } else { pos savePos; line saveLine; col saveCol; // 常数距离回滚安全 } } emit(TokenType.NUMBER, start, sl, sc); }这段回滚是整个扫描器里唯一的“退格”。它安全的前提是回滚距离固定、只涉及三个变量、且回滚前没有emit过任何东西。如果哪天要给数字加更多后缀比如1.0f、0x1Fu回滚逻辑就得跟着重新推一遍很容易漏。字符串扫描的坑在转义和未闭合上private void scanString() { int start pos, sl line, sc col; advance(); // 吃掉开引号 StringBuilder value new StringBuilder(); while (!isAtEnd() peek() ! ) { char c advance(); if (c \\) { if (isAtEnd()) break; char e advance(); switch (e) { case n: value.append(\n); break; case t: value.append(\t); break; case : value.append(); break; case \\: value.append(\\); break; default: value.append(e); break; // 未知转义按原样保留 } // 注意这里吃的是 n 这个普通字符不会触发换行计数 } else if (c \n) { // 字符串不允许跨行遇到真实换行就地判错不吞掉后续代码 errors.add(new LexError(sl, sc, 字符串字面量未闭合, start)); tokens.add(new Token(TokenType.ERROR, src.substring(start, pos), start, sl, sc)); return; } else { value.append(c); } } if (isAtEnd()) { errors.add(new LexError(sl, sc, 字符串字面量未闭合已到文件末尾, start)); tokens.add(new Token(TokenType.ERROR, src.substring(start, pos), start, sl, sc)); return; } advance(); // 吃掉闭引号 emit(TokenType.STRING, start, sl, sc); }两个细节值得单独点出来。第一转义序列里的\n是两个字符反斜杠和字母 n。advance()读到字母 n 不会触发换行计数所以行列号是对的如果实现里偷懒用src.substring直接判contains(\n)就会把转义和真实换行搞混。第二未闭合字符串必须在遇到换行时立刻退出而不是一路吃到文件末尾。后者的后果是整个文件剩下的内容都被当成一个字符串界面上从出错那行开始全部变成同一种颜色后面所有 token 消失学生看到这一幕会以为整套代码崩了。4. 界面层与词法器的边界为什么界面不该“顺手”做词法判断4.1 输出协议一个 Result 对象装下 token 和 error界面和词法器之间最好只有一次函数调用、一个返回值。词法器接一个String吐一个Result别的什么都不做不弹窗、不打日志、不碰界面组件。public final class Result { private final ListToken tokens; private final ListLexError errors; private final boolean success; public Result(ListToken tokens, ListLexError errors) { this.tokens Collections.unmodifiableList(tokens); this.errors Collections.unmodifiableList(errors); this.success errors.isEmpty(); } // getters... }这个约定带来三个直接好处。一是可测试不用启动界面就能对一个字符串断言 token 序列回归用例写起来非常轻。二是可复用同一份词法器既能接到桌面界面上也能接到命令行测试里还能在批量扫描时并发跑因为Lexer每次new一个没有共享可变状态。三是错误不中断errors是个列表而不是异常扫描器遇到非法字符时记录一条然后继续一次扫描能把整个文件的错误全报出来而不是报第一个就停。对界面来说这意味着用户改一处代码能看到所有问题不用改一个跑一次。错误恢复的具体做法就是“跳过一格继续扫”private void scanOperatorOrDelimiter() { int start pos, sl line, sc col; if (pos 1 src.length()) { String two src.substring(pos, pos 2); if (TWO_CHAR_OPS.contains(two)) { // ! || -- - - advance(); advance(); emit(TokenType.OPERATOR, start, sl, sc); return; } } char c peek(); if (ONE_CHAR_OPS.indexOf(c) 0) { advance(); emit(TokenType.OPERATOR, start, sl, sc); return; } if (DELIMITERS.indexOf(c) 0) { // ( ) { } [ ] ; , advance(); emit(TokenType.DELIMITER, start, sl, sc); return; } // 认不出的字符吃掉它、记一笔、继续保证一次扫描报全所有错误 advance(); errors.add(new LexError(sl, sc, 无法识别的字符 c , start)); tokens.add(new Token(TokenType.ERROR, String.valueOf(c), start, sl, sc)); }两个字符的运算符必须先于单字符判断这是最长匹配在运算符上的又一次体现。ab如果先命中单字符就会得到两个语法分析阶段才报错错误位置和真实原因已经隔了一层。这种“延迟暴露”是词法器最常见的隐性缺陷。4.2 语法高亮token 类型到样式的映射与偏移计算高亮本质上是一次区间染色把 token 的[offset, offset lexeme.length())映射到一种样式交给文本组件去应用。映射表通常就是一个EnumMapToken 类型样式说明KEYWORD粗体 蓝色关键字数量固定优先级最高IDENTIFIER默认前景色不染色也能看染色反而干扰NUMBER紫红色数字字面量STRING绿色含引号整体染色COMMENT灰色斜体必须染色否则容易被误读成代码OPERATOR / DELIMITER深灰弱化减少视觉噪音ERROR红色波浪下划线与错误列表联动private void highlight(Result result, StyledDocument doc) { // 先整体清空避免上一次的样式残留叠加成本次 doc.setCharacterAttributes(0, doc.getLength(), defaultStyle, true); for (Token t : result.getTokens()) { if (t.type TokenType.EOF) continue; int start t.offset; int len t.lexeme.length(); if (start len doc.getLength()) continue; // 防御文本已被并发修改 doc.setCharacterAttributes(start, len, styleOf(t.type), true); } }这里有两个必须遵守的纪律。第一先清空再加样式。文本组件的样式是叠加的如果只加不清用户改一次代码就多叠一层几次之后整片文本都变成红色。第二用 offset 加 lexeme 长度定位不要用两次indexOf反推。反推在重复 token比如一行里五个i上会稳定错位而且复杂度是 O(n²)。4.3 错误定位行列号必须在 advance 里累加报错信息里那个“第几行第几列”看起来是小事实际是学生调试时最依赖的东西。事后计算行号的写法通常是拿到 offset然后数前面有多少个\n// 反面教材每个错误都从头数一遍 int line 1; for (int i 0; i offset; i) if (src.charAt(i) \n) line;单个错误时看不出问题一个文件几十个错误时就是 O(n·m)十万字符的输入直接卡住界面。更麻烦的是列号还得再扫一遍找最后一个换行。正确做法已经在第 3 章的advance()里写死了扫描过程中顺手维护取用时 O(1)。还有两个和界面强相关的细节。一是换行规范化界面里的文本可能是\r\n而词法器按\n计数\r会被当成空白跳过行号没问题但 offset 和界面文档的 offset 会因为多出来的\r而错位。稳妥做法是在送入词法器之前统一把\r\n换成\n并且让界面显示同一份规范化后的文本。二是制表符宽度列号按字符算是准确的但用户眼里 Tab 占了 4 格报错箭头指过去会偏。这个问题在纯文本输出里无解在界面里则可以通过“用列号定位到行首偏移再让文本组件自己算像素位置”绕过去不要试图自己算显示宽度。5. 常见问题排查词法器“看起来对但实际错”的五种典型现象5.1 高亮整体偏移越往文件后面偏得越多现象打开一个几百行的源文件前面几十行高亮正常后面开始串色红色关键字染到了变量名上越往后越离谱。原因界面在送文本给词法器之前做了预处理去 BOM、trim、换行规范化但词法器返回的offset是基于处理后的字符串界面却拿它去索引原始文档。只要预处理改变了任何一个字符的长度后面所有 offset 全部平移。解决把“规范化”这一步固定成一个函数界面显示和送进词法器用的是同一个字符串对象或者干脆在Result里额外返回规范化后的文本让界面用它重建显示内容。别在两个地方各做一次规范化。5.2 一个未闭合的块注释把整个文件吞掉现象源码里写了/*忘了闭合点分析之后界面上从那一行开始全部变灰后面的 token 一个都没有错误列表里也是空的。原因skipBlockComment写成while (peek() ! * || peek(1) ! /) advance();在文件末尾peek()返回\0条件永远成立一路吃到 EOF 才退出循环而且退出后没有报错。这种“静默吞掉”比报错更危险因为用户以为代码没问题。解决循环条件里必须带!isAtEnd()退出后判断是不是因为*/才退出的不是就补一条“块注释未闭合”的错误并把从/*起点到 EOF 的内容整体标成一个 COMMENT token。用户在界面上看到最后一大片灰色加上错误列表里那一行立刻就知道问题在哪。5.31..5被切成1.和.5报错位置莫名其妙现象写区间语法for i in 1..5时报错说“意外的数字字面量 .5”位置在第 1 行第 15 列而用户觉得自己写的完全合理。原因数字扫描看到.就无条件吃下去紧接着又吃后面的数字1.成了一个 token剩下.5又成了另一个 token。解决按第 3 章的写法只有当.后面紧跟数字时才把它归入当前 token。同时给这一类输入建一条固定回归用例别指望以后每次改扫描器都记得这个边界。5.4 报错行号总是差一行或者第一行报成第 0 行现象错误提示说第 5 行有问题实际看是第 6 行或者第一行的错误显示成第 0 行第 0 列。原因两种都可能。一是line初始化为 0而给人看的行号必须从 1 开始。二是换行处理和 token 起点记录顺序错了——如果在advance()吃掉换行之后才去读line那么换行符后面那个 token 的行号是对的、换行符前面那个 token 却拿到了下一行的行号。解决line 1; col 1初始化每个扫描函数开头先int sl line, sc col;把起点存下来emit时传的是存下来的那份而不是当时的line。这个模式在第 3 章的每个扫描函数里都出现了不是巧合。5.5 打字时界面卡顿长文件尤其明显现象在输入框里每敲一个字符都重新全量扫描加重绘几百行的文件每敲一下卡半秒。原因把“文本变化”和“重新分析”直接绑在一起没有防抖也没有增量。全量重扫是 O(n)全量重绘所有样式也是 O(n)加起来每次按键都做一遍完整工作。解决文本变化后用 150 到 300 毫秒的防抖等用户停下来再扫扫描本身很快真正的开销在样式应用可以只重绘内容发生变化的行区间。再进一步可以按行缓存 token 结果只重扫被修改的行——但这一步复杂度上升明显教学项目做到防抖加区间重绘就足够流畅了。6. 设计取舍手写扫描器和生成器之间教学项目为什么该选手写到这里可以回答一个绕不开的问题既然有成熟的词法分析生成器为什么不直接用非要手写几百行扫描函数先把取舍摊开看。生成器的优势是规范和一致你写规则文件它构造 DFA自动保证最长匹配和优先级不会出现ifx被切错这种低级问题规则多了也不容易乱。代价是生成的代码基本不可读调试时你面对的是一张状态转移表出错只能反推。手写的优势正好反过来逻辑和意图一一对应加一条规则就是加一个if报错文案可以精确到“字符串未闭合”看一眼代码就知道为什么会这么切代价是每一条边界都得自己想清楚1..5、1e、ifx这些坑一个都躲不掉。维度手写扫描器生成器规则变更成本改几行分支改规则文件 重新生成错误信息质量可精确到语义未闭合、非法转义通常只到“状态 字符”边界处理全靠自己推容易漏由 DFA 保证一致可调试性断点能停在具体分支断点停在驱动器里看不出意图适合场景教学、中小语言、需要精细报错规则多且稳定、报错要求不高教学场景该选手写理由不是“手写更牛”而是因为词法分析的全部知识点都在边界上。最长匹配、优先级、回滚、错误恢复、行列号维护这些东西用生成器时全被工具接管了你得到的是一个能跑的黑匣子学不到任何东西。手写一遍你才会真正理解为什么关键字要最后查表、为什么未闭合字符串必须就地退出、为什么advance()要独占指针修改权。验证这件事的方法也不复杂不需要什么框架。准备一组“魔鬼输入”每次改动扫描器之后全跑一遍看 token 序列和错误列表是否符合预期// 一组覆盖边界的回归输入改动扫描器后必跑 String[] cases { ab, // 最长匹配a b不是 a b ifx, // 关键字前缀必须是 IDENTIFIER 1..5, // 小数点NUMBER DOTDOT NUMBER 1e, // 指数回滚NUMBER IDENTIFIER \abc, // 未闭合字符串必须立刻报错并停在该行 /* never closed, // 未闭合块注释必须报错而不是静默吞掉 int 变量 1;, // 中文标识符看语言规范是否允许 a\r\nb // 换行规范化行号必须是 1 和 2 };这组输入的价值在于它们每一个都对应上面某一节讲过的机制而不是随机凑出来的测试数据。跑通了说明最长匹配、前瞻、回滚、错误恢复、行列号维护这五件事同时成立跑不通报错会直接指向是哪一环出了问题。这份带界面的完整源文件价值也在这里它把扫描器、token 结构、结果协议、高亮映射、错误列表这几层放在同一份可运行的代码里注释标在每个容易踩坑的分支旁边。想验证某个机制改一行输入就能在界面上看到 token 流怎么变比对着规范文档想象要快得多。从那以后我每次写扫描器都强制先把那组魔鬼输入跑一遍再动界面。后悔药没处买——有一次偷懒跳过了1..5结果半天的调试全耗在一个本该五行代码解决的边界上。希望这份拆解和这份带注释的源码能帮你少走一遍那条弯路。本文还有配套的精品资源点击获取