简介这份资料面向山东大学编译原理与技术课程新版实验一至三专注于编译器前端构建核心覆盖词法分析器与语法分析器两大模块也涉及符号组织与对象生成等实验关联内容适合正在学习编译原理、需要独立完成实验或对照自查的本科生使用。压缩包共15个文件其中8个头文件和5个C源文件分别承载lexer、parser、对象生成及各数据结构定义另附1个构建脚本和1个Markdown说明文档便于按模块阅读代码、快速编译与验证效果。包体仅30KB结构紧凑。目前已有58人学习下载。借助该工程读者可以直观理解有限自动机如何完成Token识别、上下文无关文法如何构造抽象语法树并熟悉递归下降、LL或LR分析的实现组织方式同时对处理不规则语法、编译错误恢复以及为后续代码生成预留接口等问题也能获得可供参考的排错思路和代码骨架有利于把实验要求与理论知识点逐一对应起来。1. 山东大学编译原理实验一~三这三个作业不是分开写是一条编译前端流水线很多同学拿到新版实验一~三以为是一个词法分析器、一个语法分析器、一个中间代码生成器三个程序各自交差就行。实际等你把三个实验的验收要求放在一起看就会发现实验一吐出的 token 流要能被实验二消费实验二在做 LL(1) 预测分析或递归下降时挂的语义动作要能输出实验三要求的三地址码。三件事串起来才是这门编译原理与技术实验真正想让你搭的东西——一条能跑通的最小编译前端。这篇文章不贴完整源码讲清楚每个实验的取舍、关键参数和我在这些实验里踩过的坑。2. 实验一词法分析手写 DFA 状态转移表还是用 flex接口决定成败2.1 为什么我不建议一上来就用 flex黑匣子代码和接口别扭编译原理实验一到实验三最常见的翻车点反而不是词法本身而是选错了实现方式。用 flex或者 Java 界的 JFlex生成词法分析器表面上几行正则就写完但生成的 C 代码是一大坨表驱动的自动机默认只暴露yylex()返回 token 编号这个接口语义值要通过全局变量yylval传递。你后面要手写 LL(1) 预测分析器时这个接口用起来非常别扭token 编号、语义值、行列号散在两个文件里排查问题全靠脑内关联。我在搜索引擎里翻“java编译原理”相关的作业贴时见过不少用 JFlex 写实验一、然后用 JavaCC 写实验二最后阶段三个实验代码风格完全不统一的例子。新版实验如果明确规定不允许调用自动生成工具那就必须手写即便允许我也建议手写 DFA。你后面实验二和实验三要反复回来改 token 定义——比如发现没被识别、注释跨行时行号不对——手写的状态转移表改起来一目了然flex 要重新生成还不敢保证不引入新问题。2.2 token 设计表关键字、运算符、界符怎么划分才不挡后续的路词法分析的第一个实际问题是 token 种类怎么定。以山大实验最常见的类 C 子集为例我一般分成五类标识符、数字字面量、关键字、运算符、界符再加上一个文件结束符。下面是 token 设计和语义值的对应关系token 类型词法模式语义值用途ID字母或下划线开头后接字母/数字/下划线字符串变量名变量与函数名NUM数字串实验阶段通常只做整数整数值字面量KEYWORDint/float/if/else/while/return/void 等关键字编号语法结构词OP - * / ! || !运算符字符串表达式与判断界符( ) { } ; ,单个字符语法结构分隔END文件结束-语法分析的结束标志这里有个容易被忽略的设计决策关键字是单独一类还是并入 ID 再查表我建议单独一类。因为实验二的预测分析表用 token 类型做横向表头如果你把if、else都算作 ID语法分析器就只能靠sval字符串区分它们预测分析表没法写。关键字单独命名成KEYWORD_IF、KEYWORD_ELSE后面一切都会清爽很多。2.3 核心代码DFA 驱动循环与非法字符跳过的恢复策略手写词法分析器的核心是一个按状态转移推进的循环。下面这个nextToken()是实验一能直接跑的骨架状态判断用分支而不是转移表因为实验一阶段的 token 种类有限分支比查表更直白// token.hTokenType 和 Token 结构 enum class TokenType { ID, NUM, KEYWORD, OP, LPAREN, RPAREN, LBRACE, RBRACE, SEMI, COMMA, END }; struct Token { TokenType type; std::string sval; // 标识符名 / 运算符字符串 int ival 0; // 数字字面量的值 int line, col; // 出错定位用 };// lexer.cpp词法分析主循环 Token Lexer::nextToken() { skipWhitespaceAndComments(); // 内部调用 advance()维护 line/col Token tok; tok.line line_; tok.col col_; char c cur_; if (isalpha(c) || c _) { std::string id; while (isalnum(cur_) || cur_ _) { id cur_; advance(); } // 先收完整标识符再查关键字表避免把 if 切成 i f auto it keywords_.find(id); tok.type (it ! keywords_.end()) ? TokenType::KEYWORD : TokenType::ID; tok.sval id; return tok; } if (isdigit(c)) { int v 0; while (isdigit(cur_)) { v v * 10 (cur_ - 0); advance(); } if (isalpha(cur_)) { // 形如 123abc属于词法错误必须停在当前位置 std::cerr lex error at line_ : col_ : invalid digit after number\n; return nextToken(); // 跳过该错误后继续 } tok.type TokenType::NUM; tok.ival v; return tok; } advance(); // 先吃掉当前字符再看后继 switch (c) { case : tok.type TokenType::OP; tok.sval (cur_ ) ? (advance(), ) : ; break; case : tok.type TokenType::OP; tok.sval (cur_ ) ? (advance(), ) : ; break; case : tok.type TokenType::OP; tok.sval (cur_ ) ? (advance(), ) : ; break; case : if (cur_ ) { advance(); tok.type TokenType::OP; tok.sval ; } break; case |: if (cur_ |) { advance(); tok.type TokenType::OP; tok.sval ||; } break; case (: tok.type TokenType::LPAREN; break; case ): tok.type TokenType::RPAREN; break; case {: tok.type TokenType::LBRACE; break; case }: tok.type TokenType::RBRACE; break; case ;: tok.type TokenType::SEMI; break; case ,: tok.type TokenType::COMMA; break; default: std::cerr lex error at line_ : col_ : unexpected char c \n; return nextToken(); } return tok; }这段代码有几个参数和逻辑需要说明。keywords_是std::unordered_mapstd::string, TokenType初始化为{if: KEYWORD_IF, else: KEYWORD_ELSE, ...}查表要在标识符完整收集之后做这是防止把elseif误判成else加if的关键。advance()是负责推进cur_并更新line_/col_的唯一入口注释和换行都在skipWhitespaceAndComments()里处理——行号的更新必须集中在advance()内部否则你会看到错误位置不断漂移这是实验一最常见的玄学 bug。非法字符的恢复策略我选择了跳过加报错打印错误位置后递归调用nextToken()继续。这个策略的代价是int ab;会被识别成int a和b错误在语法分析阶段才暴露但优点是自动机永不卡死验收时能一口气处理完整个文件把全部词法错误列出来。新版实验对恢复策略没有硬性要求能定位就行。如果你想在词法层就终止把return nextToken()换成exit(1)即可。3. 实验二语法分析LL(1) 预测分析表的构造与表驱动解析3.1 文法预处理消除左递归和提取左公因子是分水岭实验二拿到手第一件事不是写代码是检查文法是不是 LL(1)。山大新版实验给的类 C 文法肯定有表达式部分而表达式天然带左递归E → E T | T。LL(1) 预测分析要求每个产生式右侧的 FIRST 集不相交左递归文法直接造表必然冲突。所以第一步是消除左递归E → T E E → T E | - T E | ε T → F T T → * F T | / F T | ε F → ( E ) | id | num第二步是提取左公因子。比如stmt → if ( E ) stmt | if ( E ) stmt else stmt这个写法两个产生式都以if开头不是 LL(1)。要改写成stmt → if ( E ) stmt else_part else_part → else stmt | ε改写之后才能在预测分析表中给(stmt, if)这个格子填唯一一个产生式。很多同学在这一步省略了公因子提取导致分析表出现 multiply defined entries一跑就报“conflict”。实验二的这一半工作量考察的就是文法改写基本功建议在代码里单独放一份文法的文本定义注释里保留改写前后的对照验收时老师问起来你也能讲清楚。3.2 FIRST 和 FOLLOW 集合的计算顺序以及手工校验技巧预测分析表每个格子的内容由 FIRST 和 FOLLOW 集合共同决定对产生式A → α把FIRST(α)里的终结符填入(A, 那个终结符)格子如果α能推导出 ε再把FOLLOW(A)里的终结符也填进去。这里最坑的是手算 FOLLOW 时丢项尤其容易忘记把$加入开始符号的 FOLLOW 集或者忘记处理A → α B β中 β 为 ε 的情况。我一般不建议手算集合而是写一小段固定点算法代码用std::setstd::string迭代到集合不再变化为止。计算顺序其实没有严格的依赖顺序只要循环跑够轮数都会收敛重点是每一轮对每条产生式都完整扫描一遍。校验技巧是打印出每个非终结符的 FIRST 和 FOLLOW 后手动挑几个关键符号验证——比如入栈开始符号时栈底是$程序跑完第一轮后program的 FOLLOW 里必须有$空白产生式ε要从 FIRST 集合里显式剔除否则预测分析表会被 ε 污染。这个集合计算脚本是实验二唯一的后悔药。分析表一旦出现冲突不是去调主循环代码而是回头检查 FIRST/FOLLOW 打印结果九成问题出在集合计算而不是表驱动逻辑。3.3 表驱动预测分析器骨架同步 token 与 panic mode 恢复预测分析器的主循环用栈来模拟推导过程每次看栈顶符号和当前输入 token 决定动作。下面是核心代码// parser.cpp表驱动 LL(1) 预测分析 bool Parser::parse(const std::vectorToken tokens) { std::stackstd::string stk; stk.push($); stk.push(startSymbol_); // startSymbol_ program size_t pos 0; while (!stk.empty()) { std::string top stk.top(); std::string lookahead tokenToString(tokens[pos]); // 关键用 token 类型而非 sval if (top $) { if (lookahead $) return true; error(unexpected end of input); return false; } if (isTerminal(top)) { if (top lookahead) { stk.pop(); pos; } else { // 终结符不匹配时丢弃当前输入 token继续尝试 error(unexpected token lookahead); pos; } } else { std::string prod table_[{top, lookahead}]; if (prod.empty()) { // panic mode跳过输入直到同步 token 出现 recover(top, pos, tokens); continue; } stk.pop(); // 产生式右侧逆序入栈ε 产生式什么也不压 std::vectorstd::string rhs split(prod); for (auto it rhs.rbegin(); it ! rhs.rend(); it) { if (*it ! ε) stk.push(*it); } } } return pos tokens.size(); }代码里tokenToString()把TokenType映射成文法终结符名字比如KEYWORD_IF映射成ifID映射成id。这里注意lookahead不能直接用sval因为if和变量ifx的 sval 不同但 token 类型不同分析表按类型查才是 LL(1) 的本意。table_的类型是std::mapstd::pairstd::string, std::string, std::string用std::map而不是unordered_map因为std::pair的哈希在旧版 C 标准下要自己写map直接能用还能打印调试。错误恢复采用 panic mode栈顶是非终结符且表项为空时recover()把输入 token 跳过直到遇到 FOLLOW 集合中的同步 token再把栈顶非终结符弹出。这个策略的代价是错误定位会略偏但换来的是分析器能继续处理后面的输入把整个文件里的语法错误都报出来。一个重要参数是同步 token 集合我建议用FOLLOW(非终结符) ∪ {;, }}把分号和右花括号加进去后错误恢复的成功率明显上升——很多同学卡在“报了一个错就死循环”就是同步集合里漏了分号。如果你拿到的是递归下降版本要求本质一样每个非终结符写成一个bool parseXxx()函数内部根据 FIRST 集合决定走哪个分支遇到树上的叶子就match(终结符)。递归下降的优点是语义动作好挂实验三的代码生成会顺滑很多缺点是文法是 LL(1) 这件事要自己保证代码里每个分支的 FIRST 冲突一眼就能看出来。4. 实验三语义分析与中间代码三地址码生成符号表作用域是重头4.1 实验三交什么三地址码的版本选择与打印格式实验三验收时看的是中间代码输出常见要求是打印三地址码也叫四元式。每条四元式形如(op, arg1, arg2, result)常见操作符集合如下操作符含义arg1arg2result - * /算术运算左操作数右操作数新临时变量赋值右值空左值jmp无条件跳转目标标签空空jnz真值跳转条件目标标签空label标签定义标签编号空空call / ret函数调用与返回函数名/返回值空空中间表示也可以选抽象语法树但语法树要再做一次遍历才能得到代码实验三只要求“能形成中间代码”时三地址码打印出来直观出错好定位。我一般建议四元式输出时用\t或空格对齐四列验收时老师一眼能看明白也方便你写 golden test 做 diff。4.2 栈式符号表进入作用域 push退出作用域 pop 的时机语义分析第一次接触变量遮蔽时最容易写错的是作用域的退出时机。符号表设计成作用域链每个作用域一个哈希表所有作用域叠成栈// symtab.h栈式作用域符号表 struct Symbol { std::string name; std::string type; // int / float / ... int offset 0; // 实验三阶段可以只打印不需要真实分配 }; class SymTab { public: void pushScope() { scopes_.push_back({}); } void popScope() { scopes_.pop_back(); } void declare(const Symbol sym) { // 只在当前作用域插入允许遮蔽外层同名变量 scopes_.back()[sym.name] sym; } const Symbol* lookup(const std::string name) const { // 从栈顶向下找先命中的就是当前可见的那个 for (auto it scopes_.rbegin(); it ! scopes_.rend(); it) { auto f it-find(name); if (f ! it-end()) return (f-second); } return nullptr; } private: std::vectorstd::unordered_mapstd::string, Symbol scopes_; };lookup()从栈顶往栈底扫天然实现了变量遮蔽内层声明了同名变量就先返回内层的。这里真正的坑是popScope()的时机。我见过最典型的报错是int x; { int x; x 1; } x 2;中第二条赋值语句报“未声明变量”。原因是有些同学在处理右花括号时先popScope()再做作用域内最后一条语句的语义动作符号表先没了代码生成里查找变量就扑空。正确顺序是在进入块时pushScope()在处理完块内所有语句、生成完这段的中间代码后再popScope()顺序不能反。4.3 语法制导翻译赋值、表达式与布尔短路回填三地址码生成的核心是语法制导翻译语法分析每规约一条产生式就触发一段代码生成逻辑。表达式部分每个非终结符在语义上带一个place属性表示存放结果的位置——变量名或临时变量。二元运算生成新临时变量// codegen.cpp用 newTemp 和 emit 生成四元式 class CodeGen { public: std::string newTemp() { return t std::to_string(tempNo_); } void emit(const std::string op, const std::string arg1, const std::string arg2, const std::string result) { quads_.push_back({op, arg1, arg2, result}); } // 处理 E - E1 op E2 std::string genBinExpr(const std::string e1, const std::string op, const std::string e2) { std::string result newTemp(); emit(op, e1, e2, result); return result; } // 处理 stmt - id E void genAssign(const std::string lhs, const std::string rhs) { emit(, rhs, , lhs); } private: std::vectorQuad quads_; int tempNo_ 0; };newTemp()从 0 开始编号t0、t1、t2一路递增打印时四列对齐。临时变量编号的起始值是个小参数建议统一为 0如果从 1 开始调试时看下标容易犯迷糊。赋值语句的result直接复用变量名不产生临时变量这样输出更接近真实汇编风格。布尔表达式是实验三最容易翻车的点因为a || b需要短路求值a为真时整体为真不再计算b。短路意味着跳转目标的地址在生成表达式代码时还不知道要事后回填。标准做法是emitWithFixup()先输出目标为?的跳转指令记录四元式下标等上下文确定后backpatch()填上真目标// codegen.cpp短路布尔表达式与回填 int emitWithFixup(const std::string op, const std::string arg1, const std::string arg2) { emit(op, arg1, arg2, ?); return static_castint(quads_.size()) - 1; } void backpatch(int idx, const std::string target) { quads_[idx].result target; } // E - E1 || E2 的翻译过程伪代码 // 先翻译 E1得到 e1.place可能是临时变量 // 生成 jnz e1.place, Ltrue ——真出口暂填 // 生成 jmp Lfalse ——假出口暂填 // 再翻译 E2得到 e2.place // 生成 jnz e2.place, Ltrue // 最后将 Ltrue / Lfalse 回填进去回填是实验三里唯一需要“想两层”的地方也是区分及格和优秀的验收点。如果你抽到的题目不要求短路只做算术表达式和赋值那emit()就够用但布尔表达式一旦出现?就一定会出现。输出前我习惯加一个断言遍历所有四元式如果还有result为?的直接报“存在未回填的跳转指令”这能拦截大部分半成品 bug。5. 三个实验串起来的常见问题排查token 不一致、作用域弹出过早、跳转目标没回填坑 1实验一的 token 类型和实验二的终结符对不上。现象是语法分析器对合法输入报告 syntax error打印 token 流发现if的 type 是ID而预测分析表在等KEYWORD_IF。原因是实验一偷懒没给关键字单设类型靠sval区分实验二按 type 查表必然失配。解决方法是回到 token 定义统一枚举给每个关键字单独一个TokenType并确保tokenToString()的映射和分析表表头用同一套命名。坑 2FIRST/FOLLOW 集合算错导致预测分析表冲突。现象是分析表里同一个格子出现两个产生式或者$在 FOLLOW 集合里丢失导致文件结束时报错。原因大多是手算时忘记将$加入开始符号的 FOLLOW或者 ε 产生式处理时把空串错误传播。解决方法是写固定点算法迭代计算打印集合做人工抽查program的 FOLLOW 必须包含$所有能推导出 ε 的非终结符其 FOLLOW 集合会合入前驱非终结符的 FOLLOW。坑 3词法错误的位置汇报漂移。现象是报错行列号和实际字符位置对不上验收时被发现。原因是注释和换行处理中直接修改了line_/col_而advance()也在修改两边冲突。解决方法是把行列更新收拢到advance()这一个函数里skipWhitespaceAndComments()只负责调用advance()和判断字符类型不直接触碰行列号。坑 4符号表弹出太早导致变量消失。现象是块语句结束后外层变量无法解析报“未声明变量”。原因是右花括号的处理顺序错了——先popScope()再做块内最后语句的语义动作。解决方法是把popScope()作为块语句处理的最后一步放在所有 emit 之后。这里有一条血泪经验处理{时pushScope()对应的popScope()必须和}的语义动作在同一次规约里不要拆到别的函数里。坑 5布尔表达式跳转目标全是?。现象是输出四元式第三列大片?或者跳转目标是 0。原因是短路求值后忘了回填或者回填的目标标签用了全局计数器的旧值。解决方法是backpatch()的参数用标签编号而不是直接填行号输出前遍历所有四元式断言没有?残留有就说明某条路的跳转目标没有确定。6. 把实验一~三做成可回归的编译前端Golden Test 和调试开关三个实验串起来后我强烈建议做一套 golden test。方法是准备一组覆盖边界情况的输入文件第一次跑完把输出保存为.golden文件之后每次改动代码跑一遍对比#!/bin/bash # regress.sh跑全部测试用例并和 golden 输出对比 for f in tests/*.c; do ./compiler $f /tmp/out.txt if ! diff -u ${f%.c}.golden /tmp/out.txt /tmp/diff.txt 21; then echo FAIL: $f head -20 /tmp/diff.txt else echo PASS: $f fi done测试用例的覆盖面直接决定测试质量。我一般会放这几类注释跨行、多个连续运算符、嵌套括号的表达式、变量遮蔽、if/else 嵌套、while 循环体里的赋值。每次改动词法或语法代码跑一遍不到一秒但能拦住八成回归问题。调试时再给编译器加三个开关-t只打印 token 流-p打印语法分析过程-c打印四元式序列。这三个开关会让实验一二三分别可见出问题时一眼知道卡在哪一层。我当年做实验一只测了 README 里的三个样例实验二第一次上机就遇到“else 前面多了个分号”的输入分析器直接卡死后来发现是同步 token 集合漏了分号。从那以后我再也不敢只测样例。编译原理实验的每一步都是递归依赖词法偷的懒语法一定还给你。希望你这次能一次把三个实验串成一条干净的流水线希望这篇对你有帮助。本文还有配套的精品资源点击获取