编译原理课程设计：四阶段流水线与四元式实现指南

简介：面向计算机专业本科生编译原理课程设计的完整实现资料，围绕词法分析与语法分析两个核心实验环节展开，适合正在做课设、需要参照可运行代码与报告写法的学生使用。压缩包共 32 个文件、约 961KB，其中 cpp、c、h 源码与词法分析头文件构成程序主体，exe 为可直接运行的可执行程序，obj、pdb、ilk 等 Debug 中间文件保留了工程编译痕迹，doc 实验报告与 ppt 答辩讲稿对应课程提交与答辩场景，txt 文件则记录产生式、符号表、token 定义等内容。目前已有 751 人学习下载，作者标注程序经检验无 BUG。读者可据此对照课程要求梳理词法扫描、属性字管理、符号表构造与语法推导的整体流程，理解头文件与源文件之间的模块划分，并参考报告结构与答辩思路完成自己的课程设计。

1. 编译原理课程设计真正卡人的地方，是流水线对不上

做编译原理课程设计的人，十个里有八个不是卡在算法推导上，而是卡在“前端跑通了、后端接不上”。词法分析器能切词，语法树也能打印，一到语义分析和中间代码生成，符号表和作用域对不上号，四元式里的临时变量到处重名；再往后走到目标代码，寄存器一简化，跑出来的结果和手算的差一截，答辩现场只能解释“理论上是对的”。这套方案针对的就是这个断层：把源语言子集、四个阶段的输入输出契约、符号表结构、四元式格式和测试用例一次性定死，让每一层都能单独验证、单独演示。适合正在做编译原理课程设计或相关毕设、需要一个既能讲清楚又能真跑起来的完整实现的人，也适合带课的助教拿去当验收时的对照参考。

2. 总体架构设计：源语言子集、目标机模型与四个阶段的职责划分

2.1 先划边界：源语言子集与目标机模型

课程设计翻车最常见的原因不是写不出来，而是文法写到一半开始加需求。“支持常见高级语言的全部语法”这种目标一旦立起来，后面必然烂尾，血泪经验就是：宁可文法小到只有二十条产生式，也要保证每条都实现完整。我一般的做法是先写一张边界表，把“支持”和“不支持”两栏都写满，不支持的那一栏明确写清楚报什么错。

源语言子集的文法用 EBNF 写死，交报告时直接贴这张表：

program -> block block -> '{' decl_list stmt_list '}' decl_list -> { decl } decl -> type ID ';' type -> 'int' | 'bool' stmt_list -> { stmt } stmt -> assign | if_stmt | while_stmt | io_stmt | block | ';' assign -> ID '=' expr ';' if_stmt -> 'if' '(' expr ')' stmt [ 'else' stmt ] while_stmt -> 'while' '(' expr ')' stmt io_stmt -> 'read' '(' ID ')' ';' | 'write' '(' expr ')' ';' expr -> or_expr or_expr -> and_expr { '||' and_expr } and_expr -> rel_expr { '&&' rel_expr } rel_expr -> add_expr [ ( '<' | '<=' | '>' | '>=' | '==' | '!=' ) add_expr ] add_expr -> mul_expr { ( '+' | '-' ) mul_expr } mul_expr -> unary { ( '*' | '/' | '%' ) unary } unary -> [ '!' | '-' ] primary primary -> ID | NUM | 'true' | 'false' | '(' expr ')'

目标机模型同样要定死，否则后面生成指令时每天都在改约定。这里的做法是假设一台只有 R0～R7 八个通用寄存器、字长 32 位、按字节编址的简化 RISC 机，指令只保留LD / ST / ADD / SUB / MUL / DIV / MOD / CMP / JMP / JZ / JNZ / IN / OUT / HALT这十几条。栈帧布局固定为：调用者压返回地址，被调者保存旧的帧指针，然后是局部变量区。因为不做函数调用，这套布局实际上只用到“帧指针 + 局部变量偏移”这一小部分，但先定下来，后面调试时心里有底。

提示：目标机模型必须在动手写代码之前写进报告的第一章，答辩时老师问“你的目标机是什么”，能立刻翻到这一页，比口头解释十分钟管用。

2.2 四阶段流水线与中间表示选型

流水线按词法、语法、语义、中间代码、目标代码五步走，但工程上分成四个可独立运行的程序入口更实用。每个阶段的产物都能打印成文本文件，出问题时用 diff 一比对，就知道是哪一层开始歪的。

src.txt --[lexer]--> tokens.txt --[parser]--> ast.txt --[sema]----> ast_typed.txt + symbols.txt --[ircode]--> quads.txt --[codegen]-> asm.txt

中间表示选四元式，也就是(op, arg1, arg2, result)形式的三地址码。理由有三条：一是它比语法树更接近目标指令，做指令选择时几乎是一对一翻译；二是回填（backpatch）这种技术在四元式上最直观，真假出口链用整数下标串起来就行；三是它足够小，一份quads.txt打印出来，答辩现场可以直接指着某一行说“这条跳转就是 while 的回边”。

四元式的具体格式要固定，不能今天用字符串、明天用对象：

# 四元式统一用列表存，方便按下标做回填 # op: 操作码字符串；arg1/arg2: 操作数（变量名、常量、临时变量名或 None） # result: 结果存放位置（临时变量名、标号名或 None） quads = [ ("=", "1", None, "i"), # i = 1 ("<=", "i", "10", "t1"), # t1 = i <= 10 ("JZ", "t1", None, "L2"), # if t1 == 0 goto L2 ("+", "sum", "i", "t2"), # t2 = sum + i ("=", "t2", None, "sum"), # sum = t2 ("+", "i", "1", "t3"), ("=", "t3", None, "i"), ("JMP", None, None, "L1"), # goto L1 ("LABEL", None, None, "L2"), # L2: ]

临时变量统一用t加自增编号生成，标号统一用L加自增编号，绝不手工起名。这一条看着琐碎，但它避免的是最难查的一类问题：两个不同的表达式恰好用了同一个临时变量名，结果在寄存器分配阶段被合并，跑出来的值偶尔对偶尔错，翻车翻得莫名其妙。

2.3 工程目录、构建与调试入口

目录结构按阶段切开，一个文件只干一件事，这样交作业时老师翻代码也能顺着读下去：

mini-compiler/ ├── src/ │ ├── lexer.py # 词法分析：源码 -> Token 流 │ ├── parser.py # 语法分析：Token 流 -> AST │ ├── ast_nodes.py # AST 节点定义与打印 │ ├── symtab.py # 符号表与作用域链 │ ├── sema.py # 语义分析：类型检查与标注 │ ├── ircode.py # 四元式生成与回填 │ ├── codegen.py # 目标代码生成 │ └── errors.py # 统一错误码与报错格式 ├── tests/ │ ├── ok_*.mc # 正例：应当编译通过 │ └── err_*.mc # 负例：应当报出指定错误码 ├── main.py # 命令行入口 └── README.md

main.py必须提供分阶段导出开关，这是整个工程里性价比最高的一个设计：

# 逐阶段导出中间产物，出问题时直接看哪一层开始歪 python main.py tests/ok_01.mc --dump tokens # 只看词法 python main.py tests/ok_01.mc --dump ast # 看语法树结构 python main.py tests/ok_01.mc --dump ir # 看四元式 python main.py tests/ok_01.mc --dump asm # 看最终指令序列 python main.py tests/err_03.mc --dump sema # 看语义错误定位信息

有了这几个开关，调试就从“对着一个报错猜”变成“逐层比对”。比如结果算错，先看tokens有没有切错，再看ast的结合性对不对，最后看ir里跳转标号有没有落空。这套流程走顺了，定位问题通常不超过十分钟。

3. 词法与语法分析实现：从正则式到分析表的落地路径

3.1 词法分析：手写扫描器与自动生成的分工

词法分析有两条路：用词法分析生成器从正则式自动生成 DFA，或者手写一个带回退的扫描器。课程设计规模下，我一般推荐手写，理由不是“简单”，而是报错信息可控——自动生成的表驱动分析器在遇到非法字符时，往往只能告诉你“在第 37 个状态挂了”，而手写扫描器能精确说出“第 3 行第 12 列出现非法字符@”。当然，如果课设明确要求用生成器，那就老老实实写正则式，把 DFA 最小化过程画进报告，两种做法在评分上各有侧重。

手写扫描器的核心是两个细节：最长匹配和位置回溯。下面这段是主循环的骨架：

KEYWORDS = {"if", "else", "while", "int", "bool", "read", "write", "break", "true", "false"} class Token: def __init__(self, kind, text, line, col): self.kind = kind # 记号类别：ID / NUM / KW / OP / EOF self.text = text # 原始词素，报错时原样回显给用户看 self.line = line # 行号，语义阶段报错全靠它定位 self.col = col # 列号 def scan(src): i, line, col = 0, 1, 1 out = [] while i < len(src): ch = src[i] if ch in " \t\r": i += 1; col += 1; continue if ch == "\n": i += 1; line += 1; col = 1; continue if src.startswith("//", i): # 行注释整段丢弃，不产生记号 while i < len(src) and src[i] != "\n": i += 1 continue if ch.isalpha() or ch == "_": # 标识符/关键字：一直吃到非字母数字 j = i while j < len(src) and (src[j].isalnum() or src[j] == "_"): j += 1 word = src[i:j] out.append(Token("KW" if word in KEYWORDS else "ID", word, line, col)) col += j - i; i = j; continue if ch.isdigit(): # 常量：本语言只做十进制整数 j = i while j < len(src) and src[j].isdigit(): j += 1 out.append(Token("NUM", src[i:j], line, col)) col += j - i; i = j; continue two = src[i:i+2] # 先试双字符运算符 if two in ("<=", ">=", "==", "!=", "&&", "||"): out.append(Token("OP", two, line, col)) i += 2; col += 2; continue if ch in "+-*/%<>!=(){};,": # 双字符失败才落到单字符 out.append(Token("OP", ch, line, col)) i += 1; col += 1; continue raise SyntaxError(f"非法字符 {ch!r}，位置 {line}:{col}") out.append(Token("EOF", "", line, col)) # 哨兵，让语法分析少写边界判断 return out

这段代码里两个地方必须留意。two = src[i:i+2]那一步就是最长匹配的落点：先按两个字符尝试，失败再退到单字符，<=才不会被切成<和=。Token里的行列号不是装饰，语义分析阶段报“变量未声明”时，能不能指到具体位置，全靠它一路带下去。EOF 哨兵则让语法分析的下一个记号永远是合法的，省掉一堆if i < len(tokens)。

关键字识别用的是“先按标识符规则切，再查表”，而不是在字符判断里单独处理。原因很实际：if和iff开头一样，如果在字符层判断关键字，很容易把iff也切成if加一个f。先统一走标识符规则、切完再查关键字表，这个坑就绕过去了。

3.2 语法分析选型：LL(1)、算符优先与 SLR(1) 的取舍

语法分析的方案选择，取决于课设要求和你想要的演示效果。四种常见做法各有适用面：

我一般选递归下降打底，因为它对“边写边加需求”最友好，每个非终结符对应一个函数，加一条产生式就是加几行代码。表达式部分按优先级分层下降，把||、&&、关系、加减、乘除、一元、primary 各写一层，结合性和优先级天然就对了，不需要额外算表：

class Parser: def parse_expr(self): return self.parse_or() def parse_or(self): node = self.parse_and() while self.at("||"): # 左结合，循环处理同级运算符 op = self.take() node = BinOp(op.line, "||", node, self.parse_and()) return node def parse_and(self): node = self.parse_rel() while self.at("&&"): # 优先级比 || 高，所以下沉一层 op = self.take() node = BinOp(op.line, "&&", node, self.parse_rel()) return node def parse_mul(self): node = self.parse_unary() while self.at("*") or self.at("/") or self.at("%"): op = self.take() node = BinOp(op.line, op.text, node, self.parse_unary()) return node

分层下降的关键在于调用关系：parse_or调parse_and，parse_and调parse_rel，一路下沉到parse_unary。表达式a + b * c里，乘号会在更深的层被吃掉，所以自然形成a + (b * c)的树形。如果图省事把加减乘除写在同一层循环里，优先级就只能靠额外判断，测2 + 3 * 4会得到 20 而不是 14。

如果课设要求交 LR 分析表，那就必须把项目集规范族、GO 函数、ACTION/GOTO 表都生成出来，代码量大约翻一倍，但演示效果更“编译原理”。此时递归下降可以先写成参考实现，用来交叉验证表驱动版本是否等价：同一批测试用例，两套前端产出的 AST 打印结果必须逐字符一致。

不管走哪条路，都要处理左递归。文法是expr -> expr '+' term这种形式时，递归下降会直接死循环，必须先改写成expr -> term { '+' term }，也就是循环形式。这一步如果忘了，程序不会报错，只会栈溢出，现象很像“卡死”，新手容易在这里卡一下午。

3.3 AST 节点设计与语法树打印

AST 是整个工程的交换中心，前端产出的东西后端全要靠它。节点设计有两个原则：每个节点必须带行号，语句列表必须是真正的列表。前者决定了语义错误能不能定位，后者决定了代码生成时能不能顺序遍历。

class Node: def __init__(self, line): self.line = line class Program(Node): def __init__(self, line, block): super().__init__(line); self.block = block class Block(Node): def __init__(self, line, decls, stmts): super().__init__(line); self.decls = decls; self.stmts = stmts class BinOp(Node): def __init__(self, line, op, left, right): super().__init__(line); self.op = op; self.left = left; self.right = right class If(Node): def __init__(self, line, cond, then_s, else_s=None): super().__init__(line); self.cond = cond; self.then_s = then_s; self.else_s = else_s class While(Node): def __init__(self, line, cond, body): super().__init__(line); self.cond = cond; self.body = body def dump(n, depth=0): """按缩进打印语法树，用于和四元式逐层比对""" pad = " " * depth name = type(n).__name__ extra = f" {n.op}" if isinstance(n, BinOp) else "" print(f"{pad}{name}{extra} @line{n.line}") for k, v in vars(n).items(): if k in ("line",): continue if isinstance(v, Node): dump(v, depth + 1) elif isinstance(v, list): for item in v: dump(item, depth + 1)

dump函数看着简单，却是后面所有调试的地基。一个while语句打印出来，应该能清楚看到条件子树和循环体子树分别在哪一层，如果打印结果里两个分支的深度一样，说明 AST 结构搭错了。我习惯每写完一个语法结构，就先跑一次--dump ast，肉眼确认树形和预期一致，再往下写语义分析。这份“先看树再写代码”的习惯，能省掉大量在四元式阶段才发现结构错误的返工。

4. 语义分析与中间代码生成：符号表、类型检查与四元式回填

4.1 符号表结构与作用域管理

符号表是语义阶段的核心数据结构，也是最容易在答辩时被追问细节的地方。这里采用的是一条作用域链：每进一个{}就压入一个新作用域，退出时弹出，查找时沿着链往上走。

class Symbol: def __init__(self, name, typ, kind="var"): self.name = name # 变量名 self.typ = typ # int / bool self.kind = kind # var（本语言暂无函数，保留字段便于扩展） self.offset = None # 栈帧内的字节偏移，进入代码生成阶段才赋值 class Scope: def __init__(self, parent=None): self.parent = parent self.table = {} # 名字 -> Symbol self.size = 0 # 本作用域已分配的字节数，用于算栈帧大小 def declare(self, sym): if sym.name in self.table: # 同一作用域内重复声明才报错 raise SemErr("E102", sym.name, sym.line) sym.offset = self.size # 分配局部变量槽位 self.size += 4 self.table[sym.name] = sym def lookup(self, name): s = self while s is not None: # 沿作用域链一直找到全局 if name in s.table: return s.table[name] s = s.parent return None # 找不到说明未声明

declare只在当前作用域的表里查重，lookup才向上遍历，这两者不能混。一旦把查重也写成向上遍历，嵌套块里再声明同名变量就会被误判成重复声明，这是语义分析阶段最典型的误报来源。反过来，如果lookup只查当前作用域，那全局变量在if块里就用不了。

偏移量的分配时机也值得说一下。size是在声明时自增的，但真正的栈帧大小要等整个块退出时才确定，所以代码生成阶段会再遍历一次作用域，把每层的size加起来。如果提前把栈帧大小写死成一个魔法数，程序里变量一多就会覆盖返回地址，跑出来的现象是“程序跑到一半跳到奇怪的地方”，非常难查。

4.2 类型检查与错误定位策略

类型检查做两件事：给每个表达式节点标注类型，以及在类型不匹配时报出明确错误码。错误码表提前定好，报告里直接贴：

关键点是“报错不中断”。课程设计的演示环节，老师通常会拿一个有五六个错误的源文件让你跑，如果编译器遇到第一个错误就exit(1)，后面四个错误全看不到，演示效果直接打折。我一般的做法是每条语句分析完后进一个同步点，遇到错误就跳到下一个分号或右花括号，然后继续：

def check_stmt(self, stmt): try: self._check_stmt_inner(stmt) except SemErr as e: self.errors.append(e) # 收集错误，不抛出到顶层 self.sync_to_boundary() # 跳到 ';' 或 '}' 之后继续下一条语句 def sync_to_boundary(self): # 语法分析阶段已经把语句边界变成了 AST 结构， # 所以这里只需要在语句列表里跳过当前项，不用真的去扫记号 pass

这段代码里sync_to_boundary留空是有原因的：AST 已经是结构化的，一条语句出错不会污染下一条，所以最省事的同步策略就是“跳过当前语句”。只有走表驱动、边解析边分析的那种设计，才需要真的去扫分号做同步。这一点在报告里可以展开写两句，说明为什么选 AST 而不是边解析边生成——结构化的中间产物让错误恢复变得非常便宜。

4.3 四元式生成与回填 patch

控制流的四元式生成，绕不开回填。if和while在生成跳转指令的那一刻，还不知道跳转目标在哪，只能先留个空，等目标确定后回来补。做法是把待补的四元式下标存成一张“链”，最后一次性 patch。

def backpatch(self, chain, target): """chain 是四元式下标列表，target 是要填入的标号名""" for idx in chain: op, a1, a2, _ = self.quads[idx] self.quads[idx] = (op, a1, a2, target) # 只改 result 字段 def gen_if(self, node): cond_t, cond_f = self.gen_cond(node.cond) # 条件表达式返回真假出口链 self.backpatch(cond_t, self.new_label()) # 真出口落到 then 开始处 self.gen_stmt(node.then_s) if node.else_s is not None: end_jmp = self.emit(("JMP", None, None, None)) # 跳过 else 分支 self.backpatch(cond_f, self.new_label()) # 假出口落到 else 开始处 self.gen_stmt(node.else_s) self.backpatch([end_jmp], self.new_label()) # then 结束后跳出整个 if else: self.backpatch(cond_f, self.new_label())

这里最容易出错的是真假出口的方向。短路求值时，a && b的假出口是a 为假和b 为假两条链的合并，a || b的真出口才是两条链合并。如果方向搞反，if (a && b)会变成“a 或 b 任一为真就进 then”，逻辑完全颠倒，而且测试用例稍微复杂一点就藏不住。测这种问题，我一般用if (false && true) write(1); else write(0);这种一眼能看出对错的用例，一次就能验出来。

new_label()生成L1、L2这样的标号名，最后在四元式末尾插一条("LABEL", None, None, "L1")作为跳转落点。所有链必须闭合，程序结束前要检查一遍quads里有没有result为None的跳转指令，有就说明有链没 patch 完，这属于“编译能过但运行会飞”的那类 bug，静态扫一遍比跑测试快得多。

4.4 从四元式到目标指令的简化映射

目标代码生成这一步，课设规模下不建议上图着色寄存器分配，投入产出比太低。我一般用一个寄存器池：表达式求值时从池里借一个寄存器，算完立刻还回去；跨越语句还活着的变量，一律存回栈帧，用的时候再LD出来。

把临时变量也放进栈帧，看起来是浪费，但它换来的是“每个变量都有确定地址”，代码生成器不需要做任何活跃性分析。课设的测试规模通常只有几十条语句，这点开销完全无所谓，而实现的复杂度下降了一大截。真要在报告里加分，可以加一小节讨论“如果要做寄存器分配，活跃变量分析怎么做”，把思路写清楚但不实现，这是性价比最高的写法。

5. 常见问题排查：五个最容易翻车的点和对应解法

5.1 前端阶段的两个高频故障

第一个：双字符运算符被拆开。现象是a <= b报语法错误，--dump tokens看输出是OP <加OP =。原因在扫描器里单字符判断写在了双字符判断之前，或者双字符表里漏了某一项。解决方式是把双字符匹配强制放在单字符之前，并且在tokens导出里把每个记号的类别和文本都打出来，一眼就能确认。这个坑我踩过不止一次，后来干脆在词法测试里加了一条断言：所有长度大于 1 的记号必须是关键字或双字符运算符，否则直接失败。

第二个：表达式结合性反了。现象是10 - 3 - 2算出 9 而不是 5，或者a = b = 1解析失败。原因是递归下降时把同级运算符写成了递归调用而不是循环，导致右结合。解决方式是把同级运算符的处理统一写成while循环，左结合自然成立；真要支持右结合（赋值语句），就单独写一层右递归。验证方法很土但很有效：手算几个减法和除法表达式，和编译器输出对一遍，对不上就是结合性问题。

第三个：悬空 else。现象是if (a) if (b) x=1; else x=2;里的else挂到了外层if上。原因是文法里if语句没有用花括号强制配对，递归下降按“就近匹配”自然形成了悬挂结构。解决办法是在文法层要求if和else的分支必须是块语句，或者显式定义matched_stmt/unmatched_stmt两类非终结符。课设规模下前者更省事，直接在文法里写死“分支必须是{}”，从源头消掉歧义。

5.2 中后端阶段的三个致命问题

第四个：作用域弹出时机错。现象是循环体里声明的变量在下一轮循环报“重复声明”，或者块内变量泄漏到块外还能用。原因通常是enter_scope和exit_scope没有和{}严格配对，尤其在if-else有多个分支时，某个分支提前 return 就把栈搞乱了。解决方式是让作用域的进入退出跟 AST 的Block节点绑定，进节点压栈、出节点弹栈，用统一的遍历函数保证配对，不要在业务逻辑里零散地手动调用。

第五个：寄存器被覆盖导致结果偶尔错。现象是简单用例全过，稍微长一点的表达式结果就不对，重跑有时还不一样。原因是寄存器池借出后没归还，或者两个操作数被分到了同一个寄存器。解决方式是给寄存器池加一个使用计数，借还必须成对，同时在生成指令后做一次静态检查：每条ADD/SUB/MUL/DIV指令的目的寄存器和两个源寄存器不能出现“目的等于某个源且该源后续还要用”的情况。这套检查写起来不到三十行，但能挡住绝大部分“玄学错误”。

6. 验收与答辩：一套现场能跑通的自检流程

验收前一周，我会把整个工程按“老师会怎么点”的顺序走一遍，做成一张自检表。这张表不是给自己看的，是答辩现场万一被要求“现场改个用例”时的底气。

演示脚本提前写成一条命令，现场不用手敲：

#!/usr/bin/env bash # 答辩演示：一条命令跑完词法、语法、语义、目标代码四层 set -e echo "=== 1. 词法 ==="; python main.py tests/ok_01.mc --dump tokens | head -20 echo "=== 2. 语法 ==="; python main.py tests/ok_01.mc --dump ast | head -30 echo "=== 3. 四元式 ==="; python main.py tests/ok_01.mc --dump ir | head -30 echo "=== 4. 目标代码 ==="; python main.py tests/ok_01.mc --dump asm | head -30 echo "=== 5. 错误用例 ==="; python main.py tests/err_02.mc || true

答辩提问其实很集中，提前把答案写在报告的对应页上就行：为什么选四元式而不是直接生成目标码（可分层验证、回填方便）；FIRST/FOLLOW 怎么算的（如果走表驱动）；回填链为什么不会断（每条跳转在生成时立刻入链，闭合检查兜底）；寄存器分配的局限在哪（没做活跃性分析，靠栈槽兜底）；错误恢复为什么不会死循环（AST 结构化，语句级跳过）。被问到答不上来的细节，就翻到--dump的输出上，指着具体那几行讲，比空口解释可信得多。

从那以后我每次做这类课设，都会在动手写第一行代码之前先把边界表、四元式格式和自检清单三样东西写出来，哪怕它们当时看起来只是几张空表格。真到联调阶段，这三张纸能把“感觉哪里不对”变成“第几层第几行不对”。希望帮到你。

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