从if语句看编译原理五阶段：词法语法语义与中间代码实战

简介：南京航空航天大学编译原理课程设计全套材料，面向计算机及相关专业学生与需要完成词法、语法分析实验的读者，可用于课程设计参考、程序调试和答辩准备。压缩包共32个文件，约961KB，包含C/C++源码与头文件、可执行程序、工程文件、课程设计报告doc、答辩PPT以及若干txt说明，覆盖词法分析、语法分析、符号表与语法树等模块，目录按词法、语法和文档分类，便于对照查阅。已有751人学习，说明其在实际课设场景中具有一定参考价值。资料中提供可运行程序与完整报告，描述称经检验程序无BUG，读者可据此理解扫描器、记号流、属性字和语法分析流程，也可借鉴报告组织与答辩展示思路，适合作为编译原理课设的完整范本与排错参照。

1. 为什么一个 if 语句要过五道关卡：编译器的分层不是为了好看

一个if语句从源码走到汇编，中间要经过词法分析、语法分析、语义分析、中间代码生成、目标代码生成五道关卡，编译原理课程设计之所以让人头大，就是因为它要求你把这五道关卡全部亲手搭一遍。直觉上，一趟扫描既认字又断句又算类型似乎更快，但真正动手就会发现，只要把两件事混在一个函数里，错误定位立刻变成黑匣子：报错行号对不上，改一处崩三处。分层的价值不在教科书好看，而在于让每一层只处理一类问题——字符怎么组成记号、记号怎么组成结构、结构怎么对应语义、语义怎么落成可优化的中间形式、中间形式怎么落到寄存器上。搞懂这条流水线每层的边界在哪，你才知道自己踩的坑该去哪一层找，也才知道为什么这门课设计得这么“重”。

2. 词法分析：正则表达式到状态机的两次坍缩

词法分析器干的活说起来简单：把一串字符切成有类型的记号（token）。但它的实现路径几乎是一条固定的流水线——正则表达式 → NFA → DFA → 最小化 DFA → 转移表。每一段变形都在回答同一个问题：怎样让“识别一个记号”这件事，从“解释规则”变成“查表跳转”。

2.1 Thompson 构造：为什么正则要先摊成 NFA

正则表达式的三种基本运算——连接、选择、闭包——天生适合归纳构造。Thompson 构造的思路是：每一种运算对应一种只有两三个状态的小结构，用 ε 边把它们串起来，递归拼装，最后得到一个有唯一入口和唯一出口的 NFA。它的好处是实现极其规整，坏处是引入了大量 ε 边，NFA 本身又不确定：同一个状态对同一个输入字符可能有多条出边，机器不知道该走哪条。

# trans[(状态, 字符)] = 后继状态集合；eps[状态] = ε 后继集合 def build(node, counter, trans, eps): if node.kind == 'char': s, e = counter.new(), counter.new() trans[(s, node.ch)] = {e} # 单字符：一条确定边 return s, e if node.kind == 'concat': s1, e1 = build(node.left, counter, trans, eps) s2, e2 = build(node.right, counter, trans, eps) eps[e1].add(s2) # 左片段出口 ε 接到右片段入口 return s1, e2 if node.kind == 'alt': s, e = counter.new(), counter.new() s1, e1 = build(node.left, counter, trans, eps) s2, e2 = build(node.right, counter, trans, eps) eps[s] |= {s1, s2} # 入口分叉，靠 ε 边做选择 eps[e1].add(e) eps[e2].add(e) return s, e if node.kind == 'star': s, e = counter.new(), counter.new() s1, e1 = build(node.inner, counter, trans, eps) eps[s] |= {s1, e} # 要么进循环体，要么直接跳过 eps[e1] |= {s1, e} # 循环体结束可以再来一次 return s, e

counter负责分配全局唯一的状态编号，trans是字符转移表，eps是 ε 转移表。注意star那一支里的两条 ε 边：一条让入口直接越过整个循环（零次匹配），一条让循环体出口回到循环体入口（多次匹配）。这两条边就是“闭包”在自动机层面的全部含义。写下这段代码时最好把每个片段的入口和出口在纸上标出来，否则 ε 边接错一根，整个 NFA 就会静默地少识别一类串，而且极难从测试结果反推。

2.2 子集构造与 DFA 最小化：把状态数按回可控范围

NFA 的不确定性在实现上是致命的：你没法把“当前可能处于哪些状态”压缩成一个整数下标，也就没法用二维数组做 O(1) 跳转。子集构造的核心动作是把“状态集合”整体当成 DFA 的一个状态，用 ε-闭包把 ε 边走完，再按输入字符求后继集合。一次闭包、一次 move、一个新集合入队，循环到不动点。理论上最坏情况会到 2 的 n 次方个状态，但真实词法规则里每个集合的规模很小，实际状态数和 NFA 往往在同一量级。

def epsilon_closure(states, eps): stack, closure = list(states), set(states) while stack: s = stack.pop() for t in eps.get(s, ()): if t not in closure: closure.add(t) stack.append(t) return frozenset(closure) def subset_construction(start, eps, trans, accept): d0 = epsilon_closure({start}, eps) ids = {d0: 0} # DFA 状态集合 -> 整数编号 work, dfa_trans, dfa_accept = [d0], {}, set() while work: cur = work.pop() if cur & accept: # 集合里含任一 NFA 接受态，整个集合就是接受态 dfa_accept.add(ids[cur]) moves = {} for s in cur: for ch, targets in trans.get(s, {}).items(): moves.setdefault(ch, set()).update(targets) for ch, targets in moves.items(): nxt = epsilon_closure(targets, eps) if nxt not in ids: ids[nxt] = len(ids) work.append(nxt) dfa_trans[(ids[cur], ch)] = ids[nxt] return ids, dfa_trans, dfa_accept

这段代码里最容易被忽略的是moves那一层的合并：同一个字符的所有后继必须先并成集合，再整体做一次闭包，而不是对每个源状态分别闭包再并。顺序写反了结果在简单文法下往往碰巧正确，一旦有 ε 边跨层就会出现漏状态。生成 DFA 后通常还要做一次最小化：先按“接受态与非接受态”划成两组，再反复按“对每个字符的去向分组签名”细分，直到组数不再变化。最小化的实际收益主要是转移表变小、缓存友好，对正确性没有影响，但课程设计的验收用例里经常有“打印自动机状态数”这一项，不做就会不好看。

2.3 最长匹配与关键字查表：DFA 跑完还要回退

自动机只回答“这个前缀能不能被接受”，不回答“应该在哪里切”。真实的词法规则要求最长匹配：>=不能被切成>和=，1.5e-3要整体识别成一个浮点数。做法是让 DFA 一直跑到无法继续为止，同时记录“最后一次停在接受态的位置和类型”，跑不动了就回退到那个位置吐出记号。这一步是手写词法器翻车的重灾区——不回退的实现在遇到a+这种规则时会把整个标识符吞掉。

关键字通常不单独建自动机，而是先按标识符规则识别，拿到字符串后查一张关键字哈希表，命中就改类型。这个顺序不能反过来，否则ifx会被切成if和x。同理，注释和空白在词法阶段就该被丢弃，不要留到语法阶段处理，否则语法分析器的每个产生式都要考虑“中间可能夹着注释”，复杂度直接翻倍。

3. 语法分析：递归下降和 LR(1) 到底在争什么

语法分析要回答的是“这串记号能不能由文法推导出来，以及按什么结构推导”。自顶向下的递归下降从开始符号出发，试图用产生式去匹配输入；自底向上的 LR 从输入出发，把记号不断归约成非终结符。两条路线的分歧不在能力，而在“谁来承担复杂度”：递归下降把复杂度交给写代码的人，LR 把复杂度交给建表程序。

3.1 递归下降与 FIRST/FOLLOW：为什么教科书文法不能直接抄

教科书上的表达式文法通常是左递归的：E → E + T | T。直接照着写递归函数会立刻栈溢出，因为parse_E()的第一件事就是调用parse_E()。消除左递归的标准改法是把它转成右递归，或者更实用的做法——改写成循环：

def parse_E(self): left = self.parse_T() # 先吃掉一个 T while self.peek() in ('+', '-'): # 后续的 + T 在循环里平铺处理 op = self.advance() right = self.parse_T() left = BinOp(op, left, right) # 左结合：新节点总是挂在左边 return left

这个循环的写法直接保住了左结合性，1-2-3会被构造成(1-2)-3。如果偷懒用右递归改写，构造出来的就是1-(2-3)，语法树长得一模一样地合法，但语义全错，而且这种错误在只测单个运算符时根本暴露不出来。FIRST 集解决“当前该选哪条产生式”，FOLLOW 集解决“当前非终结符后面能跟什么”，两者合起来才能建出 LL(1) 预测分析表。任何一条产生式的 FIRST 集和另一条的 FIRST 集相交，或者某条产生式能推出 ε 且它的 FIRST 和 FOLLOW 相交，就说明文法不是 LL(1)，必须提取左公因子或者改写文法。

3.2 LR(1) 项目集与 ACTION/GOTO 表：冲突是在哪一步埋下的

LR 的核心数据结构是项：在产生式右部插一个点，表示“已经识别到哪”，再跟一个向前看符号。闭包运算负责在点后面是非终结符时，把该非终结符的所有产生式以点在最左的形式加进来，向前看符号由 FIRST(βa) 算出来。GOTO 负责在点上移一位后求新的项集。所有项集构成项目集族，再映射成 ACTION 表和 GOTO 表。

def closure(items, grammar, first_seq): result = set(items) changed = True while changed: changed = False for (lhs, rhs, dot, la) in list(result): if dot < len(rhs) and rhs[dot] in grammar: nxt = rhs[dot] beta = rhs[dot + 1:] # 向前看符号 = FIRST(beta 后接原向前看符号) lookaheads = first_seq(beta + (la,)) for prod in grammar[nxt]: item = (nxt, prod, 0, la2) if False else None for a in lookaheads: item = (nxt, prod, 0, a) if item not in result: result.add(item) changed = True return frozenset(result)

lhs, rhs, dot, la四个字段缺一不可：少了dot就分不清移进还是归约，少了la就退化成 SLR，遇到“归约时该看哪个后续记号”会误判。冲突只有两种：移进-归约冲突和归约-归约冲突。前者最常见的来源是悬空 else 和没有分层的表达式文法，把E → E + E | E * E直接丢进去必然冲突，因为文法本身有二义性；解决办法是把表达式拆成E/T/F三层，让优先级和结合性写进文法结构里，或者用优先级声明在冲突时指定移进。后者通常来自两个不同非终结符推出了相同右部，要么合并，要么改写。LALR(1) 把同心项集合并，表小了一个数量级，代价是把某些只在向前看符号上有差别的冲突又合并了出来，这就是“LALR 比 LR(1) 弱”的全部含义。

3.3 错误恢复：为什么解析器一报错就雪崩

一个只会在第一个错误处exit(1)的解析器在课程设计里勉强能过，但遇到“少一个分号后面跟十条语句”的用例就会被判得很惨。恐慌模式恢复的做法是：报错后丢弃记号，直到遇到一个属于当前非终结符 FOLLOW 集的同步记号，然后弹出栈顶继续。这需要每个非终结符都记录自己的 FOLLOW 集和一组“可信的起始记号”。更细一点的是短语级恢复：在表达式内部发现多余运算符时，直接插入一个占位叶子节点继续往下走，把一条错误压成一个错误。恢复策略本身不改变正确程序的行为，但它决定了错误报告的质量，而错误报告质量在人工评审里权重很高。

3.4 手写递归下降还是用生成器

两条路都能拿到满分，区别在于调试成本。递归下降每一步都能打断点、看调用栈、看当前记号，出错时几乎立刻能定位到某一行；用生成器（比如某种 yacc 类工具）意味着你要先接受“冲突数”这个陌生指标，再学会从状态机描述里反推文法问题，前期门槛高，但文法改动只需要动几行声明。我的建议是：文法规模小、需要精细错误恢复的，手写；文法规则多、优先级层次复杂的，用生成器建表再把表嵌进自己写的驱动里。

4. 语义分析与中间代码：符号表、类型检查和可优化性

前面两个阶段只保证“结构合法”，语义分析才回答“这个结构有没有意义”。名字有没有声明过、类型对不对得上、函数调用参数个数对不对，都在这一层结算。中间代码则是把语法树翻译成一种更扁平、更适合反复扫描的形式，为后面的优化和目标代码生成铺路。

4.1 作用域链符号表：为什么嵌套作用域要用栈

符号表最朴素的做法是一张全局哈希表，但一旦有嵌套作用域就立刻失效：内层同名变量必须遮蔽外层，退出内层后外层变量必须“复活”。这天然是一个栈的语义。常见实现有两种：一是单表加作用域标记，查到名字后检查其作用域深度是否仍在当前可见范围内；二是链式作用域，每个作用域一张小表，查找时沿父指针向上走。

class Scope: def __init__(self, parent=None): self.table = {} # 名字 -> 类型、种类（变量/函数）、偏移量 self.parent = parent def declare(self, name, info): if name in self.table: # 同一作用域重复声明，报语义错误 raise SemanticError(f"重复声明: {name}") self.table[name] = info 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

parent指针就是作用域链，declare只在当前层写，lookup从内向外读。这种结构让“进入作用域”变成新建一个Scope，“退出作用域”变成把指针指回parent，天然避免了“删除内层变量时误删同名外层变量”这类事故。如果改用单表方案，退出作用域时必须精确恢复被遮蔽的旧条目，用一个栈记录“这个名字原来是什么”，写错一步就会在后面几十行处表现成莫名其妙的名字解析失败。

4.2 类型检查与隐式转换：语义动作里最容易翻车的地方

类型系统有两个绕不开的决策：类型等价怎么定义，隐式转换插在哪。名字等价要求两个类型是同一个声明产生的才相等，结构等价只看成员结构是否一致。对课程设计来说结构等价实现简单，但会导致“两个成员完全相同的不同结构体可以互相赋值”这种奇怪行为，写报告时最好明确说明选了哪种。隐式转换的插入位置必须固定在语义动作里，比如算术运算两侧类型不同时，在语法树上显式插入一个Cast节点，而不是在每个用到的地方临时判断。前者的转换只发生一次，后面的中间代码生成和优化都能看到它；后者会让类型判断逻辑散落在十几个函数里，改一个规则要改十几处。

还有一个容易被忽略的点：数组下标、函数实参、返回值这三处的类型检查，往往需要“可赋值性”而不是“完全相等”。整数可以赋给浮点，指针可以赋给void*，如果一律用严格相等，很多正常程序会被误判非法。

4.3 四元式与基本块：中间表示为什么长这样

三地址码的核心约束是“每条指令至多一个运算符、至多三个地址”。这个约束不是为了好看，而是为了后面做优化时每条指令的读写集合可以被精确定义。四元式是最常见的落地形式：(op, arg1, arg2, result)。

def gen_expr(node, quads, temp): if node.kind == 'num': return node.value # 常量直接作为地址返回 if node.kind == 'id': return node.name # 变量名本身就是一个地址 if node.kind == 'binop': a = gen_expr(node.left, quads, temp) b = gen_expr(node.right, quads, temp) t = temp.new() # 每个中间结果分配一个新临时变量 quads.append((node.op, a, b, t)) return t

temp.new()保证每个子表达式的值有唯一的名字，这样后面做公共子表达式消除时可以直接比较(op, arg1, arg2)三元组。如果图省事复用临时变量编号，两个不同的中间结果会撞名，优化器要么漏掉可消除项，要么把不该合并的合并了，症状是程序在某些输入下算错，而且几乎无法用肉眼看出来。基本块的划分规则同样机械：第一条语句是入口；任何跳转语句的目标语句是入口；任何跳转语句的下一条语句是入口。三条规则把整个指令序列切成一段段顺序执行、无分支进出的小块，块内指令的先后关系是确定的，这才让数据流分析有意义。

4.4 活跃变量分析：优化前必须先算清楚谁活着

活跃变量分析回答“在程序点 p 之后，变量 x 的值还会不会被用到”。如果不会，那 x 所占的寄存器就可以给别人用，这就是寄存器分配的前提。数据流方程是反向的：出口活跃集合等于所有后继入口活跃集合的并，入口活跃集合等于本块使用集合加上“出口活跃减去本块定义集合”。

def liveness(blocks, succ, use, defs): IN = {b: set() for b in blocks} OUT = {b: set() for b in blocks} changed = True while changed: changed = False for b in reversed(blocks): # 反向遍历，收敛更快 out = set().union(*(IN[s] for s in succ[b])) if succ[b] else set() in_ = use[b] | (out - defs[b]) # 先减定义，再加使用 if out != OUT[b] or in_ != IN[b]: OUT[b], IN[b] = out, in_ changed = True return IN, OUT

use是本块内“先读后写”的变量集合，defs是“先写后读”的集合，注意同一个变量在一个块内可能既读又写，顺序决定了它归哪一边。这个迭代一定收敛，因为每次更新只会让集合变大，而变量总数有限。真正的坑在过程调用：调用点会读取实参、可能修改全局变量和指针指向的内存，如果只按“显式出现的变量”算活跃性，调用之后仍然需要的全局变量会被判成死变量，寄存器一分配就出错。保守做法是把调用指令当作“所有可被调用者访问的变量都算使用”。

5. 常见问题排查：那些看起来玄学的失败

下面几条都是我在看别人做编译原理课程设计时反复遇到的，症状看起来毫无规律，原因却都很具体。

5.1 词法与语法阶段

现象：语法分析器报错的行号总是指向语句的下一行，或者if被识别成普通标识符导致后面的结构全乱。原因：词法分析器在识别完标识符后没有查关键字表，或者读取字符时多消费了一个换行符但没更新行号计数。解决：把关键字查表固定在“标识符规则命中之后、记号返回之前”，并在每次消费\n时统一更新行号，所有错误信息都从这个计数器取值，不要在多个函数里各自维护一份。

现象：解析a = b + c * d;时括号匹配正确但语法树结构错，乘法被算成了加法的一部分。原因：表达式文法没有分层，E → E + E | E * E这类二义性文法在递归下降里会按产生式书写顺序决定优先级，效果约等于随机。解决：把表达式拆成E/T/F三层，加法只出现在最外层，乘法和括号在里层，优先级就固化在文法结构里，不需要额外维护优先级表。

现象：解析器遇到第一个语法错误后连续报出几十条错误，后面每一条都指向错误位置附近。原因：报错后没有丢弃记号，解析函数在同一个位置反复调用自己。解决：报错时至少消费掉当前记号，并跳到 FOLLOW 集里的同步记号再恢复，保证每次恢复都让输入位置严格前进。

5.2 语义与符号表阶段

现象：嵌套作用域里，内层的x明明声明过，查表却返回了外层的x。原因：符号表是单表加栈，但查找时从栈底开始扫，或者退出作用域时把外层的同名条目也删了。解决：查找必须从最内层作用域开始向外，退出作用域只弹出最后一次插入的记录，用“插入时就记下被遮蔽的旧值”的方式精确回滚。

现象：函数调用传参类型不匹配时不报错，运行到中间代码生成阶段才崩。原因：语义动作只检查了参数个数，没检查类型，或者把类型检查散落在多个地方导致部分分支被遗漏。解决：所有类型检查集中在语义动作的入口处做，参数个数、每个实参的可赋值性、返回值类型一次性判完，任何一项失败立刻报错并返回错误类型节点，避免错误向下传播。

5.3 中间代码与优化阶段

现象：优化前程序输出正确，开启常量折叠后结果变了。原因：对带副作用的表达式做了折叠，比如把f() + 1里的f()当成纯函数求值了一次。解决：只有操作数全是字面量、运算符是纯算术或逻辑运算时才折叠，任何函数调用、赋值、自增一律跳过。

现象：寄存器分配后程序在某个测试用例上结果不对，关掉分配就正常，看起来像玄学。原因：活跃变量分析没有把过程调用点视为“使用所有全局变量和指针可达变量”，导致某个变量被判定为死亡，寄存器被复用。解决：在use集合里把调用指令保守处理，把所有可能被调用者访问的变量都加进去；宁可多占一个寄存器，也不要让活跃性判断出错。

现象：同一份中间代码，打印出来看完全正确，生成的目标代码却少了最后几条指令。原因：基本块划分时把跳转目标的下一条语句当成了新块的入口，导致前一个块被截断，末尾指令被归到不可达块里，后续优化按不可达直接删了。解决：划分规则照定义严格执行，块内遍历时以“入口集合”为准做切分，切完之后再打印一遍每个块的指令序号核对。

6. 设计取舍：从能跑通示例到能过隐藏用例之间隔着什么

做这门课程设计最容易犯的顺序错误，是先追求每一层的“精巧”，结果整条流水线迟迟跑不通，时间全耗在调试半成品上。我的血泪经验是反过来的：先用最简单的办法让五层全部打通，哪怕词法用一堆if手写、语法用递归下降硬编码、中间代码只生成四元式不做任何优化，也要让一个包含赋值、算术、条件、循环的小程序能完整走完词法到目标代码的全流程。这条最小可运行路径一旦存在，后面每一层的改进都有地方验证——改词法，看记号序列；改语法，看语法树；改语义，看符号表和控制台报错；改优化，看中间代码前后对比。

验证方法上，对拍比单点测试可靠得多：准备一组覆盖边界的程序，一份用解释器或现成工具算出预期输出，一份跑自己的编译器，逐条比对。隐藏用例通常集中在边界上——空语句、嵌套注释、深层括号、溢出、除零、同名变量遮蔽、函数递归调用。这些恰恰是最小示例覆盖不到的。还有一条：每一层的中间产物都要能打印出来，语法树、符号表快照、四元式序列、基本块划分、活跃变量表，全部加上开关。当优化后的程序算错时，这堆快照能让你在几分钟内判断是活跃性算错还是指令选择写错，而不是靠删代码二分。

至于取舍，寄存器分配是最典型的例子：图着色实现起来漂亮，但构建冲突图、简化、着色、溢出处理一整条链路，任何一个环节出错都表现为“结果偶尔不对”，调试成本远超收益；反倒是线性扫描分配简单、行为可预测，在课程设计的规模下几乎看不出性能差距。从那以后我每次做这类项目，都强制先把“能跑通全流程”当成唯一的验收标准，再按依赖顺序逐层加精度，每加一层都跑一遍对拍。希望这个顺序也能帮到你，资源里那份完整的实现和文档，正好可以对着这条主线去看每一层是怎么落地的。

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