简介湖南大学《编译原理》实验一资料包面向本校选课同学聚焦DFA有穷自动机相关实验的代码实现与报告撰写适用于需要提升实验评分、理解编译原理前端自动机知识点的学习者。压缩包共7个文件约764KB包含DFA_1.cpp源码、DFA_1.exe可执行程序、4个.dfa状态描述文件以及实验报告docx其中.dfa文件用于定义自动机状态转移规则cpp与exe可直接运行和查看算法效果docx则为完整实验报告参考。目前已有708人学习/下载口碑显示实验分较高可作为高分实验方案的参照。除了可运行的完整工程还搭配陈果老师课程推荐与避坑提示能帮助读者快速理解实验要求、自动机建模思路和报告组织方式。代码与报告仅作技术参考建议在理解基础上独立完成。 前阵子整理网盘又翻出当年那份“湖南大学 编译原理实验一.zip”。压缩包不大里面无非就是实验指导书、几个代码骨架和几组测试样例但每次看到它我都会想起被词法分析器支配的日子。这个实验几乎成了编译原理课程的“第一道分水岭”很多同学不是不会写代码而是不知道这份zip里到底想让你干什么结果对着屏幕空转了两三天。这篇博文我就以手头这份实验包为例把实验一的整体思路、核心原理、手写词法分析器的完整过程以及实验报告和答辩的常见坑一次说清楚。不管你是正在做这个实验、还是想提前预习编译原理都能直接照着抄作业。1. 拿到实验包后的整体思路与拆解1.1 实验一到底在考什么从词法分析到有限自动机先说结论编译原理实验一的核心目标是让你亲手实现一个词法分析器也就是编译器前端里的scanner。它的输入是一段源代码字符串输出是一串有意义的token词法单元比如关键字、标识符、常量、运算符、界符。这样做是因为编译器后续的语法分析、语义分析都不喜欢直接面对原始字符流太琐碎也太容易出错所以先把字符流“分词”成一个个语义上完整的单元后续工作才会清爽。这个实验背后的理论模型是有限自动机尤其是确定有限自动机DFA。课本上会先讲正则表达式再讲如何把正则表达式转换成NFA、DFA最后做最小化。但在课程实验里一般不会要求你把整个算法链路都写出来而是让你面对一个具体的小语言比如MiniC或自定义的简单表达式语言用某种方式实现识别。你只要能写出一个能正确切分token的程序并且能解释清楚状态转换过程实验就达标了。很多同学觉得难是因为一上来就掉进了代码细节里。实际上实验一考的是你“能不能把语言规则转化成代码逻辑”而不是纯粹的编程技巧。拿到zip包我做的第一件事不是打开main.c而是先看实验指导书里定义的那个语言到底有哪些token类型。这一步做好了后面几小时的效率远超蛮干。1.2 怎么读实验要求别急着写代码先理清token集合我见过太多人一解压就开始敲代码结果写了半天发现连“标识符能不能以数字开头”这种基本规则都没搞清楚最后反复改。正确顺序是把实验文档里的词法规则一条条列出来做成一张token表明确每个token的类别名、取值、对应的正则表达式。举个例子一个教学语言的token集合通常长这样token类别示例正则表达式简写关键字int, float, if, else对大小写敏感优先匹配标识符sum, count, _tmp[a-zA-Z_][a-zA-Z0-9_]*整型常量0, 123, 999[0-9]浮点常量3.14, 0.5[0-9].[0-9]赋值符 ; - * / ( )固定字符或定界符运算符, , 需要最长匹配列完这张表再对照实验指导书里给出的输入输出样例你会发现很多边界情况已经提前暴露了比如a1应该被切成a、、1而不是a、、、1又比如3.14是一个浮点常量不能被切成3、.、14。这些规则本质上都对应了DFA的状态转移条件理解了token集合就理解了实验要求。1.3 三个常见的“想当然”误区第一个误区是“关键字和标识符应该一起识别”。实际做法是先按标识符的规则识别出完整字符串再查关键字表如果在表里就是关键字否则才是标识符。第二个误区是“遇到不能识别的字符就直接报错结束”。一个合格的词法分析器要能定位错误位置并且尽量恢复继续扫描后面的token这样编译器的报错信息才能一次给全。第三个误区是“测试只要跑通样例就行”。实验包里的样例只是最基本的功能验证真正拉开差距的地方在于边界测试空输入、只有注释、字符、超长的标识符、1.这种不完整浮点数等等。把这些想清楚后面的代码才不会返工。2. 核心概念DFA、正则表达式与状态转换图2.1 用生活化例子理解DFA如果你觉得DFA太抽象可以把它想象成一台自动售货机。你投的每一枚硬币相当于一个输入字符机器内部的状态会随着输入的硬币种类变化而切换投了5元可能进入“余额5元”状态再投1元进入“余额6元”状态只有进入“可出货”状态时卖货动作才会发生。词法分析器也是同样的逻辑当前状态记录的是“我正在识别哪个token的哪个部分”当前字符决定了下一步跳到哪个状态。比如识别整数常量初始状态是start看到数字字符进入int_state在这个状态里如果继续看到数字留在原状态如果看到非数字字符且不是字母就说明整数token结束把读入的字符串返回出去。这个过程就是一张状态转换图你在代码里写if-else或switch本质上就是在手动模拟这张图。很多教材费大篇幅讲DFA和正则表达式的等价转换是因为它们能严格证明“什么样的语言能被词法分析器识别”。但在实验阶段你不需要每次都画一个像样的状态图再写代码但一定要有一种“字符流入、状态流转、token流出”的心智模型。有了这个模型写代码时就不会东拼西凑。2.2 三种实现路线手工编码、自动生成器、表驱动真正动手做词法分析器有三条常见路线我按适合程度排个序手工编码直接用if、switch、while配合几个辅助函数peek、next逐字符扫描。优点是直观、可控、方便调试不需要额外工具最适合课程实验和面试手写。缺点是代码稍微有点啰嗦。自动生成器flex/lex写.l文件用正则表达式描述token规则生成C代码。效率高但实验答辩时如果说不清内部原理老师很容易扣分而且很多教学环境的Windows下配置flex也是个额外负担。表驱动把DFA的状态转移关系存成二维表用状态和当前字符查表转移。这种方法通用性强适合做自动机相关的算法题但实验代码里维护这张表反而加重了理解成本。我个人的建议是老老实实手写。实验一的意义不是向你展示flex有多强大而是让你感受“从规则到状态机再到代码”的完整链路。用手写方式把整个流程走一遍后面学语法分析、语义分析时会轻松很多。等你能手写出来再用flex做一个对比实验那才是真正的扩展。2.3 逆波兰式和符号表这两个高频词你绕不开你如果翻编译原理相关的热词经常能看到“逆波兰式”和“符号表”。逆波兰式后缀表达式常和表达式语法分析一起出现因为2 3 * 4的中缀形式直接处理起来很难确定优先级转成2 3 4 * 后缀形式后就可以用一个简单栈来实现求值。虽然这通常是实验二或实验三的内容但不少学校的实验一在检查词法分析时也可能会用逆波兰式来验证你切出来的token能不能拼成一个可解析的表达式序列。换句话说你的词法分析器至少要能处理好整型常量、运算符和括号因为这是后续逆波兰式转换的基础。符号表则是编译器中用于记录变量、常量、函数等名字属性的核心数据结构实验一如果只做词法分析其实还用不到符号表但你要知道词法分析器识别出的每个标识符最终都会在符号表里登记一条记录。等到实验专门讲符号表时你会发现它和词法分析的数据结构是一脉相承的。现在不必深究但心里有这个线索会让你的实验报告有更多可延展的内容。3. 实操从零手写一个简单词法分析器3.1 环境准备与代码骨架先说环境。我当时用的是C语言因为实验包里的模板就是C写的编译环境是Linux一个gcc命令搞定。如果你在Windows上用VS或者Dev-C也都行但要注意文件编码最好统一用UTF-8否则中文注释有时会引入奇怪的字符导致词法错误。代码结构上不用设计太复杂一般分三块就行token定义、辅助函数、主扫描循环。我建议先写这样一个头文件骨架// token.h #ifndef TOKEN_H #define TOKEN_H typedef enum { TK_KEYWORD, TK_IDENTIFIER, TK_INT_CONST, TK_FLOAT_CONST, TK_OPERATOR, TK_DELIMITER, TK_ERROR, TK_EOF } TokenType; typedef struct { TokenType type; char lexeme[128]; int line; int column; } Token; #endif这里有两点值得注意一是token里保存了line和column这样出错时可以直接输出“第x行第y列出现非法字符”这才是真正的编译器风格二是lexeme保存的是字符切片而不是token类别名因为后续分析阶段需要用到具体的值。3.2 token定义与关键字处理一个简单的关键字表可以这样维护// main.c 片段 const char* keywords[] {int, float, if, else, while, return}; int isKeyword(const char* s) { for (int i 0; i sizeof(keywords)/sizeof(keywords[0]); i) { if (strcmp(s, keywords[i]) 0) return 1; } return 0; }这里有一个小技巧先按标识符规则识别完整字符串再调用isKeyword判断它是不是关键字。我见过有同学试图在状态转移时单独为每个关键字画分支那样做会很痛苦而且一旦增加关键字就要改状态图。正确的做法是用查表法这也是实际编译器中常见的处理思路。不要忘记C语言里sizeof(keywords)/sizeof(keywords[0])这个数组长度写法很多人写成sizeof(keywords)/sizeof(char*)虽然结果一样但后者可读性稍差。另外关键字表应该按字母序排好这样以后如果数据量大可以用二分查找优化。3.3 字符扫描与状态判断核心扫描函数我习惯写成这样// 从输入文件读取字符用getc直接读也行但为了演示状态机我用输入缓冲区 Token nextToken(FILE* fp, int* line, int* col) { int ch fgetc(fp); // 跳过空白字符 while (ch || ch \t || ch \n) { if (ch \n) { (*line); *col 1; } else (*col); ch fgetc(fp); } if (ch EOF) return makeToken(TK_EOF, , *line, *col); // 识别标识符或关键字 if (isalpha(ch) || ch _) { char buf[128]; int len 0; while (isalnum(ch) || ch _) { if (len 127) buf[len] ch; ch fgetc(fp); } ungetc(ch, fp); // 多读的字符吐回去 buf[len] \0; if (isKeyword(buf)) return makeToken(TK_KEYWORD, buf, *line, *col); else return makeToken(TK_IDENTIFIER, buf, *line, *col); } // 识别数字常量 if (isdigit(ch)) { char buf[128]; int len 0, isReal 0; while (isdigit(ch)) { if (len 127) buf[len] ch; ch fgetc(fp); } if (ch .) { isReal 1; if (len 127) buf[len] ch; ch fgetc(fp); while (isdigit(ch)) { if (len 127) buf[len] ch; ch fgetc(fp); } } ungetc(ch, fp); buf[len] \0; if (isReal) return makeToken(TK_FLOAT_CONST, buf, *line, *col); else return makeToken(TK_INT_CONST, buf, *line, *col); } // 运算符和界符这里只列一个的例子其他同理 if (ch ) { int next fgetc(fp); if (next ) return makeToken(TK_OPERATOR, , *line, *col); ungetc(next, fp); return makeToken(TK_OPERATOR, , *line, *col); } if (ch ( || ch ) || ch { || ch } || ch ;) { return makeToken(TK_DELIMITER, (char[]){ch, \0}, *line, *col); } return makeToken(TK_ERROR, (char[]){ch, \0}, *line, *col); }看懂这段代码的关键点是ungetc的用法当扫描到字符已经不属于当前token时必须把它重新放回输入流让下一个token能够读到它。这个细节很多教材不会写得很明确但如果不这么做你就会丢字符导致后续所有token错位。另外识别数字时如果发现.后面没有数字比如1.我的代码目前会生成一个1.的浮点token这在严格实验下可能被视为错误。更好的做法是当.后面没有数字时把.单独当成界符或运算符并且把1和.分别返回。这个边界情况需要参照实验指导书的具体规定。3.4 错误处理与边界情况错误处理是实验里最容易失分的地方。一个合格的分析器在遇到、#这类非法字符时不能直接崩溃而是要输出错误token并及时定位行号和列号。我的做法是当当前字符无法匹配任何规则时生成一个TK_ERROR然后丢弃当前字符继续扫描后面的内容。这样一次输入里有多少非法字符就能一次全部报出来。另外缓冲区越界也要考虑。上面代码里用buf[128]接收token遇到超长标识符时我选择截断到127个字符并继续消费剩余字符。实际编译器里会更复杂但实验阶段你只要做到不崩溃、不误报就已经比很多参考代码强了。还有一个容易被忽略的坑文件末尾的处理。如果用fgetc读入EOF需要先判断EOF属于普通字符还是文件结束标志。在C语言里EOF通常是-1如果你把它当成字符存进lexeme输出时会出现莫名其妙的乱码。所以代码里要在每次识别前都检查EOF确保返回TK_EOF而不是错误token。4. 实验报告与答辩中的常见问题4.1 实验报告怎么写才能拿高分实验报告不是代码的粘贴板而是让老师觉得“这个学生真的搞懂原理了”的说明书。我在写报告时一般按这个结构来组织第一块放token表把每个token类别的正则表达式写成表格第二块画一个关键token的DFA状态转换图比如识别整数和浮点数的合并状态图配上文字说明第三块写核心代码思路解释如何处理最长匹配和错误恢复第四块放测试样例特别要有边界测试比如3.14、99xx、、1.这类例子最后再写一写如果改用flex自动生成器你的实现会有什么不同。很多同学只放“我的代码跑通来了”这是最低分做法。你至少要体现出“为什么这个DFA图对应这个扫描函数”以及“为什么关键字要放在标识符后面查”。把这两句话写清楚比贴二百行代码有用得多。另外如果实验要求里提到了逆波兰式你可以在报告最后写一个小的扩展实验把识别出的中缀token流转换成后缀表达式。哪怕只做一部分也能显示出你主动探索的能力。4.2 答辩时老师最爱问的问题我当年答辩时老师非常喜欢盯着代码里那两三个ungetc的位置问“你这里为什么要把字符放回去”这个问题看着简单背后其实是在考你是否理解最长匹配和输入流的回溯。你只需要说明当前读到的字符虽然后面需要用到但它不属于当前token所以放回去让下一个token读取就解释清楚了。另一个高频问题是“关键字和标识符如何区分”。如果你答“我是先按标识符读完然后再查关键字表”老师基本就满意了。但如果你还能补一句“这样做避免了对每个关键字做单独的分支判断保持了DFA的简洁性”那就更游刃有余。还有一个比较刁钻的如果输入是ifx1你是什么结果应该返回标识符ifx、赋值符、整数1而不是关键字if加标识符x。这个问题的本质是让你理解“最长匹配原则”。解答思路是状态机一旦进入标识符状态会一直吸收合法字符直到遇到分隔符所以在读取完ifx之后才知道它不是关键字。这个案例在实验报告里放一个能明显提高印象分。4.3 几个常见的课堂讨论点除了答辩不少同学会在课程群里讨论“为什么我的词法分析器编译不过”或者“为什么输出结果和老师给的不一样”。排查这类问题我总结了一个固定套路先确认实验包里的测例到底是“输入整个文件后一行一行输出token”还是一个token占一行再确认你的程序是否把这种双字符运算符提前处理了最后再用一个极简输入从零开始逐步打断点跟踪状态。很多时候问题都不是出在核心逻辑而是出在输出格式上。所以写代码前先看样例输出格式比什么都重要。这也是我每年都会反复提醒的一句话编译原理实验的“输入输出格式”也是评分项别小看它。5. 写在最后从实验一到真正理解编译器我现在回过头看这份“湖南大学 编译原理实验一.zip”最大的收获反而不是那个词法分析器本身而是它让我第一次意识到“所有复杂工具都有可以拆解的底层逻辑”。编译器在普通人眼里神秘但当你亲手把字符流变成token流再把token流喂给下一个实验去解析你就不再害怕去看它的源码了。做实验时多用穷举法去测边界多画两张状态图多问自己几个“如果输入是xxx会怎样”这套方法论能一直用到后面的语法分析和中间代码生成。如果你正在做这个实验希望这篇分享能帮你少走点弯路也欢迎你回头再和我聊聊你踩过的坑。本文还有配套的精品资源点击获取
