简介湖南大学编译原理课程实验一资料包面向正在修读该课程、需要完成 DFA 相关实验的本科生可作为实验报告与代码撰写的参考。内容涵盖 DFA 状态图文件、C 源码、可执行程序及实验报告文档共 7 个文件压缩包大小 764KB便于快速下载解压。其中 .dfa 文件用于描述自动机状态转换.cpp 与 .exe 可配合查看、运行验证实验逻辑docx 报告则提供了完整的实验思路记录。已有 708 人学习使用资源在课程中得分较高说明其具备实际参考价值。建议结合教材与课堂内容动手改进避免照搬同时可配合陈果老师的讲解加深理解帮助实验与课程学习更顺利。 说实话每年编译原理课程一开最先被问爆的就是“实验一到底要做什么”。如果你拿到的是“湖南大学 编译原理实验一.zip”这个压缩包大概率是一个从零实现词法分析器的任务。这个实验是所有编译原理实验的地基它解决的是“怎么把源代码字符串变成编译器能理解的最小单元”这个问题。适合所有正在修编译原理、或者想搞懂前端工具链比如Babel、ESLint底层原理的人参考。我当年做这个实验的时候最大的感受是书上的正则表达式和DFA都看得懂一上手写C语言就不知道从哪开始。这篇博文就按我自己的实操经历把实验一的完整思路、核心代码细节、以及我踩过的坑全部拆开讲。1. 实验一到底在做什么定位与整体设计思路1.1 为什么编译原理的第一个实验总是词法分析编译器处理源码的第一步绝对不是直接去解析语法树而是先把一串字符“切”成有意义的单词。这个过程就是词法分析它做的事情本质上和人类读英文句子时先把句子拆成单词是一个道理。只不过编译器拆出来的单词叫“Token”每个Token带上了类别信息比如“这是一个标识符”“这是一个数字常量”“这是一个运算符”。实验一让你实现词法分析器核心目的有三个。第一让你真正理解源代码是怎么从“char数组”变成“Token流”的这是后续语法分析、语义分析的数据基础。第二让你亲手实践正则表达式和有限自动机这些理论把课本上的DFA最小化、NFA转DFA变成可以跑的代码。第三让你体会错误处理的形式——遇到非法字符时怎么办是报错终止还是跳过继续这会直接影响后面实验的联调体验。我当时拿到的实验要求不同年份可能有微调大致是输入一段源代码输出每个Token的种别码、单词值和所在行号。代码要求用C/C实现不能直接调用lex这类工具得手写扫描器。1.2 实验需求的逐条拆解别急着写代码很多人拿到实验题第一反应就是开IDE敲代码结果写到一半发现逻辑混乱。我的建议是先花半小时把需求拆成几个明确的功能点。一个典型的词法分析实验通常包含以下需求识别关键字如if、else、while、return、int、float等识别标识符变量名、函数名识别无符号整数可能包含十进制、八进制、十六进制识别运算符、-、*、/、、、!、、、、等识别界符;、,、()、{}、[]能够跳过空白符和注释单行注释、块注释出现非法字符时给出错误提示把需求拆成这样之后你会发现核心难点集中在两部分一是“如何确定一个单词的边界”什么时候算读完一个标识符二是“多字符运算符怎么处理”比如和和。这两点直接决定了你的扫描器健壮性。还有一个容易被忽略的点实验一通常要求输出种别码。种别码不是随便定的一般实验文档里会给你一张“编码表”比如1代表标识符、2代表整数常量、3代表关键字、4代表运算符。如果你自己定义编码也要保证和实验要求一致否则验收的时候对不上分。2. 核心数据结构与算法选择从理论到代码的桥2.1 手写扫描器 vs 自动生成器为什么实验要求手写你可能听说过lex/flex这类工具它们可以根据正则表达式自动生成词法分析器。实验不让你用不是因为老师老古董而是因为手写才能让你真正理解扫描器的执行过程。自动生成器封装了太多细节——正则怎么编译成DFA、状态怎么转移、冲突怎么消解你一键生成根本看不到。手写扫描器有两种主流实现方式一种是完全模拟DFA的“状态转移表驱动”一种是根据字符类型直接写“分支逻辑”。我在实验里用的是“分支逻辑 一个核心扫描循环”因为对实验规模的词法规则来说状态表反而显得笨重而直接写分支逻辑更直观、更好调试也更容易展示你理解了词法规则。2.2 核心数据结构Token结构、关键字表、符号表无论用哪种写法有几个数据结构是绕不开的。我实际用的结构长这样typedef struct { int type; // 种别码 char value[128]; // 单词原文 int line; // 所在行号 } Token;Token是最基本的输出单元。type用整数对应实验文档里的种别码value存单词本身方便后续语法分析阶段直接取用line是行号这个非常重要因为后面的语法分析报错需要“第几行出错”没有行号定位Bug会非常痛苦。关键字表我用的最简单的方式——字符串数组加二分查找const char* keywords[] {if, else, while, return, int, float, ...}; int isKeyword(char* str) { int low 0, high sizeof(keywords)/sizeof(char*) - 1; while (low high) { int mid (low high) / 2; int cmp strcmp(str, keywords[mid]); if (cmp 0) return mid 1; // 返回关键字种别码 else if (cmp 0) high mid - 1; else low mid 1; } return -1; // 不是关键字 }这里有个小细节关键字表必须按字典序排列二分查找才有意义。我第一次写的时候随手排了个数组结果一直报错排查了半天才发现是表没排序。另外用二分查找而不是线性查找虽然实验规模下差别不大但这是一个习惯问题体现你对算法效率的敏感度。符号表在实验一里可以做得轻量一点。它的核心作用是存“标识符的名称 — 某些属性”的映射。实验一阶段符号表只需要保存名字和类别做去重用同一变量名多次出现时种别码应该是同一个。我用了一个简单的链表typedef struct SymbolEntry { char name[128]; int tokenType; struct SymbolEntry* next; } SymbolEntry; SymbolEntry* symbolTable NULL;每次遇到底层标识符先查符号表如果存在就沿用之前的tokenType不存在就插入新条目。这样做的好处是如果后面实验要求做变量作用域和类型检查符号表可以直接扩展不用推倒重来。2.3 扫描主循环的设计思路一个字符一个字符地“吃掉”手写扫描器的主循环没有玄学核心思路就一句话每次从输入缓冲区读一个字符根据当前状态决定下一步动作。我习惯写成一个“前看一个字符”的扫描器也就是维护一个当前字符和一个“预读字符”因为很多词法规则比如和依赖“看完当前字符后再看一眼下一个字符”。用伪代码表示主循环大概是char ch getNextChar(); while (ch ! EOF) { if (isspace(ch)) { ch getNextChar(); continue; } if (isalpha(ch) || ch _) { // 识别标识符或关键字 } else if (isdigit(ch)) { // 识别数字常量 } else if (ch /) { // 可能是注释也可能是除法运算符 } else if (isOperatorChar(ch)) { // 识别运算符 } else { // 报错非法字符 } }这个循环看起来简单但每个分支内部都有陷阱。比如标识符分支你要一直读到第一个非字母数字字符才停而且这个“多读进去”的字符得放回去留给下一轮循环用。这就需要你维护一个“回退指针”或者用ungetc或者自己写一个带缓存指针的读取器。我在实际试验中发现用ungetc最方便但要注意有些编译器对ungetc多次回退的支持不太一样所以自己写一个缓冲区指针更可控。另外很多教程会强调“最长匹配”原则比如输入a1b你不能读到a1就停必须继续读直到遇到既不是字母也不是数字的字符才算完。同理遇到时你要先看下一个是不是如果是就组成否则单独成Token。这个“先预读、再决定、必要时回退”的逻辑是这个实验最重要的代码技巧。3. 实操过程与核心代码实现一步一步跑起来3.1 输入缓冲区的选择整读 vs 逐行读实验一处理的源代码规模一般不大我建议直接把整个文件读入内存然后维护一个全局的“当前读取位置”指针。这样比反复调用fgetc快而且方便实现“回退一个字符”的操作。我的读取器实现大概是这样char* sourceCode; // 整个源文件的内存拷贝 int pos 0; // 当前扫描位置 int line 1; // 当前行号 char getNextChar() { char c sourceCode[pos]; if (c \n) line; return c; } void unreadChar() { pos--; if (sourceCode[pos] \n) line--; }这个unreadChar函数就是“把多读的字符放回去”的关键实现。原理很简单将pos减一同时修正line计数。这里我踩过一个坑如果回退的字符正好是换行符行号会重复计算导致后面的报错行号偏大。所以unreadChar里必须同步修正line不能只改pos。读取整个文件也需要注意编码问题。实验代码一般是纯ASCII或UTF-8无BOM直接按字节读就行但如果你在Windows上用fopen记得用rb模式打开避免\r\n被自动转换导致行号错乱。这个细节我是在对比输出结果时发现的Windows下文本模式会把\r\n转成\n而Linux下不会导致同一个测试文件在两个平台的输出结果行号相差很大。3.2 标识符、关键字、数字三个最核心的分支标识符的识别分支是这样写的注意边界条件和回退逻辑if (isalpha(ch) || ch _) { char buf[128]; int len 0; buf[len] ch; ch getNextChar(); while (isalnum(ch) || ch _) { buf[len] ch; ch getNextChar(); } buf[len] \0; // 多读进去的字符要放回去 if (ch ! EOF) unreadChar(); int kwType isKeyword(buf); if (kwType ! -1) { token.type kwType; // 关键字种别码 } else { insertSymbol(buf, IDENTIFIER_TYPE); token.type IDENTIFIER_TYPE; } strcpy(token.value, buf); token.line line; }这里面最值得注意的一点是while循环结束退出的时候当前ch一定是“不属于标识符字符集合的字符”所以必须unreadChar。但有一种情况是ch为EOF这时不能回退否则会陷入死循环。这个EOF判断是个经典的隐藏Bug来源我见过很多同学卡在这里。数字的分支要区分整数、小数和科学计数法如果实验要求支持的话。我的整数识别逻辑是if (isdigit(ch)) { char buf[64]; int len 0; // 处理十进制整数也可以加0x前缀判断 while (isdigit(ch)) { buf[len] ch; ch getNextChar(); } buf[len] \0; if (ch .) { // 处理浮点数 buf[len] ch; ch getNextChar(); while (isdigit(ch)) { buf[len] ch; ch getNextChar(); } } if (ch ! EOF) unreadChar(); token.type INTEGER_TYPE; // 或 REAL_TYPE strcpy(token.value, buf); token.line line; }这里如果你想要支持浮点数需要在整数结束后判断下一个是否为小数点但要注意“1..2”这种情况虽然C语言语法里它不合法但词法分析阶段一般不会管语法错误遇到“1.”就接受为一个浮点数Token然后在语法分析阶段再报错。这是“词法阶段只负责按词法规则切分不负责语法判断”的典型例子。3.3 运算符和界符的处理最容易出细节错的区域运算符分支里最大的陷阱就是多字符运算符。我的实现方式是先读第一个字符然后预读第二个组成一个两字符的字符串去匹配if (ch || ch ! || ch || ch || ch || ch - || ch *) { char twoChar[3]; twoChar[0] ch; char next getNextChar(); if (next ) { twoChar[1] ; twoChar[2] \0; // 匹配 ! token.type TWO_OP_TYPE; } else { // 单个运算符 if (next ! EOF) unreadChar(); token.type ONE_OP_TYPE; } strcpy(token.value, twoChar); }注意我用的是“先尝试匹配双字符运算符匹配不上再回退”的策略这是实现最长匹配的通用做法。遇到的时候还要当心“”遇到“-”要当心“--”这些在C语言语法里都是独立的运算符如果你实验要求支持它们需要把this逻辑扩展。注释处理也是容易忽略的。遇到/时要连续往后看两个字符如果是//就一直读到行尾如果是/就一直读到/为止。这里有个大坑如果读到文件结尾都还没找到*/应该报错“未闭合的块注释”。我见过有同学在块注释没闭合的情况下直接退出导致后续所有代码都不识别这种错误在验收时特别容易被测试用例抓住。注释在词法分析阶段应该是直接跳过不产生Token但它需要消耗输入字符并可能增加行号所以必须在主循环里特别处理。3.4 错误处理与恢复实验一的加分项实验要求一般只提“报错”但怎么报、报完之后怎么办体现的是你对实际问题考量的完整性。我采用的策略是遇到非法字符比如、#、$这类在C语言词法规则中完全无意义的字符打印一条错误信息包括行号和非法字符本身然后跳过这个字符继续扫描。这种“跳过继续”的策略好处非常明显一次编译可以输出所有的词法错误而不是报一个错就停。如果每次报错就终止你调试一个稍微复杂点的测试用例时需要反复编译几十次才把那几个错误找全。但对于错误数量我限制了一下最多报10个错误后就终止防止死循环或者刷屏过多这个阈值是个可调参数。4. 真实踩坑记录与调试心得4.1 最长匹配一个让我多花了三个小时的Bug我在写标识符识别时一开始没注意“读完一个标识符后必须回退”这件事。结果输入source时第一次循环识别出sou然后后面的rce会被当作新的标识符。输出结果里全是这种半截单词我当时第一反应是“我的字符串读取函数有问题”后来单步调试才发现问题不在读取在于循环结束前那个字符没有放回去。这个教训很深刻词法扫描器的每一个分支结束时都必须有一个明确的“当前字符状态”约定要么你已经消费了它要么你把它放回去了。写代码之前先用一段非常简单的输入比如abc def 123在纸上推演一遍每个字符的归宿能省下大量调试时间。4.2 符号表的引入时机有人过度设计有人完全没有有些同学会在实验一里就把符号表做成带作用域嵌套的复杂结构其实不需要。实验一的核心是“识别Token”符号表在这里的用途只是把标识符去重并且为了后续实验做铺垫。过度设计会让你花大量时间写符号表管理代码反而忽略词法分析本身。反过来完全不建符号表也有问题。如果你直接每次都把标识符当作新Token输出后面的实验尤其是语义分析需要查符号表记录类型时就得回头改词法分析器。我在实验一里只做了一个最简单的插入查找链表大约50行代码但到了实验三做类型检查时在这个基础上改成哈希表、加上作用域栈非常顺手。建议你在一开始就保留一个符号表模块哪怕功能很简陋也别省。4.3 测试用例设计别只测老师给的样例实验课一般会提供一个或几个示例输入但如果你只测示例验收的时候大概率会被隐藏测试用例打懵。我的做法是构造了几类边界测试空文件和只有注释的文件验证程序不会崩溃连续多个运算符例如ab是应该输出a、、、b还是其他组合这取决于你的运算符定义数字和标识符贴在一起例如2a合法情况是什么非法时应该报错而不是扫描出2和a超长标识符比如超过你的缓冲区128字节会不会导致缓冲区溢出注释中包含关键字和运算符确保注释全部被跳过尤其是超长标识符和缓冲区溢出这个问题很多固定长度的char buf[128]实现都会踩坑。我的做法是当标识符长度超过127时报错“标识符过长”然后继续读但不再写入缓冲区。这样至少不会段错误。还有一个调试大杀器写一个输出“对照文本文件”的功能。把每一次扫描的结果Token的种别码、值、行号输出到一个文件然后和正确结果用diff命令对比。这样测试几十个用例时不用肉眼盯着屏幕一个个看。我在做实验时写了一个简单的shell脚本自动跑所有测试用例并diff结果节省了大量时间。5. 常见问题速查与优化方向5.1 常见问题速查表为了方便你自查我把这个实验里最常见的坑整理成了一张表问题现象根本原因解决方案标识符被切成两截读完单词后没有回退多余字符在循环结束后unreadChar注意EOF判断返回的行号总差1或偏大换行符被回退时没有修正line计数unreadChar中同步处理\n出现了“半个运算符”多字符运算符匹配时提前返回先预读第二字符匹配不上的回退块注释永远跳不出没考虑‘*/’的查找或忘了EOF判断用循环找*/同时判断文件结尾被拆成和缺少预读合并逻辑匹配双字符运算符数字识别到a就停边界判断没包含字母数字后紧跟字母时应该报词法错误Windows输出的行号比Linux多fopen用了文本模式统一用“rb”模式读取出错后死循环报错分支没有消费非法字符报错后pos跳过非法字符这些问题的共同根源基本都是“扫描器的状态处理不够严格”。我的建议是每写完一个分支都回头检查这个分支结束时当前字符是否被正确消费或回退以及line计数器是否与实际输入同步。5.2 做完实验一之后还能往哪些方向优化如果你做完基本要求还有余力有几个方向可以拓展。第一把查找关键字从二分查找换成“直接哈希”用字符串哈希把查找时间降为O(1)实验规模上差别不大但思路值得练。第二把硬编码的种别码改成枚举类型代码可读性提升明显。第三尝试把扫描器改成“流式”的不一次性读入全部源码而是边读边扫。这样做的好处是内存占用恒定能处理超大文件。还有一个比较有趣的扩展你可以试着把实验一的扫描器“通用化”让它通过读取一个配置文件来识别不同的词法规则这就变成了一个mini版lex。虽然工作量会增加不少但做完后你对词法分析器的理解会上升一个台阶。我当年做实验时没时间搞这个后来工作了回头写一些命令行工具时才发现这种思路在实际工程里的价值。5.3 给即将交实验的同学的一点个人体会最后说点实在的。实验一能在编译原理课程里作为“第一关”它的意义就是逼你老老实实处理字符串、状态、边界。这个过程中你可能觉得自己在写“不是编程的编程”整天和字符、指针、回退打交道非常琐碎。但实际做下来你会发现你对一个问题维度的理解会变得更清楚一个程序从源码到可执行第一步不是画架构图而是先把最原始的字节流按规则切分好。这个习惯和感觉会在你以后阅读任何需要解析文本的工具源码时派上用场。比如你去看Babel怎么解析JavaScript、去看JSON库怎么解析JSON字符串你会发现它们最核心的那层和你实验一写的扫描器逻辑惊人地相似。我个人的一个小建议是不要只把实验一当作“过关任务”尝试把它写成自己的“代码资产”。一个模块化良好的词法分析器后面做语法分析时需要加Token类型、需要关联符号表属性、需要接错误恢复都是很容易扩展的。相反如果实验一写得一团乱麻后面每个实验你都得在痛苦的代码上缝缝补补那才是真正的煎熬。祝你的编译器从这第一个实验就开始顺顺当当。本文还有配套的精品资源点击获取