简介杭电编译原理课程实验的 C 源代码包面向正在学习编译器设计的高校本科生尤其适合需完成词法分析、NFA 转 DFA、递归下降分析、LL(1) 语法分析等核心实验的读者。包内共 11 个文件含 4 个可直接运行的 exe、4 个 C 源码、2 个 txt 说明文档与 1 个 SysY 测试用例文件整体仅 334KB可执行程序与源码一一对应txt 记录图或输出信息sy 提供测试输入便于边运行边核对中间结果。已有 1605 人学习下载。实验内容覆盖较全词法分析器特别识别八进制、十六进制数及两种注释并具备错误提示子集构造法演示 NFA 转 DFA 的消歧过程递归下降分析用一组函数嵌套解析语法单位LL(1) 部分完成预测分析表的构造与输入串匹配。源码按模块组织结构清楚可直接导入工程编译运行或单步调试小体积示例既能帮初学者理解编译前端关键步骤也可作为课程设计、实验报告乃至后续扩展实验的代码参考遇到运行结果异常时还能对照代码快速定位问题。1. 编译原理实验这套 C 源码一次打通词法、NFA 转 DFA 与两种语法分析编译原理实验课是计算机专业课里公认最“劝退”的一门教材全在讲形式语言和自动机真打开实验要写的却是 C 代码。杭电这套编译原理实验源代码恰好把编译器前端最核心的四个环节一次性补齐——词法分析、子集构造法NFA 转 DFA、递归下降分析法、LL(1) 预测分析每个实验都有独立的 .cpp 源文件、可直接运行的 .exe以及配套的 test.sy、result.txt、graph.txt 输入输出样例。适合正在赶实验报告、准备考研复试机试、或者单纯想用 C 把“源码 → token → 语法分析”这条链亲手实现一遍的人。我按实验顺序把四个模块完整拆了一遍下面直接给出每个模块的输入输出约定、核心实现和最容易翻车的细节。文件对应实验输入产出词法分析.cpp / .exe词法分析器读 test.sy写 result.txt子集构造法.cpp / .exeNFA 转 DFA读 graph.txt输出 DFA 转移表递归下降分析法.cpp / .exe自顶向下语法分析输入表达式输出推导轨迹LL1.cpp / .exeLL(1) 预测分析输入符号串输出是否匹配2. 词法分析器SysY 语言八进制、十六进制与双注释格式的识别2.1 SysY 的记号谱系词法分析到底在识别什么词法分析是编译器的第一个环节职责是把纯文本的 test.sy 切成一个个有意义的记号Token。SysY 是典型的教学语言记号类别并不复杂我一般先按下面这张表把工程边界定下来再动手写代码记号类型例子识别规则关键字int、float、if、else、while、return标识符匹配后查表标识符a、_tmp、main字母或下划线开头后续字母/数字/下划线整型常量0、077、0x1F八进制 0 开头、十六进制 0x 开头运算符、-、*、/、、单字符或双字符匹配界符( ) { } ; ,单字符直接归类非法字符、# 等给出错误提示并记录行号这里最值得留意的是整型常量实验要求把八进制和十六进制单独区分开。八进制以 0 开头十六进制以 0x 或 0X 开头十六进制里可以出现 a-f八进制里出现 8、9 反而是错误边界。很多同学在这个位置只判断 isdigit遇到 0x1F 会把 x 拆成标识符这就是典型的边界没想清楚。2.2 为什么用手写状态机而不是 C 的 regex拿到题目第一反应可能是用 std::regex 匹配数字和标识符但实验的考察点恰恰是“手工构造状态机”。regex 库在 C 里编译慢、运行也慢更重要的是它把状态迁移的过程封装成了黑匣子写实验报告时你根本说不清转移函数怎么定义的。所以这份源码用的是逐字符扫描 switch 分支的方式本质上就是在模拟一个 DFA当前状态加当前输入字符决定跳转到哪个状态。核心代码大致长这样#include iostream #include fstream #include vector using namespace std; enum TokenType { ID, INT, KEYWORD, OP, UNKNOWN }; struct Token { string lexeme; // 词素也就是原始字符 TokenType type; // 记号类别 int line; // 所在行号排错时定位用 }; int main() { ifstream fin(test.sy); if (!fin.is_open()) { cerr 无法打开 test.sy endl; return 1; } string line; int lineno 0; while (getline(fin, line)) { lineno; int i 0; while (i line.size()) { if (line[i] || line[i] \t) { i; continue; } // 数字字面量识别0x 开头为十六进制0 开头为八进制其余为十进制 if (isdigit(line[i])) { string num; int base 10; if (line[i] 0 i 1 line.size() (line[i1] x || line[i1] X)) { base 16; num 0x; i 2; while (i line.size() isxdigit(line[i])) { num line[i]; i; } } else if (line[i] 0) { base 8; num line[i]; i; while (i line.size() line[i] 0 line[i] 7) { num line[i]; i; } } else { while (i line.size() isdigit(line[i])) { num line[i]; i; } } // 输出格式行号 进制 字面量原文 cout lineno : INT(base base ) num endl; continue; } // 标识符和关键字先收标识符再查关键字表 if (isalpha(line[i]) || line[i] _) { string id; while (i line.size() (isalnum(line[i]) || line[i] _)) { id line[i]; i; } cout lineno : (isKeyword(id) ? KEYWORD : IDENT ) id endl; continue; } // 运算符和界符这里按单字符处理多字符如 需再加一层判断 cout lineno : OP line[i] endl; i; } } return 0; }这段代码里需要注意几个参数和边界isdigit 判断的是十进制数字isxdigit 判断十六进制字符两者配合才能正确处理 0x1F八进制分支里我主动截断到合法字符 0-7实际使用中这里还应该检查“八进制里出现 8 或 9”的情况并报错很多同学直接丢给十进制分支处理逻辑上虽然不崩溃但和 SysY 语言定义并不一致。isKeyword 是查表函数实现方式就是把关键字集合放进 unordered_set 再查等价于初始化一个字符串数组后逐个比较我在 C 里一般用数组初始化再加循环判断避免引入额外依赖。2.3 两种注释格式单行注释与跨行块注释的状态处理test.sy 里会出现两种注释// 到行尾的单行注释以及 /* ... */ 的块注释。单行注释在 getline 循环里遇到 // 直接 break 跳出当前行的扫描即可真正吃细节的是块注释跨行的问题。用 getline 一行的方式读文件时/* 很可能在第一行开头出现*/ 在第三行才结束如果只在单行函数里找结束符第一行扫描到行尾也找不到程序就会误把第二行、第三行当作正常代码继续分析。正确做法是维护一个全局布尔变量 inBlockComment进入块注释后设置它后续每一行都先检查这个标志直到找到 */ 再复位。这份源码里采用的就是这种跨行状态保持的方案和词法分析器内部的状态机思路是完全一致的它本身就是一个状态读入状态、单行注释状态、块注释状态、字符串状态。result.txt 的输出格式建议固定为“行号 记号类别 词素”这样后面接 LL(1) 或递归下降时可以直接拿它当输入流不用二次解析。我看到不少实验报告把 token 直接打印在控制台最后验收时又要手动重跑其实把所有输出落到 result.txt 里是更省事也更容易截图存档的做法。3. 子集构造法把 graph.txt 的 NFA 变成等价 DFA 转移表3.1 为什么非要把 NFA 转成 DFANFA 允许一个状态对同一输入字符有多条转移边甚至还允许 ε 空转移识别一个字符串时要同时跟踪多个可能状态模拟起来复杂度高。DFA 每个状态对每个字符至多一条确定转移直接用一个二维数组就能表示转移表在执行阶段非常省事。编译器理论课讲子集构造法就是因为它把一个“可能有歧义”的自动机变成一个“严格确定”的自动机这一步做完之后后面所有基于 DFA 的识别都能用查表完成。子集构造法要反复做两个基本运算求某个状态集合的 ε 闭包以及对某个状态集合输入某个字符后能到达的状态集合 move。闭包运算是传递性的只要集合里有一个状态有 ε 边就要把 ε 边指向的状态也收进来持续扩张直到稳定。想清楚这个“持续扩张直到稳定”的语义代码就不容易写错。3.2 graph.txt 的输入格式约定与读取我看到的 graph.txt 是按以下格式组织的第一行是 NFA 状态数和边数接下来的每一行是一条边三个字段分别是起点、终点、转移字符其中 # 表示 ε 空转移。读取代码可以这样写#include bits/stdc.h using namespace std; const int MAXN 100; vectorpairint, char adj[MAXN]; // 邻接表pair.second 为 # 时表示 ε 边 setchar alphabet; // 字母表不含 epsilon int n, m; int main() { freopen(graph.txt, r, stdin); cin n m; for (int i 0; i m; i) { int u, v; char c; cin u v c; adj[u].push_back({v, c}); if (c ! #) alphabet.insert(c); } // 输入假设NFA 初态为 0终态为最后一个状态 n-1 return 0; }注意这里我用 # 作为 ε 的占位符因为文本文件里直接写 ε 可能涉及编码问题。alphabet 集合的作用是确定后续 BFS 构造 DFA 时要枚举哪些字符如果遗漏了某个字符DFA 转移表就会缺行最终测试时发现某个输入串匹配失败却找不到原因。3.3 队列驱动的子集构造主循环子集构造的核心逻辑是从初始状态集合的 ε 闭包出发用一个队列维护待处理的子集对每个子集、对字母表中的每个字符计算 move 结果再求 ε 闭包得到一个后继子集。如果这个子集是第一次出现就给它分配新的 DFA 状态编号并进队列。这个过程本质上就是一个 BFS用 mapset , int 做“子集到编号”的映射mapsetint, int dfaId; // NFA 状态子集 - DFA 状态编号 vectorsetint subsets; // 编号 - 子集内容 mappairint, char, int dfaTable; // (DFA状态, 字符) - 目标DFA状态 queuesetint q; setint epsilonClosure(setint S) { stackint st; for (int s : S) st.push(s); while (!st.empty()) { int cur st.top(); st.pop(); for (auto e : adj[cur]) { if (e.second # !S.count(e.first)) { S.insert(e.first); st.push(e.first); } } } return S; } setint initialState epsilonClosure({0}); dfaId[initialState] 0; subsets.push_back(initialState); q.push(initialState); while (!q.empty()) { setint cur q.front(); q.pop(); for (char c : alphabet) { setint moveSet; for (int s : cur) { for (auto e : adj[s]) { if (e.second c) moveSet.insert(e.first); } } if (moveSet.empty()) continue; setint target epsilonClosure(moveSet); if (!dfaId.count(target)) { int newId (int)subsets.size(); dfaId[target] newId; subsets.push_back(target); q.push(target); } dfaTable[{dfaId[cur], c}] dfaId[target]; } }这段代码的 q 就是 BFS 队列dfaId 承担了“子集去重”和“编号分配”双重职责dfaTable 用嵌套 map 组织转移表而不是二维数组是因为字符可能不是规则的 ASCII 序号用 map 更通用。epsilonClosure 里的栈或队列可以二选一关键是 S.count 去重防止 ε 环路导致死循环这是我在自己实现时吃过亏的地方后面避坑章还会专门展开。3.4 终态判定与 DFA 输出DFA 的终态集合判定规则是只要某个 DFA 状态对应的子集里包含 NFA 的任意一个终态这个 DFA 状态就是终态。对应这份源码里 NFA 终态为 n-1所以遍历 subsets 检查 set.count(n-1) 即可。输出 DFA 时我建议按 CSV 式格式打印每一行是一个 DFA 状态列出对每个字母表字符的后继编号这样后续用脚本做等价性验证会非常方便。这个实验给人最大的收获是把《编译原理》教材里的 ε 闭包定义变成了可运行的代码闭包计算用到栈、子集去重用到 set、BFS 用到队列一个实验把三种基础数据结构全过了一遍。实际调试时如果发现 DFA 状态数量明显异常比如接近 2 的 NFA 状态数次方优先检查 alphabet 是否完整再看 moveSet 是否漏掉了字符边。4. 递归下降与 LL(1) 预测分析自顶向下语法分析的两种落地姿势4.1 递归下降的直觉产生式怎么写的函数就怎么写递归下降分析法对学过 C 语言的人非常友好文法里有一条产生式 E - E T你就写一个叫 E 的函数函数体里先调用匹配 E 的代码、再读加号、再调用匹配 T 的代码。它的本质是把上下文无关文法的每个非终结符映射成一个递归函数函数之间通过互相调用来模拟推导过程。但这里有个硬约束文法不能有左递归。像 E - E T 这种产生式如果直接翻译成函数E 函数第一行就调用 E 函数自身连读取输入的机会都没有直接栈溢出死循环。所以实验里用的都是消除左递归之后的等价文法比如把 E - E T | T 改成 E - T { ( | -) T }也就是用循环代替左递归。对应实现是// 文法expr - term { (|-) term } // term - factor { (*|/) factor } // factor - number | (\expr) int expr() { int v term(); // 先读第一个 term while (lookahead || lookahead -) { char op lookahead; nextToken(); // 消费运算符 int rhs term(); v (op ) ? v rhs : v - rhs; } return v; }这段代码的逻辑是expr 函数先调用 term 获取左操作数然后循环检查当前 token 是不是加号或减号是就继续读右边的 term 并做运算。lookahead 是全局变量保存当前尚未消费的 tokennextToken 从词法分析产出的 token 流里取下一个。参数上term 和 expr 的返回值是整数只是为了让这个递归计算器能实际算出结果如果只是为了验证语法完全可以把返回类型改成 void只在函数里做匹配和报错。递归下降的特点是代码可读性极强每个函数对应一条产生式出错时能直接定位到是哪个非终结符的匹配逻辑出了问题。缺点是它要求文法满足 LL(1) 条件否则函数里的分支选择就要回溯实验一般不鼓励回溯实现所以更严谨的做法是走 LL(1) 预测分析表。4.2 LL(1) 的核心计算FIRST、FOLLOW 与预测分析表LL(1) 的“LL”是自左向右扫描、最左推导“1”表示每次决策只看一个前瞻符号。注意这里一个网上广泛流传的概念错误很多实验报告把 LL(1) 写成“自底向上的语法分析”这是硬伤。LL(1) 和递归下降同属自顶向下流派自底向上对应的是 LR 系列。区分标准很简单自顶向下是从开始符号出发往下推导自底向上是从输入符号串往上归约两者方向完全相反。LL(1) 分析器先要构造一张预测分析表 M[A][a]A 是非终结符a 是终结符或结束符。构造分两步第一步求所有非终结符的 FIRST 集合和 FOLLOW 集合第二步按规则填表。FIRST 集合的不动点迭代是常考点每个非终结符的 FIRST 是它所有产生式右部首符号能推出的终结符集合// FIRST 集合不动点迭代伪代码 bool changed true; while (changed) { changed false; for (auto rule : grammar) { char A rule.lhs; int before FIRST[A].size(); for (char X : rule.rhs) { if (isTerminal(X)) { FIRST[A].insert(X); break; } for (char t : FIRST[X]) { if (t ! EPS) FIRST[A].insert(t); } if (FIRST[X].count(EPS) 0) break; } if (FIRST[A].size() before) changed true; } }这段代码的终止条件是“所有 FIRST 集合都不再变化”called 循环可能要多轮才能收敛但集合元素只会增加不会减少所以最坏情况是文法符号数量的有限次迭代后必然停下。FOLLOW 集合的计算分三条规则开始符号的 FOLLOW 里加结束符、形如 A - αBβ 的产生式把 FIRST(β) 里除 ε 的元素加入 FOLLOW(B)、形如 A - αB 或 A - αBβ其中 ε ∈ FIRST(β)的产生式把 FOLLOW(A) 加入 FOLLOW(B)。这两套集合算完填表就只是个机械过程。4.3 栈驱动的表驱动分析循环预测分析表建好之后LL(1) 分析器本身用一个栈来模拟推导过程栈里初始放结束符和开始符号每次看栈顶元素和当前输入符号如果栈顶是终结符且与输入相同就弹出并前移输入指针如果栈顶是非终结符就查表取出应选的产生式把产生式右部逆序压栈表项为空则报语法错误。核心驱动代码stackchar st; st.push($); st.push(S); // S 为文法开始符号 int pos 0; string input idid*id$; while (!st.empty()) { char top st.top(); st.pop(); char cur input[pos]; if (top cur) { // 终结符匹配 pos; continue; } int ruleId table[{top, cur}]; if (ruleId 0) { // 表项为空语法错误 cerr 语法错误: 行 pos endl; break; } string rhs rules[ruleId].rhs; for (int i rhs.size() - 1; i 0; i--) { st.push(rhs[i]); } }代码里 table 用 mappairchar,char, int 实现ruleId 为 0 表示表项为空。压栈必须逆序这样下一个要处理的符号正好在栈顶。真正用于实验时建议把 stack 换成 stack 让终结符携带词法分析阶段的属性值这样 LL(1) 分析才能从“判断语法是否正确”升级成“同时生成抽象语法树”这也是往课程设计方向延伸的必经一步。从工程角度看递归下降和 LL(1) 表驱动各有优势递归下降代码好写、调试直观二三层函数递归能看到完整调用链LL(1) 表驱动把“决策逻辑”数据化只要分析表不变驱动代码可以复用到任意 LL(1) 文法上。杭电这个实验把两者分别写成独立文件正好构成对照实验每跑一次都能直观看到语法分析的两种姿势差异。5. 避坑与常见问题五个经典翻车点的现象、原因与解法一类实验源码最容易让人翻车的地方往往不在算法本身而在输入输出的边界处理。下面五条是我对着这份源码踩过的典型坑逐个给出现象、原因和解决方式。坑一块注释跨行导致词法分析结果错乱现象test.sy 里有一段从第 2 行开始的 /* 注释第 4 行才结束但 result.txt 里第 3 行的注释内容被当成代码识别输出了一堆莫名其妙的标识符和运算符。原因词法分析代码用 getline 循环逐行处理每次进入新的一行都认为注释已经结束没有维护跨行注释状态。解决在循环外声明 bool inBlockComment false每行扫描前先检查这个标志。若为 true则先在本行查找 */找到后把索引移到结束符之后并复位标志找不到则整行跳过。这个状态标志和自动机的“状态”是一回事只是它不在字符级而在行级。坑二epsilon 闭包计算死循环现象子集构造法程序运行后卡死CPU 占用率持续 100%控制台无输出。关掉后检查发现 graph.txt 里有一条从状态 1 到状态 1 的 ε 自环边。原因epsilonClosure 用递归或未去重的循环实现遇到 ε 环路时集合不断加入同一个状态永远无法稳定。解决闭包计算时用一个 set 记录已加入状态新状态只有在不存在于集合中时才入栈/入队。我上面的实现正是靠 S.count(e.first) 判断去重这个判断不能省。坑三FIRST 集合不动点迭代不收敛导致分析表全空现象LL(1) 分析器跑起来对任何输入都报语法错误打印预测分析表发现多个非终结符的行全为 0。原因文法里有 A - B 且 B - A 这样的间接循环依赖FIRST 集合迭代用单次遍历而不是循环直到稳定导致集合没有计算完整就停下。解决把单次遍历改成 while(changed) 的完整不动点迭代每轮结束后比对集合大小只要有任何增长就再跑一轮。这个循环最多跑“非终结符数量 × 产生式右部长度”量级的轮数不会拖慢程序。坑四预测分析表出现冲突项没被检测现象输入某些符号串时LL(1) 分析器行为反常时对时错调试很久才发现是分析表同一格子里填了两个产生式。原因文法本身不是 LL(1)比如产生式有公共左因子或者某个非终结符的 FIRST 和 FOLLOW 集合存在交集。填表代码没有冲突检测后填的覆盖了先填的。解决填表时对每个表项先判断是否已存在值若已被占用就打印冲突信息并指出是哪个产生式、哪个终结符。实验报告里写出这一步能额外加分因为它明确验证了“此文法是否为 LL(1)”这一结论。坑五Windows 下源码文件编码和回车符干扰识别现象代码在 Dev-C 或 VSCode 里编译运行词法分析器把行尾识别成奇怪字符或者字符串字面量总是多一个字符。原因源码或 test.sy 用 GBK 编码保存而输出到 result.txt 时按 UTF-8 解读中文注释或全角符号变成乱码同时 Windows 下文件行尾是 \r\ngetline 读出来的行尾会带 \risalpha 对 \r 判定失败。解决统一用 UTF-8 无 BOM 编码保存源码和文本文件如果是老项目迁移在读取字符串后手动去除行尾 \r或者在 g 编译时用 -stdc17 并确保编辑器配置正确。这个坑和算法无关但在实验环境中最常遇到建议一开始就检查右下角编码状态。6. 验证与调试把四个实验串成一条可复现的流水线拿到这套源码别急着改代码先按下面这张验证清单从原样运行开始确认每个 .exe 的输出符合预期再动手实验模块输入文件预期结果失败时重点排查词法分析test.syresult.txt 中八进制/十六进制正确标注块注释跨行、编码格式子集构造graph.txt控制台输出 DFA 状态数和转移表ε 回路死循环、字母表缺失递归下降控制台输入表达式可计算出结果并能输出推导过程左递归未消除LL(1) 分析LL1.cpp 内置输入串输出匹配成功/失败FIRST 集合不收敛、表冲突编译时我习惯用这条命令比 IDE 一键运行能看到更多警告信息g 词法分析.cpp -o 词法分析.exe -stdc17 -Wall-Wall 会提示未使用的变量和潜在类型问题实验代码量不大警告通常能直接指出问题行。VSCode 里配置 C/C 扩展后用这个命令做调试比 Dev-C 的图形化按钮更可控跑完再用 --run 选项避免测试结束后窗口秒关。我自己的调试习惯是把词法分析和 LL(1) 串起来测用一段带八进制常量、十六进制常量、两种注释的 test.sy 跑词法分析再把生成的 token 序列作为 LL(1) 的输入串跑语法匹配。比如构造一个包含“0x1F 077”的 SysY 代码片段词法阶段能区分十六进制和进制八进制语法阶段能正确处理加号两条链路就都验证了。进阶一点可以把 LL(1) 分析过程中选中的产生式按顺序打印出来这串产生式就是最左推导序列可以直接和递归下降的输出结果对照确认两个分析器对同一输入串的推导一致。这套实验做完之后我对编译器前端的理解从“背诵名词解释”变成了“能亲手画出状态迁移图、能解释清楚为什么 LL(1) 要求 FIRST 和 FOLLOW 不相交”。从那以后我拿到任何实验源码包都强制走同一套流程先原样运行一遍自带测试样例再逐模块拆输入输出格式最后才动手改代码。这习惯帮我避开了大部分“环境问题误当算法问题”的浪费时间操作。希望帮到你。本文还有配套的精品资源点击获取