1. 词法分析到底在做什么先别急着打开编辑器写代码我们先把词法分析这件事本身聊透。很多人第一次在头歌平台上看到“第1关词法分析”这个任务时会觉得莫名其妙——不就是把一串字符串拆成一个个单词吗这有什么可做的确实如果只是“拆单词”这事太简单了但词法分析真正的核心不在“拆”而在“分类”和“状态管理”。1.1 一句话说清词法分析的位置编译原理的整个流程是源代码 - 词法分析 - 语法分析 - 语义分析 - 中间代码生成 - 优化 - 目标代码生成。词法分析是第一步它的任务就是把一段源代码字符串按照你预先定义好的规则切成一个一个的Token记号。Token 是什么你可以把它理解成源代码的“最小有意义单位”每个 Token 包含两样东西类型和值。比如int a 10;这行代码经过词法分析后大概会变成这样Token 类型Token 值关键字int标识符a运算符数字常量10界符;语法分析器要的就是这一串带类型标记的 Token 流它根本不在乎源代码里写的是a10还是a 10因为空白字符在词法分析阶段已经被丢掉了。这就是词法分析的定位把“文本层面”的字符序列转换成“语言层面”的记号序列。1.2 从字符流到 Token 流的转换细节要实现这个转换核心机制叫做“状态转换图”和“状态机”。你想想看当你读到一个字符i时它可能是关键字if的开头也可能是标识符index的开头你没法在当前字符上立刻决定它的最终类型必须继续往下看。这种“边走边看”的过程就是状态机的工作方式。以识别标识符为例它的规则通常是以字母或下划线开头后续可以是字母、数字或下划线。对应到状态转换图就是这样的状态0初始状态如果读入字母或下划线进入状态1。状态1接受状态如果继续读入字母、数字或下划线仍然留在状态1如果读入其他字符则识别结束当前已积累的字符串就是一个标识符同时把这个“其他字符”重新放回输入流。注意这个“重新放回”操作这在词法分析里是非常重要的细节。比如输入abc123xyz当你读完abc123后遇到了不属于标识符的字符集所以abc123这个标识符已经完整但本身是下一个 Token 的开头不能丢掉。处理方法是把这个字符“回退”一个位置或者用一个缓冲区来管理。1.3 为什么这关是编译原理第一道门槛在头歌平台的课程设计里词法分析被放在第1关不是没有道理的。它强迫你建立三个认知第一任何看似简单的字符串处理背后都需要状态机来保证逻辑严谨第二一个字符的归属可能要到后面才能确定这就是“超前搜索”的雏形第三真正写代码时你会发现边界条件比你想象的要多得多——空字符、换行、行尾、非法字符每一步都要想清楚。很多同学在这儿栽的跟头是觉得逻辑太简单上来就写循环判断结果测试用例一跑就崩。所以磨刀不误砍柴工先花点时间把 Token 类型和状态转换图设计好后面实现起来会顺畅很多。2. 开工前先想清楚Token 种类与设计方案写词法分析器之前有一件看起来枯燥但特别重要的事把你需要识别的 Token 种类完整地列出来并且给每种 Token 确定一个内部编号。这就像做菜之前先备菜菜没备好炒的时候一定手忙脚乱。2.1 你需要识别哪些 Token拿头歌第1关的常见要求来说一般需要识别这几类关键字if、else、while、return、int、void等。注意关键字是语言预留的不能用作变量名。标识符用来表示变量名、函数名的字符串。数字常量通常要求识别整数有些关卡会要求识别小数。运算符、-、*、/、、、、、、、!等。界符;、,、(、)、{、}、[、]等。特殊符号字符串常量、字符常量看题目要求。在代码里最方便的方式是用一个常量类来管理 Token 类型比如public class TokenType { public static final int KEYWORD 1; public static final int IDENTIFIER 2; public static final int INTEGER 3; public static final int OPERATOR 4; public static final int DELIMITER 5; public static final int ERROR -1; }有的同学喜欢用枚举enum也可以看个人习惯。平台判题时无非两种方式一种是把 Token 类型作为整数输出另一种是输出类型名称字符串。无论哪种内部管理好编号都不会出错。2.2 关键字和标识符的“合并识别”套路一个最常见的坑是单独给每个关键字画一个状态图试图在状态机里精确匹配if、else、while。这种思路也能跑但会非常累而且容易和标识符的识别产生冲突。更聪明的做法是统一处理把关键字也当作标识符来识别等识别出一个完整的字符串后再查关键字表如果在表里就归类为关键字否则就是标识符。打个比方这就好比你收到一个快递先看包装盒上的名字如果这个人在“重点联系人名单”里就重点对待否则就当普通联系人处理。所以在设计状态转换图时只需要一张“标识符状态图”就够了关键是识别完成后做一次查表操作。这样实现简单逻辑也清晰。对于存储关键字表用HashSet就好查询效率高。SetString keywords new HashSet(Arrays.asList( if, else, while, return, int, void ));2.3 状态转换图怎么画、怎么看、怎么用“源程序的词法分析的状态转换图怎么画”是很多人搜索的问题这里我详细讲一下。状态转换图无非三种元素状态节点画成圆圈、转换边画成带箭头的线边上标着触发字符或字符集合、接受状态画成双圈。以数字识别为例规则是数字由若干个数字字符组成。它的状态图非常简单状态0遇到数字字符进入状态1状态1遇到数字字符继续留在状态1状态1是接受状态。但如果你要支持十进制小数就得多画一个状态。比如3.14状态0遇到数字进入状态1。状态1遇到数字继续留在状态1遇到小数点.进入状态2。状态2遇到数字进入状态3。状态3遇到数字继续留在状态3状态1和状态3都是接受状态。这里有个细节状态2刚刚读完小数点、还没读到小数部分不是接受状态因为你不允许一个数字以.结尾。这一点在做自动机时非常容易漏。画状态转换图的意义不在于“交作业画图好看”而在于它逼你把每一种输入情况都考虑完整。画完之后你再照着图写代码基本就是“翻译”的过程了。3. 核心实现一个不算复杂但能跑的 Java 词法分析器这一节我们直接上代码。我会用一个相对完整、可运行的 Java 版词法分析器做例子代码结构尽量保持清晰方便你在头歌平台上改编成自己的实现。3.1 数据结构与类设计先定义一个Token类用来装识别结果public class Token { public int type; // 类型编号 public String value; // 原始字符串属性值 public Token(int type, String value) { this.type type; this.value value; } Override public String toString() { return formatToken(type, value); } }主类Lexer的核心成员变量需要这几个一个字符数组或者String、一个当前扫描位置的指针pos、一个记录行号用的变量如果要支持报错定位的话。核心方法就是一个nextToken()每调用一次就返回下一个 Token。有人可能会问为什么不直接一次把整个 Token 列表返回两种方式都行。一次性返回列表看起来更简单但流式返回更贴近真实编译器的做法因为语法分析器是一个一个从词法分析器那儿索取 Token 的。头歌实验如果有多次调用的需求写nextToken()会更好扩展。3.2 主循环逐字符扫描与状态迁移实现的主循环思路是每次调用nextToken()时先跳过所有空白字符然后根据当前字符的类型进入不同的处理分支。代码骨架如下public Token nextToken() throws Exception { // 跳过空白字符 while (pos src.length() Character.isWhitespace(src.charAt(pos))) { pos; } if (pos src.length()) { return new Token(TokenType.END, EOF); } char ch src.charAt(pos); if (Character.isLetter(ch) || ch _) { return parseIdentifierOrKeyword(); } if (Character.isDigit(ch)) { return parseNumber(); } // 运算符和界符 return parseOperatorOrDelimiter(); }这里每个 parse 方法对应一个状态转换图的子图。以parseIdentifierOrKeyword为例private Token parseIdentifierOrKeyword() { int start pos; while (pos src.length()) { char ch src.charAt(pos); if (Character.isLetterOrDigit(ch) || ch _) { pos; } else { break; } } String word src.substring(start, pos); if (keywords.contains(word)) { return new Token(TokenType.KEYWORD, word); } return new Token(TokenType.IDENTIFIER, word); }你仔细对比一下这就是前面那个“标识符状态图”的直接翻译从状态0进入状态1只要当前字符属于合法字符集合就继续否则停下来查表判断最终类型。3.3 数字、运算符的识别细节数字识别如果只考虑整数逻辑也很直接。但如果考虑多一种情况比如“数字后面紧跟字母”那得注意报错。比如输入123abc很多实验要求报词法错误而不是分别识别成123和abc。原因是大多数语言的词法规则里数字后面直接跟字母是非法 token。private Token parseNumber() throws Exception { int start pos; while (pos src.length() Character.isDigit(src.charAt(pos))) { pos; } // 如果数字后面紧跟字母说明输入不合法 if (pos src.length() Character.isLetter(src.charAt(pos))) { throw new Exception(词法错误第 pos 个字符处数字后不能紧跟字母); } String num src.substring(start, pos); return new Token(TokenType.INTEGER, num); }运算符和界符识别里最需要小心的是“最长匹配”原则。比如输入你不能把它认成和两个 Token而要优先匹配成这个运算符。实现手段就是先看当前位置的两个字符是否组成一个双字符运算符如果是就用双字符如果不是再退回单字符。private Token parseOperatorOrDelimiter() throws Exception { char ch src.charAt(pos); // 双字符运算符优先尝试 if (pos 1 src.length()) { String twoChar src.substring(pos, pos 2); if (twoChar.equals() || twoChar.equals() || twoChar.equals() || twoChar.equals(!)) { pos 2; return new Token(TokenType.OPERATOR, twoChar); } } switch (ch) { case : case -: case *: case /: case : case : case : pos; return new Token(TokenType.OPERATOR, String.valueOf(ch)); case ;: case ,: case (: case ): case {: case }: case [: case ]: pos; return new Token(TokenType.DELIMITER, String.valueOf(ch)); default: throw new Exception(词法错误无法识别的字符 ch ); } }这个写法在平台实验里足够应付绝大多数情况了。不过要提醒一下“/”和注释的冲突问题有些语言的注释是//和/* */如果实验要求识别注释就不能简单地把/当运算符返回得额外判断下一个字符。这属于扩展内容但做个有准备的学员总不是坏事。3.4 错误处理与边界情况错误处理是很多同学交上去被扣分的地方。我见过最多的失败测试用例不是识别不了正常代码而是在非法输入上“表现不当”。比如输入一个或者#你的程序应该怎么办是直接崩溃还是输出一个错误提示还是悄悄跳过不同实验有不同的判题规则有的要求输出“ERROR”有的要求输出“词法错误”。你需要先看题目要求。但无论是哪种程序都不应该直接抛异常退出更不应该死循环。最稳妥的做法是遇到非法字符时记录错误信息然后跳过该字符继续扫描或者立即结束并返回错误 Token具体看题目怎么要求。边界情况还有几种一是输入为空字符串应该直接返回结束标记二是输入只有空白字符三是最后一个 Token 的右边界处理比如int a扫描完a后指针已经指向末尾循环条件要处理好避免漏掉最后一个 Token 或者索引越界。4. 实操验证与第1关的应对策略光把代码写出来还不够你还得能在头歌平台上通过判题。这一节我聊聊怎么自测以及平台上常见的几个坑。4.1 测试用例怎么写从简单到刁钻我建议写代码前先准备一组测试用例按难度递增排列。不要一上来就测复杂的先保证最简单的情况跑通空输入什么字符都没有应该返回 EOF。单关键字if。单标识符abc。带数字的表达式a 10 b;。双字符运算符if (a 10) return b;。非法字符a b。关键字与标识符冲突int ifx 1;这里ifx是标识符而不是关键字。尤其是第 7 个用例特别能检验你的“先识别完整字符串再查关键字表”逻辑对不对。如果实现方式是逐个字符匹配关键字很容易把ifx也误判成if加x。4.2 头歌平台判题常见坑头歌这类在线实验平台判题方式通常是黑盒测试只比对输出结果不看你代码长什么样。所以有几个细节特别重要第一输出格式必须严格一致。如果题目要求输出(KEYWORD, if)这种格式你多打一个空格都不行。建议先看看题目给出的样例输出对照着写toString()方法。有的平台要求用空格分隔类型和值有的要求用逗号有的要求用中括号务必逐字符匹配。第二注意测试用例可能包含多个源文件或者多行输入。也就是说你的nextToken()方法需要循环调用直到返回结束标记为止。我见过有同学代码只能跑一行遇到换行就出错多半是没在循环里正确处理换行符。换行符属于空白字符应该在跳过的范围里。第三有些平台要求你从标准输入读入源代码而不是把源代码硬编码在程序里。如果题目这么要求你就要注意别漏掉读取输入的部分。用Scanner逐行读入并拼接成一个完整字符串是简单的做法。4.3 从第1关延伸到后续语法分析最后说一个容易被忽略的角度词法分析这个模块你做得越好后面的语法分析越省力。我在做实验时的一个经验是Token 类型划分得越细语法分析时就越容易判断if后面该不该跟(while的条件怎么写。Token 类型如果混在一起比如把(和{都叫“界符”到语法分析时你怎么区分“表达式括号”和“语句块括号”所以除非题目明确要求不然我建议在内部实现里也把它们区分开哪怕输出到外部时统一成一个类型内部标识拆分清楚对自己调试也方便。如果把词法分析器写成了可复用的模块那后面的语法分析、语义分析实验就可以直接拿来用相当于把地基打牢了。很多人在第3关、第4关回头看发现 bug 出在词法分析没做好——比如标识符被错误切断或者运算符最长匹配没做导致语法树解析错位。现在多花十分钟把边界处理好后面能省几小时的排查时间。5. 常见问题与排查技巧实录这一节我把实操里高频踩过的坑统一写出来有不少是看别人代码才悟到的也有不少是自己调了半天才发现的。5.1 典型 Bug 速查表症状可能原因解决办法标识符被截断成两段状态图里没有让标识符“吸收”数字和下划线检查 while 循环里的字符集用isLetterOrDigit(ch) || ch _ifx被识别成关键字没有先收完整字符串再查表统一走标识符解析最后查关键字表被识别成和缺少最长匹配逻辑先判断双字符运算符再退回单字符数字后紧跟字母没报错没检查数字串后续字符数字解析结束后判断下一个字符是否字母程序在最后一个 Token 后崩溃循环里索引越界或者结束标记没写好每次取字符前判断pos len返回 EOF 标记结束输出了多余的空格/空行空白字符处理逻辑不完整或者 toString 多加字符检查跳空白逻辑和输出拼接无法识别!运算符判断运算符时漏掉了!把!放进双字符运算符的清单里5.2 调试时的小技巧打日志、打边界调试词法分析器最痛苦的地方在于你光看输出结果往往不知道某个 Token 是从哪一行哪一列开始的。所以我建议你在Token类里额外增加line和column两个字段不输出仅调试用。跑测试时打印出来可以迅速定位问题是出在第几行第几列。另外一个非常实用的技巧是“暂停观察”。在nextToken()的每一轮返回前打印当前pos指针的位置和刚识别的 Token 值System.out.println(当前指针: pos , 识别到: token);这样你就能清楚地看到指针的移动轨迹。很多 bug 的本质是pos多移了一位或者少移了一位通过打印指针位置三分钟之内就能定位。还有一个容易被忽略的坑如果你在运算符识别里用src.charAt(pos 1)来预读下一个字符一定要先判断pos 1是否越界不然最后两个字符处容易抛异常。类似的所有涉及pos 1或pos 2的地方都要先判断边界。最后再分享一个体会我见过很多同学把词法分析写得特别“炫”又是自动机生成器又是正则引擎结果实验平台一跑反而因为复杂度过高出了各种诡异问题。实验场景下最朴素的手写状态机反而最稳代码短、逻辑直白、容易调试。编译器业界在工具链里用 Flex、Lex 这样的生成器是因为面对的是几百种语言规则你做一个实验性的词法分析器手写完全够用。别为了炫技而炫技能跑通判题才是硬道理。