尧图网页设计 
简介面向杭电编译原理课程学习者的实验源代码包用C完成并配有可直接运行的exe程序覆盖词法分析、NFA转DFA的子集构造法、递归下降分析与LL(1)语法分析等核心实验。资源包共11个文件包含4个C源文件、4个可执行程序、2个文本说明及1个SysY测试源文件整体仅334KB轻量便于下载与课程对照。已有1605人学习使用。借助源码、可运行程序与测试文件可直观比对运行结果理解词法识别、自动机转换及语法分析流程适合正在完成相关实验或复习编译原理重点内容的本专科学生参考。1. 编译原理实验的真相跑通一个词法分析器胜过抄十份源码杭电的编译原理实验普通安排在第三学年实验从词法分析做到语法分析有的班还要求做到中间代码生成或一个简易解释器默认语言是 C验收方式是现场编译、现场跑、现场答。每年这时候都有人到处找“源代码”应付结果在验收台上一问三不知——代码能跑人过不了。这篇文章不贴所谓“完整源码”而是把这项实验真正被检验的能力拆开讲你如何用 C 把一个正则表达式变成可执行的 DFA再把 DFA 变成递归下降的语法分析最后顺手产出四元式。适合正在做课设、想自己动手又怕走弯路的人。下面每一段代码都可以直接改造成你自己的坑也会逐个标出来。2. 杭电实验的三段式结构与 C 选型理由为什么不是一个“大编译器”2.1 实验为什么是“词法—语法—中间代码”三段而不是一个大编译器编译原理这门课课本从正则表达式讲到优化到最后“生成目标代码”只有薄薄一章。杭电这类教学型课程的实验排布也遵循同一个节奏词法分析对应教材第二章语法分析对应第三、四章中间代码生成对应第七章。这样拆开的好处是每一段都能单独验收、单独给分不会出现“前面错了后面全崩”的连锁反应。网上一搜“编译原理清华大学出版社第三版第二章答案”能搜出大量文档词法分析那章的习题答案满天飞但实验题和教材习题的重合度其实很低。实验考的是把状态机跑起来不是把课后题的表格画出来。常见做法是三个实验各占一个独立工程或者一个工程分三个编译宏开关。我见过不少同学把三段全部写进一个 main 函数最终代码超过一千行验收时导师随手改一个输入就崩。更稳的结构是实验一输出 token 流实验二吃 token 流输出语法树或直接报错实验三在语法分析过程中顺带输出四元式。三段之间的接口只有两个——Token 的 vector 和四元式的 vector。接口定好了每一段都可以单独改、单独测最后才串起来。这本身就是编译原理课程想让你体会的“阶段划分”思想。还有一个容易忽略的点实验二的输入不是源程序字符串而是实验一产出的 token 序列。很多人的语法分析器里还写字符扫描逻辑属于重复造轮子。验收时导师会问“你的语法分析器输入是什么”答“token 流”或“源代码字符串”都行但你的代码必须和答案一致。最怕的是词法分析器输出带格式的文本语法分析器再去解析那个文本中间多一层不稳定。直接用 C 的结构体 vector 传递内存里交接不要落地成文件再读回来能少踩一半坑。2.2 C 选型的真实理由STL、对象模型与工作量边界为什么课程默认 C 而不是 Python最直接的原因是编译器本身要处理“内存里的程序表示”——token、语法树、符号表这些用 C 的结构体和类表达最自然也最贴近教材里那些伪代码。另一个原因是杭电这类课程大多配的是 C 程序设计的先修课STL 里的 vector、string、unordered_map 足够覆盖词法分析和语法分析的所有数据结构需求不需要额外引入第三方库。用 Python 写确实快但验收现场的问答环节会围绕指针、引用、内存生命周期展开你用 Python 糊过去问题答不上来照样扣分。具体到数据结构选型三个核心容器就够了Token 用 struct 而不是 class避免一大堆访问器方法关键字表用 unordered_set 做 O(1) 查找四元式用 vector 顺序存储。符号表在实验阶段不需要哈希表一个 vectorpairstring, string 记录“名字 → 类型”就够等做到中间代码生成时再用 unordered_map 加速查找。我一般会提醒第一次写的人不要一开始就设计 Visitor 模式、抽象语法树基类这些教科书里的高级玩意儿课设工作量摆在那里简单直接的数据结构反而更容易通过验收。还有一个现实原因C 的调试工具链成熟。实验一的状态机出错可以用 gdb 打断点看当前状态值实验二的递归下降函数栈天然对应文法推导过程栈顶函数就是当前正在展开的非终结符。这些在答辩时要讲给导师听也是加分点。相比之下 Python 的递归栈信息对语法错误定位帮助有限解释器的动态类型还会让“类型存错”这类问题延迟暴露。用 C 写编译原理实验本质上是把你前两年学的内存、指针、STL 全部复用一遍这是这门课隐藏的考察目标。2.3 验收现场看什么代码能跑只是及格线现场问答才是拉分项杭电编译原理实验的评分大致是“功能分 代码质量分 答辩分”的结构。功能分看测试用例是否通过这部分代码能跑就有代码质量分看状态转移表是不是写死的、有没有魔数、报错信息是否带行列号答辩分最直接——导师会随机指一个函数问你“这段在干什么”或者给你一个新的关键字让你当场加进去。很多人的源代码是从学长那里拷来的功能全对但导师指着 DFA 最小化函数问“这个 partition 为什么按终态和非终态分组”就答不上来了。这一章想说的核心是把实验拆成三段每段都用最朴素的数据结构实现保留足够多的注释和中间打印这些才是答辩时的素材。下一章开始进入第一段词法分析器——这里也是全文代码量最大、坑最密集的部分。3. 用 C 写词法分析器Token 定义、状态转移表与 DFA 最小化落地3.1 先定义 Token 与符号表头文件里不急着写状态机很多人的第一个错误是上来就写状态转移逻辑Token 类型只用一个整数表示。结果是报错信息只能输出“第 10 行有错”说不出错在哪个词、哪一列。实验一的评分标准里通常有“错误定位”这一项所以 Token 结构体里必须带行列号。我习惯在 token.h 里这样定义// token.h实验一、实验二共用不要改动接口 #ifndef TOKEN_H #define TOKEN_H #include string enum TokenType { T_KEYWORD, // int, float, if, else, while, return ... T_IDENTIFIER, // 变量名、函数名 T_CONSTANT, // 整数、浮点数常量 T_OPERATOR, // - * / ! T_DELIMITER, // ; ( ) { } , T_EOF // 文件结束 }; struct Token { TokenType type; std::string lexeme; // 原始字符串比如 while int line; // 行号从 1 开始 int col; // 列号从 1 开始 }; #endif逻辑说明lexeme存原始文本line和col用于报错定位。enum 按顺序排列测试时可以写switch(token.type)按类型处理EnumClass 在这里反而啰嗦。你可能会想加double value字段存常量数值但实验阶段不建议加——解析数值是语法分析的事词法分析只负责切出“这是一个数字常量”不做类型转换。加了反而让词法分析器和语法分析器的职责边界模糊答辩时容易被追问。关键字表单独放一个文件。注意“c字符串数组初始化”这个热搜词对应的需求就在这里——很多人会在 main 里写一个巨大的if-else if链判断关键字那是坏味道。正确的是先按标识符读入完整单词再查哈希表// keywords.h #pragma once #include string #include unordered_set static const std::unordered_setstd::string kKeywords { int, float, double, char, if, else, while, do, for, return, void, break, continue };逻辑说明词法扫描读到一串字母先认为它是标识符读完之后去kKeywords里查一次命中就把 type 改成T_KEYWORD。这就是“最长匹配 关键字表回查”的标准做法下一节展开讲。static const放在头文件里多个源文件包含时各自持有一份副本对实验规模来说无所谓但记住了这比你用#define宏定义关键字数组要正规得多。3.2 状态转移表的两种组织方式二维数组与 switch-case 的取舍词法分析器的核心是一个 DFA。教材里画状态图代码里要落地常见两种做法二维数组转移表或者 switch-case 硬编码。二维数组更接近教材适合写在实验报告里switch-case 迭代更快但代码冗长。我推荐二维数组因为验收时导师会问“你的 DFA 怎么表示的”你指着一张小表格讲状态迁移比在一百行 switch 里翻 case 要清楚得多。先定义字符类别。注意这里决定转移表有多少列类别分得越细表越精确但写起来越烦。实验规模下分 5 类就够字母、数字、运算符、空白、其他。列的顺序要固定全文件统一// dfa_table.cpp状态转移表-1 表示非法转移 // 行索引 状态编号列索引 字符类别 // 列定义0字母 1数字 2运算符 3空白 4其他 static const int kClassCount 5; static const int kStateCount 8; static const int kDfa[kStateCount][kClassCount] { // S0 字母 数字 运算符 空白 其他 /* 0 */ { 1, 2, 3, 0, -1 }, /* 1 */ { 1, 1, -1, -1, -1 }, // 标识符/关键字 /* 2 */ {-1, 2, -1, -1, -1 }, // 整数常量 /* 3 */ {-1, -1, -1, -1, -1 }, // 运算符按实际运算符扩展 // 状态 4-7 留给多字符运算符如 ! };逻辑说明状态 0 是起始态。读到字母进状态 1状态 1 里继续读字母或数字都留在状态 1读到非字母数字就结束一个词读到数字进状态 2状态 2 只接受数字。运算符相关状态这里简写成一行真正实现时需要两个字符才能判定所以状态 3 读到要进状态 4状态 4 读到才输出T_OPERATOR。这正好对应教材里“识别 和 的区别”那道经典题。主扫描循环用一个char前看字符。注意 C 里peek()和get()的处理很多翻车都发生在“读了一个字符没放回去”。我习惯用一个int lookahead变量保存当前字符循环体开头判断// scanner.cpp主扫描循环骨架 // 每次调用 NextToken() 返回一个 Token文件读完返回 T_EOF Token NextToken() { SkipWhitespace(); // 跳过空白内部维护行号列号 int line currentLine, col currentCol; int state 0; std::string lexeme; while (state ! -1) { int ch GetChar(); // 读取一个字符-1 表示 EOF int cls CharClass(ch); // 映射到 0-4 的类别 int next kDfa[state][cls]; if (next -1) { UngetChar(); // 撤销读取词不在状态机的接受范围内 break; } lexeme.push_back((char)ch); state next; } return MakeToken(state, lexeme, line, col); }逻辑说明SkipWhitespace()负责跳过空格、制表符、换行并在跳过时累计currentLine和currentCol这样 Token 不用额外保存位置信息就能定位。CharClass()把字符映射成 0 到 4 的整数字母和数字用std::isalpha/std::isdigit判断运算符用一个 switch 匹配 - * / !。UngetChar()是关键——DFA 在某个状态发现下一个字符无转移时这个字符属于下一个 Token必须放回输入流。漏掉这一步词法分析器会丢掉字符最常见的现象是int a1;里的a后面直接跟时被吞掉。你可能会问如果状态 1 是接受态但当前字符已经读过头了怎么办这正好是“最长匹配”的实现要领——不要一看到接受态就立刻返回要继续读直到无转移为止。状态 1 里读字母或数字都留在状态 1所以abc123会被完整读成一个标识符而不是先输出abc再输出123。教材里这一点只写在图注里代码里实现错的人非常多。3.3 DFA 最小化划分法的 C 实现与验收加分点杭电的实验一通常有“对 DFA 进行化简”的加分要求做法是等价类划分。原理很简单把所有状态按“是否为终态”分成两组然后反复检查——如果两个状态在同一组里对任意输入字符它们跳转到的状态必须也在同一组否则分裂。直到没有组能再分裂同一组的状态就可以合并最终得到一个状态数最少的 DFA。用 C 实现的核心是维护一个vectorint group数组group[i]表示状态 i 当前属于哪一组// minimize.cpp等价类划分法的核心循环 #include vector #include map // states 里标记了每个状态是否为终态trans是原始转移表 std::vectorint MinimizeDfa(const std::vectorint isFinal, const std::vectorstd::vectorint trans) { int n isFinal.size(); std::vectorint group(n, 0); int groupCount 2; for (int i 0; i n; i) group[i] isFinal[i] ? 1 : 0; // 初始分组终态/非终态 bool changed true; while (changed) { changed false; std::mapint, std::vectorint split; // 新分组结果 for (int state 0; state n; state) { // 对每个状态算出一个“签名”对每个输入字符去到的组号 std::vectorint signature; for (int cls 0; cls kClassCount; cls) { int target trans[state][cls]; signature.push_back(target -1 ? -1 : group[target]); } // 签名按顺序拼起来用 map 收集同签名状态 int key 0; for (int sig : signature) key key * 10 (sig 1); split[key].push_back(state); } if (split.size() groupCount) { changed true; groupCount split.size(); int g 0; std::vectorint newGroup(n, 0); for (auto [key, statesInGroup] : split) for (int s : statesInGroup) newGroup[s] g; group newGroup; } } return group; }逻辑说明签名的构造是整个算法的灵魂。两个状态等价的前提是对每个字符类别都跳到等价的状态这个“跳去哪一组”的序列就是签名。用mapint, vectorint收集签名相同的状态一组就对应合并后的一个新状态。key的计算方式只是把签名序列压成一个整数避免用vectorint直接做 map 键的繁琐写法如果字符类别超过 5 类这个压法可能会溢出改用std::mapstd::vectorint, std::vectorint就行了。参数说明isFinal数组里1表示终态0表示非终态trans就是上一节的kDfa转移表。最小化之后你还需要根据group数组重新生成一张更小的转移表这一步没什么难度把group映射到新状态编号即可。答辩时导师会问你“初始分组为什么只分两组”答案是非终态和终态不可能等价因为终态意味着“识别完一个词”非终态不是。这个问题的标准答法就是这句话先背住。这里有一个常见的翻车点最小化合并状态后老的起始态 group 编号不一定是 0新表的起始态对应group[0]。很多人合并完直接拿 0 当起始态结果识别全部错位状态数倒是少了一个词也认不出来了。正确做法是先查group[0]得到新起始态编号再重新标记。4. 语法分析选递归下降还是 LR 表驱动C 代码骨架与四元式生成4.1 选递归下降的三个理由代码量、报错质量与提问环节语法分析是编译原理实验里争议最大的一段。教材花了三章讲 LL(1)、LR(0)、SLR(1)、LR(1) 的自动机构造实验课上真正动手写时大多数人会问到底手写递归下降还是先构造分析表再写驱动我的建议很明确选递归下降。原因有三第一代码量少一个量级LL(1) 分析表需要手动计算 FIRST 和 FOLLOW写错一个集合整张表就废了而递归下降的每个函数对应一个非终结符出错时函数调用栈直接告诉你“正在展开哪个非终结符”。第二报错质量高递归下降天然知道当前期望什么能输出“第 12 行期望 运算符 实际看到标识符 a”这种带上下文的信息。第三答辩环节导师更愿意问递归下降——因为每个函数都能指着讲而 LR 分析表驱动是一个大循环加一张表讲不出太多代码设计。这里要澄清一个误区实验要求是“语法分析器”而不是“必须用 LR”。杭电的编译原理课讲 LR 是重点但那是理论课的重点实验课的验收标准是“能正确判断合法/非法程序并给出合理报错”。递归下降是文法 LL 的子集但课设语言的文法完全可以用 LL 描述。如果你对 LR 自动机构造有执念可以额外写一份 SLR(1) 分析表生成器作为加分项而不是替换递归下降。两条路都做的人也有但那是拿优秀项目的节奏普通目标没必要。4.2 一个能跑通表达式与赋值语句的递归下降骨架先定义实验语言的文法。我按常见的课设规模取一个子集覆盖赋值、算术表达式、括号和分号program → stmt_list stmt_list → stmt stmt_list | ε stmt → if_stmt | assign_stmt | expr_stmt assign_stmt → ID expr ; expr_stmt → expr ; expr → term ( term | - term )* term → factor ( * factor | / factor )* factor → ID | NUM | ( expr )这个文法已经是 EBNF 形式(...)*表示循环消除了左递归。递归下降就是让每个非终结符对应一个 bool 函数返回 true 表示解析成功// parser.h递归下降语法分析器 #include token.h #include vector class Parser { public: explicit Parser(const std::vectorToken tokens) : tokens_(tokens), pos_(0) {} bool ParseProgram() { while (!Check(T_EOF)) { if (!ParseStatement()) { ReportError(非法语句); return false; } } return true; } private: bool ParseStatement() { // if 开头走 if 分支ID 后跟 走赋值否则按表达式语句处理 if (Check(T_KEYWORD) Current().lexeme if) return ParseIf(); if (Check(T_IDENTIFIER) PeekNext().type T_OPERATOR PeekNext().lexeme ) return ParseAssign(); return ParseExprStmt(); } bool ParseAssign() { Advance(); // 吃掉 ID Advance(); // 吃掉 if (!ParseExpr()) return false; if (!Match(T_DELIMITER, ;)) { ReportError(赋值语句末尾缺少分号); return false; } return true; } bool ParseExpr() { if (!ParseTerm()) return false; while (Match(T_OPERATOR, ) || Match(T_OPERATOR, -)) { if (!ParseTerm()) return false; } return true; } bool ParseTerm() { if (!ParseFactor()) return false; while (Match(T_OPERATOR, *) || Match(T_OPERATOR, /)) { if (!ParseFactor()) return false; } return true; } bool ParseFactor() { if (Match(T_IDENTIFIER)) return true; if (Match(T_CONSTANT)) return true; if (Match(T_DELIMITER, ()) { if (!ParseExpr()) return false; return Match(T_DELIMITER, )); } ReportError(期望标识符、常量或左括号); return false; } // Check / PeekNext / Match / Advance / Current 是辅助函数下一节补全 };逻辑说明ParseExpr对应term ( term | - term )*先调ParseTerm解析第一个因子再用 while 循环处理或-的重复。这个结构的巧妙之处在于运算符优先级是嵌套在调用层级里的——expr调termterm调factor所以a b * c会被正确解析成a (b * c)。如果你把加减乘除都写在同一个函数里平铺循环优先级就会变成从左到右这是新手最容易翻车的地方。补充一个细节ParseStatement里的“ID 后跟 ”判断依赖PeekNext()提前看下一个 token。如果当前是 ID 而下一个是这是赋值语句否则是表达式语句。这种“前看两个 token”的判断在递归下降里很常见代价是代码里要多写几个辅助函数但能避免回溯。回溯在递归下降里是灾难——它会把报错信息变混乱因为你不知道哪个分支才是对的。辅助函数的关键实现// parser_helpers.cppParser 内部辅助函数 bool Check(TokenType type) const { return pos_ tokens_.size() tokens_[pos_].type type; } bool Match(TokenType type, const std::string lexeme) { if (pos_ tokens_.size() tokens_[pos_].type type tokens_[pos_].lexeme lexeme) { pos_; return true; } return false; } const Token PeekNext() const { // 越界时返回一个静态的 EOF Token避免写 if 判断 static const Token kEof { T_EOF, , -1, -1 }; return pos_ 1 tokens_.size() ? tokens_[pos_ 1] : kEof; }参数说明Match是递归下降里最常用的函数它既做“当前 token 是否符合预期”的判断又做“吃掉 token”的动作。PeekNext返回一个静态的kEof来兜底越界这是 C 里避免“返回引用指向局部变量”的惯用写法。很多人的段错误就出在这里——PeekNext直接返回tokens_[pos_ 1]而 pos_ 已经在最后一个 token 上越界访问。用静态对象的引用做兜底一劳永逸。4.3 左递归消除与优先级把文法改写成 EBNF 再落成 C 的步骤教材里的表达式文法长这样E → E T | T T → T * F | F F → ( E ) | id | num这个文法是正确的上下文无关文法但不能直接写递归下降因为ParseE的第一行就要调ParseE无限递归。消除左递归的标准做法是改写为右递归或 EBNF 循环。右递归版本是E → T E E → T E | ε对应的 C 要写两个函数ParseE和ParseEPrime其中ParseEPrime先判断当前 token 是不是是就继续不是就返回 true空串。这个写法正确但别扭因为 ε 分支让代码多一层而循环版本更直观// 把 E → E T | T 变成 while 循环 bool ParseE() { ParseT(); while (NextIsPlus()) { Advance(); ParseT(); } return true; }两种写法在功能上等价但循环版本的处理顺序和代码阅读体验更好。EBNF 里的*本质上就是 while 循环所以我在实验语言里直接用 EBNF 定义文法省去“手动消左递归”这一步。写报告时把文法定义成 EBNF代码和报告完全对应答辩时不用额外解释“E 对应哪个函数”。优先级处理的要诀一句话优先级越低的运算对应越外层的函数。加减在最外层ParseExpr乘除在中间层ParseTerm括号和因子在最里层ParseFactor。如果你想加一元负号-a在ParseFactor里加一个分支想加幂运算a ^ b结合性是右结合优先级高于乘除需要加一个比ParseTerm更深的ParsePower且循环里不能简单 while——右结合要用递归而不是循环实现。这属于进阶扩展实验能跑通加减乘除和括号就已经覆盖大纲要求。4.4 顺手生成四元式把语法制导翻译嵌进下降函数里很多实验要求“在语法分析过程中生成中间代码”也就是语法制导翻译。做法很朴素在递归下降的循环里每归约一个产生式就往四元式数组里 push 一条。先是四元式的结构定义// quad.h四元式定义与输出 #include string #include vector struct Quad { std::string op; // 运算符 - * / JMP JZ std::string arg1; // 左操作数 std::string arg2; // 右操作数可空 std::string result; // 结果变量或跳转目标 }; static std::vectorQuad g_quads; // 全局四元式表实验规模够用 static int g_tempIndex 0; std::string NewTemp() { return t std::to_string(g_tempIndex); }逻辑说明NewTemp()生成形如t1、t2的临时变量名。全局变量在课设规模是能接受的省去到处传引用的麻烦但答辩时你最好补一句“真实项目不会用全局变量这里为了实验简洁”。这句话能显得你懂工程实践。四元式的输出格式通常要求对齐打印报告里贴出来像这样1: a b t1 2: * t1 c t2然后把生成逻辑嵌进ParseTerm。原来的ParseTerm只做“是否匹配”现在要让ParseFactor返回操作数的名字在循环里生成临时变量// parser_translate.cpp在 ParseTerm 里生成算术四元式 std::string ParseTerm() { std::string left ParseFactorValue(); // 返回 a 或 3 或临时变量名 while (Match(T_OPERATOR, *) || Match(T_OPERATOR, /)) { std::string op Previous().lexeme; // 上一轮 Match 吃掉的运算符 std::string right ParseFactorValue(); std::string result NewTemp(); g_quads.push_back({op, left, right, result}); left result; // 关键链式运算的左手边更新 } return left; }逻辑说明a * b * c的翻译过程是——第一次循环生成* a b t1第二次循环左手边从a变成了t1生成* t1 c t2。这个“左手边更新”是四元式生成最容易漏的一步。漏掉的话输出会变成* a b t1和* a c t2两个计算互不关联c直接参与乘法中间结果t1被丢弃。实验验收时导师只要拿a * b * c一跑就能看出来。赋值语句的翻译更简单。ParseAssign里解析完表达式拿到右边结果直接生成一条四元式// 赋值语句的翻译 bool ParseAssign() { std::string name Current().lexeme; // 变量名 Advance(); // 吃掉 ID Advance(); // 吃掉 std::string value ParseExprValue(); g_quads.push_back({, value, , name}); Match(T_DELIMITER, ;); // 吃掉分号 return true; }逻辑说明四元式 value name表示把value赋值给namearg2 留空。跳转相关的四元式if 语句的JZ需要回填处理这放下一章讲因为回填是坑最密集的地方。5. 编译原理实验常见问题与排查源代码跑不起来先查这五处5.1 一运行就段错误数组越界还是对象生命周期问题现象输入一个最简单的int a 1;程序直接崩终端打印 Segmentation fault没有任何报错信息。用 gdb 打断点在 main 函数入口逐行执行到第二次调用NextToken()时崩溃。原因PeekNext()或扫描循环里越界访问 token 数组。最常见的是词法分析器在UngetChar()的实现上出错——用一个字符变量保存“回退的字符”结果连续回退两次把变量覆盖了输入流错位。语法分析器那边则是pos_已经等于tokens_.size()还去访问tokens_[pos_ 1]。解决给所有辅助函数加边界检查。PeekNext()用静态 EOF Token 兜底Check()和Match()里先判断pos_ tokens_.size()。词法分析器的UngetChar()用一个独立栈保存回退字符不要用单一变量回退两个字符的情况在识别和时一定会出现。写完这两处段错误基本绝迹。5.2 关键字被当成标识符最长匹配的扫描顺序错了现象输入int a;词法输出第一个 token 是T_IDENTIFIERlexeme 是int而不是T_KEYWORD。语法分析器看到int不是标识符报“非法语句”。原因扫描循环在状态 1标识符状态里遇到空白字符时DFA 无转移直接返回了 token类型标记为标识符没有查关键字表。这是扫描逻辑顺序问题——三个动作的先后必须是“读完整词 → 查关键字表 → 决定类型”而不是“在状态机里提前判断”。解决在MakeToken里加上关键字表回查// MakeToken状态机识别完成后统一处理 Token MakeToken(int state, const std::string lexeme, int line, int col) { Token tok; tok.lexeme lexeme; tok.line line; tok.col col; if (state 1) { auto it kKeywords.find(lexeme); tok.type (it ! kKeywords.end()) ? T_KEYWORD : T_IDENTIFIER; } else if (state 2) { tok.type T_CONSTANT; } else { tok.type T_OPERATOR; } return tok; }逻辑说明只有走出状态 1 的词才可能是关键字所以只在state 1时查表。有些人的做法是在扫描循环里每个字符都判断“当前字符串是不是关键字”那是错的——intx的前两个字符构不成int就漏判而且会误判in。查表必须在完整读词后进行。5.3 递归下降死循环空产生式与 EOF 边界没处理现象程序跑起来不崩溃但也不结束CPU 占用 100%像是卡死了。打印日志发现ParseProgram无限调用ParseStatement而ParseStatement返回 true 但pos_没变。原因文法里有stmt → ε空产生式但代码里没处理“当前 token 不属于 stmt 的 FIRST 集就退出”的情况。典型场景是输入文件末尾多了一个换行词法分析器没有输出 T_EOF语法分析器拿到空 token 流每轮都匹配失败但也不报错pos_ 永远是 0。解决ParseProgram的循环条件必须是!Check(T_EOF)并且ParseStatement里所有分支都不匹配时直接返回 false 让外层报错退出不要静默返回 true。另一个检查点是词法分析器文件读取到末尾必须显式输出一个T_EOFtoken而不是返回空 vector。养成写好这两个边界的习惯死循环基本不会出现。5.4 四元式跳转目标全是 -1迭代器失效还是回填时机错现象if (a b) c 1;生成的中间代码里JZ四元式的result是-1或者空字符串只有if没有跳转目标中间代码无法继续处理。原因if 语句的翻译需要在生成条件表达式之后、生成语句体之前先留一条JZ四元式等语句体生成完再把实际跳转标签填回去。很多人的代码是这样写的auto quad g_quads.back();拿到引用然后 push 更多四元式回头再改quad——g_quads是std::vectorpush 导致扩容引用失效回填全部落空。解决不要存引用存下标。回填时用下标访问// 正确的回填方式存下标而不是存引用 int jumpIndex g_quads.size(); g_quads.push_back({JZ, condResult, , }); // result 待回填 ParseStatement(); // 生成语句体的四元式 g_quads[jumpIndex].result L std::to_string(label);逻辑说明jumpIndex是size_t类型在 push 之后依然有效。回填的本质是“先占位后补地址”这是编译原理教材里明确讲的案例代码里用下标实现最稳妥。另一个常见错误是回填的标签编号冲突——if 和 while 都用一个label全局计数器就没问题如果每个分支里单独初始化计数器标签就会重复跳转全乱。5.5 中文注释与文件编码VSCode 配置下 C 源码的常见翻车现象代码在本机 Visual Studio 或 VSCode 里编译运行正常拿到实验室的 Linux 机器上一编译注释乱码或者词法分析器把中文注释里的字符当成非法输入直接报错。原因Windows 下 VSCode 默认可能是 GBK 编码保存源文件Linux 的 GCC 默认按 UTF-8 解析。注释里的中文变成乱码还算小事字符串或注释里的全角符号比如中文分号“”会被词法分析器的CharClass映射成“其他”类别触发非法字符报错。解决统一编码。VSCode 里点右下角编码按钮选择“通过编码保存”为 UTF-8。编译命令加参数指定输入编码g -finput-charsetUTF-8 -stdc17 main.cpp。词法分析器这边CharClass里对“其他”类别的处理要输出明确报错带上行列号而不是静默跳过——静默跳过会让非法字符凭空消失程序“能跑”但行为错误。这条属于环境坑和编译原理本身无关但每年都有不少人死在验收前的最后一步。6. 用随机用例验证整条流水线一份能自证正确的最小测试方案实验做完后最重要的一个习惯是不要用手敲的三五个用例验证。手敲用例覆盖不到上下文边界比如a*bc和a*(bc)的优先级差异再比如if嵌套while。我建议写一个最简单的随机程序生成器批量生成合法程序再准备一小批非法的跑全链路验证。// test_generator.cpp生成随机合法程序用于回归 // 用法./generator 100 | ./compiler --parse // 100 表示生成 100 条语句 #include cstdlib #include iostream #include string #include vector std::string RandExpr(int depth) { if (depth 0) { return (rand() % 2) ? a : std::to_string(rand() % 100); } int op rand() % 4; const char* ops[] {, -, *, /}; std::string l RandExpr(depth - 1); std::string r RandExpr(depth - 1); return ( l ops[op] r ); } int main(int argc, char* argv[]) { int n argc 1 ? std::atoi(argv[1]) : 100; srand(42); // 固定种子保证可复现 for (int i 0; i n; i) { if (rand() % 3 0) { std::cout a RandExpr(3) ;\n; } else { std::cout b RandExpr(2) ;\n; } } return 0; }逻辑说明固定随机种子 42 保证每次生成的用例完全一致这是可复现测试的底线。RandExpr用递归深度控制表达式嵌套深度 3 会生成类似((a 3) * (b - 8))的结构覆盖括号和运算符优先级。为什么用(expr op expr)而非expr op expr为了让生成的表达式总是带括号避免优先级歧义把“合法程序”误判成“非法”。测试生成器只负责制造合法输入不该制造边界争议。随机合法程序能验证“不该报错时别报错”但还要准备非法样例验证报错路径缺分号、括号不匹配、a 1这类运算符连续、空文件、只有注释、超长标识符。这些样例应该手写放进一个invalid_cases/目录一条条跑确认每条都报错且报错位置合理。我的习惯是保留三份固定文件valid_min.txt最小合法集、valid_random.txt随机生成、invalid_cases.txt非法样例每次改完代码都先跑这三份再提交这个习惯帮我躲过了至少三次验收现场翻车。最后说一句编译原理实验的价值不在源码本身而在于你亲手把“字符串变成结构化表示”这个过程走了一遍这套思维在以后写解释器、写 DSL、做静态分析时都会回来找你。希望帮到你。本文还有配套的精品资源点击获取 编译原理实验指南：用C++实现词法分析、递归下降与四元式生成
简介面向杭电编译原理课程学习者的实验源代码包用C完成并配有可直接运行的exe程序覆盖词法分析、NFA转DFA的子集构造法、递归下降分析与LL(1)语法分析等核心实验。资源包共11个文件包含4个C源文件、4个可执行程序、2个文本说明及1个SysY测试源文件整体仅334KB轻量便于下载与课程对照。已有1605人学习使用。借助源码、可运行程序与测试文件可直观比对运行结果理解词法识别、自动机转换及语法分析流程适合正在完成相关实验或复习编译原理重点内容的本专科学生参考。1. 编译原理实验的真相跑通一个词法分析器胜过抄十份源码杭电的编译原理实验普通安排在第三学年实验从词法分析做到语法分析有的班还要求做到中间代码生成或一个简易解释器默认语言是 C验收方式是现场编译、现场跑、现场答。每年这时候都有人到处找“源代码”应付结果在验收台上一问三不知——代码能跑人过不了。这篇文章不贴所谓“完整源码”而是把这项实验真正被检验的能力拆开讲你如何用 C 把一个正则表达式变成可执行的 DFA再把 DFA 变成递归下降的语法分析最后顺手产出四元式。适合正在做课设、想自己动手又怕走弯路的人。下面每一段代码都可以直接改造成你自己的坑也会逐个标出来。2. 杭电实验的三段式结构与 C 选型理由为什么不是一个“大编译器”2.1 实验为什么是“词法—语法—中间代码”三段而不是一个大编译器编译原理这门课课本从正则表达式讲到优化到最后“生成目标代码”只有薄薄一章。杭电这类教学型课程的实验排布也遵循同一个节奏词法分析对应教材第二章语法分析对应第三、四章中间代码生成对应第七章。这样拆开的好处是每一段都能单独验收、单独给分不会出现“前面错了后面全崩”的连锁反应。网上一搜“编译原理清华大学出版社第三版第二章答案”能搜出大量文档词法分析那章的习题答案满天飞但实验题和教材习题的重合度其实很低。实验考的是把状态机跑起来不是把课后题的表格画出来。常见做法是三个实验各占一个独立工程或者一个工程分三个编译宏开关。我见过不少同学把三段全部写进一个 main 函数最终代码超过一千行验收时导师随手改一个输入就崩。更稳的结构是实验一输出 token 流实验二吃 token 流输出语法树或直接报错实验三在语法分析过程中顺带输出四元式。三段之间的接口只有两个——Token 的 vector 和四元式的 vector。接口定好了每一段都可以单独改、单独测最后才串起来。这本身就是编译原理课程想让你体会的“阶段划分”思想。还有一个容易忽略的点实验二的输入不是源程序字符串而是实验一产出的 token 序列。很多人的语法分析器里还写字符扫描逻辑属于重复造轮子。验收时导师会问“你的语法分析器输入是什么”答“token 流”或“源代码字符串”都行但你的代码必须和答案一致。最怕的是词法分析器输出带格式的文本语法分析器再去解析那个文本中间多一层不稳定。直接用 C 的结构体 vector 传递内存里交接不要落地成文件再读回来能少踩一半坑。2.2 C 选型的真实理由STL、对象模型与工作量边界为什么课程默认 C 而不是 Python最直接的原因是编译器本身要处理“内存里的程序表示”——token、语法树、符号表这些用 C 的结构体和类表达最自然也最贴近教材里那些伪代码。另一个原因是杭电这类课程大多配的是 C 程序设计的先修课STL 里的 vector、string、unordered_map 足够覆盖词法分析和语法分析的所有数据结构需求不需要额外引入第三方库。用 Python 写确实快但验收现场的问答环节会围绕指针、引用、内存生命周期展开你用 Python 糊过去问题答不上来照样扣分。具体到数据结构选型三个核心容器就够了Token 用 struct 而不是 class避免一大堆访问器方法关键字表用 unordered_set 做 O(1) 查找四元式用 vector 顺序存储。符号表在实验阶段不需要哈希表一个 vectorpairstring, string 记录“名字 → 类型”就够等做到中间代码生成时再用 unordered_map 加速查找。我一般会提醒第一次写的人不要一开始就设计 Visitor 模式、抽象语法树基类这些教科书里的高级玩意儿课设工作量摆在那里简单直接的数据结构反而更容易通过验收。还有一个现实原因C 的调试工具链成熟。实验一的状态机出错可以用 gdb 打断点看当前状态值实验二的递归下降函数栈天然对应文法推导过程栈顶函数就是当前正在展开的非终结符。这些在答辩时要讲给导师听也是加分点。相比之下 Python 的递归栈信息对语法错误定位帮助有限解释器的动态类型还会让“类型存错”这类问题延迟暴露。用 C 写编译原理实验本质上是把你前两年学的内存、指针、STL 全部复用一遍这是这门课隐藏的考察目标。2.3 验收现场看什么代码能跑只是及格线现场问答才是拉分项杭电编译原理实验的评分大致是“功能分 代码质量分 答辩分”的结构。功能分看测试用例是否通过这部分代码能跑就有代码质量分看状态转移表是不是写死的、有没有魔数、报错信息是否带行列号答辩分最直接——导师会随机指一个函数问你“这段在干什么”或者给你一个新的关键字让你当场加进去。很多人的源代码是从学长那里拷来的功能全对但导师指着 DFA 最小化函数问“这个 partition 为什么按终态和非终态分组”就答不上来了。这一章想说的核心是把实验拆成三段每段都用最朴素的数据结构实现保留足够多的注释和中间打印这些才是答辩时的素材。下一章开始进入第一段词法分析器——这里也是全文代码量最大、坑最密集的部分。3. 用 C 写词法分析器Token 定义、状态转移表与 DFA 最小化落地3.1 先定义 Token 与符号表头文件里不急着写状态机很多人的第一个错误是上来就写状态转移逻辑Token 类型只用一个整数表示。结果是报错信息只能输出“第 10 行有错”说不出错在哪个词、哪一列。实验一的评分标准里通常有“错误定位”这一项所以 Token 结构体里必须带行列号。我习惯在 token.h 里这样定义// token.h实验一、实验二共用不要改动接口 #ifndef TOKEN_H #define TOKEN_H #include string enum TokenType { T_KEYWORD, // int, float, if, else, while, return ... T_IDENTIFIER, // 变量名、函数名 T_CONSTANT, // 整数、浮点数常量 T_OPERATOR, // - * / ! T_DELIMITER, // ; ( ) { } , T_EOF // 文件结束 }; struct Token { TokenType type; std::string lexeme; // 原始字符串比如 while int line; // 行号从 1 开始 int col; // 列号从 1 开始 }; #endif逻辑说明lexeme存原始文本line和col用于报错定位。enum 按顺序排列测试时可以写switch(token.type)按类型处理EnumClass 在这里反而啰嗦。你可能会想加double value字段存常量数值但实验阶段不建议加——解析数值是语法分析的事词法分析只负责切出“这是一个数字常量”不做类型转换。加了反而让词法分析器和语法分析器的职责边界模糊答辩时容易被追问。关键字表单独放一个文件。注意“c字符串数组初始化”这个热搜词对应的需求就在这里——很多人会在 main 里写一个巨大的if-else if链判断关键字那是坏味道。正确的是先按标识符读入完整单词再查哈希表// keywords.h #pragma once #include string #include unordered_set static const std::unordered_setstd::string kKeywords { int, float, double, char, if, else, while, do, for, return, void, break, continue };逻辑说明词法扫描读到一串字母先认为它是标识符读完之后去kKeywords里查一次命中就把 type 改成T_KEYWORD。这就是“最长匹配 关键字表回查”的标准做法下一节展开讲。static const放在头文件里多个源文件包含时各自持有一份副本对实验规模来说无所谓但记住了这比你用#define宏定义关键字数组要正规得多。3.2 状态转移表的两种组织方式二维数组与 switch-case 的取舍词法分析器的核心是一个 DFA。教材里画状态图代码里要落地常见两种做法二维数组转移表或者 switch-case 硬编码。二维数组更接近教材适合写在实验报告里switch-case 迭代更快但代码冗长。我推荐二维数组因为验收时导师会问“你的 DFA 怎么表示的”你指着一张小表格讲状态迁移比在一百行 switch 里翻 case 要清楚得多。先定义字符类别。注意这里决定转移表有多少列类别分得越细表越精确但写起来越烦。实验规模下分 5 类就够字母、数字、运算符、空白、其他。列的顺序要固定全文件统一// dfa_table.cpp状态转移表-1 表示非法转移 // 行索引 状态编号列索引 字符类别 // 列定义0字母 1数字 2运算符 3空白 4其他 static const int kClassCount 5; static const int kStateCount 8; static const int kDfa[kStateCount][kClassCount] { // S0 字母 数字 运算符 空白 其他 /* 0 */ { 1, 2, 3, 0, -1 }, /* 1 */ { 1, 1, -1, -1, -1 }, // 标识符/关键字 /* 2 */ {-1, 2, -1, -1, -1 }, // 整数常量 /* 3 */ {-1, -1, -1, -1, -1 }, // 运算符按实际运算符扩展 // 状态 4-7 留给多字符运算符如 ! };逻辑说明状态 0 是起始态。读到字母进状态 1状态 1 里继续读字母或数字都留在状态 1读到非字母数字就结束一个词读到数字进状态 2状态 2 只接受数字。运算符相关状态这里简写成一行真正实现时需要两个字符才能判定所以状态 3 读到要进状态 4状态 4 读到才输出T_OPERATOR。这正好对应教材里“识别 和 的区别”那道经典题。主扫描循环用一个char前看字符。注意 C 里peek()和get()的处理很多翻车都发生在“读了一个字符没放回去”。我习惯用一个int lookahead变量保存当前字符循环体开头判断// scanner.cpp主扫描循环骨架 // 每次调用 NextToken() 返回一个 Token文件读完返回 T_EOF Token NextToken() { SkipWhitespace(); // 跳过空白内部维护行号列号 int line currentLine, col currentCol; int state 0; std::string lexeme; while (state ! -1) { int ch GetChar(); // 读取一个字符-1 表示 EOF int cls CharClass(ch); // 映射到 0-4 的类别 int next kDfa[state][cls]; if (next -1) { UngetChar(); // 撤销读取词不在状态机的接受范围内 break; } lexeme.push_back((char)ch); state next; } return MakeToken(state, lexeme, line, col); }逻辑说明SkipWhitespace()负责跳过空格、制表符、换行并在跳过时累计currentLine和currentCol这样 Token 不用额外保存位置信息就能定位。CharClass()把字符映射成 0 到 4 的整数字母和数字用std::isalpha/std::isdigit判断运算符用一个 switch 匹配 - * / !。UngetChar()是关键——DFA 在某个状态发现下一个字符无转移时这个字符属于下一个 Token必须放回输入流。漏掉这一步词法分析器会丢掉字符最常见的现象是int a1;里的a后面直接跟时被吞掉。你可能会问如果状态 1 是接受态但当前字符已经读过头了怎么办这正好是“最长匹配”的实现要领——不要一看到接受态就立刻返回要继续读直到无转移为止。状态 1 里读字母或数字都留在状态 1所以abc123会被完整读成一个标识符而不是先输出abc再输出123。教材里这一点只写在图注里代码里实现错的人非常多。3.3 DFA 最小化划分法的 C 实现与验收加分点杭电的实验一通常有“对 DFA 进行化简”的加分要求做法是等价类划分。原理很简单把所有状态按“是否为终态”分成两组然后反复检查——如果两个状态在同一组里对任意输入字符它们跳转到的状态必须也在同一组否则分裂。直到没有组能再分裂同一组的状态就可以合并最终得到一个状态数最少的 DFA。用 C 实现的核心是维护一个vectorint group数组group[i]表示状态 i 当前属于哪一组// minimize.cpp等价类划分法的核心循环 #include vector #include map // states 里标记了每个状态是否为终态trans是原始转移表 std::vectorint MinimizeDfa(const std::vectorint isFinal, const std::vectorstd::vectorint trans) { int n isFinal.size(); std::vectorint group(n, 0); int groupCount 2; for (int i 0; i n; i) group[i] isFinal[i] ? 1 : 0; // 初始分组终态/非终态 bool changed true; while (changed) { changed false; std::mapint, std::vectorint split; // 新分组结果 for (int state 0; state n; state) { // 对每个状态算出一个“签名”对每个输入字符去到的组号 std::vectorint signature; for (int cls 0; cls kClassCount; cls) { int target trans[state][cls]; signature.push_back(target -1 ? -1 : group[target]); } // 签名按顺序拼起来用 map 收集同签名状态 int key 0; for (int sig : signature) key key * 10 (sig 1); split[key].push_back(state); } if (split.size() groupCount) { changed true; groupCount split.size(); int g 0; std::vectorint newGroup(n, 0); for (auto [key, statesInGroup] : split) for (int s : statesInGroup) newGroup[s] g; group newGroup; } } return group; }逻辑说明签名的构造是整个算法的灵魂。两个状态等价的前提是对每个字符类别都跳到等价的状态这个“跳去哪一组”的序列就是签名。用mapint, vectorint收集签名相同的状态一组就对应合并后的一个新状态。key的计算方式只是把签名序列压成一个整数避免用vectorint直接做 map 键的繁琐写法如果字符类别超过 5 类这个压法可能会溢出改用std::mapstd::vectorint, std::vectorint就行了。参数说明isFinal数组里1表示终态0表示非终态trans就是上一节的kDfa转移表。最小化之后你还需要根据group数组重新生成一张更小的转移表这一步没什么难度把group映射到新状态编号即可。答辩时导师会问你“初始分组为什么只分两组”答案是非终态和终态不可能等价因为终态意味着“识别完一个词”非终态不是。这个问题的标准答法就是这句话先背住。这里有一个常见的翻车点最小化合并状态后老的起始态 group 编号不一定是 0新表的起始态对应group[0]。很多人合并完直接拿 0 当起始态结果识别全部错位状态数倒是少了一个词也认不出来了。正确做法是先查group[0]得到新起始态编号再重新标记。4. 语法分析选递归下降还是 LR 表驱动C 代码骨架与四元式生成4.1 选递归下降的三个理由代码量、报错质量与提问环节语法分析是编译原理实验里争议最大的一段。教材花了三章讲 LL(1)、LR(0)、SLR(1)、LR(1) 的自动机构造实验课上真正动手写时大多数人会问到底手写递归下降还是先构造分析表再写驱动我的建议很明确选递归下降。原因有三第一代码量少一个量级LL(1) 分析表需要手动计算 FIRST 和 FOLLOW写错一个集合整张表就废了而递归下降的每个函数对应一个非终结符出错时函数调用栈直接告诉你“正在展开哪个非终结符”。第二报错质量高递归下降天然知道当前期望什么能输出“第 12 行期望 运算符 实际看到标识符 a”这种带上下文的信息。第三答辩环节导师更愿意问递归下降——因为每个函数都能指着讲而 LR 分析表驱动是一个大循环加一张表讲不出太多代码设计。这里要澄清一个误区实验要求是“语法分析器”而不是“必须用 LR”。杭电的编译原理课讲 LR 是重点但那是理论课的重点实验课的验收标准是“能正确判断合法/非法程序并给出合理报错”。递归下降是文法 LL 的子集但课设语言的文法完全可以用 LL 描述。如果你对 LR 自动机构造有执念可以额外写一份 SLR(1) 分析表生成器作为加分项而不是替换递归下降。两条路都做的人也有但那是拿优秀项目的节奏普通目标没必要。4.2 一个能跑通表达式与赋值语句的递归下降骨架先定义实验语言的文法。我按常见的课设规模取一个子集覆盖赋值、算术表达式、括号和分号program → stmt_list stmt_list → stmt stmt_list | ε stmt → if_stmt | assign_stmt | expr_stmt assign_stmt → ID expr ; expr_stmt → expr ; expr → term ( term | - term )* term → factor ( * factor | / factor )* factor → ID | NUM | ( expr )这个文法已经是 EBNF 形式(...)*表示循环消除了左递归。递归下降就是让每个非终结符对应一个 bool 函数返回 true 表示解析成功// parser.h递归下降语法分析器 #include token.h #include vector class Parser { public: explicit Parser(const std::vectorToken tokens) : tokens_(tokens), pos_(0) {} bool ParseProgram() { while (!Check(T_EOF)) { if (!ParseStatement()) { ReportError(非法语句); return false; } } return true; } private: bool ParseStatement() { // if 开头走 if 分支ID 后跟 走赋值否则按表达式语句处理 if (Check(T_KEYWORD) Current().lexeme if) return ParseIf(); if (Check(T_IDENTIFIER) PeekNext().type T_OPERATOR PeekNext().lexeme ) return ParseAssign(); return ParseExprStmt(); } bool ParseAssign() { Advance(); // 吃掉 ID Advance(); // 吃掉 if (!ParseExpr()) return false; if (!Match(T_DELIMITER, ;)) { ReportError(赋值语句末尾缺少分号); return false; } return true; } bool ParseExpr() { if (!ParseTerm()) return false; while (Match(T_OPERATOR, ) || Match(T_OPERATOR, -)) { if (!ParseTerm()) return false; } return true; } bool ParseTerm() { if (!ParseFactor()) return false; while (Match(T_OPERATOR, *) || Match(T_OPERATOR, /)) { if (!ParseFactor()) return false; } return true; } bool ParseFactor() { if (Match(T_IDENTIFIER)) return true; if (Match(T_CONSTANT)) return true; if (Match(T_DELIMITER, ()) { if (!ParseExpr()) return false; return Match(T_DELIMITER, )); } ReportError(期望标识符、常量或左括号); return false; } // Check / PeekNext / Match / Advance / Current 是辅助函数下一节补全 };逻辑说明ParseExpr对应term ( term | - term )*先调ParseTerm解析第一个因子再用 while 循环处理或-的重复。这个结构的巧妙之处在于运算符优先级是嵌套在调用层级里的——expr调termterm调factor所以a b * c会被正确解析成a (b * c)。如果你把加减乘除都写在同一个函数里平铺循环优先级就会变成从左到右这是新手最容易翻车的地方。补充一个细节ParseStatement里的“ID 后跟 ”判断依赖PeekNext()提前看下一个 token。如果当前是 ID 而下一个是这是赋值语句否则是表达式语句。这种“前看两个 token”的判断在递归下降里很常见代价是代码里要多写几个辅助函数但能避免回溯。回溯在递归下降里是灾难——它会把报错信息变混乱因为你不知道哪个分支才是对的。辅助函数的关键实现// parser_helpers.cppParser 内部辅助函数 bool Check(TokenType type) const { return pos_ tokens_.size() tokens_[pos_].type type; } bool Match(TokenType type, const std::string lexeme) { if (pos_ tokens_.size() tokens_[pos_].type type tokens_[pos_].lexeme lexeme) { pos_; return true; } return false; } const Token PeekNext() const { // 越界时返回一个静态的 EOF Token避免写 if 判断 static const Token kEof { T_EOF, , -1, -1 }; return pos_ 1 tokens_.size() ? tokens_[pos_ 1] : kEof; }参数说明Match是递归下降里最常用的函数它既做“当前 token 是否符合预期”的判断又做“吃掉 token”的动作。PeekNext返回一个静态的kEof来兜底越界这是 C 里避免“返回引用指向局部变量”的惯用写法。很多人的段错误就出在这里——PeekNext直接返回tokens_[pos_ 1]而 pos_ 已经在最后一个 token 上越界访问。用静态对象的引用做兜底一劳永逸。4.3 左递归消除与优先级把文法改写成 EBNF 再落成 C 的步骤教材里的表达式文法长这样E → E T | T T → T * F | F F → ( E ) | id | num这个文法是正确的上下文无关文法但不能直接写递归下降因为ParseE的第一行就要调ParseE无限递归。消除左递归的标准做法是改写为右递归或 EBNF 循环。右递归版本是E → T E E → T E | ε对应的 C 要写两个函数ParseE和ParseEPrime其中ParseEPrime先判断当前 token 是不是是就继续不是就返回 true空串。这个写法正确但别扭因为 ε 分支让代码多一层而循环版本更直观// 把 E → E T | T 变成 while 循环 bool ParseE() { ParseT(); while (NextIsPlus()) { Advance(); ParseT(); } return true; }两种写法在功能上等价但循环版本的处理顺序和代码阅读体验更好。EBNF 里的*本质上就是 while 循环所以我在实验语言里直接用 EBNF 定义文法省去“手动消左递归”这一步。写报告时把文法定义成 EBNF代码和报告完全对应答辩时不用额外解释“E 对应哪个函数”。优先级处理的要诀一句话优先级越低的运算对应越外层的函数。加减在最外层ParseExpr乘除在中间层ParseTerm括号和因子在最里层ParseFactor。如果你想加一元负号-a在ParseFactor里加一个分支想加幂运算a ^ b结合性是右结合优先级高于乘除需要加一个比ParseTerm更深的ParsePower且循环里不能简单 while——右结合要用递归而不是循环实现。这属于进阶扩展实验能跑通加减乘除和括号就已经覆盖大纲要求。4.4 顺手生成四元式把语法制导翻译嵌进下降函数里很多实验要求“在语法分析过程中生成中间代码”也就是语法制导翻译。做法很朴素在递归下降的循环里每归约一个产生式就往四元式数组里 push 一条。先是四元式的结构定义// quad.h四元式定义与输出 #include string #include vector struct Quad { std::string op; // 运算符 - * / JMP JZ std::string arg1; // 左操作数 std::string arg2; // 右操作数可空 std::string result; // 结果变量或跳转目标 }; static std::vectorQuad g_quads; // 全局四元式表实验规模够用 static int g_tempIndex 0; std::string NewTemp() { return t std::to_string(g_tempIndex); }逻辑说明NewTemp()生成形如t1、t2的临时变量名。全局变量在课设规模是能接受的省去到处传引用的麻烦但答辩时你最好补一句“真实项目不会用全局变量这里为了实验简洁”。这句话能显得你懂工程实践。四元式的输出格式通常要求对齐打印报告里贴出来像这样1: a b t1 2: * t1 c t2然后把生成逻辑嵌进ParseTerm。原来的ParseTerm只做“是否匹配”现在要让ParseFactor返回操作数的名字在循环里生成临时变量// parser_translate.cpp在 ParseTerm 里生成算术四元式 std::string ParseTerm() { std::string left ParseFactorValue(); // 返回 a 或 3 或临时变量名 while (Match(T_OPERATOR, *) || Match(T_OPERATOR, /)) { std::string op Previous().lexeme; // 上一轮 Match 吃掉的运算符 std::string right ParseFactorValue(); std::string result NewTemp(); g_quads.push_back({op, left, right, result}); left result; // 关键链式运算的左手边更新 } return left; }逻辑说明a * b * c的翻译过程是——第一次循环生成* a b t1第二次循环左手边从a变成了t1生成* t1 c t2。这个“左手边更新”是四元式生成最容易漏的一步。漏掉的话输出会变成* a b t1和* a c t2两个计算互不关联c直接参与乘法中间结果t1被丢弃。实验验收时导师只要拿a * b * c一跑就能看出来。赋值语句的翻译更简单。ParseAssign里解析完表达式拿到右边结果直接生成一条四元式// 赋值语句的翻译 bool ParseAssign() { std::string name Current().lexeme; // 变量名 Advance(); // 吃掉 ID Advance(); // 吃掉 std::string value ParseExprValue(); g_quads.push_back({, value, , name}); Match(T_DELIMITER, ;); // 吃掉分号 return true; }逻辑说明四元式 value name表示把value赋值给namearg2 留空。跳转相关的四元式if 语句的JZ需要回填处理这放下一章讲因为回填是坑最密集的地方。5. 编译原理实验常见问题与排查源代码跑不起来先查这五处5.1 一运行就段错误数组越界还是对象生命周期问题现象输入一个最简单的int a 1;程序直接崩终端打印 Segmentation fault没有任何报错信息。用 gdb 打断点在 main 函数入口逐行执行到第二次调用NextToken()时崩溃。原因PeekNext()或扫描循环里越界访问 token 数组。最常见的是词法分析器在UngetChar()的实现上出错——用一个字符变量保存“回退的字符”结果连续回退两次把变量覆盖了输入流错位。语法分析器那边则是pos_已经等于tokens_.size()还去访问tokens_[pos_ 1]。解决给所有辅助函数加边界检查。PeekNext()用静态 EOF Token 兜底Check()和Match()里先判断pos_ tokens_.size()。词法分析器的UngetChar()用一个独立栈保存回退字符不要用单一变量回退两个字符的情况在识别和时一定会出现。写完这两处段错误基本绝迹。5.2 关键字被当成标识符最长匹配的扫描顺序错了现象输入int a;词法输出第一个 token 是T_IDENTIFIERlexeme 是int而不是T_KEYWORD。语法分析器看到int不是标识符报“非法语句”。原因扫描循环在状态 1标识符状态里遇到空白字符时DFA 无转移直接返回了 token类型标记为标识符没有查关键字表。这是扫描逻辑顺序问题——三个动作的先后必须是“读完整词 → 查关键字表 → 决定类型”而不是“在状态机里提前判断”。解决在MakeToken里加上关键字表回查// MakeToken状态机识别完成后统一处理 Token MakeToken(int state, const std::string lexeme, int line, int col) { Token tok; tok.lexeme lexeme; tok.line line; tok.col col; if (state 1) { auto it kKeywords.find(lexeme); tok.type (it ! kKeywords.end()) ? T_KEYWORD : T_IDENTIFIER; } else if (state 2) { tok.type T_CONSTANT; } else { tok.type T_OPERATOR; } return tok; }逻辑说明只有走出状态 1 的词才可能是关键字所以只在state 1时查表。有些人的做法是在扫描循环里每个字符都判断“当前字符串是不是关键字”那是错的——intx的前两个字符构不成int就漏判而且会误判in。查表必须在完整读词后进行。5.3 递归下降死循环空产生式与 EOF 边界没处理现象程序跑起来不崩溃但也不结束CPU 占用 100%像是卡死了。打印日志发现ParseProgram无限调用ParseStatement而ParseStatement返回 true 但pos_没变。原因文法里有stmt → ε空产生式但代码里没处理“当前 token 不属于 stmt 的 FIRST 集就退出”的情况。典型场景是输入文件末尾多了一个换行词法分析器没有输出 T_EOF语法分析器拿到空 token 流每轮都匹配失败但也不报错pos_ 永远是 0。解决ParseProgram的循环条件必须是!Check(T_EOF)并且ParseStatement里所有分支都不匹配时直接返回 false 让外层报错退出不要静默返回 true。另一个检查点是词法分析器文件读取到末尾必须显式输出一个T_EOFtoken而不是返回空 vector。养成写好这两个边界的习惯死循环基本不会出现。5.4 四元式跳转目标全是 -1迭代器失效还是回填时机错现象if (a b) c 1;生成的中间代码里JZ四元式的result是-1或者空字符串只有if没有跳转目标中间代码无法继续处理。原因if 语句的翻译需要在生成条件表达式之后、生成语句体之前先留一条JZ四元式等语句体生成完再把实际跳转标签填回去。很多人的代码是这样写的auto quad g_quads.back();拿到引用然后 push 更多四元式回头再改quad——g_quads是std::vectorpush 导致扩容引用失效回填全部落空。解决不要存引用存下标。回填时用下标访问// 正确的回填方式存下标而不是存引用 int jumpIndex g_quads.size(); g_quads.push_back({JZ, condResult, , }); // result 待回填 ParseStatement(); // 生成语句体的四元式 g_quads[jumpIndex].result L std::to_string(label);逻辑说明jumpIndex是size_t类型在 push 之后依然有效。回填的本质是“先占位后补地址”这是编译原理教材里明确讲的案例代码里用下标实现最稳妥。另一个常见错误是回填的标签编号冲突——if 和 while 都用一个label全局计数器就没问题如果每个分支里单独初始化计数器标签就会重复跳转全乱。5.5 中文注释与文件编码VSCode 配置下 C 源码的常见翻车现象代码在本机 Visual Studio 或 VSCode 里编译运行正常拿到实验室的 Linux 机器上一编译注释乱码或者词法分析器把中文注释里的字符当成非法输入直接报错。原因Windows 下 VSCode 默认可能是 GBK 编码保存源文件Linux 的 GCC 默认按 UTF-8 解析。注释里的中文变成乱码还算小事字符串或注释里的全角符号比如中文分号“”会被词法分析器的CharClass映射成“其他”类别触发非法字符报错。解决统一编码。VSCode 里点右下角编码按钮选择“通过编码保存”为 UTF-8。编译命令加参数指定输入编码g -finput-charsetUTF-8 -stdc17 main.cpp。词法分析器这边CharClass里对“其他”类别的处理要输出明确报错带上行列号而不是静默跳过——静默跳过会让非法字符凭空消失程序“能跑”但行为错误。这条属于环境坑和编译原理本身无关但每年都有不少人死在验收前的最后一步。6. 用随机用例验证整条流水线一份能自证正确的最小测试方案实验做完后最重要的一个习惯是不要用手敲的三五个用例验证。手敲用例覆盖不到上下文边界比如a*bc和a*(bc)的优先级差异再比如if嵌套while。我建议写一个最简单的随机程序生成器批量生成合法程序再准备一小批非法的跑全链路验证。// test_generator.cpp生成随机合法程序用于回归 // 用法./generator 100 | ./compiler --parse // 100 表示生成 100 条语句 #include cstdlib #include iostream #include string #include vector std::string RandExpr(int depth) { if (depth 0) { return (rand() % 2) ? a : std::to_string(rand() % 100); } int op rand() % 4; const char* ops[] {, -, *, /}; std::string l RandExpr(depth - 1); std::string r RandExpr(depth - 1); return ( l ops[op] r ); } int main(int argc, char* argv[]) { int n argc 1 ? std::atoi(argv[1]) : 100; srand(42); // 固定种子保证可复现 for (int i 0; i n; i) { if (rand() % 3 0) { std::cout a RandExpr(3) ;\n; } else { std::cout b RandExpr(2) ;\n; } } return 0; }逻辑说明固定随机种子 42 保证每次生成的用例完全一致这是可复现测试的底线。RandExpr用递归深度控制表达式嵌套深度 3 会生成类似((a 3) * (b - 8))的结构覆盖括号和运算符优先级。为什么用(expr op expr)而非expr op expr为了让生成的表达式总是带括号避免优先级歧义把“合法程序”误判成“非法”。测试生成器只负责制造合法输入不该制造边界争议。随机合法程序能验证“不该报错时别报错”但还要准备非法样例验证报错路径缺分号、括号不匹配、a 1这类运算符连续、空文件、只有注释、超长标识符。这些样例应该手写放进一个invalid_cases/目录一条条跑确认每条都报错且报错位置合理。我的习惯是保留三份固定文件valid_min.txt最小合法集、valid_random.txt随机生成、invalid_cases.txt非法样例每次改完代码都先跑这三份再提交这个习惯帮我躲过了至少三次验收现场翻车。最后说一句编译原理实验的价值不在源码本身而在于你亲手把“字符串变成结构化表示”这个过程走了一遍这套思维在以后写解释器、写 DSL、做静态分析时都会回来找你。希望帮到你。本文还有配套的精品资源点击获取