编译原理课程设计全链路：五段流水线与四元式解释执行

简介：南京航空航天大学编译原理课程设计全套资料，面向计算机专业学生及需要完成词法、语法分析实验的课程设计者，帮助梳理从源程序扫描到语法处理的实现路径，并可作为课设报告与答辩准备的参考。压缩包共32个文件、约961KB，包含源码与头文件、工程配置、可执行程序、课程设计报告、答辩演示文稿及若干说明文本，覆盖词法分析、语法分析等模块，目录按工程与文档分置，便于对照阅读和复现实验。目前已有751人学习下载，具有一定参考热度。资料中既有经检验可运行的程序工程，也保留了实现代码与调试产物，读者可据此理解属性字、符号表、Token识别等关键环节，参考工程组织方式与报告写作框架，减少环境配置和排错中的反复尝试，适合作为课程设计阶段的辅助材料。

1. 编译原理课程设计从零跑通：五段流水线，一份源码包就够

课设答疑里见过的翻车现场，十有八九出在同一个地方：文法写出来了，LL(1) 表也推完了，然后盯着屏幕不知道第一行代码该写什么。这份编译原理课程设计包把整条链路拆成可以直接跑通的五段：词法分析、语法分析、符号表与语义检查、四元式生成、四元式解释执行，源语言是一个类 PL/0 的极小子集，覆盖赋值、算术表达式、if/else、while、过程调用和一维数组。计算机专业正在做课设的同学，可以整体跑通再按验收要求裁剪，也可以只取其中一段去补自己的半成品——最省时间的是四元式解释器那部分，它能把"我的分析器到底对不对"这个问题当场变成一个能看见的输出。

2. 词法与语法分析落地：把 800 行前端拆成三个可验证的节点

前端是整个课设里最容易"看着写完了其实没通"的部分。常见做法是先把词法分析器单独跑起来，喂一段源码，把 token 流打印到文件里逐行核对；token 流对了再动语法分析，这样出问题时你只需要怀疑一层，而不是两层一起猜。

2.1 词法分析：单遍扫描 + 最长匹配 + 行列号

课程设计里最不该省的是位置信息。很多同学的词法分析器只返回 token 类型和字符串，等到语法分析报错时只能说"第 N 个 token 出错了"，答辩演示时非常被动。

// lexer.cpp —— 单遍扫描，最长匹配，每个 token 带行列号便于报错定位 enum TokenType { TK_ID, TK_NUM, TK_IF, TK_WHILE, TK_PLUS, TK_ASSIGN, TK_EOF, TK_ERR }; struct Token { TokenType type; std::string lexeme; int line, col; // 报错定位用，语法分析阶段原样往下传 }; class Lexer { const std::string& src; size_t pos = 0; int line = 1, col = 1; public: Token next() { skipSpaceAndComment(); // 跳过空白与 // 行注释 if (pos >= src.size()) return {TK_EOF, "", line, col}; char c = src[pos]; if (isdigit((unsigned char)c)) return number(); // 连续 digit 组成整数 if (isalpha((unsigned char)c) || c == '_') return identOrKeyword(); return opOrPunct(); // 运算符：双字符优先于单字符 } };

opOrPunct()里必须先判<=、>=、:=这类双字符运算符，再退到单字符。这一步顺序写反，a := b会被拆成a、:、=三个 token，语法分析报的错误信息会把你带到完全错误的方向去。identOrKeyword()查一张关键字表，命中就把TK_ID改成对应的关键字类型，没命中保留标识符——关键字不要单独写一个分支，否则加一个保留字就要改三处代码。

2.2 递归下降还是 LL(1) 表驱动：按验收标准选，不按难易选

这一步的选型几乎决定了后面两周的工作量。四种常见方案的差别不在"哪个更高级"，而在你的验收要求写了什么。

如果验收只要求"能正确识别合法程序并报告非法程序"，递归下降性价比最高，语法树直接在函数返回值里就建好了。如果验收明确要求输出分析栈的每一步变化，那就只能走表驱动——这不是难度问题，是输出格式问题。LR 系列在课设里最大的价值是能处理左递归，代价是状态图调试起来像黑匣子，一旦 ACTION 表出现移进-归约冲突，你得把项目集打印出来一个个看。

2.3 用脚本核对 FIRST/FOLLOW，别在纸上硬推

手工推 FIRST/FOLLOW 是课设里错得最隐蔽的环节：推错一个集合，分析表里就少一项，程序只在特定输入下才崩，你根本定位不到。与其反复擦纸，不如写三十行脚本让机器算，然后拿结果跟你纸上的推导对。

# first_follow.py —— 从文法文本算 FIRST/FOLLOW，用来核对手工推导 EPS = '~' # 用 ~ 表示空串，避免和编码打架 VN, grammar = set(), {} def load(path): for raw in open(path, encoding='utf-8'): line = raw.split('#')[0].strip() # 支持行尾注释 if not line: continue head, body = [s.strip() for s in line.split('->')] VN.add(head) for alt in body.split('|'): grammar.setdefault(head, []).append(alt.split()) def first_of_seq(seq): res = set() for sym in seq: f = FIRST[sym] if sym in VN else {sym} res |= (f - {EPS}) if EPS not in f: # 遇到推不出空的符号就停 return res return res | {EPS} load('grammar.txt') FIRST = {a: set() for a in VN} changed = True while changed: # 不动点迭代，文法带环也能收敛 changed = False for head, alts in grammar.items(): for rhs in alts: add = first_of_seq(rhs) - FIRST[head] if add: FIRST[head] |= add changed = True

grammar.txt一行一条产生式，写成E -> T E'这种形式，多条候选式用|分隔。脚本跑完把 FIRST 表打印出来，和你纸上推的逐格对——对不上的那一格，八成是你漏了某个候选式能推出空串的情况。FOLLOW 的算法结构一样，只是要多一步：当某个非终结符后面整段都能推空时，把左部的 FOLLOW 继承过来，别漏了这条。

提示：把grammar.txt和脚本一起放进仓库，改文法的时候重跑一次，比事后 debug 分析表便宜得多。

3. 语义分析与四元式生成：符号表和作用域栈怎么设计才不返工

语法树建出来只是"结构对了"，真正决定程序跑不跑得对的是符号表和中间代码。这两块如果一开始设计得草率，后面每加一个语言特性都要回头改，改到最后代码会变成一团改不动的东西。

3.1 符号表：作用域栈 + 每层一张哈希表

用全局map<string, Symbol>是课设里最常见的省事写法，也是递归过程出错的第一嫌疑。过程第二次被调用时，形参的偏移量被覆盖，返回地址算错，结果就变成"第一次对、第二次翻倍"。

// symtab.cpp —— 分层作用域栈，进入/退出作用域时整层压入弹出 struct Symbol { std::string name; Type type; // int / array(lo,hi) / proc(形参表) int offset; // 相对 fp 的偏移，代码生成阶段直接取用 int level; // 声明所在作用域层号 }; class ScopeStack { std::vector<std::unordered_map<std::string, Symbol>> frames; public: void enter() { frames.emplace_back(); } void leave() { frames.pop_back(); } // 退出作用域整层丢弃 bool declare(const Symbol& s) { auto& top = frames.back(); if (top.count(s.name)) return false; // 只有同层重定义才算错 top[s.name] = s; return true; } const Symbol* lookup(const std::string& n) { // 由内向外逐层查 for (auto it = frames.rbegin(); it != frames.rend(); ++it) if (it->count(n)) return &it->at(n); return nullptr; } };

关键点是offset在声明那一刻就算好，而不是等到代码生成时再算。这么做的好处是代码生成阶段完全不需要关心作用域，拿到符号直接取偏移。计算偏移时记得数组要按hi - lo + 1个单元递增，而不是只占一个位置——这个疏漏会导致局部数组和后面的局部变量地址重叠，表现出来就是"数组一赋值，别的变量跟着变"。

3.2 类型检查插在哪一层

两种主流做法：一种是语法分析时顺便算（递归下降里每个表达式函数返回一个带类型的节点），另一种是分析完再单独遍历一遍语法树。前者代码短，后者职责清。我一般推荐在表达式函数返回时就带上类型，因为类型错误的位置信息在那个时刻最准确，等到单独遍历时你只有节点上的行列号，报错定位会漂。

类型检查至少要覆盖三件事：赋值左右类型可兼容、过程调用实参个数和类型对得上、数组下标是整型。第三点最容易被跳过，但它是课设演示时最容易被问到的地方。

3.3 控制流回填：先占位再补地址

if和while的四元式生成绕不开回填。核心思路是：生成跳转指令时目标地址还不知道，先填一个占位值，把这条指令的下标挂到一条"待回填链"上，等目标位置确定了再统一改。

int emit(Op op, int a, int b, int c); // 生成一条四元式，返回其下标 void backpatch(std::vector<int>& chain, int target) { for (int i : chain) code[i].dst = target; // 链上每一处都填同一个目标 } // if E then S1 else S2 的骨架 int jf = emit(JF, exprPlace, 0, 0); // 条件为假跳走，目标待定 genStmt(s1); int j = emit(JMP, 0, 0, 0); // S1 执行完要跳过 else backpatch(jf, nextQuad()); // 假出口 = else 的第一条 genStmt(s2); backpatch(j, nextQuad()); // S1 的跳转落在整个 if 之后

nextQuad()取的是"下一条将要生成的四元式下标"，所以必须在目标指令已经 emit 之后再取。写成backpatch(jf, nextQuad() - 1)这种写法，在else分支为空时会偏一条，表现出来就是"简单用例全过、嵌套用例全错"。

4. 四元式解释执行：16 条指令 + 一个栈式虚拟机跑通全部用例

四元式生成完，很多课设就停在这里，交上去只有一堆打印出来的中间代码。加一个两百行的解释器，你就能当场演示"源码进、结果出"，这个差距在验收环节非常明显。

4.1 指令集设计：16 条够用，多了是负担

指令集不是越全越好。课设规模的源语言，下面这张表基本能覆盖全部语义，再加就是给自己找活干。

这里的dst、src1、src2存的都是"相对于当前栈帧 fp 的偏移"，只有跳转类指令例外，它们存的是四元式下标。这个区分一定要在代码里用注释标清楚，混用是后面所有诡异错误的根源。

4.2 栈帧布局与主循环

栈帧按固定顺序排：返回值、返回地址、旧 fp、形参、局部变量、临时量。临时量放在最上面，表达式求值过程中只需要一路往上递增偏移，不需要回收。

// vm.cpp —— 四元式解释器主循环 int fp = 0, sp = 0, pc = 0; while (pc < code.size()) { Quad q = code[pc++]; switch (q.op) { case ADD: stack[fp + q.dst] = stack[fp + q.src1] + stack[fp + q.src2]; break; case ASSIGN: stack[fp + q.dst] = stack[fp + q.src1]; break; case JMP: pc = q.dst; break; case JZ: if (stack[fp + q.src1] == 0) pc = q.dst; break; case CALL: { stack[sp] = pc; // 保存返回地址 stack[sp + 1] = fp; // 保存旧 fp fp = sp + 2; // 新栈帧基址 sp = fp + frameSize(q.dst); // 按被调过程的局部量大小开栈 pc = q.dst; break; } case RET: { int ret = stack[fp - 2]; // 取出返回地址 sp = fp - 2; fp = stack[fp - 1]; // 恢复调用者栈帧 pc = ret; break; } default: break; } }

CALL里frameSize需要知道被调过程要多少局部单元，最省事的做法是在符号表里给每个过程记一个frameSize，生成 CALL 时把它塞进四元式的某个字段，或者另开一张表按入口下标查。别在解释器里现场遍历符号表，那样每次调用都是一次线性查找，递归一深就明显变慢。

4.3 用例批量比对：别一条条手工看输出

到这一步，正确性靠眼睛核对已经不现实了。写个脚本把所有用例跑一遍，逐行比对期望输出，失败的打前几行差异出来。

# run_tests.py —— 批量跑用例并与 .out 期望文件比对 import subprocess, pathlib, sys cases = sorted(pathlib.Path('tests').glob('*.src')) fail = 0 for c in cases: got = subprocess.run(['./compiler', str(c)], capture_output=True, text=True) want = c.with_suffix('.out').read_text(encoding='utf-8').strip() if got.stdout.strip() != want: fail += 1 print(f'[FAIL] {c.name}') print(' expect:', want.splitlines()[:3]) print(' actual:', got.stdout.strip().splitlines()[:3]) print(f'{len(cases) - fail}/{len(cases)} passed') sys.exit(1 if fail else 0)

用例目录按语法特性分组命名（01_assign.src、02_if_else.src、07_recursion.src），失败时看文件名就知道是哪一块出问题。这套脚本还有一个隐性价值：改完代码跑一次全绿，你才敢继续动下一处。

5. 避坑与排查：课程设计里最容易翻车的五处沉默失败

这些问题的共同点是——编译器不报错，程序也跑完了，就是结果不对。这类"沉默失败"占掉了课设后期绝大部分时间，提前知道能省一整周。

5.1 前端阶段：词法与文法里的三个坑

现象：输入少一个右括号，程序不报错，而是卡住不动。原因：预测分析驱动的循环里，遇到分析表中没有对应表项时直接continue，但读头没有前进，下一轮还是同一个 token，于是死循环。 解决：驱动循环里加一条硬性约束——每一轮要么消费一个 token，要么显式报错退出。简单做法是记录上一轮的pos，本轮结束若pos未变则直接抛错。

现象：带//注释的用例结果全错，不带注释的全对。原因：词法在识别/时先匹配了单字符除法，//被当成两个除号参与表达式解析，后面的代码全被吞进表达式里。 解决：严格遵守最长匹配，先检查两个字符的组合（//、<=、>=、:=、<>），都不匹配再退到单字符。这个顺序写死在opOrPunct()的第一行，别分散到多个分支里。

现象：while循环体里只有一条语句时正常，写两条语句就只执行第一条。原因：文法是S -> while E do S，循环体只允许单个语句，第二条语句被解析成了外层程序的语句。 解决：把循环体改成S -> while E do begin SList end，或者显式引入block非终结符。改文法后记得重跑 2.3 的脚本，FIRST/FOLLOW 会跟着变。

5.2 后端阶段：符号表与运行时的两个坑

现象：递归过程（比如求阶乘）第一次调用结果正确，第二次调用结果翻倍。原因：符号表用了全局单表，形参偏移在每次declare时被覆盖，第二次调用用的是被改过的偏移，读到了上一层栈帧的数据。 解决：改成作用域栈，进入过程体enter()，退出leave()。同时确认offset是在声明时一次性算好并写进符号表的，不在运行期动态计算。

现象：while里嵌两层if，循环退出位置偏一条指令，多执行或少执行一次。原因：回填时先取nextQuad()再emit占位指令，目标地址比实际位置小 1；或者两条待回填链被合并到同一个vector里，backpatch时把不该改的指令也改了。 解决：所有跳转一律先emit占位、拿到下标，再在目标位置确定后统一回填；每条链单独一个vector，不要图省事共用。

注意：这五个问题里有四个在"语法正确的正常输入"下不会暴露，建议专门准备一组畸形输入用例（缺括号、非法字符、重定义、数组越界下标），跑一遍能一次性筛掉大部分隐患。

6. 从能跑到能讲：错误恢复、常量折叠与一份自检清单

能跑通用例只是及格线，验收时真正拉开差距的是两件事：出错时编译器说的是不是人话，以及你对自己那几千行代码有没有数。

6.1 错误恢复：恐慌模式 + 同步集，二十行就能加上

语法分析遇到错误直接exit(1)是最省事的做法，也是最容易被追问的做法。恐慌模式的核心很简单：报错之后不退出，而是丢弃 token 直到遇到一个"肯定能重新开始"的符号，然后继续分析。

// 同步集：这些符号出现在哪里都大概率是语句边界，可以安全恢复 const std::set<TokenType> SYNC = {TK_SEMI, TK_END, TK_ELSE, TK_EOF}; void recover(TokenType expected) { reportError(expected, cur.line, cur.col); // 先报清楚期望什么、实际是什么 while (cur.type != TK_EOF && !SYNC.count(cur.type)) cur = lexer.next(); // 丢弃到同步集 }

同步集的选择标准是"这个符号之后大概率是一条新语句的起点"，分号和end是最典型的两个。加上这个之后，一段代码里的多个语法错误能一次全报出来，而不是改一个跑一次。

6.2 四元式上的两个廉价优化

不用做数据流分析，在emit这一层就能拿下两个优化，各二十行左右：常量折叠和公共子表达式消除。常量折叠在生成算术四元式前检查两个操作数是不是都来自常量表，是就直接算出来生成一条ASSIGN。公共子表达式消除用一张(op, src1, src2) -> dst的哈希表，生成前先查，命中就复用已有的结果单元。

要注意折叠的边界：除法遇到除数为 0 不能折，直接保留原四元式让运行时去暴露；浮点如果有的话，折叠顺序要和运行时一致，否则会出现"优化前后结果差一位"的玄学问题。

6.3 交付前自检表

最后一行最值得警惕：单条手工跑过、批量跑挂，通常是程序里有未初始化的全局状态，用例之间互相污染。从那以后我每次加完新特性，都强制先跑一遍全量回归再去看单条输出，不然很容易被"这条明明是过的"这种错觉带偏。

希望帮到你。

本文还有配套的精品资源，点击获取