简介：这份资源是南京航空航天大学编译原理课程设计的完整成果包，面向正在做编译原理课设，或希望弄懂词法分析、语法分析实现方式的计算机专业学生。包内共32个文件，以txt格式的头文件与说明、c 与 cpp 源码、exe 与 obj 编译产物为主，另有doc 课设报告与 ppt 答辩演示、dsw、dsp 工程配置及 pdb、ilk 等调试文件，压缩包约961KB；内容覆盖词法分析、语法分析与符号表管理等模块，结构上按词法、语法两部分分目录组织。程序经作者检验无 BUG，已有751人学习。读者可据此获得一套可运行、可对照的完整实现：从 lex.c、symboltable.cpp 等源码理解 token 识别与属性字管理流程，借课设报告与答辩幻灯梳理设计思路与实验结论，并用现成工程快速复现与调试，减少从零搭建环境、排查错误的时间，适合作为课设参考与复习模板。
1. 编译原理课程设计：为什么“能跑通”只是及格线
编译原理课程设计的评分表上，“程序能跑出正确结果”通常只占很小一栏。真正拉开差距的是中间那几层看不见的结构：词法分析器里那张 DFA 转移表、语法分析器里那组 LR 项目集、符号表里那条作用域链、中间代码里那些临时变量编号。任何一层偷懒，后面都会变成难以定位的 bug——<=被切成<和=两个记号，或者循环里的变量在寄存器分配后莫名被覆盖。这份资源把“字符串 → 词法单元流 → 语法树 → 带注解的树 → 三地址码 → 目标代码”这条流水线完整实现了一遍，并配了设计文档说明每一步的取舍。搞懂它，拿到的不只是计算机专业课程设计的分数，而是一套能解释任何编译器行为的底层模型。
2. 前端的两张表：词法分析为什么用 DFA，语法分析为什么要建状态机
前端干的事说起来朴素：把一串字符变成一棵树。但真正落到实现上，它靠的是两张预先算好的表——词法分析器的 DFA 转移表，和语法分析器的 ACTION、GOTO 表。这两张表都不是手写的，而是从更上层的描述（正则、文法）机械推导出来的。理解这个推导过程，比记住“词法用正则、语法用上下文无关文法”有用得多，因为所有难调的 bug 都藏在推导的不动点里。
2.1 从正则到 DFA：扫描器本质上是一张二维数组
正则表达式只有三种基本运算：连接、选择、闭包。Thompson 构造的思路是给每种运算做一个“只有一个入口、一个出口”的 ε-NFA 片段，然后靠 ε 边把片段拼起来。为什么要引入 ε 边这种看似多余的东西？因为拼接时不需要修改任何片段的内部结构，只在外围加两条 ε 边就行。这是典型的分治设计：片段可复用、可组合，构造过程本身就是一个递归下降。
下面是从正则片段到子集构造的骨架，省略了具体解析部分，只保留机制。
# ε-NFA：trans[(state, char)] -> set(states)，char 为 None 表示 ε 边 class NFA: def __init__(self): self.trans, self.n = {}, 2 self.start, self.accept = 0, 1 def new_state(self): self.n += 1 return self.n - 1 def add(self, s, ch, t): self.trans.setdefault((s, ch), set()).add(t) def concat(a, b): """连接：a 的出口用 ε 边接到 b 的入口""" a.add(a.accept, None, b.start) return a, b.accept def union(a, b): """选择：新建入口，用两条 ε 边分别指向两个片段""" s, f = a.new_state(), a.new_state() a.add(s, None, a.start); a.add(s, None, b.start) a.add(a.accept, None, f); a.add(b.accept, None, f) a.start, a.accept = s, f return a def star(a): """闭包：入口可跳过整个片段，出口可回到入口""" s, f = a.new_state(), a.new_state() a.add(s, None, a.start); a.add(s, None, f) a.add(a.accept, None, a.start); a.add(a.accept, None, f) a.start, a.accept = s, f return a拿到 ε-NFA 后，真正跑起来的扫描器不会去模拟 NFA 的状态集合，而是先把它确定化。子集构造的核心只有两个函数：ε-closure求一个状态集合在 ε 边下能扩张到哪，move求读入某个字符后能到达哪些状态。
def eps_closure(states, trans): stack, seen = list(states), set(states) while stack: s = stack.pop() for t in trans.get((s, None), ()): if t not in seen: seen.add(t); stack.append(t) return frozenset(seen) def subset_construct(nfa): start = eps_closure({nfa.start}, nfa.trans) dfa, work = {start: {}}, [start] while work: cur = work.pop() chars = {ch for (s, ch) in nfa.trans if s in cur and ch is not None} for ch in chars: moved = {t for s in cur for t in nfa.trans.get((s, ch), ())} nxt = eps_closure(moved, nfa.trans) dfa[cur][ch] = nxt if nxt not in dfa: dfa[nxt] = {}; work.append(nxt) return dfa # 每个 key 是一个 DFA 状态，即一个 NFA 状态集合subset_construct里，cur是当前 DFA 状态对应的 NFA 状态集合，chars是从这个集合出发所有可读的字符，nxt就是读入字符后落到的新集合。循环结束时，dfa的键去重后就是全部 DFA 状态，每一条边对应转移表里的一个格子。最坏情况下状态数会指数爆炸到 2 的 n 次方，但真实编程语言的词法规则通常只有几十到几百个 DFA 状态，完全可控。
扫描时还有一件必须做的事：最长匹配。看这段循环。
def scan(dfa, start_state, accept_map, text, pos): state, last_accept, last_pos = start_state, None, pos i = pos while i < len(text) and text[i] in dfa[state]: state = dfa[state][text[i]] i += 1 if state in accept_map: # 记录最近一次到达接受态的位置 last_accept, last_pos = accept_map[state], i if last_accept is None: raise LexError(f'非法字符 {text[pos]!r} 于第 {pos} 列') return last_accept, last_pos # 只吃进最长匹配那一段accept_map记录每个 DFA 状态对应哪条规则（因为多个接受态可能对应不同 token，比如关键字和标识符）。last_pos是关键：DFA 走到一个非接受态时不能立刻报错，而要回退到最近一次接受的位置。没有这个回退，<=会被切成<和=，1.5e-3会在小数点后断掉。
关键字识别有两种常见做法：把关键字直接写进正则一起扫，或者先按标识符规则扫出整个单词再查哈希表。后者更常见，因为关键字表很小，查表是常数时间，还能顺便把“关键字不能当变量名”的检查放在语义阶段统一处理。扫描器最终会编译成一个next[state][char_code]的二维数组，每个字符一次数组索引，比一长串if-else分支预测失败要稳定得多。
2.2 项目集闭包与移进-归约：语法分析器的状态机从哪来
如果说词法分析是把字符流压成记号流，语法分析就是把记号流还原成树。LR 分析器的做法是：先把文法编译成一个确定有限自动机，自动机的每个状态代表“我已经看到哪几条产生式的哪个位置”。这个“看到了哪个位置”就是项目（item），形式是A → α·β，点左边是已识别的部分，点右边是待识别的部分。
构造状态机的两个原语是闭包和 GOTO。闭包的含义是：如果点后面跟着一个非终结符，那这个非终结符的所有产生式都可能从这里开始，都得加进来。
grammar = [ ('E', ('E', '+', 'T')), ('E', ('T',)), ('T', ('T', '*', 'F')), ('T', ('F',)), ('F', ('(', 'E', ')')), ('F', ('id',)), ] prods_of = {} for i, (lhs, rhs) in enumerate(grammar): prods_of.setdefault(lhs, []).append(i) def closure(items): result, work = set(items), list(items) while work: pi, dot = work.pop() rhs = grammar[pi][1] if dot < len(rhs) and rhs[dot] in prods_of: # 点后是非终结符 for pj in prods_of[rhs[dot]]: if (pj, 0) not in result: result.add((pj, 0)); work.append((pj, 0)) return frozenset(result) def goto(items, sym): moved = {(pi, dot + 1) for (pi, dot) in items if dot < len(grammar[pi][1]) and grammar[pi][1][dot] == sym} return closure(moved) if moved else frozenset()closure的work列表是必须的：加入一个新项目后，它点后面的非终结符可能又带来新的项目，得反复展开到不动点。goto则把点统一右移一位，再求一次闭包。主循环从closure({(0, 0)})出发，对每个状态枚举点后面的符号，反复调用goto，直到没有新状态产生。
states, index = [], {} start = closure({(0, 0)}) states.append(start); index[start] = 0 i = 0 while i < len(states): cur = states[i]; i += 1 syms = {grammar[pi][1][dot] for (pi, dot) in cur if dot < len(grammar[pi][1])} for sym in syms: nxt = goto(cur, sym) if nxt not in index: index[nxt] = len(states); states.append(nxt)index把状态集合映射成整数编号，这个编号就是分析表里的行号。点后是终结符的边，在 ACTION 表里填移进；点走到产生式末尾的项目，在 ACTION 表里填归约。至于归约到哪一行，SLR 用 FOLLOW 集判断，LR(1) 给每个项目附带一个展望符，更精确但状态数会涨，LALR 则把同心项目集合并起来取折中。
冲突是绕不开的。表达式文法E → E + E | E * E | id在构造表时一定会出现移进-归约冲突，因为a + b * c到底先算加法还是先算乘法，文法本身没说。教学做法是改写文法，分层成E → E+T → T → T*F → F；工程做法是在文法描述里给终结符标优先级和结合性，冲突发生时比较“待移进记号的优先级”和“待归约产生式的优先级”，谁高听谁的，相等就按结合性决定。悬挂 else 的冲突同理，靠“else 移进优先”这条规则解决。这两条路没有对错，前者把复杂度放进文法，后者把复杂度放进表构造器。
3. 语义分析与中间表示：符号表和三地址码为什么是分水岭
语法树只保证结构合法，不保证有意义。int x; x = "hello";在语法上完全正确，语义阶段才拦得住。这一步要做三件事：建符号表管理名字与作用域、做类型检查、生成中间表示。中间表示的选择直接决定后端好不好写，所以它常被当成编译器前后端的分界线。
3.1 作用域链：符号表不是一张哈希表就够
一个作用域一张表，表里存名字到符号的映射，表之间用父指针连成链，这套结构就是作用域链。查找时从当前层往外走，找到第一个就停，天然实现了变量遮蔽；退栈时直接丢掉整张表，不需要逐个删除。
class Symbol: def __init__(self, name, typ, kind='var', offset=0): self.name, self.type = name, typ self.kind, self.offset = kind, offset class Scope: def __init__(self, parent=None, tag='global'): self.table, self.parent, self.tag = {}, parent, tag def define(self, sym): if sym.name in self.table: # 同一层重复定义直接报错 raise SemanticError(f'{sym.name} 在当前作用域重复定义') self.table[sym.name] = sym def resolve(self, name): s = self while s is not None: if name in s.table: return s.table[name] s = s.parent return None # 未声明define只查当前层的table，这是关键——内层同名变量遮蔽外层是合法行为，不能报错。resolve沿parent逐层向上，返回第一个命中的符号。offset是后端分配栈帧时用的相对偏移，语义阶段先占位，后端再回填。
另一条路是“单表 + 撤销日志”：只维护一张全局哈希表，进入作用域时记录本次插入了哪些名字，退出时按日志删除。它的好处是查找永远是 O(1)，不用走链；坏处是编译器中途崩溃时状态不好恢复，且嵌套极深时日志会变长。两种都有人用，课程设计里作用域链更好调试，因为你可以随时把整条链打印出来看。
类型检查通常和符号表同步进行。类型等价有两种判定：名字等价要求两个类型来自同一个声明，结构等价只看成员构成是否一致。多数教学编译器用结构等价，实现上是一个带记忆化的递归比较，避免结构体互相引用时无限递归。
3.2 四元式与回填：短路求值的跳转地址是怎么补上的
中间表示有很多种，三地址码是最适合教学的一种，因为它足够扁平：每条指令最多三个操作数，形如x = y op z。具体存储成四元式(op, arg1, arg2, result)就行。
quads = [] def emit(op, a1='-', a2='-', r='-'): quads.append([op, a1, a2, r]) return len(quads) - 1 # 返回下标，方便后面回填跳转目标 def backpatch(targets, label): for i in targets: quads[i][3] = label # 把占位的跳转目标统一改成真实标号为什么要回填？因为生成a && b的代码时，你还不知道a为假要跳到哪里——右边b的代码还没生成。常见做法是让每个布尔表达式返回一对“跳转链”：真链记录“结果为真时该跳但还没填目标”的四元式下标，假链同理。
def gen_cond(node): """返回 (真链, 假链)，链上是等待回填的四元式下标""" if node.kind == 'and': t1, f1 = gen_cond(node.left) t2, f2 = gen_cond(node.right) backpatch(t1, len(quads)) # 左边为真，继续算右边 return t2, f1 + f2 # 任一边为假，整个表达式为假 if node.kind == 'or': t1, f1 = gen_cond(node.left) t2, f2 = gen_cond(node.right) backpatch(f1, len(quads)) # 左边为假，继续算右边 return t1 + t2, f2 # 关系运算：直接生成条件跳转，两个链各挂一条待填的四元式 ti = emit('if', node.left, 'goto', '-') fi = emit('ifFalse', node.left, 'goto', '-') return [ti], [fi]and的处理值得细看：左边为真的链要回填成“当前四元式下标”，也就是右边代码的起点；而整个and表达式为假的条件是左边假或右边假，所以两个假链直接拼接。这套机制的好处是代码只生成一遍、不做二次遍历，边生成边留洞，最后统一补上。如果先算右边再算左边，p != NULL && p->x这种写法就会在空指针上翻车，这是典型的语义被实现顺序带偏的例子。
中间表示故意做成扁平结构，动机有三层：与具体机器解耦，换目标平台只换后端；便于做局部优化，活跃变量、常量折叠在四元式序列上都是线性扫描能做的事；临时变量的生命周期一目了然，为寄存器分配铺路。AST 更贴近源码，但节点嵌套深，做数据流分析要先拍平，不如一开始就别立起来。
4. 后端与优化：寄存器分配为什么最终变成图着色
后端要做的事是：把中间代码映射到真实指令，把无限的临时变量塞进有限的寄存器。寄存器数量是硬约束， spills 一旦处理不好，前面所有正确的逻辑都会以“变量值莫名变了”的形式崩掉。这个问题的标准解法是图着色，而图着色之前必须先知道“哪些变量同时活着”。
4.1 活跃变量分析：不动点迭代在收敛什么
一个变量在某点活跃，意思是“它当前的值在后面的某条路径上还会被用到”。这个定义天然是反向的：要看后面，不看前面。写成数据流方程就是：
out[n] = ∪ in[s]，s 是 n 的所有后继in[n] = use[n] ∪ (out[n] - def[n])
use[n]是节点 n 在定义之前就使用的变量集合，def[n]是节点 n 定义的变量集合。这两个集合是局部信息，扫一遍指令就能算出来；难点在out[n]依赖后继的in，而控制流图里有环，只能迭代到不动点。
def liveness(nodes, succ, use, defs): live_in = {n: set() for n in nodes} live_out = {n: set() for n in nodes} changed = True while changed: # 集合只会变大，必然收敛 changed = False for n in reversed(nodes): # 逆序能让信息更快往前传 new_out = set() for s in succ[n]: new_out |= live_in[s] new_in = use[n] | (new_out - defs[n]) if new_in != live_in[n] or new_out != live_out[n]: live_in[n], live_out[n] = new_in, new_out changed = True return live_in, live_out参数说明：nodes是逆后序遍历得到的节点序列，succ是后继表，use和defs是每节点的局部集合。收敛性由单调性保证——live_in和live_out每轮只会变大不会变小，集合全集有限，最多迭代到上界就停。
循环回边是这里最容易出错的地方。如果遍历顺序按源码顺序而不是逆后序，循环头的活跃信息要绕一整圈才传回来，迭代轮数会明显变多；更糟的是有人为了“加速”只遍历一次，结果循环体内的变量活跃区间算短了，后面寄存器分配直接把两个冲突变量分到同一个寄存器。逆后序遍历加上不动点循环，这两件事缺一不可。
4.2 冲突图与着色：K 个寄存器不够时溢出到哪
拿到活跃信息后，冲突图的构造很直接：任意两个在同一点同时活跃的变量连一条边，它们不能共用寄存器。接下来就是经典的图着色问题，K 就是可用寄存器数（还要扣掉专门给栈指针、帧指针留的位置）。
def color(graph, K): g = {v: set(ns) for v, ns in graph.items()} stack = [] while g: low = [v for v, ns in g.items() if len(ns) < K] v = low[0] if low else max(g, key=lambda x: len(g[x])) # 度数高者优先溢出 stack.append(v) for u in g: g[u].discard(v) del g[v] colors = {} while stack: v = stack.pop() used = {colors[u] for u in graph[v] if u in colors} for c in range(K): if c not in used: colors[v] = c break else: colors[v] = None # 无可用颜色，标记为溢出到栈槽 return colors第一个循环是简化阶段：反复摘掉度数小于 K 的节点压栈，因为这些节点在回填时一定能找到颜色。如果剩下的节点度数都大于等于 K，就挑度数最高的先摘，它成为溢出候选。第二个循环是回填阶段：按栈的逆序把节点放回去，看邻居已经用了哪些颜色，挑一个没被占的。colors[v] = None表示这个变量要写到栈上，每次使用前插入 load、定义后插入 store。
这套算法是启发式的，不保证最优，但实践效果足够好。课程设计里常见的一个错误是：把溢出候选直接丢掉不管，没有生成对应的 load/store，导致该变量的值被后面分配的寄存器覆盖，表现为“循环第二圈开始结果就不对”。另一个错误是没有把物理寄存器约束建模进去，比如某些指令要求操作数必须在固定寄存器里，这需要在冲突图上预先合并节点。
4.3 优化的边界：哪些变换是“保语义”的
后端优化里最安全的是常量折叠和常量传播：编译期能算出来的表达式直接算掉，2 * 3变成6。稍微危险一点的是公共子表达式消除，它依赖“两个表达式之间没有对相关变量的写操作”这个前提，判断错了就会把已经变化的值复用成旧值。窥孔优化则是在指令序列上开一个小窗口，把load r1, x; store x, r1这种冗余对消掉，实现简单、收益稳定。
有一条经验值得记住：任何优化都必须能在语义上给出“为什么可以这么做”的解释，说不清就不要做。死代码消除看起来很安全，但如果被删掉的指令有副作用（比如函数调用、对 volatile 变量的写），删了就是错的。寄存器分配里的溢出处理也一样，它本质上是在“用内存换寄存器”，只要 load/store 插在对的位置，程序语义不变；插错位置，程序照样能跑，只是结果错得毫无规律。
5. 避坑与排查：课程设计里最容易翻车的几类问题
5.1 现象：<=被切成两个记号，或if被识别成标识符
原因：扫描器没有做最长匹配，读到 DFA 的非接受态就停了；或者关键字表和标识符规则的处理顺序反了，先按标识符规则吃掉整个单词，之后没有回头查关键字表。
解决：扫描时维护last_accept和last_pos，只有走到接受态才更新，循环结束后回退到最近一次接受的位置；关键字统一在标识符扫描完成后查哈希表，命中就改 token 类型，不在词法规则里重复写一遍关键字。改完拿<=、<<=、1.5e-3、if四个输入各跑一遍，看 token 序列对不对。
5.2 现象：递归下降解析器在深表达式上栈溢出，或者一进函数就死循环
原因：文法里有直接左递归，E → E + T写成递归下降就是parse_E()第一句调parse_E()，栈帧无限增长。
解决：改成右递归形式E → T E'，E' → + T E' | ε，把左结合性交给循环实现而不是递归实现。改完检查一遍所有产生式，凡是以自身开头的都要处理。如果不想改文法，就换表驱动的 LR 分析器，它对左递归天然免疫。
5.3 现象：内层作用域退出后，外层同名变量取不到值
原因：exit_scope只把当前层的表丢掉，但没有正确恢复父指针；或者用了单表加撤销日志的方案，日志记录漏了“被遮蔽的旧符号需要重新插回”这一步。
解决：作用域链方案里，进入作用域就新建Scope(parent=cur)，退出时直接把cur = cur.parent，父表从头到尾没被修改过，不存在恢复问题。用撤销日志的话，define时如果发现同名符号已存在，要把旧符号也记进日志，退出时按逆序恢复。写完立刻测一段三层嵌套、里外同名的代码，把每条resolve的结果打出来对。
5.4 现象：短路表达式右侧被求值，空指针判断失效
原因：代码生成时按语法树的自然顺序先算左子树再算右子树，&&和||被当成普通二元运算处理，没有生成条件跳转。
解决：给布尔表达式单独一套生成逻辑，返回真链和假链，&&只在左边为真时才把控制流交给右边。回填时注意链的拼接顺序，and的假链是两边假链的并集，or的真链是两边真链的并集。验证方法很简单：构造一个右边会除零的表达式，左边为假时程序必须正常结束。
5.5 现象：寄存器分配后，循环体内某个变量第二圈开始值不对
原因：活跃变量分析只迭代了一轮，或者遍历顺序不是逆后序，循环回边上的活跃信息没有正确传播，导致两个实际冲突的变量被判定为不冲突，分到了同一个寄存器。
解决：确认数据流迭代跑到changed == False才退出，遍历用逆后序。调试时把每个基本块的live_in、live_out打印出来，重点看循环头的集合是否包含循环体内定义、循环外使用的变量。再补一个最小复现：循环里两个变量交替赋值，输出它们的值，能稳定复现就说明找到了。
6. 设计取舍：手写递归下降和表驱动 LR 为什么都活着
课程设计做到最后，很多人会问一个问题：既然 LR 能处理几乎所有文法，为什么还有那么多编译器用手写递归下降？答案在于取舍的方向不同。递归下降是自顶向下的，代码结构和文法一一对应，加一条新语法就是加一个函数，报错时能精确说出“这里期望一个表达式，实际看到的是分号”，这对用户体验至关重要；代价是文法必须先消除左递归、提取左公因子，能覆盖的文法类小一些。表驱动 LR 是自底向上的，文法几乎不用改写，覆盖范围广；代价是分析表是算出来的，出错时你只能看到“状态 37 遇到记号 12 无法转移”，错误恢复要靠额外规则设计，调试时得把项目集打印出来才能看懂。
我的建议是：前端用递归下降，后端用表驱动。前端追求的是可读性和错误信息质量，而且表达式文法的左递归消除是机械操作，做一次就熟了；后端的状态转移、活跃变量、着色这些全部是数据驱动的不动点计算，写成表反而更清晰。中间表示也一样，AST 适合做语义检查和报错定位，三地址码适合做优化和代码生成，两者各留一层，转换一次，换来的是后面每一步都能独立调试。
验证方法上，不要只测“结果对不对”。每加一个阶段就加一个 dump 开关：词法阶段打 token 序列，语法阶段打带缩进的树，语义阶段打符号表和类型，中间代码阶段打四元式，后端打活跃变量集合和着色结果。分层 dump 的好处是，出错时你能一眼定位到哪一层的输出第一次偏离预期，而不是从最终结果反推。我当初偷懒只测最终输出，一个变量值错的问题查了整整两天，最后发现是作用域退栈时父指针没接上。
从那以后我每次写这类东西，都强制自己先把每一层的中间结果打印出来跑通，再往下接。希望帮到你。
本文还有配套的精品资源，点击获取
