简介编译原理是计算机科学的核心领域这套实验代码来自中国海洋大学2020年春季学期编译原理课程面向该校计算机相关专业学生和自学编译器构造的开发者。资源覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与编译器综合的完整教学链条对应8个实验及实验要求既有手工实现也涉及Flex、Bison等工具可系统训练编译器各阶段实现思路。压缩包共74个文件约774KB包含C源码、Flex词法规则、Bison语法规则、头文件、可执行程序、makefile与实验要求文本目录按实验编号整理便于对照练习和反复调试。实验配有测试用例、产生式说明和运行结果输出能够帮助理解抽象语法树、符号表、类型检查等关键概念尤其适合需要完整实验代码与可运行样例的课程学习者作为参考已有4400余人学习下载。1. 编译原理全套实验与其从零硬写不如先拆框架如果你这学期也在啃编译原理大概率绕不开这么一套组合拳词法分析、语法分析、语义分析、中间代码生成。某高校的课程把这几个环节拆成五个实验每个实验单独交源码和实验报告最后合成一个能跑通 if-else、while、函数声明的迷你编译器。我拿到这套实验源码包时的第一反应是“又是个黑匣子”翻完才发现里面的坑早有人趟过一遍——词法分析里最容易翻车的换行符处理语法分析里悬空 else 的歧义语义阶段符号表作用域没回滚导致的重复声明误报每一条都有对应解法。这份资源适合三类人实验截止前需要快速补进度的想照着完整框架重写一遍验证理解的以及想知道课程设计里哪些点容易丢分的。下面按实验顺序拆开讲。2. 实验全景一份源码包如何覆盖前端到中间代码2.1 五个实验的划分与提交清单编译原理课程实验一般不会让“一个编译器一次交齐”而是拆成阶段提交既避免最后一晚通宵也方便在中间卡进度。这套资源包的划分方式很典型词法分析、语法分析、符号表与语义分析、中间代码生成最后是一个综合性集成实验。有些学校还会追加目标代码生成或自己写虚拟机但核心始终是前面这四段。下面这个表格基本就是这套实验的评分结构交作业前照着这一列检查比对着课本目录检查靠谱得多。实验编号覆盖内容核心考察点常见交付物实验一词法分析状态机建模、正则表达式、Token 分类Lexer 源码 测试用例实验二语法分析文法改写、递归下降 / LR、错误处理Parser 源码 文法说明实验三符号表与语义分析作用域、类型检查、属性计算SymbolTable 源码 语义测试实验四中间代码生成三地址码、控制流翻译、数组寻址IR 输出 运行记录实验五综合集成前后端串联、错误恢复、报告完整工程 演示记录注意实验三和实验四经常被合并成一个“语义分析”大实验但内部还是分两段验收先检查符号表再检查中间代码。这份资源里两者分开建目录说明课程组确实是想让学生分两次提交。2.2 开发环境与工具链选型很多人在环境选择上纠结半天其实课程实验的核心就一句话老师要在你的机器上能一键编译、一键跑通。资源里的源码是用 C 写的工程结构保持得比较干净不依赖 flex、bison 这类生成器而是纯手写词法状态机和递归下降解析器。手写还是用生成器是个值得说清楚的选择。flex/bison 的优势是开发快正则表达式和文法写完后自动生成 C 代码但劣势也明显一旦匹配行为不符合预期生成的 DFA 像一个黑匣子很难定位到底是哪一条转移写错了。课程实验通常还要求交实验报告手写代码更容易把“状态转移图”和“递归下降子程序调用关系”画出来。另一个现实情况是部分课程明确禁止使用 bison/yacc要求必须体现自己对状态转移和栈式解析的理解。所以我一般建议除非老师明确允许否则用手写至少把词法分析器手写出来。编译器版本用支持 C11 以上的就行资源里的代码没有用到特别新的特性最常用的就是vector、unordered_map、string和标准 IO。如果你本机只有默认 GCC直接编译通常不会报错。工程根目录放一个 Makefile 管构建测试脚本一般放在tests/下。看这份资源的目录结构基本是一个标准的前端项目布局. ├── include/ │ ├── token.h │ ├── lexer.h │ ├── parser.h │ ├── ast.h │ └── symbol_table.h ├── src/ │ ├── lexer.cpp │ ├── parser.cpp │ ├── ast.cpp │ ├── symbol_table.cpp │ └── main.cpp ├── tests/ │ ├── test_lexer.cpp │ ├── test_parser.cpp │ └── test_ir.cpp ├── examples/ │ ├── test_if.c │ ├── test_while.c │ └── test_array.c ├── Makefile └── README.md2.3 源码目录怎么读入口、依赖和 Makefile拿到源码包建议按照“Token - Lexer - Parser - AST - SymbolTable - main”的顺序读不要一上来就打开main.cpp。token.h定义了所有 Token 类型比如关键字、标识符、整型字面量、运算符和分号这是前端模块之间的通用接口lexer.h只负责把字符流切成长度为 1 的 Token 流parser.h消费 Token 流并构建 AST。模块之间通过头文件的接口咬合内部实现互不牵扯。这里先看 Makefile确认构建目标是什么通常目标名是compiler或minic。然后直接跑make如果编译通过再进入tests目录逐个跑测试最后看examples里的样例源文件。常见调用方式是接受一个文件路径作为参数make ./minic examples/test_if.c如果实验要求生成中间代码程序会把三地址码打到终端或写进out.ir。main.cpp里一般长这样int main(int argc, char* argv[]) { if (argc 2) { std::cerr usage: minic file std::endl; return 1; } std::ifstream in(argv[1]); Lexer lexer(in); Parser parser(lexer); auto program parser.parseProgram(); SemanticAnalyzer analyzer; analyzer.check(program); IrGenerator generator; generator.generate(program); return 0; }argc判断必须有很多同学在自己机器上跑通交到老师那里因为没传文件名直接崩了这种零分很冤。Lexer拿到文件流后Parser从 Lexer 里逐个取 TokenAST 构建完再做语义检查和中间代码生成整个链路非常直白。3. 词法分析手写状态机的实现细节3.1 手写自动机还是 flex 生成词法分析实验的核心是正则表达式到状态机的转换。用 flex 写几行正则确实很快但实验报告要求画 DFA 状态转移图时很多人就答不上来了。手写状态机则相反每个状态对应代码里的一个枚举值每次读入一个字符就做一次状态转移逻辑完全透明。以 C 语言子集为例词法需要处理的 Token 大致分四类标识符与关键字、整数与浮点数、运算符与分界符、字符串与注释。每类对应一个或多个状态。我见过不少实现把状态枚举写得超级长其实没必要把状态数控制在 START、IN_ID、IN_NUM、IN_STRING、IN_COMMENT 这几个核心状态用一个switch就能覆盖绝大部分语言。选手写还有一个实践原因编译器前端最花时间的不是逻辑而是“边界条件”。flex 的正则把浮点数、负数、注释这些边界条件隐藏了一旦出问题你不知道是正则写错还是优先级不对。手写状态机则要求你显式处理字符回退和最长匹配这套肌肉记忆对后面做语法分析也很有用。3.2 状态机核心代码与关键参数下面这段代码是从资源包里提炼出的核心框架只看nextToken()这一个函数就能理解整套词法设计。为了避免每次判断是不是文件尾构造时会在输入缓冲末尾偷偷塞一个EOF字符。Token Lexer::nextToken() { LexState state START; std::string lexeme; while (true) { char c peek(); // 只看不消费 switch (state) { case START: if (isalpha(c) || c _) { state IN_ID; lexeme c; advance(); } else if (isdigit(c)) { state IN_NUM; lexeme c; advance(); } else if (c || c - || c * || c /) { lexeme c; advance(); return Token(OP, lexeme, line, col); } else if (c || c \t) { advance(); // 空白跳过 } else if (c \n) { advance(); line; col 0; } else if (c EOF_CHAR) { return Token(END, , line, col); } else { error(unexpected character); } break; case IN_ID: if (isalnum(c) || c _) { lexeme c; advance(); } else { return makeKeywordOrId(lexeme); } break; case IN_NUM: if (isdigit(c)) { lexeme c; advance(); } else if (c .) { lexeme c; advance(); state IN_FLOAT; } else { return Token(NUM, lexeme, line, col); } break; case IN_FLOAT: if (isdigit(c)) { lexeme c; advance(); } else if (c .) { error(invalid float: two dots); } else { return Token(FLOAT, lexeme, line, col); } break; } } }peek()只返回当前位置字符但不移动指针advance()才真正消费字符并更新行号列号这样的分离让你可以在一个状态里多看几个字符而不丢失位置。所有能被归纳为同一类 Token 的字符流最终都汇聚到对应的结束分支。从参数角度看line和col应该从 1 开始累计col在遇到\n时清零。错误处理里必须携带行列号否则语法分析阶段的报错无法定位。makeKeywordOrId内部查关键字表查到了就是关键字 Token查不到就是标识符 Token。3.3 测试用例把贪婪匹配的坑堵在前面词法分析的测试用例不需要多但必须覆盖边界。我通常建议至少准备下面这五组输入跑不过就不用进语法分析了。// 用例1单个运算符不能拆成和 1 2 // 用例2数字后面紧跟字母报错还是切分 123abc // 用例3浮点数.5和1.要不要支持 x 1.5 .5 // 用例4注释未闭合 /* comment // 用例5最后一个 token 没有换行符 a 1很多人的词法器能处理前面四组却在第五组上翻车。原因是nextToken()依赖空格或运算符来触发“返回当前标识符”如果读到了文件尾还没触发标识符就永久停留在缓冲区里。解决办法是在初始化时给输入末尾追加一个哨兵字符或者在advance()里检测到 EOF 后主动返回当前 lexeme。资源里对这种情况有处理但我在课上见过太多实现都没加这一层判断。4. 语法分析递归下降与错误恢复4.1 文法改写消除左递归与提取公共因子语法分析实验通常要求你选的文法能被递归下降解析器处理。递归下降本质上是 LL(1) 解析最怕两件事左递归和公共前缀。左递归的出现很自然因为常人习惯把表达式写成E - E T | T但解析器不能先调用自己再读 token否则会无限递归。标准做法是把左递归改写成右递归原文法 E - E T | T 改写后 E - T E E - T E | ε这里E对应 EBNF 里的( T )*在递归下降里实现时其实不需要真的建一个parseEPrime函数用一个while循环就能表示“循环匹配加法运算符和操作数”。所以代码比文法更简洁。公共前缀的问题类似如果两个产生式都以同一个非终结符开头那么解析器读完第一个 token 后无法决定走哪条分支。解决方法是提取左公因子。比如if语句的悬空 else 改造本质上就是一次公因子提取这个在第 5 章会专门讲。4.2 递归下降子程序与 FIRST/FOLLOW 集递归下降解析器的每个非终结符对应一个解析函数函数返回一个 AST 节点。下面这段代码是表达式层级的典型实现std::unique_ptrExpr Parser::parseExpression() { auto expr parseTerm(); // 先处理乘除法所在的层级 while (token.is(TokenType::PLUS) || token.is(TokenType::MINUS)) { Token op token; advance(); auto right parseTerm(); expr std::make_uniqueBinaryExpr(op, std::move(expr), std::move(right)); } return expr; }逻辑说明parseTerm()对应文法里的T它内部再调用parseFactor()处理括号和单个数字。PLUS和MINUS的判断放在 while 里语义就是“任意多个 ( | - ) T ”这与改写后的E完全等价并且天然保留了左结合性。std::make_unique生成新节点后左边子节点是之前循环累积的结果右边是当前新解析出的操作数。这个实现里最有价值的点是循环就是右递归的迭代形态。写代码时可以不用显式计算 FIRST 集但你要知道为什么这里能形成循环因为parseExpression调用parseTerm后下一轮只要 peek 到加减号就能进入下一次循环不可能死递归。真正的 FIRST/FOLLOW 集计算一般被放在parseFactor或语句解析里用于决定是否调用某个分支。比如解析if语句时求值表达式之后遇到RBRACE还是ELSE直接决定了走哪个分支。手算 FIRST 集不复杂把每条产生式右部首字符收集起来即可FOLLOW 集要小心空串传递资源里的实验报告模板把这两个集合的计算过程写成了表格这是报告里最值钱的部分。4.3 错误恢复同步 token 集怎么设好的语法分析器不应该碰到第一个错误就崩溃而应该尽量跳过一段代码接着解析后面的内容让一次编译能暴露多个错误。递归下降解析器里最常用的错误恢复手段是同步 token 集合。做法是每当一个解析函数发现自己期望的 token 对不上就调用同步例程把 token 一直丢弃到某个安全的同步点。同步点一般选分号、右花括号或者某些关键字的开始位置。void Parser::synchronize() { advance(); while (!token.is(TokenType::EOF)) { if (token.is(TokenType::SEMI)) { advance(); return; } if (token.is(TokenType::RBRACE)) { return; // 不消费右花括号留给上层处理 } advance(); } }这个方法很简单但同步 token 的选择有讲究。选少了比如只看分号遇到漏写右花括号的错误就会一路跳过整个函数选多了比如把RBRACE也消费掉又可能导致块语句的括号配平出错产生连锁误报。我一般建议分号在同步时消费掉右花括号留给上级处理这样块结构不容易被破坏。错误恢复的判定标准是“少误报、不掩盖真错误”实验里老师会用几组带语法错误的输入来测看你的编译器报错位置准不准。同步 token 没设计好的代码最典型的表现是“错一行报三行”那基本就是同步过度了。5. 避坑课程实验里最常见的五个翻车点5.1 未初始化变量让状态机卡死在循环里现象词法分析器一运行就卡死CPU 占用百分之百终端输出一堆乱码或直接无输出。原因advance()函数里用来暂存当前字符的成员变量没有初始化第一次调用peek()时读到的是一块栈上残留数据既不是字母也不是数字更不是空格和文件结束符。状态机一边读一边往前挪指针永远等不到一个能触发return的字符于是陷入死循环。解决在 Lexer 构造函数里把所有成员变量初始化尤其是当前字符和行列号然后主动调用一次advance()把第一个真实字符读进来。Lexer::Lexer(std::istream input) : input(input), line(1), col(0), currentChar(0) { advance(); // 读入第一个字符 }另外不能只依赖currentChar判断是否到文件尾advance()里要把input.get(currentChar)的返回值保存下来文件读到底要同步设置一个isAtEof标志后续状态转移优先检查该标志。5.2 换行和 EOF 处理不当导致最后一个 token 丢失现象源程序最后一行如果没写换行符最后一个变量名没有被识别成 token编译报“无效输入”。原因词法分析器通常以空白、运算符作为标识符结束的触发条件。文件已经读完但currentChar还没被“消费”也没有触发标识符结束的逻辑整个 lexeme 留在缓冲区里最终被直接丢弃。解决在advance()中检测到读不到新字符时把当前状态强制切到“缓冲区内 lexeme 可返回”的状态。可以在nextToken()的IN_ID分支里显式判断 EOF也可以更简单打开文件后先向内存 buffer 尾部追加一个\n这样最后一个标识符一定会被空白符终结。很多生产级编译器的做法是在输入流末尾加一个不可见的哨兵 token词法器读到哨兵就返回 END。这个思路是通用的。5.3 浮点数与负数的词法冲突现象输入1..2时词法器把1.识别成浮点数然后剩下.2报“非法字符”输入-3时被拆成负号-和数字3语法分析阶段不好处理。原因浮点数正则写成[0-9](.[0-9])?时扫描器看到小数点就直接贪婪吞下不会向后多看一个字符来判断这是否是..而某些教学语言里..是区间运算符。负数则是一个语法问题把一元负号交给词法层处理会让 Token 种类膨胀也破坏了词法和语法之间的职责边界。解决词法分析器在数字状态遇到.时先往后读一位如果下一个也是.说明这是区间运算符的开头数字解析立即结束并把小数点“吐回”输入流。负数不放进词法器统一在语法层用“一元负号”产生式处理Factor - NUM | - Factor | ( Expr ) | ID这样-3会被解析成- (3)的 Factor 节点类型检查和中间代码生成都只需要考虑一元运算符而不需要单独定义负数 Token。这个决策看起来简单但能省掉后面很多麻烦。5.4 悬空 else 与语句结束符的歧义现象输入if (a) if (b) x 1; else y 2;按 C 语言规则 else 应该匹配内层 if但解析器却把它挂到了外层 if 上语义结果不对。原因递归下降解析器在解析完第一个 if 的 then 分支后如果 then 分支本身也是 if它无法确定当前遇到的 else 是属于内层还是外层。普通文法存在二义性递归下降默认“就近匹配”是碰巧不是可靠保证。解决把语句文法拆成“完整语句”和“不完整语句”两个非终结符这是教科书标准做法Stmt - MatchedStmt | UnmatchedStmt MatchedStmt - if ( Expr ) MatchedStmt else MatchedStmt | otherStmt UnmatchedStmt- if ( Expr ) Stmt | if ( Expr ) MatchedStmt else UnmatchedStmt解析器的parseIfStatement要设计成先匹配接收条件表达式随后判断当前 token 是不是else从而决定走哪个分支。从实现角度把悬空 else 的判断放在语法层比在 AST 构造后做修正干净得多。这个坑在实验报告里属于“设计亮点”写出来比单纯贴代码更容易拿分。5.5 符号表作用域没回滚导致重复声明误报现象两个完全不同的函数里都声明了int x;语义检查阶段却报“变量 x 重复声明”。原因符号表实现只有一个平铺的std::unordered_mapstd::string, VarInfo插入和查找都只对着这一个表。进入函数 A 时插入x接着进入函数 B 又插入x查找时只看有没有同名 key完全没考虑这两个x在不同的作用域里。解决把符号表改成栈式作用域结构每一层作用域对应一个独立的unordered_map进入大括号或函数体时压栈退出时弹栈。查找变量时从栈顶往下逐层查struct SymbolTable { std::vectorstd::unordered_mapstd::string, VarInfo scopes; void pushScope() { scopes.emplace_back(); } void popScope() { scopes.pop_back(); } VarInfo* find(const std::string name) { for (auto it scopes.rbegin(); it ! scopes.rend(); it) { auto found it-find(name); if (found ! it-end()) { return found-second; } } return nullptr; } bool declare(const std::string name, const VarInfo info) { auto top scopes.back(); return top.emplace(name, info).second; } };注意declare调用top.emplace的返回值插入失败说明当前作用域已经存在同名变量这是“重复声明”的唯一判断依据。查找时要考虑嵌套作用域比如外层函数变量可以被内层引用。如果popScope忘记调用错误照样会出现所以实验三的测试用例里专门设计了一段跨函数的同名变量程序用来验证作用域是否正确回滚。6. 验收技巧用三地址码自检整条编译链路6.1 先把语义动作写进属性栈做语义分析和中间代码生成时有一个很实用的技巧不要等到 AST 遍历完成后才生成 IR而是在递归下降解析的过程中同步生成。这样语义错误能提前暴露调试时也能直接看到“某条语句翻译成了哪几条指令”。拿a b * c来说递归下降从parseExpression进入parseTerm再进入parseFactor从最深的乘法开始翻译。关键函数是生成三地址码的辅助过程struct Attr { std::string type; std::string addr; }; std::string IrGenerator::newTemp() { return t std::to_string(tempCount); } void IrGenerator::genBinaryOp( Attr result, const Attr left, const Attr right, const std::string op) { result.addr newTemp(); emit(result.addr left.addr op right.addr); }emit把生成的字符串写进全局指令列表。每次生成新临时变量tempCount自增一次这样每一行 IR 的编号不会重复。参数里left和right的addr可能是普通变量名也可能是上一个临时变量最终都能拼出合法的表达式。6.2 两分钟自检法输入下面这段小程序对比自己编译器的输出是否符合预期a 2 3 * 4;预期三地址码t1 3 * 4 t2 2 t1 a t2如果输出变成了a 2 3 * 4这种一条指令的形态说明parseExpression没有正确划分层级如果输出是t1 3 * 4、t2 2 3、a t2 * 4说明节点合并顺序出了错。自检的思路就是拿几个已知语义的小程序先手写出三地址码再比较机器输出不匹配就逐层打断点看 AST 结构。这个方法在跑if-else和控制流时更好用。if (a 0) x 1; else x 2;的 IR 里必须出现两个标签一个跳过 then 分支一个跳转到 if 结尾。见过太多同学代码里只生成了一个标签自然是流程图没画对。从那以后我每次提交实验前都强制自己跑一遍“中间代码自检清单”表达式层级对不对、临时变量编号从 1 开始还是从 0 开始、标签是否成对出现。这套习惯帮我避开了大部分白扣的分资源包里的实验报告模板也留了一张空表让你自己填测试记录直接照着写就行。希望帮到你。本文还有配套的精品资源点击获取