简介一份面向湖南大学编译原理课程的实验参考资料聚焦实验一从DFA设计与代码实现到实验报告撰写的完整流程。课程实验分数占比很高作者特别强调代码与报告仅供思路参考建议结合自身理解进行实践不宜直接照搬。内容预览显示包内包含DFA_1.cpp源文件、4个dfa状态定义文件、一份docx实验报告以及一个可直接运行的exe程序可对照查看词法分析中确定有限自动机的构造、状态转换表与程序运行效果能直观理解自动机如何完成输入串的识别与状态跳转。资源整体共7个文件压缩包仅764KB体量虽小但结构完整便于快速下载查阅。目前已有709人浏览学习说明其在同课程学生中具备一定的参考热度适合需要理解实验一设计思路、比对报告结构或快速上手编程实现的学习者。1. 拿到《编译原理实验一.zip》之后你先想清楚这三件事解压《编译原理实验一.zip》那一刻大多数人心里想的其实是“我能不能找到一个能直接交的代码”。但等你真的跑过一轮评测就会发现实验一考的不是代码量而是你有没有把“一堆字符”变成“一串有结构的 token”这件事想明白。A 同学第一次拿到这份压缩包的时候花了一个晚上在搞环境真正写词法的时间还不如调一个中文注释的编码问题多。这份实验包能解决的事情很具体给你一个语法定义的子集让你实现词法分析把输入源码翻译成带行号、列号和类型的 token 序列再跟标准输出做比对。适合现在正在修编译原理课、或者想自己补一遍编译基础的人。而我写这篇文章的目的只有一个把这门实验从“打开压缩包”到“能过基础样例、知道坑在哪”的完整路径讲清楚不绕弯子。2. 实验一的真实考察点词法分析的两种实现路线2.1 拿到压缩包后的信息核对顺序我拿到这类实验压缩包第一件事永远是先看目录而不是急着打开代码文件。常见做法是解压之后先执行一条命令unzip 实验一.zip -d exp1 ls -R exp1然后依次确认四类东西实验文档、骨架代码、测试样例、构建脚本。文档决定你用什么语言、输出什么格式骨架代码决定你能不能直接编译测试样例决定你拿什么做验收构建脚本决定你到底是手写编译命令还是用 CMake/Makefile。四个缺一个都会在最后提交的时候出问题。所以不要一上来就翻 flex 的教程。先看文档里写的输出格式。实验一最常用的评分方式是“把你的输出和标准输出逐字符比对”所以每一行的格式、空格、逗号、换行都算分。先找文档里的“样例输出”把它当作你在实现的规格说明书而不是把老师上课给的 PPT 当规格。2.2 手写状态机还是用生成器先看评分方式再选这是选型问题。常见的实现路线有两条手写一个 DFA 状态机扫描器或者用 flex 这类生成器写 .l 文件。我用一张表直接对比路线优点缺点适合场景手写扫描器逻辑完全可控调试直观能精确控制行列号与错误恢复代码量大数字、注释这些状态容易漏边界实验限定 C/C/Python 手写或者你想把自动机原理彻底弄懂flex 生成器正则表达能力强代码短产出稳定生成代码是黑匣子行号列号要靠 yytext 手动维护报错信息难改实验允许提交 .l 文件或者你只想把重心放在后面的语法分析如果压缩包里的骨架是 C 工程且明确要求“实现一个词法分析程序”那通常默认是手写。如果文档里写了“请使用 flex 编写”那别犹豫用 flex。还有一条判断标准看测试样例的输入规模。如果样例里有大量非法字符、形如.5的浮点数、/*和除号混排的情况手写反而更容易处理这类错误恢复因为 flex 的默认行为是遇到匹配失败就报错并停止。2.3 词法边界关键字、数字、注释与错误恢复的最小状态集不管哪条路线你要管理的状态至少包含这几类标识符、关键字、整数、浮点数、字符串、注释、空白、非法字符。我见过最多的翻车不是不会写而是边界没建全。例如关键字大部分实现是先识别出标识符然后查表这没问题但有人为了省事直接在正则里把关键字写在标识符规则前面导致ifx这种名字被切成了if和x这就是典型的边界错。数字的状态要拆成整数、小数、指数三段因为1e不是合法浮点数.5合法3.在多数语言里合法。注释要区分行注释和块注释块注释必须处理未闭合的情况。非法字符不能直接终止程序而是记录行列号后跳过恢复扫描。这套最小状态集就是实验一的核心。你不需要在一开始设计成一个能编译完整 C 语言的词法器只需要保证实验文档里给出的语法子集全部覆盖。做减法比做加法重要先把你明确要支持的 token 类型列成表再动手。3. 先跑通骨架再写代码最小命令与工程组织3.1 解压缩后的第一件事文档、构建脚本、测试样例先过一遍一个经常被忽略的经验先试试不写任何代码能不能把骨架工程编译出一个可执行文件。如果这一步都过不去后面写了也白写。建议按这个顺序检查cd exp1 find . -maxdepth 2 -type f | sort head -n 60 README* 2/dev/null || ls -la如果有 Makefile 就直接make如果没有就在文档里找编译命令。很多实验包的骨架是故意留了缺口的比如某个函数返回空、某个头文件没包含这时候跑一次编译才能看到真实缺口是什么。我一般会记录下第一条编译错误先修环境问题不碰业务逻辑。判断标准很简单能不能跑出一个“接收输入并原样返回”的程序。这一步成功之后再去动词法逻辑。A 同学第一次拿到包没先编译直接写了两百行状态机最后发现 main 函数入口跟实验要求的参数形式不一致整个重来。3.2 原样编译一次官方样例确认输出格式编译通过之后找测试样例目录里的第一个样例直接喂给程序。如果是命令行程序./lexer test/01_basic.c输出会是一堆你不认识的 token 序列。这时候不要慌拿它和实验文档里的“预期输出”做一次 diff。这里要说一个血泪经验格式比逻辑更先决定你的分数。行号从 0 还是从 1 开始列号是字符偏移还是字节偏移token 类型名是大写还是小写都可能导致整段输出对不上。diff (./lexer test/01_basic.c) test/01_basic.outdiff 的输出会精确告诉你是哪一行不一致。修格式问题的成本远低于修逻辑所以这一部一定不能省。任何一份实验一的压缩包文档里必然写了输出格式把它当作协议来对齐。3.3 token 类型表与关键字表怎么组织骨架代码里通常会有一个枚举或者宏定义例如typedef enum { TOKEN_IDENT, TOKEN_KEYWORD, TOKEN_INT, TOKEN_FLOAT, TOKEN_OP, TOKEN_EOF } TokenType;关键字表我一般单独放一个数组方便扩展。用 C 的话可以直接用字符串数组和二分查找也可以接受线性查找因为关键字数量极少const char* keywords[] { if, else, while, return, int, float, void, NULL };这里带出一个参数关键字表的大小写是否敏感。实验文档没说默认按小写处理。如果你把If误判成关键字多半是查表前没有做规范化。token 类型表的设计决定了后面所有输出的可读性也决定了你是否能在测试阶段快速定位问题。我习惯在 token 结构里同时保留原始文本、类型、行号、列号这四个字段在调试时缺一不可。4. 核心实现写一个能过基础样例的词法分析器4.1 输入缓冲与主循环先跳过空白再识别 token我通常会写成一个类或者一个结构体把输入字符流和当前位置、当前行列号放在一起。主循环的逻辑非常简单跳过空白和注释读一个 token输出直到 EOF。下面是一个能直接运行的 Python 骨架逻辑与 C 版本通用只是把内存管理省掉了。import sys class SimplaLexer: def __init__(self, text: str): self.text text self.pos 0 # 当前字符下标 self.row 1 self.col 0 def peek(self, offset: int 0) - str: idx self.pos offset if idx len(self.text): return return self.text[idx] def advance(self) - str: ch self.peek() self.pos 1 if ch \n: self.row 1 self.col 0 else: self.col 1 return ch def skip_whitespace(self): while self.peek() in ( , \t, \n, \r): self.advance()这里的关键参数是pos和row/col的维护。很多人会在跳过换行时忘记把col归零导致所有行号对但列号错。我习惯把advance()做成唯一的读取入口这样可见字符、换行、EOF 的处理都集中在一处不会出现某个分支漏更新行列号的情况。4.2 标识符与关键字先拼完再查保留字表标识符的规则一般是字母或下划线开头后续跟字母、数字、下划线。实现时注意不要一边读一边判断是不是关键字而应该先把整个标识符拼出来然后查表。def read_identifier(self): start_row, start_col self.row, self.col parts [] while self.peek().isalnum() or self.peek() _: parts.append(self.advance()) word .join(parts) token_type KEYWORD if word in self.keywords else IDENT return { type: token_type, value: word, row: start_row, col: start_col, }这段逻辑值得说明先拼词再判定类型。如果你在循环里见到i就猜它是关键字那就没法处理ifx、int_value这类正常标识符。查表用 Python 的 set 就够了如果是 C 语言可以写一个静态数组然后逐个比较或者按首字母分桶效果差不多。keyword 集合里放什么以实验文档中的关键字列表为准不要自己加。4.3 数字识别整数、小数、科学计数法的三种边界数字是实验一里最容易翻车的部分。一个完整的数字状态流转应该是先收整数部分如果遇到小数点则进入小数部分如果遇到e或E则进入指数部分。三种边界分别是.5这种小数点开头、3.这种小数点结尾、1e5这种指数形式。def read_number(self): start_row, start_col self.row, self.col parts [] while self.peek().isdigit(): parts.append(self.advance()) is_float False if self.peek() .: is_float True parts.append(self.advance()) while self.peek().isdigit(): parts.append(self.advance()) if self.peek() in (e, E): is_float True parts.append(self.advance()) if self.peek() in (, -): parts.append(self.advance()) if not self.peek().isdigit(): # 1e 这种输入属于非法数字需要报错 raise SyntaxError(finvalid number at row {self.row}, col {self.col}) while self.peek().isdigit(): parts.append(self.advance()) return { type: FLOAT if is_float else INT, value: .join(parts), row: start_row, col: start_col, }这里三个边界对应的处理逻辑分别是.开头时会先进入小数点分支但由于整数部分为空这时要在外层判断是否允许这种“省略整数部分”的写法3.的情况要看实验文档的语法定义有的语言允许有的要求小数点后必须跟数字1e是明确的错误必须抛出异常或记录错误而不能默默吞掉。4.4 注释跳过与非法字符的错误恢复注释有两种行注释//和块注释/* ... */。块注释的特例是未闭合。我的做法是在主循环里先判断当前字符是否为/如果下一个字符是/则跳到行尾如果是*则进入块注释扫描。def skip_comment(self): if self.peek() / and self.peek(1) /: while self.peek() and self.peek() ! \n: self.advance() return True if self.peek() / and self.peek(1) *: self.advance() self.advance() while True: if not self.peek(): raise SyntaxError(unclosed block comment) if self.peek() * and self.peek(1) /: self.advance() self.advance() break self.advance() return True return False碰到非法字符时比如、#这类不在任何 token 规则里的字符我的处理方式是记录错误信息、打印到 stderr然后跳过该字符继续扫描。千万别直接 return 退出因为评测样例里常常故意混入非法字符来验证错误恢复能力。跳过非法字符时行列号照样更新这样后续 token 的行列号不会错位。5. 常见问题与避坑实验一里最容易翻车的五个点5.1 关键字被误判成标识符先拼完再查表现象输入if(x) return 1;输出的第一个 token 是IDENT: if而不是KEYWORD: if。 原因代码里先匹配了“字母开头”的分支并且这个分支只识别为一个普通标识符没有在收尾时查关键字表。 解决把标识符的字符收集完整后统一查一次保留字表。查表动作必须在拼词之后不能在拼词过程中提前决定类型。 我见过有人用正则把关键字写在前面结果ifx被拆成if和x这就是另一个方向的反例。记住一个原则关键字表中的单词必须准确等于完整标识符才匹配。5.2 浮点数边界漏判.5、3.、1e5各占一坑现象.5报非法字符3.后面跟着的字符被吞掉1e被当作合法数字输出。 原因数字状态机只覆盖了“整数部分 可选小数点 小数点后数字”这一条理想路径没有考虑省略整数部分、小数点结尾、指数部分缺失三种情况。 解决先读整数部分再看小数点遇到小数点后无论后面是否还有数字先确认实验语法是否允许指数部分遇到e/E后必须要求后面至少有一位数字否则报错。这三个边界是评审样例最爱挖的位置也是最能拉开分数差距的位置。5.3/*与除号歧义向前看一个字符的代价现象输入a b /* c结果程序以为注释以/*开始然后找不到结束符直接抛异常。 原因扫描器看到/就把下一个字符固定下来而没有考虑/后面跟空格、或者/本身就是除法运算符的场景。 解决在识别到/时向前看一个字符。如果下一个字符是*且中间没有空格才进入注释否则把/当作运算符输出。同理//行注释必须在/后紧跟/才触发。 这个坑的典型特征是最简单的算术表达式样例能过稍微复杂一点的表达式就崩溃。5.4 中文注释与编码字节流别乱解码现象本地跑样例输出正确换一台机器或者评测端跑就出现乱码甚至把中文注释的内容输出成非法 token。 原因词法分析器把源文件按字节流读入遇到中文字符的 UTF-8 多字节序列时每个字节都可能是不可打印字符如果代码里用isalpha()这类函数判断就会把它们当成标识符的一部分或者非法字符。 解决注释和字符串之外确保跳过注释的逻辑不检查内容如果你明确知道源文件是 UTF-8读出字节后先解码再判断字符类型。如果实验要求只支持 ASCII 输入在文档限制集合外直接报“非法字符”也算正确行为关键是不能稳定复现的乱码问题一定要在提交前用中文注释样例试一遍。5.5 EOF 收尾丢 token循环退出前补一次 flush现象输出少最后一个标识符或数字比如return 0;的输出里只有return没有0。 原因主循环里检测到 EOF 时直接 break但此时正在拼的 token 还没从缓冲里吐出来。很多人写循环条件是while (peek() ! EOF)结果最后一个字符被当作结束标志而不是先完成 pending token 再退出。 解决循环退出前检查当前是否处于“正在读标识符/数字”的中间状态如果有则补做一次收尾函数调用。更稳妥的做法是让每个 token 读取都从“空白之后读取第一个有效字符”开始读到不可继续的字符时就立即返回 token而不是等循环退出再处理。6. 进阶把实验一的 lexer 接到语法分析去6.1 给 token 加行列区间而不仅仅是一个起点如果你打算继续做实验二那词法器输出的信息会直接决定语法分析报错体验。起点行列号只够你告诉用户“错误发生在某一行”但不够指出“错误范围”。我习惯在 token 结构里额外记录结束行列位置也就是记录读取最后一个字符之后的状态。这个信息在实验二里非常有用。比如语法分析遇到if (a )你要报错就得指出从a到)之间丢了表达式。如果你只有起点就只能报“第 2 行有错”用户还得自己猜。行列区间的维护成本不高就是在advance()里同步更新 row/coltoken 读完后再读一次当前状态作为终点。6.2 把 token 流序列化成 JSON 行方便调试与后续对接这是我在本地调试时的习惯也推荐给你在程序里加一个“调试输出模式”把 token 按 JSON 行格式输出每行一个 token。import json def emit_token(tok): print(json.dumps({ type: tok[type], value: tok[value], start: [tok[row], tok[col]], end: [tok[end_row], tok[end_col]], }, ensure_asciiFalse))好处是你可以用 Python 脚本或者 jq 快速过滤 token 类型做统计和回归测试。比如统计所有关键字出现的次数、检查某个标识符的覆盖范围。再往后做实验二时这个 JSON 流还能直接喂给语法分析器作为输入 token 源省掉重新读文件解析的重复工作。如果实验要求必须输出固定文本格式那就把这个开关作为运行时参数不影响正式提交。6.3 一个习惯三正三负的测试夹具先行最后说一个我自己的习惯写主循环之前先定测试用例。六个用例三个合法输入三个非法输入。合法输入覆盖普通表达式、嵌套注释、浮点数非法输入覆盖1e、未闭合注释、非法字符。每实现一个 token 类型就立刻跑一遍这六个用例而不是全部写完再统一调试。这个习惯帮我避免了很多“全写完一起查 bug”的尴尬。词法分析的逻辑是线性流任何一步状态机错位都会让后面的 token 全部偏移。逐个类型推进、每个类型用一个样例验证虽然看起来慢但整体调试时间反而是最少的。实验一不是靠惊艳的设计拿分是靠稳定输出拿分。希望这个思路帮到你少走一点我在反复编译、反复 diff 里走过的弯路。本文还有配套的精品资源点击获取