简介一份面向杭电《编译原理》课程的C实验源代码资源包覆盖词法分析、非确定有限自动机到确定有限自动机的子集构造法、递归下降分析及LL(1)语法分析等编译器前端核心实验适合正在修读编译原理或需要对照实现的学生参考。包内共11个文件含4个C源文件、4个可直接运行的exe程序、2个文本说明与1个SysY测试文件压缩包仅334KB轻量便捷。目前已有1605人学习下载。各实验均提供源码与对应可执行程序词法分析部分针对SysY语言实现了八进制、十六进制数识别以及两种注释格式的错误提示处理子集构造法演示了非确定状态集到确定状态集的转换流程递归下降与LL(1)分析器通过函数递归与预测分析表完成语法结构的判定。借助附带测试样本和输出文本读者可以对照运行结果快速理解每一步实现原理并据此完成自身实验任务或排错修改提升对编译器工作流程的掌握。1. 编译原理实验为什么总栽在 C 上你要的不是源码是一条能跑的流水线编译原理实验挂在验收现场的原因通常不是不懂 DFA 或 LL(1)而是课本上的伪代码到了 C 里不知道从哪一行开始写。标题里「编译原理实验 杭电 源代码 C」指向的是一类典型课程作业用 C 实现一个能完成词法分析、语法分析、乃至中间代码生成的小型编译器。这类实验有个反直觉的结论——最难的部分不是算法而是把算法组织成一个能一步步打印中间结果的工程。接下来的内容分两条线索一条给正在熬夜赶实验的在读学生另一条给需要快速带实验、说清楚验收标准的助教。目标只有一个让你交出去的不是一堆能编译通过的 C 文件而是输入源代码、输出 token 与四元式的完整流水线。2. 词法、语法、语义三阶段到底各做什么状态机、递归下降与四元式的 C 选型编译原理实验名义上是「写一个编译器」实际上是「写三个小程序」词法分析器、语法分析器、语义/中间代码生成器。三段的验收标准完全不同混在一起做是新手最常见的翻车姿势。下面按教材顺序把每段拆开讲清楚用什么 C 结构去承载以及每个选型的理由。2.1 词法分析手工状态机比正则库更适合教学实验词法分析器把源代码字符串变成 token 流是编译流水线的第一段。工程上这是最简单的部分教学上却是最容易丢分的地方——很多同学用 std::regex 或 flex 快速生成了 tokenizer却在答辩时回答不了「DFA 怎么构造」这个必问题。无论你用的是清华大学出版社那本经典教材还是本校自编讲义第二章词法分析对应的实验内容就是这一节。杭电、山科大这类学校的编译原理实验通行走法是要求手写状态机一个 while 循环、一个状态枚举、若干分支把教材里 DFA 的状态转移图一行行变成代码。先定义 token 的数据结构。这个结构要带行号和列号因为它决定了后面语法分析的报错能力千万不能省// token.h —— 词法单元类型定义 enum class TokenType { Identifier, Keyword, Number, Operator, LParen, RParen, LBrace, RBrace, Semicolon, EndOfFile }; struct Token { TokenType type; std::string text; int line; // 第几行报告和报错全靠它 int column; // 第几列 };然后是核心的词法循环。这里用「当前字符是什么类别」决定进哪个分支而不是对每个字符做 if 判断目的就是让代码结构和状态转移图一一对应报告好写、答辩好讲// tokenizer.cpp 核心循环只保留主干逻辑 std::vectorToken tokenize(const std::string src) { std::vectorToken tokens; size_t i 0; int line 1, col 1; while (i src.size()) { char c src[i]; if (isspace(static_castunsigned char(c))) { // 跳过空白换行时更新行号 if (c \n) { line; col 1; } else col; i; } else if (isalpha(c) || c _) { // 标识符或关键字 size_t start i; while (i src.size() (isalnum(src[i]) || src[i] _)) i; std::string word src.substr(start, i - start); tokens.push_back({keywordTable.count(word) ? TokenType::Keyword : TokenType::Identifier, word, line, col}); col static_castint(i - start); } else if (isdigit(static_castunsigned char(c))) { // 数字字面量 size_t start i; while (i src.size() isdigit(static_castunsigned char(src[i]))) i; tokens.push_back({TokenType::Number, src.substr(start, i - start), line, col}); col static_castint(i - start); } else { // 运算符与标点 std::string op(1, c); if (i 1 src.size() twoCharOps.count(src.substr(i, 2))) { op src[i 1]; i; col; // 吃掉第二个字符 } tokens.push_back({TokenType::Operator, op, line, col}); i; col; } } tokens.push_back({TokenType::EndOfFile, , line, col}); return tokens; }三个参数值得注意。keywordTable 用 std::unordered_set std::string 初始化别用 C 风格字符串数组加 strcmp那样代码会膨胀三分之一twoCharOps 是 {, !, , , , ||} 这类双字符运算符集合实验只要求单字符运算符时直接删掉这个分支isspace 和 isdigit 的参数要 cast 成 unsigned char否则遇到扩展 ASCII 字节时是未定义行为这是 C 里常见的面试陷阱。手工状态机的优点是整个逻辑肉眼可见每个 if 分支都能对应状态转移图的一根线。缺点也明显运算符多了以后维护成本高。但教学实验的源语言一般只有几十个 token这个体量完全不需要引入正则库或生成器。2.2 语法分析递归下降和 LALR(1) 是两条完全不同的路线语法分析把 token 流变成语法树是整个实验的体力活。路线选择上实验要求通常已经替你做了决定关键是能认出它的暗示。先把两条路线摆开路线适合的文法C 落地方式答辩被问最多的坑手写递归下降LL(1)需要改写非终结符 ↔ 成员函数左递归死循环、回溯产生副作用分析表驱动SLR(1)/LALR(1)二维分析表 状态栈表构造错了却不知道错在哪生成器flex/bisonLALR(1).y 文件生成 C报告里根本写不清 Action 表判断方法很简单实验要求如果写了「消除左递归、提取左因子」那是要走递归下降如果写了「构造 SLR(1) 分析表」那是要走表驱动或 bison如果只要求「能跑通以下测试用例」选递归下降最稳因为它的错误定位最好做代码也最容易讲。递归下降的核心模式是「一个非终结符一个函数」。以最经典的表达式文法为例E → E T | T 这种左递归写法不能直接翻译成函数要先改写成 E → T { (|-) T }再落成循环// parser.cpp —— 处理表达式 E - T { (|-) T } bool Parser::parse_expression() { if (!parse_term()) return false; // 先处理一个项 while (peek().type TokenType::Operator (peek().text || peek().text -)) { next(); // 吃掉运算符 if (!parse_term()) return false; // 再处理一个项 // 到这里已形成一个运算符节点真正的 AST 构建在第 3 章 } return true; }这里 peek() 负责「看当前 token 但不消费」next() 负责「消费一个 token」。这两个原语是所有递归下降函数的地基建议在 Parser 类里用两个成员变量实现一个存 token 数组一个存当前下标。函数的返回值有两种风格用 bool 表示匹配成功与否或者返回 unique_ptr 表示构建出的子树。前者适合先跑通后者适合直接生成 AST不要混用。提示递归下降里如果发现同一个非终结符的两个分支都以同一个 token 开头说明文法有 FIRST 集冲突需要提取公共左因子否则代码里必然出现「回溯」。教学实验为简化起见给的测试用例通常都能用一路预测搞定。2.3 语义分析与中间代码三地址码是实验报告的“黑匣子”不少学校的实验大纲会在语法树之外再要求一层中间代码杭电的编译原理实验就属于这一类。工业编译器在这一层会做大量优化但教学实验关心的只有一个能不能把语法树翻译成一串结构化的三地址码即四元式运算符、两个操作数、结果。中间表示常见的有三种后缀式、三元式、四元式。教学实验首选四元式理由很实在C 里用一个 struct 就能表达实验报告里画成表格也最直观解释器或者后端的代码生成器拿着它就能逐条翻译不会出现后缀式求值那种「操作数栈藏在算法里」的黑匣子。// ir.h —— 四元式一条三地址指令 struct Quad { std::string op; // 运算符 - * / jz jmp ... std::string arg1; // 第一个操作数源程序里的变量名或字面量 std::string arg2; // 第二个操作数没有就填空串 std::string result; // 结果新生成的临时变量名 t1、t2 ... };用 string 而不是直接存 int 值是有意为之。统一用字符串表示操作数后端代码生成器就不需要维护一套「这是变量还是常量」的判别逻辑临时变量名用 t1、t2 递增生成既方便在报告里展示「新变量生成」的过程也让最终的目标代码一眼能看懂。翻译 a b c 这个赋值语句时语义动作会连续产生两条四元式quads.push_back({, b, c, t1}); // t1 b c quads.push_back({, t1, , a}); // a t1为什么先算右值再赋值因为通常把赋值表达式的右值计算放在前面左值放在最后一条这样后续处理 a (b c) * d 时只需要在中间插入乘法的那条四元式整个序列仍然保持顺序一致。这一小段代码虽然简单但它体现了「语法制导翻译」的核心思想语法树的每个节点挂一个语义动作遍历时动作执行、四元式落盘实验报告的「中间代码生成」一章就有了完整素材。3. 搭一个 500 行以内能跑的 C 编译骨架目录划分、Token 流与 unique_ptr 管理的 AST前两章把每个阶段的选型讲完了接下来解决「从哪一行开始写」。很多实验翻车不是算法不会而是代码全堆在一个 main.cpp 里改一处坏一处。我一般会先用半小时把工程骨架立起来再往里面填逻辑。骨架越干净后半个晚上的调试越顺利。3.1 工程目录与 CMake 最小配置先把地盘划清几百行的小工程不需要任何花哨架构但目录必须按「编译流水线的三段」来划。词法报错时你不会想跑到 parser 文件夹里找问题compiler-demo/ ├── CMakeLists.txt ├── include/ │ ├── token.h # Token 与 TokenType │ ├── lexer.h # 词法分析器接口 │ └── ast.h # AST 节点定义 ├── src/ │ ├── main.cpp # 入口读文件 → 词法 → 语法 → 打印 │ ├── lexer.cpp │ └── parser.cpp └── tests/ └── demo.c # 一个简单的测试输入CMakeLists.txt 里第一件事就是把 C 标准锁死这是全工程最容易被忽略的一行cmake_minimum_required(VERSION 3.16) project(compiler_demo LANGUAGES CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_executable(compiler src/main.cpp src/lexer.cpp src/parser.cpp )注意 set(CMAKE_CXX_STANDARD_REQUIRED ON) 这行不能省否则 CMake 会「如果能用 17 就用不能用就悄悄降级」本地编过、评测机编不过的惨剧有一半就是这么来的。如果实验室还在用 Dev-C 这类老环境就把 CMake 换成在工程选项里手动勾选「C17」原理一样。在 vscode 里配置好 c/c 扩展和 CMake 插件后CtrlShiftB 就能一键构建没必要装重型 IDE。3.2 Token 流与 Lexer 接口把所有字符操作封进两个原语词法分析器最容易写成一坨「边读边判断」的意大利面。我常用的组织方式是先把「看一个字符」和「吃一个字符」封装成 peek 和 advance 两个原语所有分支逻辑只跟这两个函数打交道// lexer.h #ifndef COMPILER_LEXER_H #define COMPILER_LEXER_H #include token.h #include string #include vector class Lexer { public: explicit Lexer(std::string src); std::vectorToken run(); // 返回完整 token 流 private: char peek() const; // 看当前字符不移动位置 char advance(); // 取当前字符并前进一格 std::string m_src; size_t m_pos 0; // 当前位置 int m_line 1; // 当前行号 int m_col 1; // 当前列号 }; #endifm_pos 用 size_t 而不是 int是因为它要和 src.size() 比较int 与 size_t 混比会产生符号转换警告评测环境开 -Wall 时会直接当成错误。peek 的实现只有一行return m_pos m_src.size() ? m_src[m_pos] : \0;返回 \0 表示输入耗尽这样词法分支里不用到处判断越界。advance 则负责推进 pos 并更新行号列号唯一要注意的是遇到 \n 时列号要归 1。run() 的主循环直接复用 2.1 的 tokenize 逻辑只是把分支拆成 lex_keyword、lex_number、lex_operator 三个私有函数。这样做的收益在调试期才看得到用 c 随机数生成器铺一批畸形输入进到 lex_number 时你可以只在这个函数里打断点不用在两百行的 switch 里翻。3.3 AST 节点unique_ptr 让内存管理交给树结构自己语法树是典型的树形结构节点严格父子关系没有共享。这种结构用 std::unique_ptr 最合适每个父节点持有子节点的所有权树析构时从上往下自动释放不需要手写析构函数也不会有 shared_ptr 在复杂表达式里形成引用环的玄学问题。// ast.h —— 极简 AST只覆盖表达式与赋值语句 #include memory #include string struct ExprNode { virtual ~ExprNode() default; virtual void dump(int depth) const 0; // 打印树验收演示用 }; struct NumberNode : ExprNode { std::string value; void dump(int depth) const override; }; struct BinaryOpNode : ExprNode { std::string op; std::unique_ptrExprNode left; std::unique_ptrExprNode right; void dump(int depth) const override; };这里有个很多人一上来就写错的点基类必须声明虚析构函数。如果漏掉virtual ~ExprNode() default通过基类指针 delete 派生对象时派生类成员不会被释放内存泄漏在几百行的程序里不容易暴露但 Valgrind 一跑就现原形。dump 的实现核心是「用 depth 控制缩进」让每层节点在终端里像目录树一样展开void BinaryOpNode::dump(int depth) const { std::cout std::string(depth * 2, ) op: op \n; if (left) left-dump(depth 1); if (right) right-dump(depth 1); } void NumberNode::dump(int depth) const { std::cout std::string(depth * 2, ) num: value \n; }把 AST 变成可打印的文本是比「程序能跑」更重要的里程碑——因为你能肉眼检查语法树长什么样才能去验证语法分析逻辑对不对。等这棵树的打印稳定了再把 2.3 节的四元式生成挂到树的遍历上整条流水线就真正通了。4. 编译原理实验避坑指南5 条来自验收现场的翻车记录下面五条全是学生作业里反复出现、验收现场反复翻车的记录每一条都按现象、原因、解决三步写。前两条是词法阶段的中间两条是语法阶段的最后一条直接决定你能不能过评测。4.1 Windows 下读 UTF-8 源码文件第一个 token 就识别错现象测试文件是从课程示例或开源仓库下载的 UTF-8 编码用 std::ifstream 按文本模式读进来后中文注释乱码跟在注释后面的关键字被识别成非法标识符。原因Windows 上 ifstream 默认按本地代码页GBK解释字节流UTF-8 编码的中文字节序列被拆成两个半字符另外 VS 保存文件时可能写入 UTF-8 BOMEF BB BF使得源码串的第一个字符不是合法 ASCII 符号词法循环一进来就乱了。解决最稳的读法是用二进制模式读整个文件自己剥掉 BOMstd::ifstream in(path, std::ios::binary); std::string src((std::istreambuf_iteratorchar(in)), std::istreambuf_iteratorchar()); if (src.size() 3 static_castunsigned char(src[0]) 0xEF static_castunsigned char(src[1]) 0xBB static_castunsigned char(src[2]) 0xBF) { src src.substr(3); // 剥掉 UTF-8 BOM }注意这里的字节比较必须 cast 成 unsigned char否则 char 的符号扩展会让 0xEF 变成负数条件永远不成立。至于中文注释教学实验的源语言通常只包含 ASCII 字符直接丢弃注释内容是保证不翻车的最短路径。提示如果实验允许把测试用例统一转成 UTF-8 无 BOM能省下大半编码调试时间。4.2 词法状态全塞进一个枚举能跑但根本没法答辩现象词法分析器功能完全正常但状态枚举定义了六十多个值switch 里套了四层 if运行倒是快报告里却画不出状态转移表答辩被问「这个状态怎么来的」只能支支吾吾。原因把 DFA 的「状态」和「当前字符属于哪一类」两个维度混在一个枚举里本质上是把二维状态转移表压成了一维的 if-else 串。解决拆成两个枚举。第一个表示字符类别digit、alpha、operator、space第二个表示词法状态Start、InIdent、InNumber、InOperator。主循环里先算字符类别再查状态代码与状态转移表严格一一对应。判断自己是走对了还是绕进去了有个笨办法如果两个状态的「进入条件」除了字符不同之外还有重叠就该考虑是不是把类别和状态混了。4.3 递归下降遇上左递归文法演示现场直接栈溢出现象按教材原文 E → E T | T 写 parse_expression函数第一行调用自身一运行控制台秒刷几千行递归调用然后崩掉。原因左递归文法的产生式右边第一个符号还是这个非终结符自己。翻译成函数后parse_expression 还没做任何实质匹配就先调用了 parse_expression栈当然会被打穿。解决这是最多人栽的语法分析坑解法只有一个先改文法再写代码。把 E → E T | T 等价改写成 E → T { T }也就是 2.2 里的 while 循环版本。快速判断文法是否有左递归的办法盯着产生式看右边第一个符号如果要定义的那个非终结符自己就是左递归必须改写后重新推导一遍测试用例。4.4 把编译错误当 C 异常抛遇到坏输入整个程序崩掉现象在 IDE 里运行编译器输入故意构造的非法表达式比如 a 1 程序直接跳到「未处理的异常」窗口标准输出出现一长串堆栈地址。原因把「编译器要报告编译错误」和「C 运行时故障」混为一谈。编译错误是编译器的正常输出它的本职工作是发现问题、指出位置、继续诊断而抛异常是程序自身的异常路径两者不该共用一套机制。解决定义自己的诊断错误类型错误信息只走打印不进异常栈struct CompileError { int line; int col; std::string msg; };解析函数遇到非法输入时记录 CompileError 并返回 false或空的可选值main 函数统一打印「第 x 行第 y 列: 描述」。这样不管输入多离谱程序都能稳定输出诊断信息答辩时反而显得健壮——「你故意输错的输入你的编译器也能说清楚错在哪」是很有说服力的一句话。4.5 本地 VS 编过评测机上编不过现象代码在 Visual Studio 里全是绿色对勾交到评测环境用 g 编译却报「xxx is not a member of std」。网上抄的源代码也可能踩同一个坑对方用的标准比你这边新。原因本地 IDE 和评测线的编译器版本不一致。最常见的两个元凶是 std::formatC20 才进标准和 C20 的 range 头文件老 g 根本不认识。解决治本办法是 CMake 里锁 C173.1 那两行 set写代码时字符串格式化一律用 stringstream 或 printf不用 format。提交之前养成一个习惯在命令行用g -stdc17 -Wall -Wextra把整个工程编一遍把警告当错误改掉。vscode 配好 c/c 环境后这条命令在终端里两秒就能跑完别只看 IDE 的绿色对勾。5. 从「能交差」到「能答辩」AST 可视化与回归测试守门代码能跑只是及格线能讲清楚才是高分线。这一章给骨架加两个不值钱但很提气的小工具一个把语法树画成图片一个用样例集守门。5.1 把 AST 导出成 dot答辩现场用一张图说话Graphviz 的 dot 格式是纯文本写个导出函数就能让语法树可视化。给每个节点在遍历时分配一个整数 id输出节点定义和父子边// dump_dot.cpp —— 将 AST 导出为 Graphviz dot 文本 void dump_dot(const ExprNode* node, std::ostream out, int id) { int cur id; // 当前节点编号 out n cur [label\ node-name() \];\n; for (const ExprNode* child : node-children()) { int childId id; dump_dot(child, out, childId); // 先递归再输出边 out n cur - n childId ;\n; } }关键在于每个递归调用传递同一个 id 引用保证整棵树编号全局递增。children() 可以临时把 BinaryOpNode 的 left/right 塞进 vector。导出后用dot -Tpng ast.dot就能出图。验收演示时把源码、token 序列、AST 图、四元式表四件套并排放大评分老师一眼就能看清你做了哪几层、每层之间怎么衔接。这个操作本身不值钱但「每阶段都有可见输出」的工程意识在答辩里非常加分。5.2 用一组样例回归测试给重构留一颗后悔药很多实验代码是「改一个 bug 引入两个新 bug」。守住底线最便宜的办法是回归脚本跑完所有样例把输出与期望的基线文件比对#!/usr/bin/env bash # 回归脚本跑完所有样例并与期望输出比对 for f in tests/in/*.c; do name$(basename $f .c) ./compiler $f out_$name.txt if diff -u tests/expect/$name.txt out_$name.txt /dev/null; then echo $name: PASS else echo $name: FAIL fi done样例至少覆盖这几类合法表达式、含多余空白的、非法嵌套括号、连续赋值、注释夹在代码中间。期望文件不必手工精打——编译器第一版跑通后把输出复制成基线之后改文法、调语义动作都靠它看回归。没有这层保护你会在临交作业前把 4.3 节的文法改写改出新的栈溢出而不自知。我做这类实验最大的教训是「别急着写主流程」。先把词法输出 token、语法输出树、语义输出四元式每个阶段都做成可以独立打印的模块再回头微调错误恢复任何一边出问题都能顺着中间文件定位。编译原理实验的分值分配里「能跑」只占一半另一半在「讲得清」——一棵能打印的语法树和一张四元式表就是答辩现场最硬的两张底牌。希望帮到你少走几个弯路。本文还有配套的精品资源点击获取