简介北邮编译原理课程词法分析器实验的完整源码包面向正在学习编译原理的本科生以编译器前端的关键环节为切入点帮助理解扫描器如何将源代码字符流拆分为记号并识别关键字、标识符、常量、运算符等词素。包内共4个文件包含C实现的主程序与头文件以及配套说明文档和测试用例文本压缩包整体仅10KB结构紧凑适合直接阅读核心代码。源码覆盖词法规则定义、输入流预处理、分词算法、符号栈管理与错误恢复等关键模块采用手写分析器的方式呈现可直观对照基于正则表达式或EBNF描述的词法规则以及从规则到状态转换图的实现路径。目前已有1000人学习下载学生在完成课程实验时可将其作为独立实现的参考既能借鉴词素分类、符号表组织与错误定位思路也能据此排查自身代码在边界字符与特殊输入上的处理漏洞为后续语法分析与语义分析打下基础。1. 编译原理实验一词法分析器到底在考什么编译原理课的第一关永远是词法分析器。北邮这门课的实验一要求把一份源程序拆成一条条Token流很多人的编译原理实验分数就折在这个看似不起眼的环节上。这份在学生圈子里传了很多届的“词法分析器.zip”装的是实验一整套可用的实现从源码到测试用例再到实验报告都有。我把它拆过一遍第一感觉是代码确实能跑但直接照抄去验收大概率被助教问住。真正的价值在于看懂它的识别主循环怎么设计、符号表怎么查、错误怎么恢复——这些才是编译原理实验和普通编程作业的分水岭。适合正在赶实验一的在校生也适合想用手写词法分析器入门编译器的自学者。2. 设计与选型状态转移图先于代码2.1 手工识别还是正则引擎实验约束下的唯一选择词法分析器有两条技术路线一是用Lex/Flex这类生成器写规则让工具自动生成DFA二是纯手写状态机。北邮实验一通常明确要求手写识别过程不允许用生成器目的是让你亲手实现一遍DFA的状态转移过程。所以这份资源的核心不是正则表达式而是一张状态转移图。状态转移图长什么样以标识符为例起始状态S0遇到字母进入S1在S1里继续遇到字母或数字保持在S1遇到其他字符从S1退出识别出一个标识符。数字、运算符、界符各有一组子图。把整张图并起来就是以状态为行、以输入字符类别为列的二维表。我一般会在草稿纸上先把这张表画全再动键盘画不全就写代码后期一定改到吐。状态 / 字符类别letterdigit - * /空白换行其他S0 起始S1S2S3S0S0S5ERRS1 标识符S1S1ENDENDENDENDENDS2 整数ERRS2ENDENDENDENDENDS3 运算符ENDENDENDENDENDENDENDS5 字符串S5S5S5S5ERRENDS5这张表就是后面所有代码的依据。如果你在资源里看到大段switch-case或if-else那只是表的另一种写法如果能直接改成二维数组驱动说明作者的表画得很规整。注意表里的END不是退出程序而是“当前词素到此结束回到S0重新开始”。2.2 标识符和关键字先识别再查表顺序不能反初学最容易犯的错是在识别过程中判断关键字边读边比对。正确做法是先按标识符规则把一整串字母数字读完形成词素lexeme再拿这个词素去查关键字表命中了就是关键字没命中才算用户标识符。顺序反了会出大问题比如输入intx会被拆成int和x两个Token。我先定义了完整的Token类型枚举这是整个分析器的地基public enum TokenType { KEYWORD, IDENTIFIER, INTEGER, FLOAT, CHAR_CONST, STRING_CONST, OPERATOR, DELIMITER, ERROR, EOF }关键字表在这份资源的Java版本里我习惯用集合加枚举来判断import java.util.HashSet; import java.util.Set; public class KeywordTable { private static final SetString KEYWORDS new HashSet(); static { // 实验里定义的C语言子集关键字就这十几个 String[] words { int, char, float, double, if, else, while, for, return, void, struct, sizeof }; for (String w : words) { KEYWORDS.add(w); } } public static boolean isKeyword(String lexeme) { return KEYWORDS.contains(lexeme); } }这段逻辑很直白静态块一次性加载关键字集合isKeyword做O(1)查表。要点是集合必须初始化一次千万别写成每次识别都new一个Set否则性能直接废掉。如果你的实验语言是C子集把关键字列表换成对应保留字即可。另外注意大小写敏感像Int这种不能算关键字这是最容易和助教争论的细节。2.3 表驱动识别主循环把IF-Else收敛成状态跳转有了状态表主循环就剩两件事读一个字符查类别按状态跳转。这是整个实验最核心的一层后面的符号表、错误处理都挂在这层之下。private static final int S0 0, S1 1, S2 2, S3 3, S5 5; private static final int CHAR_LETTER 0, CHAR_DIGIT 1; private static final int CHAR_OP 2, CHAR_SPACE 3, CHAR_QUOTE 4; // 状态转移表行是当前状态列是字符类别-1表示词素结束 private static int[][] transTable { // letter digit op space quote /* S0 */ { S1, S2, S3, S0, S5 }, /* S1 */ { S1, S1, -1, -1, -1 }, /* S2 */ { -1, S2, -1, -1, -1 }, /* S3 */ { -1, -1, -1, -1, -1 }, /* S5 */ { S5, S5, S5, S5, -1 }, };状态值-1代表当前字符不属于该状态的合法转移触发-1说明词素结束需要回退处理。写代码时有个常用的收敛手法把-1统一导向一个“结束并回退”的出口不要在每种状态里单独写emit逻辑。这样后面加注释状态、字符串状态只是往表里加行加列主循环基本不动。从状态图到代码的映射还有一个容易漏掉的点运算符本身要区分单字符和双字符比如和是两个Token。你在表驱动方案里处理这个要么在S3状态里多读一个字符做二次判断要么在主循环结束后单独处理。我建议把双字符运算符的判断做成一个独立的lookahead函数和状态表分离否则状态数量会膨胀得很厉害。提示表驱动不是银弹。实验一用表驱动很顺手但到了实验三语法分析阶段表驱动的可读性会明显下降。你在资源里看到状态表也好、switch-case也好关键是理解“状态—输入类别—转移”这个三元关系而不是拘泥于某种写法。3. 核心实现Token识别与缓冲区的配合3.1 Token结构与类型枚举Token是词法阶段的输出单元至少包含三样东西类型、词素文本、行号。很多实验报告要求输出四元组就是把行号、类型、词素、符号表ID一起打印。先看Token类public class Token { public TokenType type; public String lexeme; public int line; public int symbolId; // 符号表项下标-1表示没有对应项 public Token(TokenType type, String lexeme, int line, int symbolId) { this.type type; this.lexeme lexeme; this.line line; this.symbolId symbolId; } Override public String toString() { return line type lexeme symbolId; } }这里的symbolId留给符号表用词法阶段对标识符和常量都要填上。toString格式尽量和实验要求对齐有的班要求输出到文本文件交给实验二去读格式中途不要随便改。我经常在验收前统一跑一遍样例逐行比对输出文件避免助教脚本判分时报格式不符。3.2 缓冲区整文件读入与双指针滑动词法分析器的输入缓冲区有两派做法一种是流式读字符每次读一个配合一个字符的推回另一种是整文件读入内存用两个指针在内存里滑动。我倾向后者理由很简单实验一手写状态机整文件读入能减少I/O干扰还方便排查越界。import java.nio.file.Files; import java.nio.file.Paths; public class Lexer { private String source; private int pos 0; // 当前扫描指针 private int start 0; // 当前词素起始指针 private int line 1; // 行号计数器 public Lexer(String path) throws Exception { source new String(Files.readAllBytes(Paths.get(path))); } private char peek() { if (pos source.length()) return \0; return source.charAt(pos); } private char advance() { char c peek(); if (c \n) line; pos; return c; } }peek是看一眼当前字符但不移动指针advance是真正的消费。start标记当前词素的开头一个词素结束时用source.substring(start, pos)取文本。要点是换行计数必须放在advance里行号统计才不会漏。很多实现把行号处理散落在主循环外面结果多行注释里一出现换行行号就崩了。注意如果实验环境是Windows读文件时用UTF-8无BOM编码。有BOM的话文件开头会多一个不可见字符\uFEFF它会被当成非法字符第一条Token就报错所有后续行号集体偏移一位。3.3 数字与字面量识别的边界控制数字识别不止是“读到连续数字”。北邮实验里的数字通常包含整数、小数和科学计数法。指数部分的正负号、小数点后至少一位数字都是边界条件。核心逻辑public Token scanNumber() { start pos; boolean isFloat false; while (Character.isDigit(peek())) { advance(); } if (peek() .) { isFloat true; advance(); if (!Character.isDigit(peek())) { return emitError(小数点后缺少数字); } while (Character.isDigit(peek())) { advance(); } } if (peek() E || peek() e) { advance(); if (peek() || peek() -) { advance(); } if (!Character.isDigit(peek())) { return emitError(指数部分缺少数字); } while (Character.isDigit(peek())) { advance(); } isFloat true; } String text source.substring(start, pos); if (isFloat) { return new Token(TokenType.FLOAT, text, line, -1); } return new Token(TokenType.INTEGER, text, insertConstant(int, text), -1); }三个坑集中在这里第一.后必须跟数字形如1.要报错第二指数符号后的正负号只能出现一次且必须后跟数字第三如果实验要求整数是32位你需要在拼出词素后检查取值范围超出就报整数溢出。我一般把溢出检查抽成单独方法不埋在这段识别代码里否则数字解析和错误判定耦合在一起Debug时很难定位。字符串识别是另一个重头。双引号里出现换行通常非法转义序列要能跳过双引号而不结束字符串。基本结构是public Token scanString() { start pos; advance(); // 跳过左引号 while (peek() ! peek() ! \0) { if (peek() \\) { advance(); // 跳过反斜杠 } advance(); } if (peek() \0) { return emitError(字符串未闭合); } advance(); // 跳过右引号 String text source.substring(start, pos); return new Token(TokenType.STRING_CONST, text, line, -1); }这里的关键是转义处理遇到反斜杠时多消费一个字符不管它是什么。这样不会触发循环结束条件真正落单的才会。3.4 识别主循环的调度逻辑有了scanNumber、scanString、scanIdentifier这些识别函数主循环需要决定什么时候调用谁。这就是词法分析器的“调度中枢”public Token nextToken() { skipWhitespaceAndComments(); if (pos source.length()) { return new Token(TokenType.EOF, EOF, line, -1); } char c peek(); if (Character.isLetter(c)) { return scanIdentifier(); } if (Character.isDigit(c)) { return scanNumber(); } if (c ) { return scanString(); } // 运算符和界符走统一的scanOperator return scanOperator(); }skipWhitespaceAndComments把空格、Tab、换行和注释全部吃掉让nextToken每次被调用时都停在真正需要识别的位置。这个分层调度值得学习每个识别函数只管一个词法类别互不干扰。资源里如果代码全堆在一个方法里你就要警惕那通常是后续实验扩展时最难改的写法。4. 符号表与错误恢复词法层对后续实验的影响4.1 符号表的结构选择词法分析阶段的符号表主要存两类东西用户标识符和常量。标识符又分变量名和函数名常量分整数、浮点、字符串三类。实验报告一般会要求画出符号表结构最省事的是按序数组加线性查找但性能真的不行。我在这份资源的实现基础上更推荐哈希表import java.util.HashMap; import java.util.Map; public class SymbolTable { private MapString, Symbol table new HashMap(); private int nextIndex 0; public Symbol lookup(String name) { return table.get(name); } public int insert(String name, String kind, String attr) { if (table.containsKey(name)) { return table.get(name).index; } Symbol s new Symbol(nextIndex, name, kind, attr); table.put(name, s); nextIndex; return s.index; } }insert先查重已存在就直接返回旧下标不存在才分配新下标。这个细节直接决定同一变量出现五次符号表里占几行。助教很可能拿这个卡你重复出现的标识符符号表里应该只有一项。kind字段填“变量”“常量”“函数”等类别attr字段填类型或常数值。验收时把这些完整打出来比只给一个ID更容易拿分。4.2 常量表与字符串驻留标识符和常量虽然都进符号表但处理方式有区别。标识符靠名字判重常量则要按值判重。同一个整数233出现三次理论上只占一个表项。我在实现里会单独维护一个常量表public class ConstantTable { private MapString, Integer intTable new HashMap(); private MapString, Integer floatTable new HashMap(); private int nextIndex 0; public int insertInt(String value) { return intTable.computeIfAbsent(value, v - nextIndex); } }用computeIfAbsent可以一行完成查重和插入。这里有个设计取舍字符串常量要不要驻留驻留的意思是内容相同的字符串只保存一份返回同一个符号表下标。实验一阶段很多同学不做字符串驻留导致同样一段字符串每次出现都占新表项。等实验二做语义分析时字符串比较变成下标比较你会感谢当初多写这几行。4.3 错误恢复策略词法错误主要有三类非法字符、非法数字组合、字符串未闭合。错误处理的目标不是中断程序而是记录错误后继续扫完整个文件这样一次运行能暴露全部问题。常见策略是生成ERROR Token并跳过坏词素public ListString scanErrors new ArrayList(); public Token emitError(String message) { String bad String.valueOf(source.charAt(pos)); scanErrors.add(Line line : lex error: message - bad); pos; return new Token(TokenType.ERROR, bad, line, -1); }注意这里跳过的是单个字符。遇到“123abc”不能跳一个字符了事需要把整个词素消费完再报错否则abc会被当成标识符错误提示变得莫名其妙。我习惯在scanNumber里检测到数字后跟字母时直接把后续字母一起消费完当作一个整体错误Token。错误信息列表单独存别和Token流混在一起。到了实验二错误Token会参与语法分析但错误信息只打印到控制台或单独文件避免污染Token流。4.4 与实验二语法分析的接口约定词法分析做完输出的是Token流但实验二的语法分析器需要的是结构化数据。把Token存成内存数组实验二可以直接遍历如果做成每次调用nextToken()的拉取模式实验二就要同步调整。这份资源里的实现是前者一次扫描全生成Token列表挂在Lexer对象上。输出到文件的话我建议固定成这种格式行号 类型名 词素 符号表ID 1 KEYWORD int -1 1 IDENTIFIER a 0 2 INTEGER 233 1每行用空格分隔末尾不要多余空格。助教脚本多是用文本比对多余空格和Tab都是扣分点。我吃过一次亏在Windows上写完文件换行符是\r\n拿到Linux验收环境一比对每行都多出个\r整个实验一判零分。从那以后我产出文件一律用UTF-8无BOM加LF换行输出前强制检查一遍格式不在细节上赌运气。5. 词法分析器避坑指南五处高频翻车现场5.1 关键字被拆成两半现象输入“intValue3”输出里同时出现了“int”关键字和“Value”标识符原本应该是一个完整的标识符被拆碎了。原因识别循环里每读一个字符就检查累积串是否为关键字一旦匹配立即输出并重置状态。这是把“查表”错误地安排进了“识别”过程导致完整词素被拦腰截断。解决记住识别和查表的边界。先完整读出一个词素再交给KeywordTable判断。词素“intValue”在完整形式下查不到关键字自然就是标识符。我改这个bug花了整整一个下午最后发现只是把isKeyword调用从循环里挪到了循环外。5.2 多行注释吞掉行号现象注释跨三行之后后续所有报错行号比实际少了三行调试时对着源码怎么都对不上。原因处理“/”和“”进入注释状态后直接用下标循环读字符直到“/”绕过了advance方法里的换行计数逻辑。解决把换行计数统一收敛到advance这一个方法里所有字符消费都必须走它。注释状态遇到\n也要调用advance而不是用source.charAt直接越位。这样行号统计只有一个入口天然不可能不一致。5.3 数字后跟字母的碎片报错现象输入“123abc”报错只说“非法字符1”然后把abc当作标识符继续处理错误信息完全看不出问题出在哪。原因scanNumber遇到数字后的字母时只把当前数字跳掉没有消费整个词素的剩余部分。解决在数字识别退出逻辑里检测字母如果数字结束后紧跟字母把其余字母一并消费完生成一个完整词素粒度的错误Token。错误信息写成“非法数字词素 123abc”比碎成三条错误可读性强太多排查时一眼就能定位。5.4 字符串转义提前终止现象输入“say hi”字符串在反斜杠后面的那个双引号处就结束了后面的内容全乱套。原因字符串扫描循环里只判断到“”就收尾没有处理反斜杠转义的情况转义的引号被误认成字符串结束符。解决在字符串循环里加一个判断读到反斜杠时跳过下一个字符不管下一个是什么。这样不会触发结束条件真正落单的才会。输入里出现裸换行也要单独报错不能让它静默截断字符串。5.5 文件末尾最后一个Token丢失现象样例最后一行是“return 0;”跑完输出里找不到最后的界符“;”甚至最后一个常量也经常消失。原因主循环以pos source.length()为终止条件循环退出前最后一次词素结束动作没有执行残余字符被丢弃。解决主循环后单独处理EOF状态在读到\0时强制走一遍正常的词素结束流程而不是直接break。还有一个连带习惯每次写完都用一个末尾没有换行的文件测试专门验证文件最后一个字符的处理。6. 验证与进阶用一组用例把分析器钉死词法分析器写完靠“感觉能跑”验收肯定不够。我平时把测试用例分成三类正向样例、边界样例、错误样例各自放单独目录。正向样例是一段正常的类C代码边界样例是空文件、全是空白、只有注释、超长标识符、大整数、科学计数法的各种变体错误样例就挑上面五处翻车对应的输入。测试目录样例内容预期结果positiveint a1; return a2;无错误TokenToken流完整boundary空文件 / 只有注释只输出EOF行号正确error123abc / 未闭合字符串errors数量大于0不崩溃批量跑测试可以用下面这个主类public class TestRunner { public static void main(String[] args) throws Exception { String[] dirs {positive, boundary, error}; for (String d : dirs) { File folder new File(d); if (!folder.exists()) continue; for (File f : folder.listFiles()) { Lexer lexer new Lexer(f.getPath()); ListToken tokens lexer.scan(); System.out.printf(%s: %d tokens, %d errors%n, f.getName(), tokens.size(), lexer.scanErrors.size()); } } } }重点看errors数量而不只是Token数量错误样例里errors必须大于0正向样例里errors必须等于0边界样例里不允许出现数组越界和空指针。三组都过了实验一验收基本稳了。进阶玩法是把Token流接到一个简单的递归下降语法分析器上哪怕只解析赋值语句和if语句也能反过来验证词法输出是否完整。我最后一次帮学弟复盘实验一最大的教训是词法分析器八成的bug藏在边界字符上多一个\0、少一个\n结果天差地别。从那以后我每次写完都强制把所有样例完整跑一遍再提实验报告不跑测试就敢提交的事再也没干过。希望这份词法分析器资源加上你对照文章做的排查能在实验一上帮你少熬两个夜。本文还有配套的精品资源点击获取