简介：《北邮编译原理课程设计》配套工程包面向计算机专业学生与编译器入门者，以Pascal语言为示例，串联词法分析、语法分析、语义分析、代码生成，以及符号表管理与错误处理等完整流程，适合课程设计复现与编译原理实践练习。压缩包共83个文件、约123KB，其中21个h头文件与19个cpp源文件构成编辑器与虚拟机主体，另有8个pas与8个asm样例程序、8个bin可执行文件及rez、rc等资源脚本，兼顾解析、汇编与界面模块。已有1195人学习下载。读者可从中获得一套可运行的类Pascal编译与汇编编辑环境：文档视图框架、文本编辑控件、虚拟机实现与多组测试用例相互配合，便于对照抽象语法树构造、三地址码生成与优化思路，也能借样例程序验证递归、循环、分支等语句的编译结果，是理解编译器各阶段衔接与工程组织的实用参考。

1. 编译原理课程设计真正卡人的地方：不是算法，是从“能跑”到“能验收”

编译原理课程设计这门课，真正让人卡住的往往不是 LR 分析表怎么构造，而是“书上算法看懂了”到“验收时能在十分钟内跑完一组用例、并说清每个阶段输出了什么”中间那段距离。常见做法是交一套完整前端加一个简单后端：词法、语法、语义、中间代码、目标代码五段流水，任何一段的输出格式对不上，后面就全盘返工。这篇笔记按实际动手顺序拆开讲：源语言子集怎么划、词法状态机怎么写、符号表在哪儿进出栈、四元式怎么生成、寄存器分配做到什么程度够用，以及验收现场最常见的几类翻车怎么定位。适合已经学过一遍理论、手上还没有一份能跑骨架的人。

2. 词法与语法分析的落地选择：手写递归下降还是让工具生成分析表

动手之前必须先做一个决定：语法分析用工具自动生成，还是手写递归下降。这个选择决定了后面三天的调试体验。我的血泪经验是，课程设计这种规模（文法十几条产生式、源语言几百行能跑完），手写递归下降的总体耗时明显低于调 LALR 冲突，因为冲突排查基本是黑匣子——工具只告诉你“这里有 shift/reduce 冲突”，剩下的靠猜。

2.1 源语言子集怎么划：先定文法再动键盘

很多人上手就建工程、写 main 函数，写到一半发现if语句的end和while的end撞了，回头改文法，前面的词法、AST 节点、语义动作全部重来。正确的顺序是先在纸上把 EBNF 定死，并且保证它满足两个条件：能被 LL(1) 判定（手写递归下降的前提），以及每条语句有明确的开头关键字。

一条可用的、类 PL/0 的过程式语言子集长这样：

program → block '.' block → decls stmts decls → { 'var' ident { ',' ident } ';' } { 'proc' ident '(' [ ident { ',' ident } ] ')' ';' block ';' } stmts → stmt { ';' stmt } stmt → ident ':=' expr | 'if' cond 'then' stmts [ 'else' stmts ] 'end' | 'while' cond 'do' stmts 'end' | 'read' ident | 'write' expr | 'call' ident [ '(' expr { ',' expr } ')' ] | 'begin' stmts 'end' cond → expr relop expr expr → term { ('+' | '-') term } term → factor { ('*' | '/') factor } factor → ident | number | '(' expr ')' | '-' factor

这份文法的关键在于每个语句都以独立的关键字或可区分的记号开头：if、while、read、write、call、begin，赋值语句以标识符开头而过程调用以call开头，所以两条路径不会打架。stmts内部用;分隔，end结束，天然避免了悬挂 else 的歧义——else只可能出现在then分支之后，看到else就归约到最近的if。

提示：把产生式控制在 15 条以内。每多一条，词法、语法、语义、代码生成四处都要跟着改一遍，后面做寄存器分配的时间会被挤压得所剩无几。

为什么不用左递归写法（expr → expr '+' term）？因为递归下降遇到左递归会直接栈溢出。要么改写成右递归或循环形式（上面的{ ... }就是循环），要么改用 LR 生成器。我一般会选前者，理由很朴素：循环写法写出来就是while语句，一眼能看出在哪退出，调试时打断点也好打。

源语言还要提前确定类型系统。课程设计通常只要求整型和布尔，但如果你打算做数组或者过程参数传递，现在就要写进文法，不能等语义分析写到一半再补。补文法意味着 AST 节点要加、符号表条目要加字段、四元式要多一种形式，三处一起改，比重写还累。

2.2 词法分析器的最长匹配与状态机写法

词法分析的目标是把字符流切成记号流，同时记录每个记号的行号和列号——这一点很多实现会漏，等到语法报错时只输出“第 3 个记号附近有错”，验收时被追问位置就没法回答了。列号是必须的。

实现上有两条路：逐字符状态机，或者一条合并正则。前者适合教学演示，后者出活快、可读性好，我一般用后者。核心是把所有词法规则拼成一条带命名组的正则，用finditer一次性扫描，正则的贪婪匹配天然保证了最长匹配（:=不会被切成:和=）。

import re KEYWORDS = {'var', 'proc', 'if', 'then', 'else', 'end', 'while', 'do', 'read', 'write', 'call', 'begin'} # 顺序很重要：:= 必须排在单字符 : 之前，<= 必须排在 < 之前 TOKEN_SPEC = [ ('NUMBER', r'\d+'), ('IDENT', r'[A-Za-z_]\w*'), ('ASSIGN', r':='), ('RELOP', r'<=|>=|<>|<|>|='), ('OP', r'[+\-*/]'), ('LPAREN', r'\('), ('RPAREN', r'\)'), ('COMMA', r','), ('SEMI', r';'), ('DOT', r'\.'), ] # 合并成一条 master regex，每组命名，groupdict 里非 None 的那组即命中类型 MASTER = re.compile('|'.join(f'(?P<{n}>{p})' for n, p in TOKEN_SPEC)) class Token: __slots__ = ('kind', 'text', 'line', 'col') def __init__(self, kind, text, line, col): self.kind, self.text, self.line, self.col = kind, text, line, col def __repr__(self): return f'{self.kind}({self.text})@{self.line}:{self.col}' def tokenize(src): tokens, line, line_start = [], 1, 0 pos = 0 while pos < len(src): ch = src[pos] if ch in ' \t\r\n': # 跳过空白，维护行号 if ch == '\n': line += 1 line_start = pos + 1 pos += 1 continue if src.startswith('//', pos): # 行注释直接吞到行尾 pos = src.find('\n', pos) pos = len(src) if pos == -1 else pos continue m = MASTER.match(src, pos) if not m: raise SyntaxError(f'非法字符 {src[pos]!r} 于 {line} 行 {pos - line_start + 1} 列') kind = m.lastgroup text = m.group() if kind == 'IDENT' and text in KEYWORDS: kind = text.upper() # 关键字与标识符分开判定 tokens.append(Token(kind, text, line, pos - line_start + 1)) pos = m.end() tokens.append(Token('EOF', '', line, pos - line_start + 1)) return tokens

逻辑说明：外层while负责推进位置，空白和注释在正则匹配之前单独处理，因为它们不该产生记号；MASTER.match(src, pos)从当前位置开始匹配，m.lastgroup告诉我们命中的是哪个命名组；标识符命中后再查KEYWORDS集合，是关键字就改类型，这样词法层只维护一张表，加关键字不用改组名。

参数说明：TOKEN_SPEC的顺序不能随便调，Python 正则的交替是“先匹配先赢”，:=放在:前面才能保证赋值号不被拆开。line_start是为了算列号，每次换行时更新为行首偏移。Token.__slots__不是必须的，但记号数量大的时候能省不少内存——一万个记号看不出差别，几十万行输入时能感觉到。

判空和位置信息是这一段的产出质量分水岭。验收时随便给一行非法字符，能不能报出准确行列，直接体现实现是“跑通”还是“做完”。

2.3 递归下降骨架与 FIRST 集冲突的现场处理

递归下降的骨架极其规整：每个非终结符对应一个方法，方法内部按产生式的 FIRST 集选分支。写的时候有三件事要提前想清楚：向前看几个记号、错误怎么抛、错误之后怎么继续。

class ParseError(Exception): def __init__(self, msg, tok): super().__init__(f'{msg}，位置 {tok.line}:{tok.col}，当前记号 {tok.kind}') self.tok = tok class Parser: def __init__(self, tokens): self.toks, self.i = tokens, 0 def peek(self, k=0): idx = min(self.i + k, len(self.toks) - 1) return self.toks[idx] def accept(self, kind): if self.peek().kind == kind: self.i += 1 return True return False def expect(self, kind): tok = self.peek() if tok.kind != kind: raise ParseError(f'期望 {kind}', tok) self.i += 1 return tok # block → decls stmts def parse_block(self): decls = self.parse_decls() stmts = self.parse_stmts() return ('block', decls, stmts) # decls → { var ... } { proc ... } def parse_decls(self): vars_, procs = [], [] while self.accept('VAR'): # FIRST = {VAR} names = [self.expect('IDENT').text] while self.accept('COMMA'): names.append(self.expect('IDENT').text) self.expect('SEMI') vars_.extend(names) while self.accept('PROC'): # FIRST = {PROC} name = self.expect('IDENT').text params = [] if self.accept('LPAREN'): if self.peek().kind != 'RPAREN': params.append(self.expect('IDENT').text) while self.accept('COMMA'): params.append(self.expect('IDENT').text) self.expect('RPAREN') self.expect('SEMI') body = self.parse_block() self.expect('SEMI') procs.append((name, params, body)) return ('decls', vars_, procs) # stmt → ident ':=' expr | if | while | read | write | call | begin def parse_stmt(self): tok = self.peek() if tok.kind == 'IDENT': name = self.expect('IDENT').text self.expect('ASSIGN') return ('assign', name, self.parse_expr()) if tok.kind == 'IF': ... raise ParseError('无法识别的语句起始', tok)

逻辑说明：peek()是唯一读记号的地方，accept()是“可选匹配”，expect()是“必须匹配”，这套三件套能把绝大多数分支写得线性可读。parse_decls里两个while分别对应var声明块和proc声明块，因为文法规定声明必须在语句之前，所以不需要额外判断顺序，两条循环跑完就是全部声明。

参数说明：peek(k)里的k是向前看偏移量，默认 0；把索引min到最后一个记号（EOF）上，可以避免越界，代价是错误位置可能落在 EOF 上——这正是我们想要的，报错时报在文件末尾最合理。parse_stmt里只对标识符起始的分支做展开，其余关键字分支按同样模式写，每个分支第一句必须是expect掉那个关键字，否则错误恢复会卡在原地。

真正会卡住的是 FIRST 集冲突。典型场景是stmt里既有ident ':=' expr又有过程调用不带call关键字的写法——两个分支都以IDENT开头，必须看第二个记号才能决定。处理办法按代价从低到高排列：第一，改文法让每个分支有唯一首关键字（上面给call加关键字就是这么干的）；第二，提取左公因子，把公共前缀提前消费掉，再按后续记号分叉；第三，加大向前看个数，peek(1)判一次即可。

不要用回溯实现递归下降。回溯能让任何文法跑起来，但一旦出错，你连“错在哪一层”都定位不到，调试时间会翻几倍。宁可改文法，也不要用回溯。

错误恢复是这一段的加分点，做法很朴素：在parse_stmts这一层捕获ParseError，记录错误、跳过记号直到遇到同步集合里的记号（SEMI、END、ELSE、EOF），然后继续解析下一条语句。这样一次编译能报出多个错误，而不是第一个错就整体退出，验收时演示效果差别很大。

3. 符号表与语义分析：把类型检查挂在哪些产生式上才不会返工

语义分析是整套流水里最容易写成一团乱麻的部分，因为它横跨声明、引用、类型、作用域四件事，任何一件处理得不干净，都会在代码生成阶段以“莫名其妙的结果错误”形式爆出来。

3.1 分层符号表的实现与作用域进出时机

符号表最朴素也最够用的实现是作用域栈：一个列表，每个元素是一层dict，进块压栈，出块弹栈，查名从栈顶往下找。

class Symbol: def __init__(self, name, kind, type_=None, level=0, offset=0, params=None): self.name, self.kind, self.type = name, kind, type_ self.level, self.offset = level, offset self.params = params or [] class ScopeStack: def __init__(self): self.stack = [{}] # 第 0 层是全局作用域 self.level = 0 def enter(self): self.stack.append({}) self.level += 1 def leave(self): self.stack.pop() self.level -= 1 def declare(self, sym): cur = self.stack[-1] if sym.name in cur: # 同层重名必须报错 raise SemanticError(f'重复声明 {sym.name}') sym.level = self.level cur[sym.name] = sym def lookup(self, name): for scope in reversed(self.stack): # 由内向外，内层遮蔽外层 if name in scope: return scope[name] return None

逻辑说明：declare只允许在当前层查重，不能跨层查——内层同名变量遮蔽外层是合法语义。lookup从栈顶向下找，第一次命中就返回，这就是静态作用域链。leave直接弹栈，不用逐个删除，比“进块记列表、出块回滚”的写法简洁得多。

参数说明：level用于后面代码生成时区分局部变量和全局变量，offset是相对所在过程活动记录的偏移，语义分析阶段只分配、不真正使用，等到代码生成时按类型大小累加即可。params存形参列表，调用时做参数个数和类型核对。

作用域进出时机要精确对齐block：进入block前压栈，把形参声明进去，再处理var声明，然后处理语句，最后弹栈。有一个坑：过程名本身要声明在外层作用域，因为同层的其他过程可能互相调用，如果声明在内层，递归调用自己的时候就查不到。

3.2 语义动作的插入位置：自顶向下与自底向上的差别

递归下降是自顶向下的，语义动作的插入位置和课本上讲的 yacc 风格自底向上不一样，容易照抄出错。核心原则只有一条：声明必须在被使用之前完成，而语句是边解析边检查的，所以声明阶段要单独走一趟。

具体做法是在parse_block里分两段：先调parse_decls把本层所有变量和过程名登记进符号表（这一趟不检查过程体），再调parse_stmts处理语句。这样写，过程体里调用一个在后面才定义的同层过程也能通过——因为所有过程名在进入语句之前就已经在表里了。

参数说明：表格里的“时机”决定了错误报在哪一行。如果赋值语句的类型检查拖到整个 block 结束再做，报错行号就丢了，只能报“某个语句有类型错误”，验收时基本没法演示。所以类型检查必须紧贴表达式解析的返回点做，parse_expr返回时带上静态类型，调用方立刻比对。

注意：过程名占位这一步不能省。先 declare 一个只有名字和 kind 的空符号，等参数列表解析完再回填params和返回类型，这样过程体内递归调用自己时lookup能命中，只是此时params还没填——所以递归调用的参数检查要延后到过程体解析完之后再统一跑一遍。

3.3 四元式生成与临时变量管理

中间代码用四元式足够：(op, arg1, arg2, result)。生成时机就在语义检查通过之后，同一个函数里顺手emit出去。

class QuadGen: def __init__(self): self.quads = [] self.tmp = 0 def new_tmp(self): self.tmp += 1 return f't{self.tmp}' def emit(self, op, a1='', a2='', res=''): self.quads.append((op, a1, a2, res)) return len(self.quads) - 1 # 返回下标，供回填使用 def gen_expr(self, node): kind = node[0] if kind == 'num': return str(node[1]) if kind == 'var': return node[1] if kind == 'binop': left = self.gen_expr(node[2]) right = self.gen_expr(node[3]) t = self.new_tmp() self.emit(node[1], left, right, t) return t raise NotImplementedError(kind) def gen_if(gen, cond_node, then_stmts, else_stmts=None): c = gen.gen_expr(cond_node) jf = gen.emit('JMPF', c, '', '') # 条件为假时跳到 else 或 end then_stmts() if else_stmts: jend = gen.emit('JMP', '', '', '') gen.quads[jf] = ('JMPF', c, '', len(gen.quads)) else_stmts() gen.quads[jend] = ('JMP', '', '', len(gen.quads)) else: gen.quads[jf] = ('JMPF', c, '', len(gen.quads))

逻辑说明：emit返回下标而不是立即填目标地址，是因为生成跳转指令那一刻还不知道要跳到哪里——if的条件为假时目标地址要等then分支生成完才知道。这就是回填（backpatch）：先留空，回头按下标改写四元式里的第四个字段。

参数说明：new_tmp生成的t1、t2是虚寄存器，后面寄存器分配时把它们和用户变量一视同仁地做活跃变量分析。gen_expr返回的是“存放这个表达式结果的位置名”，可能是常量、变量名或临时变量，调用方不需要关心是哪一种，这样递归生成才写得干净。JMPF的语义是“条件为假就跳”，所以then分支结束要再补一条无条件JMP跳过else。

临时变量的数量会直接影响后端寄存器压力。一个能省的地方是：a + 0、a * 1这类表达式可以在生成前折叠掉，虽然课程设计不要求优化，但常量折叠能显著减少四元式条数，验收时看着也清爽。

4. 从中间代码到目标代码：基本块、活跃变量与寄存器分配怎么落到能跑

后端是最能拉开差距的部分。绝大多数实现会停在“把四元式逐条翻译成汇编”这一步，能跑，但等于没用寄存器；再往前一步做活跃变量分析和寄存器分配，才算把课程设计的后半段真正做完。

4.1 基本块划分与控制流图构建

基本块划分的规则很简单：第一条四元式是入口；任何跳转指令的目标是入口；任何跳转指令的下一条是入口。按入口切段就是基本块。

def build_blocks(quads): leaders = {0} for i, (op, a1, a2, res) in enumerate(quads): if op in ('JMP', 'JMPF'): leaders.add(int(res)) # 跳转目标是入口 if i + 1 < len(quads): leaders.add(i + 1) # 跳转的下一条是入口 leaders = sorted(leaders) blocks, index_of = [], {} for bi, start in enumerate(leaders): end = leaders[bi + 1] if bi + 1 < len(leaders) else len(quads) index_of[start] = bi blocks.append({'start': start, 'end': end, 'succ': []}) for bi, b in enumerate(blocks): last = quads[b['end'] - 1] if last[0] == 'JMP': b['succ'].append(index_of[int(last[3])]) elif last[0] == 'JMPF': b['succ'].append(index_of[int(last[3])]) if b['end'] < len(quads): b['succ'].append(index_of[b['end']]) else: if b['end'] < len(quads): b['succ'].append(index_of[b['end']]) return blocks

逻辑说明：先扫一遍收集所有入口下标，排序后相邻入口之间就是一个块。第二遍扫每个块的最后一条指令，按指令类型连边：JMP只连目标，JMPF连目标和顺序下一条，普通指令只连顺序下一条。

参数说明：res字段在这里既存结果也存跳转目标地址，是四元式常见的复用方式，读的时候要按op判断含义。index_of把四元式下标映射到块编号，否则连边时还得二分查找。块内的顺序下一条如果是最后一个块的末尾，要判b['end'] < len(quads)，不判就会越界。

控制流图只是中间结构，不要急着打印。等活跃变量分析做完再一起输出，能省一轮调试。

4.2 活跃变量分析与冲突图

活跃变量分析是反向数据流：一个变量在某个点活跃，意思是“从这点到它下次被定值之前，会被用到”。迭代到不动点。

def liveness(blocks, quads): for b in blocks: use, defs = set(), set() for i in range(b['end'] - 1, b['start'] - 1, -1): op, a1, a2, res = quads[i] for src in (a1, a2): if src and not src.isdigit() and src not in defs: use.add(src) if res and op not in ('JMP', 'JMPF') and not res.isdigit(): defs.add(res) use.discard(res) # 先定值后使用，不算 use b['use'], b['def'] = use, defs b['live_in'], b['live_out'] = set(), set() changed = True while changed: changed = False for b in reversed(blocks): out = set() for s in b['succ']: out |= blocks[s]['live_in'] inn = b['use'] | (out - b['def']) if out != b['live_out'] or inn != b['live_in']: b['live_out'], b['live_in'] = out, inn changed = True return blocks

逻辑说明：第一步逐块反向扫，算出块内的use（先使用后定值）和def（块内定值）。第二步反复迭代live_in = use ∪ (live_out - def)，直到没有任何块变化。反向遍历块列表能加快收敛，但不是必须的。

参数说明：a1、a2里可能出现常量，用isdigit()粗筛掉——严格说负数常量要用正则判，但课程设计的常数一般非负，够用。JMP、JMPF的res是跳转目标不是定值，必须排除，否则会把一个地址当成活变量。

拿到每个块的live_out之后，逐条指令反推，就能在每条指令的位置上得到活跃变量集合。两个变量在同一条指令处同时活跃，就在冲突图里连一条边，后面按图着色分配寄存器。图着色如果时间不够，退一步做线性扫描分配也能交差，效果差一些但代码量只有三分之一。

4.3 指令选择与目标机模拟器验证

指令选择的目标不是“生成最优代码”，而是“生成能被我自己的模拟器跑对的代码”。所以第一步是先写模拟器，用二十行代码定义寄存器、内存和指令语义。

class VM: def __init__(self, nreg=8, memsize=1024): self.reg = [0] * nreg self.mem = [0] * memsize self.pc = 0 self.ops = { 'LOAD': lambda r, a: setattr(self, 'reg', self._set(r, self.mem[a])), 'STORE': lambda r, a: self.mem.__setitem__(a, self.reg[r]), 'ADD': lambda r, s: self._set(r, self.reg[r] + self.reg[s]), 'SUB': lambda r, s: self._set(r, self.reg[r] - self.reg[s]), 'MUL': lambda r, s: self._set(r, self.reg[r] * self.reg[s]), 'JMP': lambda a: setattr(self, 'pc', a - 1), 'JZ': lambda r, a: setattr(self, 'pc', a - 1) if self.reg[r] == 0 else None, 'HALT': lambda: setattr(self, 'halted', True), }

逻辑说明：每个lambda实现一条指令，pc自增逻辑放在主循环里，跳转类指令把pc设成目标减一，主循环再统一加一。JZ用条件表达式，条件不成立时不动pc，自然顺序执行。

参数说明：nreg是可用寄存器数，设成 8 是因为课程设计的表达式深度一般不超过 8，超了就溢出到内存。memsize只是防止越界，真正要分配多少取决于变量数。模拟器的指令集要和后端生成的指令一一对应，多一条少一条都会在跑用例时炸。

验证顺序不能反：先手写一段目标代码在模拟器上跑通，确认指令语义对了，再让编译器生成代码去跑。顺序反了，出了问题你分不清是编译器错了还是模拟器错了，这就是典型的黑匣子排查困境。

5. 验收前的排查清单：五类翻车现象与定位方法

下面这五条都是我自己踩过或者帮别人定位过的，按出现频率排序。每条的排查路径都比现象本身重要。

5.1 合法语句报语法错，报错位置还往前漂

现象：一段完全合法的if ... then ... end被报“期望 SEMI”，而且报错行号比真正的语句结束行还靠前。

原因：错误恢复时跳过了记号但没有更新当前位置，或者peek的min钳位让索引停在最后一个记号上反复触发同一条报错。另一种常见原因是stmts的循环条件写成了while not accept('END')，遇到嵌套if里的end提前退出。

解决：错误恢复后必须显式推进索引至少一位，防止原地打转；stmts的终止判断改成“当前记号属于 FOLLOW 集（END、ELSE、EOF、SEMI）就退出”，不要用单个关键字判。定位时把每个expect前后各打一行peek()，看索引是不是只增不减。

5.2 语义检查全绿但运行结果对不上

现象：所有类型检查通过，生成的代码也能跑完，但write输出的数字差一或差一个固定值。

原因：多半是四元式里操作数顺序反了。a - b生成成SUB b, a这种，减法、除法、比较运算都会错，加法乘法因为交换律看不出来，所以只有部分用例翻车，特别迷惑。

解决：在gen_expr里对非交换运算符单独加断言，或者在四元式打印时把每个binop的左右操作数和源码顺序并排打出来对比。另外检查回填时JMPF的目标是不是落到了then分支的第一条而不是最后一条。

5.3 加了寄存器分配之后结果变成随机数

现象：不做寄存器分配、全部走内存时结果正确；一开分配，同一份代码多次运行结果不一样。

原因：活跃变量分析的迭代没有跑完，或者live_out用了上一轮的值却没触发changed；更隐蔽的是把跳转目标当成了变量，冲突图里多出几条边，导致两个真正冲突的变量被分到同一个寄存器。

解决：先关掉分配、把冲突图打印成文本邻接表，人工核对三五个变量的冲突关系是否合理；再打开分配、把每条指令分配前后的寄存器映射打出来，找一个结果出错的用例，从后往前追第一个值不对的位置。迭代收敛的判据写成“本轮所有块的live_in和live_out都没变”，别只判其中一个。

5.4 自己的用例全过，验收临时加一条就崩

现象：准备的十组用例全绿，现场加一个嵌套过程调用或者空语句块，直接抛异常。

原因：用例覆盖的是“正常路径”，边界没测：空stmts、只有声明的块、参数个数为 0 的调用、表达式里连续括号、负数常量、被注释掉的整行。这些在文法里都合法，但代码里往往有[0]取首元素或者pop()空栈的操作。

解决：写一个最小用例集，每个文法产生式至少两条——一条最简、一条最繁。跑之前先过一遍所有list[0]和stack[-1]，凡是可能为空的都加判空。这个习惯比事后 debug 省的时间多得多。

5.5 大输入下超时或栈溢出

现象：几十行的测试程序秒出结果，几千行的输入要么等很久，要么直接RecursionError。

原因：递归下降的调用深度和表达式嵌套深度成正比，长表达式链会爆栈；另一个原因是符号表lookup每次都从头扫，声明多的时候是平方复杂度。

解决：把表达式解析里的左结合改写成循环（term { ('+'|'-') term }本来就是循环，别写成递归），能把深度从 O(n) 降到 O(1)；符号表加一层dict缓存最近的查询结果，或者干脆每层作用域用一个dict链，别用列表遍历。真要跑大输入，sys.setrecursionlimit只是缓解，不是解决。

6. 让验收一眼看出水平的三个增量：错误恢复、中间代码可视化与差分测试

前面五章做完，功能上是完整的，但验收时十个人交上来的东西看起来差不多。真正能拉开差距的是三件小事，成本都不高，但能让评审在两分钟内判断出这套实现是“照着课本拼的”还是“自己想过”。

第一件是错误恢复。多数实现遇到第一个语法错误就exit(1)，一次只能报一个错。改成在语句层捕获、跳到同步集合后继续，一次编译能报出全部错误，并且每条都带行列号。这件事的代码量大概三十行，但演示效果是质变——你可以现场故意写三个错，看它一次性全报出来。要注意的是错误恢复后不要重复报同一个位置的错，加一个“上次报错位置”的记录，相同位置直接跳过。

第二件是中间代码与 CFG 的可视化。不用画图，纯文本就够：四元式按基本块分组打印，每块标出live_in和live_out，块之间用->连边。评审想看优化效果时，你能指着某一行说“这个变量在这里就死了，所以寄存器可以复用”，比空口讲原理有说服力得多。输出格式建议固定成每行一条，方便和测试用例的期望输出做比对。

第三件是差分测试。写一个二十行的解释器，直接对 AST 求值，然后拿“解释器结果”和“编译后模拟器结果”对比。随机生成或者手写一批表达式程序，两边跑，不一致就说明前面某一环有问题。这套东西的价值在于：它把“我觉得应该对”变成了“两条独立路径互相验证”，定位问题时能快速二分——解释器对而模拟器错，问题在后端；两边都错，问题在前端。

我自己的习惯是：动手写第一行代码之前，先把“最小用例集”和“期望输出格式”定下来，后面每加一个功能就往里塞一条用例。这个习惯是被坑出来的——有一次改文法改到凌晨，功能全对，但输出格式和之前不一致，前面攒的用例全部失效，只能一条条重看。后来就学乖了，格式先冻结，用例跟着功能长，改文法的时候跑一遍就知道有没有伤到别的地方。希望帮到你。

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