编译原理实验代码全链路：词法分析、语法分析与四元式回填

简介：面向计算机专业学生与编译原理初学者，这份电子科技大学编译原理实验代码提供词法分析器、语法分析器及配套工程的可运行实现参考，可用于课程实验复现、代码对照与原理理解。压缩包共21个文件，约203KB，以5个cpp源文件和4个头文件为核心，辅以2个pas示例、docx运行说明、Visual Studio工程文件及exe可执行程序，覆盖输入读取、字符处理、词法分词、语法解析等模块，便于查看实现细节与工程组织方式。已有2114人学习，说明其在课程实验场景中具有一定参考价值。读者可结合运行说明配置环境、运行可执行程序观察结果，再对照源码理解token流生成、抽象语法树构建及模块间调用关系，也可借鉴其中的文件处理与错误记录思路，用于自己的实验排错和设计完善。

1. 编译原理实验代码：从词法到目标代码的完整链路拆解

多数人第一次打开编译原理实验框架，看到的是一个写好的驱动骨架加几个空函数，评分脚本只认标准输出，文法错一个符号整条链就崩。这份某高校的编译原理实验代码，把词法分析、语法分析、语义分析、中间代码生成到目标代码生成这几段全部填满，每个阶段能单独跑，也能串成一条完整流水线。它解决的不是"编译原理是什么"，而是"我这个表达式文法为什么建不出 LL(1) 表、四元式为什么少一条、布尔表达式回填为什么错位"。适合正在做课程实验、想拿一份能跑通的实现对照排查的人，也适合想回头补一遍前端流程的从业者。

2. 词法分析器：从正规式到 DFA 的落地路径

2.1 先定 token 表，别急着写状态机

词法这一层的翻车点很少在算法上，多数在接口。实验框架的驱动通常固定了 token 输出格式：(种别码, 属性值, 行号, 列号)，种别码是框架给的枚举值，属性值对标识符是名字本身、对常数是数值。你要是先把状态机写得漂亮，最后发现种别码对不上框架常量，前面全要返工。我一般先按框架的枚举把表抄一遍，再倒推每种 token 需要哪些字符集。

这张表是后面一切的前提：状态机只需要保证"识别出的串 → 类别"映射正确，输出格式由表驱动，改格式不动算法。

2.2 子集构造法：NFA 到 DFA 的可执行版本

从正规式到 DFA 的教材流程是 Thompson 构造出 NFA、子集构造去 ε、再最小化。实验里真正要写的是中间那步，这里给一份可以直接跑的版本，NFA 用嵌套字典表示，ε 边用空字符串做键。

# NFA 表示：trans[state][char] = set(states)，ε 边用 '' 作键 def epsilon_closure(states, trans): """求状态集合的 ε 闭包，用栈做深度优先，避免递归爆栈""" stack = list(states) closure = set(states) while stack: s = stack.pop() for nxt in trans.get(s, {}).get('', set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure) def move(states, ch, trans): """从集合整体出发，沿字符 ch 走一步能到达的状态集合""" out = set() for s in states: out |= trans.get(s, {}).get(ch, set()) return frozenset(out) def subset_construction(start, alphabet, trans, accept): """返回 (dfa 状态列表, dfa 转移表, dfa 终态下标集)""" d0 = epsilon_closure({start}, trans) dfa_states, index = [d0], {d0: 0} dfa_trans, dfa_accept = [], set() i = 0 while i < len(dfa_states): cur = dfa_states[i] row = {} if cur & accept: # DFA 状态含任一 NFA 终态即为终态 dfa_accept.add(i) for ch in alphabet: nxt = epsilon_closure(move(cur, ch, trans), trans) if not nxt: # 空集不建状态，等价于死状态 continue if nxt not in index: # frozenset 可哈希，直接当字典键去重 index[nxt] = len(dfa_states) dfa_states.append(nxt) row[ch] = index[nxt] dfa_trans.append(row) i += 1 return dfa_states, dfa_trans, dfa_accept

这段代码的三个关键点：epsilon_closure只对 ε 边做闭包，顺序无关，所以用栈还是队列都行；move返回的是集合，必须再套一次 ε 闭包才是 DFA 的一个状态，漏了这一步就会出现"看起来能跑但少识别串"的玄学问题；frozenset能哈希，是子集构造做去重的常用手段，换成 list 就得自己写比较。accept是 NFA 终态集合，判断条件是"交集非空"而不是"包含"，因为一个 DFA 状态可能同时对应多个 NFA 终态。

最小化不是必做项，实验评分通常不查状态数。但如果你的 DFA 要手写成 switch-case 扫描器，做一遍 Hopcroft 划分能少写一半分支，这个收益是实打实的。

2.3 扫描器与实验框架的输出对齐

有了 DFA 转移表，扫描器本体就是"最长匹配 + 回退"。很多实验要求支持关键字不区分大小写，那就统一转小写再查表，但属性值保留原始大小写，这个细节决定你能不能过隐藏用例。

KEYWORDS = {'if', 'else', 'while', 'for', 'int', 'float', 'return'} def scan(src, dfa_trans, accept_states, final_state): i, line, col = 0, 1, 1 tokens = [] while i < len(src): if src[i].isspace(): line += src[i] == '\n' col = 1 if src[i] == '\n' else col + 1 i += 1 continue state, last_accept, last_pos = 0, None, i j = i while j < len(src): ch = src[j] if ch not in dfa_trans[state]: break state = dfa_trans[state][ch] j += 1 if state in accept_states: # 记录最近一次"能被接受"的位置 last_accept, last_pos = state, j if last_accept is None: # 一个字符都吃不下，报错并跳过 tokens.append(('ERROR', src[i], line, col)) i, col = i + 1, col + 1 continue lexeme = src[i:last_pos] kind = classify(lexeme) # 查关键字表/常数判定，见 2.1 的表 tokens.append((kind, lexeme, line, col)) col += last_pos - i i = last_pos return tokens def classify(lexeme): if lexeme[0].isalpha() or lexeme[0] == '_': return lexeme.lower() if lexeme.lower() in KEYWORDS else 'ID' if lexeme[0].isdigit() or lexeme[0] == '.': return 'CONST' return lexeme # 运算符和界符直接用符号本身做种别

逻辑上有两处容易写错。last_accept必须是"最近一次进入终态"的位置，不能是第一次，否则123.45会被截成123再把.45当新 token；出错分支必须前进一格，不然遇到非法字符就是死循环。classify里关键字判断用lower()查表但返回原串，是为了兼容框架对大小写的宽容度。参数方面，dfa_trans是 2.2 的产物，accept_states是终态下标集合，final_state这个形参在实际实现里可以去掉，我保留它只是为了和部分框架的函数签名对齐。

写完这层，建议先拿一份包含注释、浮点数、错误字符的源文件单跑，把 token 序列打出来肉眼对一遍，再进语法分析。

3. 语法分析：LL(1) 与 LR(1) 两张表怎么选、怎么生成

3.1 FIRST/FOLLOW 与预测分析表

选 LL(1) 还是 LR，不看难度看文法。实验文法里常有左递归和公共左因子，LL(1) 必须先改写，改写会改变语法树形状，如果你的语义分析依赖树结构，改写的代价不小；LR 能直接吃左递归，但表大、调试靠打印状态栈。我的建议是：文法里算术表达式用 LR，语句部分用 LL(1) 或递归下降，这是多数实验框架能接受的组合。

FIRST 集是后面所有表的基础，写成不动点迭代最稳：

def compute_first(grammar, terminals): """grammar: {A: [('B','c'), ('d',), ()]}，空元组表示 A -> ε""" first = {A: set() for A in grammar} for t in terminals: first.setdefault(t, set()).add(t) changed = True while changed: changed = False for A, prods in grammar.items(): for prod in prods: if not prod: # A -> ε if '' not in first[A]: first[A].add(''); changed = True continue for sym in prod: add = first[sym] - {''} if not add <= first[A]: first[A] |= add; changed = True if '' not in first[sym]: # 该符号不能推出空，停止 break else: # 整条产生式都可空 if '' not in first[A]: first[A].add(''); changed = True return first def first_of_seq(seq, first): """求符号串的 FIRST，供产生式右部和 FOLLOW 计算复用""" out = set() for sym in seq: out |= first[sym] - {''} if '' not in first[sym]: return out out.add('') return out

for...else这个写法要留意：else 只在循环没被 break 时执行，正好对应"所有符号都可空"这一分支，比用标志位干净。first_of_seq里遇到不可空符号立即返回，是性能上的必要，不是风格问题。

预测分析表按M[A][a] = 产生式填：对每条A -> α，把FIRST(α)-{ε}里的终结符都填上；若 α 可空，再把FOLLOW(A)填上。填表时同格写第二次就是冲突，直接在这里报出来，比等到分析时崩掉好定位。

3.2 LR(0) 项目集族到 SLR 的 ACTION 表

SLR 是实验里性价比最高的选择：项目不带展望符，归约看 FOLLOW 集，代码量比 CLR 少一半，冲突也比 LR(0) 少得多。项目用三元组(左部, 右部元组, 点位置)表示。

def closure_slr(kernel, prods, nonterms): """kernel 是核项目集合，prods: {B: [('x','y'), ...]}""" items, stack = set(kernel), list(kernel) while stack: head, body, dot = stack.pop() if dot < len(body) and body[dot] in nonterms: B = body[dot] for p in prods[B]: it = (B, tuple(p), 0) if it not in items: items.add(it); stack.append(it) return frozenset(items) def goto(items, X, prods, nonterms): """点右移过符号 X 后求闭包，空核返回空集""" kernel = {(h, b, d + 1) for (h, b, d) in items if d < len(b) and b[d] == X} return closure_slr(kernel, prods, nonterms) if kernel else frozenset() def build_canonical(prods, nonterms, terminals, start_item): """构造 LR(0) 项目集规范族，返回 (状态列表, 状态间转移)""" states, index, trans = [closure_slr({start_item}, prods, nonterms)], {}, {} index[states[0]] = 0 i = 0 while i < len(states): for X in list(nonterms) + list(terminals): nxt = goto(states[i], X, prods, nonterms) if not nxt: continue if nxt not in index: index[nxt] = len(states); states.append(nxt) trans[(i, X)] = index[nxt] i += 1 return states, trans

start_item一般写成("S'", ("S",), 0)，即增广文法的初始项目。build_canonical每轮对当前状态尝试所有文法符号，goto返回空就跳过，这是把"点后面有哪些符号"交给统一循环处理，不用单独枚举。表填法：点后是终结符 a 时填ACTION[state][a] = shift goto(state,a)；点后是$且项目为S' -> S.时填 accept；点是项目末尾时按FOLLOW(左部)里每个符号填reduce；非终结符的 goto 填 GOTO 表。这一步的坑我在第 5 章展开。

3.3 移进-归约冲突的处理顺序

写出冲突不稀奇，知道按什么顺序处理才重要。下面这张对比表是我踩过之后整理的处理优先级，从上往下依次尝试：

优先级方案落地时，在填表函数里加一个比较逻辑：冲突双方一个 shift 一个 reduce，若被归约产生式的优先级高于待移进终结符就 reduce，反之 shift，同级看结合性。这套规则在表达式文法上基本能一次过，剩下的冲突再按表往下走。

4. 语义分析与中间代码：AST 到四元式的属性计算

4.1 AST 节点与符号表的数据结构

中间代码这一章是实验里最容易"看起来对、跑起来错"的地方，根因往往是数据结构没设计好。AST 节点用统一类加kind字段，比给每种节点写一个类省事，遍历时用字典分发。

class Node: __slots__ = ('kind', 'value', 'children', 'lineno') def __init__(self, kind, value=None, children=None, lineno=0): self.kind = kind # 'num' / 'id' / 'binop' / 'assign' / 'if' ... self.value = value # 运算符、标识符名、常量值 self.children = children or [] self.lineno = lineno class SymbolTable: """作用域栈，每层一个字典，查找从内向外""" def __init__(self): self.scopes = [{}] def enter(self): self.scopes.append({}) def leave(self): self.scopes.pop() def declare(self, name, typ, extra=None): if name in self.scopes[-1]: # 同层重复声明必须报错 raise SyntaxError(f'重复声明 {name}') self.scopes[-1][name] = {'type': typ, 'extra': extra or {}} def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] return None

__slots__在节点数量上万时能明显省内存，实验规模下可有可无，但养成习惯不亏。declare里的同层重复检查是必须的，跨层允许同名遮蔽，这是 C 系语言的常规语义，别把检查写成全局唯一。lookup从内层向外找，返回 None 表示未声明，调用方负责报错并带上行号。

4.2 类型检查的遍历骨架

类型检查是自底向上算类型、遇到不合法组合就报错。写成后序遍历，每个节点返回自己的类型。

def check(node, symtab, errors): """返回节点类型，出错时记录并返回 'error' 以便继续检查后续节点""" if node.kind == 'num': return 'float' if isinstance(node.value, float) else 'int' if node.kind == 'id': ent = symtab.lookup(node.value) if ent is None: errors.append((node.lineno, f'未声明的标识符 {node.value}')) return 'error' return ent['type'] if node.kind == 'binop': lt = check(node.children[0], symtab, errors) rt = check(node.children[1], symtab, errors) if 'error' in (lt, rt): return 'error' if node.value in ('+', '-', '*', '/'): return 'float' if 'float' in (lt, rt) else 'int' # 隐式提升 if node.value in ('<', '>', '==', '!='): return 'bool' if node.kind == 'assign': lt = check(node.children[0], symtab, errors) rt = check(node.children[1], symtab, errors) if lt != 'error' and rt != 'error' and lt != rt and 'float' in (lt, rt): pass # 允许 int 赋给 float，反之报错 elif lt != rt and lt != 'error': errors.append((node.lineno, '赋值类型不匹配')) return lt for c in node.children: # 兜底：未知节点也要递归下去 check(c, symtab, errors) return 'error'

关键是不要把错误当异常抛出去。实验用例里通常有多个错，抛第一个就中断会导致输出和标准答案对不上，正确做法是记录后返回'error'继续遍历。int到float的隐式提升在赋值方向上是允许的，反方向要报错，这个方向别写反。

4.3 四元式生成：S 属性和 L 属性怎么配合

表达式到四元式是自底向上，E -> E1 + T时两个子表达式的值都已经算出来，直接产出(+ , a, b, t)。但布尔表达式的短路求值是自顶向下的，a && b在 a 为假时不该生成 b 的代码，这就必须回填。回填是这门课实验的分水岭，写不出回填基本拿不到中间代码的分。

quads = [] # 每个元素 (op, arg1, arg2, result) def emit(op, a1, a2, res): quads.append((op, a1, a2, res)) return len(quads) - 1 # 返回下标，作为回填位置 def backpatch(lst, target): """把 lst 中所有待填位置的目标改为 target""" for i in lst: op, a1, a2, res = quads[i] quads[i] = (op, a1, a2, target) def gen_bool(node, true_list, false_list): """布尔表达式：把为真/为假时该跳的地方分别挂到两个链表""" if node.kind == 'binop' and node.value in ('<', '>', '==', '!='): idx = emit('j' + node.value, node.children[0].value, node.children[1].value, 0) true_list.append(idx) # 结果字段留空，等回填 false_list.append(emit('jmp', '-', '-', 0)) return if node.kind == 'binop' and node.value == '&&': l_true, l_false = [], [] gen_bool(node.children[0], l_true, l_false) backpatch(l_false, len(quads)) # 左边为假直接跳到整体为假 gen_bool(node.children[1], true_list, false_list) true_list[:0] = l_true return if node.kind == 'binop' and node.value == '||': l_true, l_false = [], [] gen_bool(node.children[0], l_true, l_false) backpatch(l_true, len(quads)) # 左边为真直接跳到整体为真 gen_bool(node.children[1], true_list, false_list) false_list[:0] = l_false return # 普通标识符当条件：生成 jnz false_list.append(emit('jz', node.value, '-', 0)) true_list.append(emit('jmp', '-', '-', 0))

backpatch之所以能工作，是因为它回填的是四元式的result字段，而这个字段在生成时先写 0 占位。&&的处理顺序很重要：先回填左子式为假的跳转目标，然后再生成右子式，否则右子式的四元式会插到中间，目标下标全错。true_list[:0] = l_true用切片赋值是为了原地合并链表，保序，别用+生成新对象再赋值给形参，那改不到调用方的列表。这套写法在if/while语句里复用：if对应gen_bool(cond, t, f)后backpatch(t, then_start)。

5. 常见问题排查：实验代码跑不通的五个现场

5.1 词法与语法侧的三个现场

第一个：浮点数被切成两个 token。现象是3.14输出成3和.14，隐藏用例一带小数就错。原因多半在扫描器里"进入终态就停"，没记录最近接受位置，遇到第二个小数点前的状态直接退出。解决方式是把"上一次进入终态的位置"存下来，扫描到不能再走时才回退到该位置，同时数字状态机里加一个"已见小数点"的标志，第二次遇到点直接进错误状态并报列号，而不是静默截断。

第二个：LL(1) 表出现同格双产生式。现象是填表时M[E][+]被写两次，程序用后写的覆盖前面的，跑出来一堆语法错。原因基本是左递归没消干净，或者a b | a c这种公共左因子没提取，FIRST 集重叠。解决顺序是先消除左递归（引入E'再展开），再提取左公因子，然后重算 FIRST/FOLLOW。如果消完还有冲突，说明文法本身不是 LL(1) 的，别硬凑，换 LR 或者改成递归下降手写判定。

第三个：LR 分析器一开始就 accept。现象是输入第一个符号就报接受，或者栈里还有内容就停。原因通常是规范族初态写成了("S", (...), 0)而没做增广，导致S' -> S.这个接受项目根本不存在；另一种是接受条件写成了"栈顶是开始符号就接受"，漏了必须同时读到结束符$。解决办法是用增广文法S' -> S造初态，接受动作严格限定在ACTION[state]["$"]且该项目为S' -> S.时触发，其余情况一律不 accept。

5.2 语义与中间代码侧的两个现场

第四个：四元式整体错位一条。现象是a = b + c生成了三条四元式但跳转目标全部偏一，运行结果莫名其妙。原因是回填时把"下一条四元式的下标"错写成了"当前下标"，或者emit返回的是列表长度而不是最后一个下标。这类问题没有后悔药，只能在emit里固定返回len(quads) - 1，所有跳转目标统一用len(quads)表示"下一条"，并在生成完毕后打印整张四元式表逐条核对，别靠运行结果反推。

第五个：类型检查通过但运行崩。现象是语义分析无报错，生成的目标代码执行时除零或者数组越界。原因是类型检查只查了类型合法性，没查常量表达式里的除零、数组下标是否常量且越界。补法是给binop的/分支加一条"右操作数为常量 0 就报运行时警告"，数组访问节点单独检查下标常量范围。这类检查不影响评分主流程，但能让你的实现看起来是认真做过的。

提示：这五条里前三条占了实际调试时间的大头，建议在写第一阶段代码时就把对应的自检打印加上，别等集成后再回头找。

6. 优化与验证：让四元式真的跑出结果

6.1 基本块划分与控制流图

优化前必须切基本块，规则只有三条：第一个四元式是入口；任何跳转语句的下一条是入口；任何标号是入口。入口之间就是块。

def split_blocks(quads): leaders = {0} for i, (op, a1, a2, res) in enumerate(quads): if op in ('jmp', 'jz', 'jnz', 'ret') and i + 1 < len(quads): leaders.add(i + 1) if op in ('jlt', 'jgt', 'jeq', 'jne') and i + 1 < len(quads): leaders.add(i + 1) if op == 'label': leaders.add(i) marks = sorted(leaders) blocks = [] for k, start in enumerate(marks): end = marks[k + 1] if k + 1 < len(marks) else len(quads) blocks.append(quads[start:end]) return blocks

leaders用集合去重，排序后再切片，这样块之间天然按顺序。条件跳转有两个后继（目标块和下一块），jmp只有一个，出口块没有，控制流图的边就在这一步建起来。别把label当成可执行语句删掉，块划分和后续回填都依赖它。

6.2 常量折叠与窥孔优化

块内先做常量折叠，把t1 = 2 * 3直接算成t1 = 6；再做公共子表达式消除，用(op, a1, a2)做键查已算过的结果；最后窥孔一遍，删掉x = x + 0、x = x * 1和跳转到下一条的jmp。

def fold_constants(quads): const = {} # 变量 -> 已知常量值 out = [] for op, a1, a2, res in quads: if op in ('+', '-', '*', '/') and a1 in const and a2 in const: v = eval(f'{const[a1]} {op} {const[a2]}') # 仅演示，生产代码别用 eval const[res] = v out.append(('=', v, '-', res)) continue if op == '=' and isinstance(a1, (int, float)): const[res] = a1 elif res in const: del const[res] # 被重新赋值，常量信息失效 out.append((op, a1, a2, res)) return out

const表在遇到对同一变量的新赋值时必须失效，否则会把旧常量带进后续计算，这是折叠最典型的错。eval只用于演示，实际实现要按运算符分支手写，避免把不可信输入送进去。折叠后要重跑一遍基本块划分，因为被删掉的跳转可能让两个块合并。

6.3 用回归用例卡住正确性

优化最怕"优化前对、优化后错"，所以每加一个 pass 都要跑一遍回归。我维护的用例表长这样：

跑法是把优化前后的四元式都打印出来人工比对，再拿同一份输入喂给解释执行器看输出是否一致。我在项目里留了一个--dump-quads开关，任何阶段都能把中间表示吐出来，这个开关救过我很多次。

从那以后我每次改优化 pass，都强制先跑这张回归表再看结果，绝不信"这次改动很小"的直觉。希望帮到你。

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