简介一份覆盖中国海洋大学2020年春季编译原理课程的完整实验源码与要求文档面向正在学习编译器构造的学生适合作为课程设计、实验复现及排错参考。压缩包共七十四个文件、约七百七十四KB包含C语言源码、词法规则文件、语法规则文件、头文件、构建脚本、可执行程序、文本说明与测试用例等既能查看词法语法规则对应的工程结构也能直接编译运行验证结果。实验内容覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与编译器综合八个模块并附实验要求文档帮助读者将编译原理理论落地为可运行代码理解符号表、类型检查、递归下降解析和代码生成等关键环节。已有四千四百一十五人学习或下载可作为编译原理课程实验的完整参考与对比素材。1. 编译原理全套实验一份能直接跑通的课程源码包如果你正在补编译原理的实验报告大概率经历过这种场景讲义上的文法规则背得滚瓜烂熟一写代码就翻车——词法分析器的状态机多吞字符、递归下降碰上左递归直接爆栈、符号表作用域串了导致变量覆盖。这套以 OUC 名义整理发布的编译原理全部实验源码正好把这条完整的编译链路端到了眼前词法分析、语法分析、语义分析、中间代码生成每个实验都有可编译运行的 C 语言实现带清晰的目录结构和测试用例。它适合三类人一是想直接交作业拿高分的学生二是想搞明白编译原理各阶段之间到底怎么衔接的初学者三是准备二次开发做课程设计、想快速搭一个编译框架出来的开发者。这篇笔记就把我拆包验证的过程完整写下来连踩过的坑也一并交代。2. 实验全景与技术选型从 token.h 到 intercode.c 的递进关系2.1 目录结构一套自顶向下的模块划分方式拿到源码包先看目录一条非常清晰的编译流水线就摆在眼前。源码包根目录下有 include 和 src 两个主目录include 头文件负责定义各阶段的对外接口src 里的 C 文件按实验编号逐个实现。test 目录放的是配套的测试用例每个用例文件名都对应某个语言特性比如 test_expr.c 专门验证表达式解析test_loop.c 验证循环语句的中间代码输出。compiler-lab/ ├── include/ │ ├── token.h # Token 结构定义与关键字表 │ ├── lexer.h # 词法分析器对外接口 │ ├── parser.h # 语法树节点与递归下降接口 │ ├── symtab.h # 符号表数据结构 │ ├── intercode.h # 三地址码结构定义 │ └── utils.h # 错误处理与公共工具 ├── src/ │ ├── lexer.c # 实验1词法分析状态机实现 │ ├── parser.c # 实验2语法分析递归下降实现 │ ├── semantic.c # 实验3语义检查与符号表填充 │ └── intercode.c # 实验4中间代码生成 ├── test/ │ ├── test_expr.c # 表达式优先级测试 │ ├── test_decl.c # 变量声明与初始化测试 │ ├── test_loop.c # while/for 循环中间代码测试 │ └── test_err.c # 语法错误用例 ├── Makefile └── README.md这个目录设计的好处是每完成一个实验代码都只在 src 里增加一个新文件不动已有的模块。lexer.c 只负责输出 Tokenparser.c 只消费 Token 流semantic.c 在语法树构建完成后做类型检查和符号登记intercode.c 最后扫描语义分析的结果产出三地址码。我建议你拿到包后先按这个顺序读一遍头文件接口清晰之后后面的实现逻辑基本不用猜。2.2 技术选型为什么用 C 而不是 Java 或 Python整套实验以 C 语言实现为主线这个选型放到课程实验场景里非常合理。编译原理讲义上讲词法分析通常画状态转换图C 语言里用 switch 或 if 分支配合一个“当前字符”变量就能直接模拟状态转移不需要像 Python 那样靠正则库偷懒也更贴近底层逻辑。另一个关键点是 C 的指针操作天然适合构建语法树和符号表这类链式结构。parser.c 里每个语法节点就是一个 malloc 出来的结构体通过指针把子节点串成一棵树symtab.c 里的作用域链表则用嵌套的指针结构模拟出词法作用域的层次。相比 Java 那种偏“啰嗦”的面向对象写法C 写出来更短也更接近编译原理课程里伪代码的描述方式。当然这么做也有代价——内存管理和字符串操作都得自己小心处理比如 strcpy 拷贝越界这个坑我后面详说。不过实验规模小总共几千行代码手动管理内存完全在可控范围内。2.3 各实验模块的接口约定靠结构体串联起来的编译流水线模块之间靠三个核心结构体衔接。token.h 里定义了 Token词法分析器吐出的是这个结构体数组parser.h 定义了 ASTNode语法分析阶段把它组装成一棵语法树intercode.h 定义了 Quad 结构体代表三地址码的一行。// token.h typedef struct Token { int type; // TOKEN_KEYWORD / TOKEN_IDENTIFIER / TOKEN_NUMBER ... char value[64]; // 实际的词素文本 int line; int col; } Token;Token 结构体同时携带行号和列号为的是语法分析阶段报错时能精确提示位置。value 数组固定 64 字节超过这个长度的标识符会被截断这是一个简化设计——绝大多数课程实验的测试用例都不会写超长命名。ASTNode 的字段则包含节点类型、子节点指针、携带的操作符或变量名等信息。// parser.h typedef struct ASTNode { int type; // NODE_IF / NODE_WHILE / NODE_ASSIGN / NODE_BINOP ... char value[64]; // 变量名或字面量 struct ASTNode* left; struct ASTNode* right; struct ASTNode* next; // 语句列表通过 next 串联 } ASTNode;这三个结构体是整套实验的骨架二次开发时新增语法特性基本都要从扩展结构体字段开始。下一章逐个拆核心模块的代码实现。3. 核心模块拆解词法、语法、语义分析的完整实现路径3.1 词法分析状态机驱动的 token 识别lexer.c 的核心是一个有限状态自动机的循环实现有点像一个长着多个出口的管道——每个分支只消费属于自己类别的字符碰到不匹配立刻停下。这个函数的输入是一个 LexContext 结构体里面保存了源文件指针、当前字符、当前行列号。// lexer.c 词法分析核心循环 #define MAX_TOKEN_LEN 64 LexToken* next_token(LexContext* ctx) { // 跳过分隔字符 while (ctx-ch || ctx-ch \t || ctx-ch \n) { next_char(ctx); } char buf[MAX_TOKEN_LEN]; int len 0; // 标识符 / 关键字分支 if (isalpha(ctx-ch) || ctx-ch _) { while (isalnum(ctx-ch) || ctx-ch _) { buf[len] ctx-ch; next_char(ctx); } buf[len] \0; // 查关键字表命中则返回关键字 token for (int i 0; i KEYWORD_COUNT; i) { if (strcmp(buf, keywords[i]) 0) { return new_token(TOKEN_KEYWORD, buf, ctx-line, ctx-col); } } return new_token(TOKEN_IDENTIFIER, buf, ctx-line, ctx-col); } // 数字常量分支顺带处理浮点数 if (isdigit(ctx-ch)) { while (isdigit(ctx-ch)) { buf[len] ctx-ch; next_char(ctx); } if (ctx-ch .) { buf[len] ctx-ch; next_char(ctx); while (isdigit(ctx-ch)) { buf[len] ctx-ch; next_char(ctx); } } buf[len] \0; return new_token(TOKEN_NUMBER, buf, ctx-line, ctx-col); } // 运算符与界符分支 for (int i 0; i OP_COUNT; i) { if (ctx-ch ops[i]) { next_char(ctx); return new_token(TOKEN_OPERATOR, ops[i], ctx-line, ctx-col); } } error(ctx, 无法识别的字符); return NULL; }这段代码的核心设计是“当前字符即状态”——ctx-ch 保存的就是状态机的当前输入next_char 每调用一次就前移一个字符、更新状态。标识符分支里先卡住首字符必须是字母或下划线后续循环吃进字母数字下划线数字分支先吃整数部分遇到小数点再吃小数部分这相当于把“无符号数”词法的状态图直接翻译成了代码。一个容易踩的细节是数字分支里用了 ctx-ch . 这个前瞻判断如果小数点后面跟的不是数字比如输入“1.”循环直接退出并把“1.”整体当作数字返回。这在课程层面可以接受因为测试用例一般不会出现这种写法但如果你要做严格一点的编译器这里需要加一个 peek 函数再往前看一位。工程上常见的做法是词法分析器维护一个 peek 缓冲区需要前瞻时先保存当前位置再读判断完再回退这套源码没有做这一步算是简化之处。3.2 语法分析递归下降处理表达式优先级parser.c 用的是手写递归下降没有引入 Yacc/Bison 这类生成器。这么做的好处是代码量可控出错时调试直观——编译原理用户手册上的文法规则怎么画代码就怎么写。表达式优先级解析是最经典的递归下降演示案例加减乘除和括号的处理逻辑如下。// parser.c 表达式E - T {(|-) T} static void parse_expression(Parser* p) { parse_term(p); // 先解析一个项 while (p-tok.type TOKEN_PLUS || p-tok.type TOKEN_MINUS) { advance(p); // 吃掉运算符 parse_term(p); // 再解析下一个项 } } // 项T - F {(*|/) F} static void parse_term(Parser* p) { parse_factor(p); while (p-tok.type TOKEN_MUL || p-tok.type TOKEN_DIV) { advance(p); parse_factor(p); } } // 因子F - (E) | int | id static void parse_factor(Parser* p) { if (p-tok.type TOKEN_LPAREN) { advance(p); parse_expression(p); // 括号内是一个完整表达式 expect(p, TOKEN_RPAREN, 缺少右括号); } else if (p-tok.type TOKEN_NUMBER || p-tok.type TOKEN_IDENTIFIER) { advance(p); // 叶子节点直接吃掉 } else { error(p, 表达式语法错误); } }这里最值得留意的是文法改写思路。原始文法里的 E → E T 是左递归递归下降直接写这个规则会导致函数无限调用自身、永不返回。所以源码里把它改写成了 E → T {(|-) T}花括号表示“零个或多个”对应代码里的 while 循环。parse_expression 先无条件调一次 parse_term把第一个操作数吃掉然后循环看当前 token 是不是加减号——是就吃运算符再解析下一个单项。整个结构非常机械但从左到右读一遍就能理解优先级是怎么体现的。parse_factor 处理括号时先吃掉左括号然后递归调用 parse_expression这就是括号优先级高于加减乘除的代码根源——最内层的括号先被解析。嵌套括号的层数取决于函数调用的栈深度我在第 4 章会写一个和这个相关的翻车现象。3.3 语义分析符号表与作用域链表的配合semantic.c 做的事情是在语法树构建完成后遍历 AST 做类型检查、登记变量声明、检查重复定义和未声明变量。符号表的核心数据结构是 Scope 链表每个 Scope 管理一层作用域。// symtab.c 作用域链表实现 typedef struct Symbol Symbol; struct Symbol { char name[64]; int type; // 0int 1float int initialized; // 是否已初始化 Symbol* next_in_scope; // 本作用域下个符号 }; typedef struct Scope { Symbol* head; struct Scope* parent; // 外层作用域 } Scope; Scope* scope_push(Scope* current) { Scope* s (Scope*)malloc(sizeof(Scope)); s-head NULL; s-parent current; return s; } Symbol* sym_lookup(Scope* current, const char* name) { for (Scope* s current; s ! NULL; s s-parent) { for (Symbol* sym s-head; sym ! NULL; sym sym-next_in_scope) { if (strcmp(sym-name, name) 0) { return sym; } } } return NULL; }sym_lookup 的查找顺序是“从内向外一层层找”内层作用域的同名变量会遮蔽外层。这个行为对应了 C 语言里局部变量遮蔽全局变量的语义。作用域进入和离开的时间点分别是遇到左花括号和右花括号进入函数体时调用 scope_push离开时 scope_pop 把整层符号全部丢弃。这个实现比“一张哈希表存所有变量”要正确得多后者在嵌套作用域里会直接翻车。3.4 中间代码生成三地址码的临时变量分配策略intercode.c 把语法树线性化成一串三地址码 Quad每行指令的形式是“op 参数1 参数2 结果”。这个阶段的核心工作有两个一是确定表达式求值的顺序二是为中间结果分配临时变量编号。看一下表达式“a b * c”生成的指令序列你就明白了。// intercode.c 三地址码生成示例 // 输入表达式a b * c // 生成中间代码 // t1 b * c // t2 a t1 // result t2 typedef struct Quad { int op; // OP_ADD / OP_SUB / OP_MUL / OP_DIV int arg1, arg2, result; // 操作数索引或常量编号 struct Quad* next; // 串成指令链表 } Quad;临时变量编号从 t1 开始每生成一个新运算结果就自增一次。乘法的优先级高于加法所以 b * c 先被求值、结果存入 t1随后 a 和 t1 再相加减得到 t2。这个过程对应了语法分析阶段 parse_term 在 parse_expression 内部先被调用的次序——语法树的后序遍历天然就是中间代码的生成顺序。这套源码的临时变量编号是全局统一的没有按作用域分段课程实验完全够用但如果你想把代码扩展到支持函数调用这个编号策略就需要做成“函数级隔离”。第 6 章二次开发部分我会给一个具体的改法。4. 避坑与排查实验跑不通的五个高频原因4.1 注释未闭合导致词法状态卡死现象测试文件里写了一个 /* 开头的注释但忘了写结束标记运行词法分析后发现从注释位置往后所有的代码都变成了空白程序还不报错。词法分析器里把 /* 识别成运算符后后面的字符被连续吞掉整个文件被当作 Token 流输出后续语法分析直接失败。原因lexer.c 没有把注释当作独立状态处理读到“/”时走了运算符分支下一个字符“*”被当作乘号注释内容里的每一行都被当成非法字符逐个触发报错或者被静默跳过。更隐蔽的情况是状态机里没有“在注释中”这个状态导致注释内容和代码混在一起。解决我一般在 lexer.c 里单独加一个 COMMENT_STATE 分支遇到 /* 后进入“读注释直到 */ 或 EOF”的循环。这个循环体内不做任何 token 识别只是逐字符前进并更新 ctx-line。如果读到文件结束还没见到闭合标记主动调 error 报行号——这才是正确行为注释不闭合是源程序的错误不能静默吞掉。4.2 左递归让递归下降解析器陷入死循环现象实验二跑一个简单的 a b 测试程序卡死CPU 占用拉满最后在 GDB 里 CtrlC 中断栈回溯显示 parse_expression 一直在调用自己。进度条走了十万次都没结束。原因这是典型的“把文法原封不动搬进代码”的翻车。原始文法 E → E T | T 直接翻译成函数parse_expression 第一件事就是调用 parse_expression永不触底。正常改法就是把左递归文法改写为 E → T {(|-) T}也就是第 3 章代码里展示的 while 循环形式。解决检查你写的递归下降函数凡是函数体第一行就调用同名函数的情况基本都是左递归。镇压办法是先写出非左递归的等价文法一般带星号和花括号的文法表示循环带问号的表示可选然后再翻译成代码。4.3 符号表作用域泄漏导致变量覆盖现象两个函数里都声明了局部变量 i解析第一个函数时正常解析第二个函数的声明时sym_lookup 查到了第一个函数里那个 i直接报“重复定义”。或者更糟糕函数 A 里对 i 的赋值居然写到函数 B 作用域的 i 上。原因进入新函数体时没有调 scope_push 压入新作用域或者把 scope_push 放在了错误的位置。常见误用是在 parser 还没看到左花括号时就切换了当前作用域或者 scope_pop 时把外层作用域也顺带释放了。解决在语义分析的回调里严格绑定花括号事件——遇到 { 调 scope_push遇到 } 调 scope_pop。排错时可以写一个测试用例两个函数各声明同名变量打印符号表确认是两个不同条目。拿这套源码做二次开发时注意别把 sym_lookup 用成“全局单表查找”。4.4 临时变量编号不统一的中间代码错乱现象中间代码输出里出现 t3 t3 1 这样的赋值或者一个变量从未被定义就被使用。检查 intercode.c 的日志发现有的模块从 1 开始编号有的模块从上一次的值继续编号两段临时变量编号重叠了。原因这套源码里临时变量的计数器和函数调用栈绑定如果你在生成中间代码时用了多个函数但计数器是全局静态变量没有在每个函数开头清零编号就会跨函数混乱。课程实验里一般只有一个主流程这个 bug 可能要等到扩展函数支持时才暴露。解决我的习惯是每进入一个函数体就重置临时变量计数这样每个函数的三地址码都从 t1 开始。输出的中间代码要按函数名分组这样后面做目标代码生成时寄存器分配才不用处理跨函数的编号冲突。4.5 测试用例的编码与换行符问题现象Windows 上编写测试用例后用 gcc 编译运行词法分析器把最后一个字符读成乱码或者行号统计比实际多了好几行。用 Notepad 打开源文件看到是 CRLF 换行而词法分析器只把 \n 当作换行\r 被当成了普通字符Token 值里混入回车符。原因Linux 工具链只认 \nWindows 记事本默认写 CRLF词法分析器没有对 \r 做丢弃处理。它在跳过空白字符的逻辑里只列了空格、制表符、换行回车符不被识别。解决在词法分析器的“跳过分隔字符”循环里加上 \r一行代码解决。另外一个顺手的小技巧是测试用例文件统一用 UTF-8 without BOM 保存BOM 的 EF BB BF 三个字节会被读成非法字符导致第一行所有 token 的行号全部错位。5. 环境搭建与运行把整套实验从源码变成可执行程序5.1 编译前的环境准备源码包是纯 C 项目没有任何第三方依赖编译环境只需要一个支持 C99 的编译器。Windows 上我一般用 MinGW-w64 的 gccmacOS 直接用系统自带的 clangLinux 上 sudo apt install gcc make 一条命令装齐。不需要额外安装 Flex、Bison 这类工具因为 parser.c 是手写的递归下降这一套源码的定位就是纯手工实现。检查 gcc 是否可用的命令gcc --version make --version如果你在两台机器上跑建议源码和测试用例的文本格式统一第 4 章提过的换行符问题就是跨平台最容易踩的坑。把文件同步到 Linux 上跑之前先执行一遍 dos2unix 转换省得词法分析器把 \r 也读进去。5.2 编译与运行Makefile 的作用源码包自带的 Makefile 把编译过程收敛成了一条命令。在源码包根目录执行 make会自动编译 src 目录下所有的 C 文件生成名为 compiler 的可执行文件。Makefile 的依赖关系写的很清楚——修改了 lexer.c 就只重新编译 lexer.o再重新链接增量编译不会浪费时间。make # 编译全部源码生成 compiler ./compiler test/test_expr.c # 对测试用例做词法语法语义中间代码编译过程如果报错第一优先看头文件的路径。Makefile 里用 -Iinclude 指定头文件目录如果你的 IDE 没导入 include 目录编译器会各种找不到 token.h这是最常见的“明明源码没问题却编译不过”的原因。compiler 的默认行为是读取一个 .c 文件依次执行四个阶段的处理最后把生成的中间代码打印到 stdout。想只看词法分析结果可以在 intercode.c 的 main 调用处临时注释掉中间代码生成这一行——我拆包时就是这么干的先验证前一个阶段的输出再放行下一个阶段排查效率高很多。5.3 各实验的验证方法测试用例对照输出源码包里 test_expr.c 是最简单的入口内容是一串表达式int a 10; float b 2.5; a a b * 3;对应生成的中间代码应该是类似下面的输出t1 b * 3 t2 a t1 a t2注意顺序——b * 3 率先求值这就是语法分析阶段 parse_term 先于 parse_expression 执行的直接结果。输出顺序如果反了说明你的 parser.c 里乘法先于加法处理的逻辑没有正确传导到中间代码生成。这个测试用例是验证“语法优先级正确传导到代码生成”的重要指标。5.4 调试技巧开启 lexer 的 trace 模式源码头文件里预留了一个名为 LEXER_TRACE 的宏开关。打开后next_token 每返回一个 Token 就在 stderr 打印一行 token 的类型和词素文本方便你看清词法分析器到底从源文件里读了什么。这在排查“多吞字符”“少吞字符”时比想象的要有用。gcc -DLEXER_TRACE -Iinclude src/*.c -o compiler_debug ./compiler_debug test/test_decl.c一个血泪经验词法层的错误症状会在语法层被放大十倍。比如标识符识别少吞了结尾字符parser 看到的是两个 token 粘在一起报错位置完全不指向真正的词法问题。所以我的习惯是先开 trace 验证 token 序列再关掉去排查语法问题不要一个 debug 找一晚上。6. 二次开发实战给这个编译器加一个幂运算符选幂运算符 ^ 作为扩展案例是因为它涉及编译流水线的全部四个阶段改动链路完整且不复杂。语音转换到现网就三步动作每一段都能验证中间结果。先改词法层。token.h 里的运算符表增加一个条目lexer.c 的 ops 数组同步加一个 ^。注意词法层要处理双字符运算符的优先级逻辑比如 ^ 这类复合赋值运算符如果后续要支持词法层得用最长匹配原则逐个对照。这里我们只加单字符 ^。再改语法层。幂运算是右结合的文法要写成 F → F ^ F | 其他因子左右结合性不同生成的代码顺序完全不同。右结合意味着 2 ^ 3 ^ 2 要解析成 2 ^ (3 ^ 2)所以解析因子时遇到 ^ 不能像加减乘除那样写成 while 循环要改成递归调用parse_factor 里检测到 ^ 后继续递归调用 parse_factor 解析右侧操作数。然后改语义和中间代码层。intercode.c 的 Quad 结构体里 op 字段增加 OP_POW中间代码生成时把语法树里 NODE_POW 节点翻译成一条 t_result t_left ^ t_right。语义分析阶段不需要额外处理因为 ^ 和加减乘除一样属于二元运算类型检查规则照抄乘法的即可。改造完的验证方式是写一个测试用例输入 2 ^ 3 ^ 2预期中间代码输出应该是先算 3 ^ 2 得到 t1再算 2 ^ t1 得到最终结果。这个输出顺序直接反映右结合性的实现是否正确。这套源码改起来的一个重要经验编译器的每一个功能都是沿着“词法 Token → 语法树节点 → 三地址码指令”这条链条逐层落地的改动词法层时就要想清楚它对应语法树的哪个节点、会生成哪条中间代码。我后来每次做扩展都强制自己先画一条改动链路图从 token 类型到 AST 节点到 Quad 指令每一步标注影响的范围全部标注完才开始改代码。那次之后改完编译器的各个阶段基本一次通过希望这个习惯也能帮到你。本文还有配套的精品资源点击获取