简介这份压缩包提供了一份编译原理课程中词法分析器的C实现面向正在学习编译原理、需要完成相关实验或深入理解词法分析整体流程的高校学生。程序支持启动后输入测试程序名自动对源码进行词法分析并以单词二元式序列输出结果同时针对SAMPLE字符集之外的非法字符、字符常数缺少右单引号、注释缺少结尾界符*/等典型错误能够准确指出错误性质和出现位置。压缩包内含1个.cpp源文件大小约2KB代码量不大但覆盖了词法分析的核心逻辑便于逐行研读和在此基础上扩展。目前已有4264人学习下载适合作为词法分析实验的参考模板帮助读者理解关键字与标识符识别、状态转换、错误处理机制以及二元式输出格式设计等关键环节。1. 编译原理词法分析器为什么是课程设计里唯一能拿满分的模块编译原理词法分析器看着只是把源码切成 Token好像没什么技术含量实际上整条编译链路里报错行号准不准、关键字串不串味、注释会不会吞掉代码全在这一步定型。很多用 Java 写编译原理实验的同学都有这种体会语法分析器写了三周没崩词法分析器的缓冲区先崩了。这篇文章把我做词法分析器用的 Token 设计、状态转换图、手写代码和排错经验串一遍给正在做编译原理实验的读者一条能照抄的落地路径也适合想回看底层状态机的从业者。2. 先定 Token 种别再写代码状态转换图与正规式的对应关系词法分析器做的事一句话读字符流吐出 Token 流。Token 流就是一组{种别, 单词, 行号, 列号}记录。这一步不关心if后面有没有括号、声明合不合法它只负责把sum切成一个标识符把10.5切成一个实数然后遇到这种字符时给你一个明确的词法错误。听起来简单但真正动手时第一个问题往往是我到底要识别多少种东西我一般的做法是先别打开编辑器拿一张纸把这门语言里所有合法的词列出来。列出来的过程就是设计 Token 种别表的过程。2.1 Token 种别表种别码定多少位正规式怎么写Token 种别表的常见格式是种别、种别码、正规式、示例。种别码在课程设计里通常就是一个整数常量后续语法分析器靠这个整数判断当前读到的是什么东西。下面是我常用的一张最小表覆盖大多数编译原理实验要求种别种别码正规式示例实例关键字1if | else | while | for | return ...if标识符2[a-zA-Z_][a-zA-Z0-9_]*sum整数3[0-9]1024实数4[0-9]\.[0-9]10.5字符串5...hello运算符6 | | | - | * | / ...界符7, ; ( ) [ ] { }{错误--表格里最需要动脑子的是关键字到底算不算独立的种别。很多同学会把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 SetString 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不会被拆成ifx。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两条路径怎么选参数怎么给不少编译原理实验允许或者鼓励用工具生成词法分析器。工具派最常用的是 FlexC/C 生态和 JFlexJava 生态。工具的好处是正规式写得快几行就声明完所有规则但代价是你要接受一套额外的 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 对非法字符的恢复策略相对固定。维度手写状态机Flex/JFlex 工具代码量约 300 行 Java约 100 行规则文件状态控制完全可控自动生成 DFA错误定制灵活依赖动作代码行列号维护手动自动%line %column适合场景实验、学习、少量 Token生产环境、大量 Token这里有个容易被忽视的点用工具时正则规则命中的优先级取决于规则在文件中的顺序。比如关键字规则必须写在标识符规则前面否则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输出两个 TokenKEYWORD 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 或简单的断言跑一遍ListToken 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()返回 1IDENTIFIER.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 开关留下来后面写语法分析器时继续用。这个习惯救过我很多次希望帮到你。本文还有配套的精品资源点击获取