编译原理词法分析器实验：从状态机设计到代码实现，避开那些隐蔽的坑

简介：东南大学编译原理课程词法分析器实验报告，面向计算机相关专业学生、教师及编译原理初学者，用于理解词法分析的整体设计流程与自动机状态转换过程。报告基于C++语言，采用NFA转换为DFA再由DFA0处理错误输入的思路，对关键词、界符、运算符、标识符、数字及空白符等词法单元完成识别，并能在发现错误后跳过错误局部继续显示。实验内容涵盖词法分析设计、自动机描述、核心数据结构描述与核心算法描述四部分，详细给出了token序列、关键词表、界符表、运算符表、id表和数字表等数据结构的使用方式，并以addToken函数为例说明核心算法的实现过程，便于读者对照实验要求自行设计或改进词法分析器代码。压缩包内共有1个docx文件，大小约415KB，方便直接查阅、打印或按章节对照学习。目前已有761人浏览或学习，适合完成课程实验、复习编译原理知识点或准备相关考试的学生参考。

1. 东南大学编译原理词法分析器实验：先想清楚再动手，比写代码更重要

词法分析器是编译原理课程里第一个真正让理论落地的实验，很多同学拿着《编译原理》教材（哪怕是清华大学出版社第三版）翻到第二章，正则表达式、NFA、DFA 的推导看懂了，打开 IDE 却不知道第一行代码写什么。这份实验报告对应的核心任务并不复杂：读入一段 C 语言风格的源代码文本，把它拆成一个个 token——关键字、标识符、数字、运算符、界符，同时识别出词法错误。整个过程不涉及语法树、不做语义分析，但它决定了编译器后续所有阶段的输入质量。

我在带新人做这个实验时最常说的话是：不要在状态转换图上花太多时间画图，先把手动构造词法分析器的三种方案选型想清楚——直接手写状态机、基于正则表达式构造 NFA 再转 DFA、或者用 flex 自动生成。课程要求通常偏向手写，因为要考察你是否真的理解确定有限自动机的本质。这篇文章按我实际做实验的路径来写：从词法规则设计到核心代码实现，再到五个容易让实验报告翻车的隐蔽坑，最后给你一个验证词法分析器正确性的通用方法。

2. 词法规则设计：从正则表达式到状态转换图，这一步决定你写多少行代码

2.1 token 分类表：先把“合法单词”定义清楚，否则后面全是返工

动手写代码之前，必须做一件看起来枯燥但价值最高的事：把实验要求支持的 token 种类逐条列成表格。东南大学这份实验的常见要求是覆盖 C 语言子集，我在拿到实验说明后的第一步永远是确认一个边界问题——关键字表里到底包含哪几个词？有的实验要求保留 int、float、if、else、while、return 等 32 个标准关键字，有的只要求支持 8 个基础关键字。这个差异直接决定哈希表大小和查找逻辑，我见过太多人因为关键字表没对齐实验要求，报告写完了才发现识别结果比助教给的参考输出少了两种 token 类型。

我一般把 token 分为五类：关键字、标识符、常数（整数/小数）、运算符（含复合运算符）、界符（分号、逗号、括号等）。每类分配一个枚举值，方便后续报告里统计和展示。这里要注意一个容易被忽略的类别——注释，很多实验要求词法分析器跳过//和/* */注释，这需要在状态转换图里单独设计两个状态，否则注释里的“关键字”会被误识别成 token 输出。

定义分类表的同时，就要同步确定一个关键决策：关键字和标识符是分开识别还是统一识别后再查表？我推荐后者——先按标识符的规则读出一个完整单词，再去关键字表里查，命中则输出关键字 token，否则输出标识符 token。这个方案的优点是状态转换图少两个状态，缺点是每读一个标识符都要做一次哈希查找。对于课程实验的代码量，这点性能开销完全可以忽略，但代码结构清晰很多。

2.2 状态转换图的手工构造：从 NFA 到 DFA 再到最小化，实验报告的核心章节

这一步是把正则表达式机化成可执行逻辑的关键。教材里会先讲 NFA 如何用 ε 闭包合并状态，再讲子集构造法转 DFA，最后讲最小化。我实际写代码时并不会真的在程序里实现这三步转换——课程实验通常不要求你写一个通用的正则到 DFA 编译器，而是要求你针对定义好的词法规则，手工设计出确定有限自动机，再把状态转换表或转换逻辑直接写进代码。

以标识符的识别为例，它的正则表达式是[A-Za-z_][A-Za-z0-9_]*，对应的 DFA 只有两个核心状态：初始状态读入首字符后进入“标识符中”状态，此后只要读入的是字母、数字或下划线就留在该状态，读到其他字符则结束当前 token。整个过程最多两个状态，但实验报告里值得展开的地方在于：你是如何让这个自动机与关键字表协同工作的。我的做法是在“标识符中”状态的结束分支里，把完整单词切出来，再走查表逻辑。

运算符的识别才是状态图真正变复杂的地方。以<为例，读入<后不能立刻确定是小于号还是小于等于号，需要再读一个字符做超前判断。如果是=，输出<=；否则退一个字符，输出<。这就是编译器教材里说的超前搜索（lookahead），实现时我一般用put_back()函数把多读的字符退回输入流，而不是自己维护一个缓冲区。这个机制在实现++、--、&&、||等复合运算符时都会用到，状态转换图上会形成一条“读入第一个字符→读入第二个字符→判断分支”的路径。

整份实验报告里，状态转换图这部分值得写透：把数字识别（整数→浮点数的状态迁移要做）、运算符识别（单字符→双字符的迁移要做）、注释跳过（单独的状态环路）三张图画清楚，代码实现反而可以放在报告附录里，因为助教评分时最看重的是你有没有真正理解 DFA 的构造逻辑，而不是贴一大段没有注释的 C 代码。

3. 核心实现：手动构造一个能跑的词法分析器，附完整代码与参数说明

3.1 数据结构与 token 定义：枚举、结构体、缓冲区缺一不可

我习惯用 C 语言写这个实验，因为指针操作直观，而且 C 本身就是词法分析器最常处理的输入语言，写起来没有 JDK 和 C++ 标准库的额外包装感。不过用 Java 或 Python 也能完成，只是状态判断的写法和缓冲区管理差异比较大。下面这段代码是 token 定义和数据结构部分，直接复制可用，但你要根据自己的实验要求增删枚举项。

typedef enum { TOKEN_KEYWORD, // 关键字 TOKEN_IDENTIFIER, // 标识符 TOKEN_INTEGER, // 整型常量 TOKEN_FLOAT, // 浮点常量 TOKEN_OPERATOR, // 运算符 TOKEN_DELIMITER, // 界符 TOKEN_ERROR, // 词法错误 TOKEN_EOF // 文件结束 } TokenType; typedef struct { TokenType type; char lexeme[64]; // 单词原文 int line; // 所在行号，错误报告要用 int column; // 所在列号 union { int intVal; float floatVal; char opChar; // 运算符可用字符串，但单个字符更省空间 } value; } Token;

我在设计Token结构体时把line和column字段放进去，很多初版代码没有这两个字段，等到调试语法错误时发现定位不了输入出错位置，只能回头改结构体——改本身不复杂，但要在所有构造函数和输出函数里同步加上字段。这里有个参数值得注意：lexeme[64]的长度按实验要求来，通常标识符长度在 32 字节以内就够了，但如果你输入的测试用例里有超长变量名，就要把数组加长到 128 或改成动态分配，否则会缓冲区溢出。

Token 的输出格式各校要求不同，我做得比较多的是把type用数字编号输出、lexeme原样输出、line和column用括号括起来。这样助教比对结果时一眼能看出差异在哪一行。

3.2 状态转换驱动函数：最容易被写得一团乱麻的 200 行

核心的识别逻辑我放在一个get_token()函数里，它的职责是：从输入流中读取字符，根据当前状态决定下一步动作，最终返回一个 Token。这个函数最忌讳写成 IF 嵌套地狱——先判断是不是字母，再判断是不是数字，再判断是不是符号，嵌套十层之后代码没法维护。

我的做法是维护一个state变量，每个状态对应一段清晰的 switch-case 逻辑。状态编号通过宏定义管理，这样代码可读性比直接写数字高得多。

#define STATE_START 0 // 初始状态 #define STATE_IDENTIFIER 1 // 正在读标识符 #define STATE_INTEGER 2 // 正在读整数 #define STATE_FLOAT_1 3 // 已读小数点，等待小数部分 #define STATE_FLOAT_2 4 // 正在读小数部分 #define STATE_OPERATOR 5 // 正读运算符（待确认是否复合） #define STATE_COMMENT_1 6 // 正读 // 注释 #define STATE_COMMENT_2 7 // 正读 /* 注释（可能是 * 待确认结束） #define STATE_DONE 8 // 完成一个词法单元 Token get_token(FILE *fp) { int state = STATE_START; char ch; char buffer[128]; // 累积当前 token 的字符 int buf_len = 0; int start_line = current_line; // 在进入 START 时记录行号 while (state != STATE_DONE) { ch = getc(fp); if (ch == '\n') current_line++; // 行号递增属于词法阶段的工作 switch (state) { case STATE_START: if (isalpha(ch) || ch == '_') { state = STATE_IDENTIFIER; buffer[buf_len++] = ch; } else if (isdigit(ch)) { state = STATE_INTEGER; buffer[buf_len++] = ch; } else { /* 处理运算符和界符，见下文 */ } break; case STATE_IDENTIFIER: if (isalnum(ch) || ch == '_') { buffer[buf_len++] = ch; } else { ungetc(ch, fp); // 把多读的字符退回输入流 state = STATE_DONE; } break; case STATE_INTEGER: if (isdigit(ch)) { buffer[buf_len++] = ch; } else if (ch == '.') { state = STATE_FLOAT_1; buffer[buf_len++] = ch; } else { ungetc(ch, fp); state = STATE_DONE; } break; case STATE_FLOAT_1: if (isdigit(ch)) { state = STATE_FLOAT_2; buffer[buf_len++] = ch; } else { // 小数点后没数字，按整数加小数点错误处理 ungetc(ch, fp); state = STATE_DONE; // 返回时标记错误类型 token.type = TOKEN_ERROR; } break; } } buffer[buf_len] = '\0'; /* 收尾：查关键字表、构造 Token、返回 */ }

ungetc是 C 标准库提供的字符回退函数，这里的作用就是实现超前搜索。它在逻辑上把“已读但未消费”的字符放回流中，下一次getc还能读回来。我在STATE_IDENTIFIER的结束分支里使用它，是因为标识符的终止符（比如空格、运算符）不属于当前 token，必须退回给下一次调用。这里有一个关键点：ungetc只保证至少能回退一个字符，所以不要连续多次调用它。如果需要回退多个字符，就得自己维护一个预读缓冲区。

这个驱动函数的核心参数是状态转移条件，它们是词法规则的直接机化。值得注意的是STATE_FLOAT_1分支处理了一个很容易漏掉的错误：输入1.时，小数点后有终止符但没有数字，这不符合浮点数规则。我在这个状态里直接把 token 标记为TOKEN_ERROR。还有一种做法是把它识别为整数 1 加一个小数点界符，两种方案各有取舍，关键是实验报告里要写清楚你的自动机对这个边界输入的处理策略。

3.3 关键字表和运算符表：两个静态表解决 90% 的查表逻辑

识别完标识符之后，剩下的工作就是查表。C 语言里用数组加循环就能做，如果想体现一点编译原理课程学到的知识，可以用哈希表。但课程实验对时间要求不严，线性查找的性能完全够，所以我更推荐直接用一个 const 数组静态初始化，代码简单且不容易出错。

const char *keywords[] = { "auto", "break", "case", "char", "const", "continue", "default", "do", "double", "else", "enum", "extern", "float", "for", "goto", "if", "int", "long", "register", "return", "short", "signed", "sizeof", "static", "struct", "switch", "typedef", "union", "unsigned", "void", "volatile", "while" }; const char *operators[] = { "+", "-", "*", "/", "%", "=", "<", ">", "!", "++", "--", "==", "!=", "<=", ">=", "&&", "||", "+=", "-=", "*=", "/=", "%=", "&", "|" }; int lookup_keyword(const char *word) { int n = sizeof(keywords) / sizeof(keywords[0]); for (int i = 0; i < n; i++) { if (strcmp(keywords[i], word) == 0) return i; } return -1; }

这里有一个很容易出错的设计决策：运算符表里的优先级。++必须排在+前面，==排到=前面，否则你在查表用strcmp做匹配时，输入++会先被匹配成两个+。我在实验报告里把这个点作为“最长匹配原则”的代码体现来写，因为助教喜欢看到这部分：教材里说“识别最长的可能词法单元”，代码里就是查表顺序控制实现的。

lookup_keyword返回 -1 表示未命中，调用处再决定输出TOKEN_IDENTIFIER还是TOKEN_KEYWORD。有的教科书建议先把关键字 dict 哈希化，这样查表 O(1) 而不是 O(n)，但不建议在实验报告里过度优化。如果测试用例量不大，线性查表完全够，还能避免哈希冲突相关的额外讨论——把篇幅留给状态图和错误处理更明智。

4. 那种让实验报告翻车的隐蔽坑：5 个实测踩过的词法分析器问题

4.1 现象：ifx被识别成关键字 if 和标识符 x

这是初学者最容易犯的错误，因为识别逻辑写成了“逐个字符比较关键字表”，在读入i和f后直接匹配到关键字if，然后结束 token，留下一个x在输入流里。原因在于没有遵循“先识别完整标识符、再查关键字表”的流程，而是把关键字匹配嵌入了状态转移过程。

解决方式在前面已经说过：状态机上只有STATE_IDENTIFIER一个状态处理字母和下划线开头的单词，结束之后整体去查关键字表。如果查不到，整个字符串作为一个标识符输出。这个改动只需要调整代码结构，不需要改状态转换图本身。这是词法分析器实验里最常被助教测试的用例之一，务必保证intx、floaty、for_loop这类输入不会被错误分词。

4.2 现象：<=被识别成<和=两个 token

如果在状态转移图里没有为复合运算符设置等待状态，每读一个运算符字符就直接输出，那么<=会被拆成两个 token、==同理。这违反了词法分析的核心原则之一——最长匹配。原因就是你在读到<时没有向后再探一个字符，直接决定输出。

解决方式是给所有可能成双的运算符设置一个“待确认”状态，读入第一个字符后记录到 buffer，再读下一个字符和预期的配对字符比对，配对成功则输出双字符运算符，否则用ungetc回退并输出单字符运算符。代码上就是STATE_OPERATOR分支的处理逻辑，测试时专门构造一个包含<、<=、==、=、++、+的输入行，逐一检查输出 token 序列。

4.3 现象：遇到无法识别的字符直接exit(1)，后续所有 token 全部丢失

有些初版程序在default分支里直接终止程序，这导致输入文件里只要有一个中文字符或特殊符号，整个词法分析过程就报废了。原因在于把“词法错误”当成“致命错误”处理了。词法分析器的正确行为是报告错误的位置和内容，然后继续向后扫描，让编译器有机会在同一个编译批次里发现更多错误。

解决方式是在STATE_START的default分支里构造一个TOKEN_ERRORtoken，记录当前字符、行号和列号，打印错误信息后回到STATE_START继续读取下一个字符。这样设计还有个好处：测试驱动时能一次跑完全部用例，而不是跑一个崩一个。我在实验报告里会专门写一条“错误恢复策略”说明，明确列出跳过非法字符和终止程序两种策略的取舍，这也是一个加分项。

4.4 现象：整数后面紧接字母（如123abc）被识别成整数123加标识符abc

这个现象是对“最长匹配”的过度理解。有的同学为了让123abc不变成两个合法 token，在数字状态里遇到字母直接报错，反而误伤了3dfoot（科学计数法或自定义字面量）。实际上123abc在 C 语言里的确是非法词法单元，因为数字结尾再接字母不是合法的整数或浮点数格式，所以确实应该报错；但如果输入是1.5e3，字母 e 是合法的指数符号——这是最容易混淆的边界。

解决方式：在STATE_INTEGER状态里遇到字母时不要立刻回退，先判断当前状态支持的合法后继字符。整数后面直接跟字母，在我这个实验的规则里定义为错误；浮点数尾数后跟字母 e 或 E 时，则进入指数状态继续读。这不是状态图复杂化的问题，而是你做词法规则汇总表时是否把指数格式写了进去。我在实验要求里凡是提到支持浮点数，就默认要支持指数格式，但如果你们学校只要求支持十进制小数，则可以不理会。

4.5 现象：/*注释嵌套导致注释提前结束

多层注释嵌套在 C 语言标准里并不支持，但测试样例里偶尔会出现/* /* */这种情况，状态机会在第一个*/处结束注释，留下*/两个字符被当作运算符处理。严格来说这符合 C 语言规范，但很多同学在报告里把“不支持嵌套注释”写成“程序bug”，这就属于自曝其短了。

解决方式：如果你想做得体面一点，在注释状态里维护一个comment_depth计数器，当读入/*时加一，遇到*/时减一，归零时才真正退出注释状态。这只是一种扩展实现，要在报告里注明“支持嵌套注释”相对于 C 语言标准是有意增强，否则助教可能认为你没掌握注释跳过的基本逻辑。就我的经验看，课程测试极少考嵌套注释，所以优先级可以放低，但报告里要明确写出注释识别到文件结尾还未结束时的错误处理——这种“文件非正常结束”场景才是必测点。

5. 进阶验证技巧：构造一个词法测试矩阵，让报告的“测试与分析”不再空洞

实验报告的最后一章通常是测试与分析，但很多同学只会贴一段输入和对应的输出截图。你在做完基础实验后，可以把测试部分升级成一个系统性的验证方案——词法测试矩阵。这个矩阵的核心思想是：把词法规则按维度分组，每组构造独立的测试用例，确保每个状态分支和错误分支都被覆盖到。

我一般按五个分组构造测试文件：合法标识符组（含下划线开头、字母开头、数字结尾）、数字常量组（整数、小数、指数、非法的 1e、1. 和 .5）、运算符边界组（<与<=、=与==、&与&&混排）、注释边界组（//结尾无换行、/*未闭合、行内注释后跟代码）、错误恢复组（多个非法字符连续出现、空文件、只有空白符）。每组输出都要和预期对比，你要有一份“预期输出”可以比对，不然你怎么知道当前代码改对了没有。

验证的实操方法是用一行 bash 命令做自动化回归测试。

./lexer test_cases/operators.c > outputs/operators.out diff outputs/operators.out expected/operators.exp

diff退出码为 0 表示输出完全一致，非零则说明有差异。每次修改词法分析器代码后重跑一遍整个测试矩阵，任何状态转移改动导致的功能回退都能被秒级发现。这比在 IDE 里肉眼比对截图高效得多，而且把测试过程和结果写进实验报告里很有说服力。我第一次带新人做这个实验的时候，他把测试文件写完后发现运算符组有 3 处输出不一致，定位到问题是ungetc回退后缓冲区状态没清空——这就是为什么要自动化回归，手动看输出很难注意到状态残留类 bug。

如果你有余力，还可以做一个更进阶的验证：写一个简单的 Lex 程序用 flex 自动生成词法分析器，在同样的测试用例上跑一遍，把你手写实现的结果和 flex 生成的结果做比较。flex 的输出作为“标准答案”参考，这个方法的合理性在于 flex 本身是教科书级别的词法分析器生成器，它的分词行为就是教材规则的忠实实现。两相对比，你不仅能发现手写实现的偏差，还能在报告中写一段“与自动生成器的一致性分析”——从我的经验看，这部分通常是区别高分报告和普通报告的加分点。

最后聊聊我从这个实验里学到的操练习惯：每改一次状态转移逻辑，就重跑一次全量测试矩阵；每个测试用例的设计都要能对应到一条词法规则或一个状态分支。实验报告写“测试与分析”章节时，把测试矩阵列出来、每一组的预期行为和实际输出对齐、错误用例对应的修复策略写清楚，这样就没人觉得你的报告是流水账。词法分析器虽小，但它教会我最重要的一课是：编译器的每一个阶段都要可验证，模块之间的边界必须清晰。这个习惯后来做任何工程任务我都保留着，希望帮到你。

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