简介《北邮编译原理课程设计》面向学习编译器构造的高校学生与自学者以 Pascal 到目标代码的完整实现为主线覆盖词法分析、语法分析、语义分析、符号表管理、错误处理、中间代码与代码生成等核心环节。压缩包共 83 个文件约 123KB包含 21 个 h 头文件、19 个 cpp 源文件、8 个 pas 示例、8 个 asm 汇编及 bin、rez、rc、vcxproj 等工程与资源文件便于对照阅读编译流程和工程组织。已有 1195 人学习下载适合用作课程设计参考与编译原理实践补强。读者可从中梳理 Pascal 编译器各阶段的实现思路观察虚拟机、汇编编辑器与测试用例的配合方式并借鉴符号表、错误报告、三地址码及优化相关设计提升系统级编程与问题拆解能力。1. 从字符流到四元式一份编译原理课程设计真正要交付的流水线某高校的编译原理课程设计评分表上写着词法、语法、语义、中间代码四栏但真正决定能不能按时交差的是最后一步源程序喂进去四元式跑出来屏幕上打印出正确结果。我见过太多人 FIRST/FOLLOW 算得飞快一动手就卡在“分析表怎么变成代码”文法写得出来却在递归下降里被左递归撑爆调用栈。这条流水线每一段都有自己的玄学词法的最长匹配、语法的冲突消解、语义的作用域进出、代码生成的跳转回填任何一个环节松动一点前面全白做。下面按我实际交付的顺序从字符流一路拆到解释执行。2. 词法分析把正则压成一张可回退的转移表词法是整条流水线里性价比最高的一段写好了后面全顺写歪了后面天天在调“为什么这个 token 少了半个字符”。课程设计一般不允许直接调 lex/flex 生成要求你手写扫描器并且能讲清楚状态转移所以选型上没什么可犹豫的——手写但要用表驱动而不是一堆 if-else 堆出来否则改一个运算符就要动五处代码。2.1 表驱动和 if-else 堆砌差别在后期改文法的时候常见做法有两种。第一种是纯手写分支遇到数字就一直吃数字遇到字母就一直吃字母遇到运算符就查一张两字符的表。这种写法前期最快二十分钟能出活但一旦语言规范里加了浮点数、十六进制、字符串转义分支就会互相打架最长匹配很容易被破坏。第二种是状态转移表把“当前状态 字符类”映射到“下一个状态”另外维护一张“哪些状态是接受态”的表。扫描时一路走记录最后一次落在接受态的位置走不动了就回退到那个位置切出一个 token。这就是最长匹配maximal munch的标准实现也是教材里 DFA 识别标识符那套东西的工程版本。我一般选第二种理由很实在表是数据改语言只要改表回退逻辑只写一次不会因为新增一个运算符就漏掉而且答辩时能直接把表画出来和 NFA 到 DFA 的子集构造对上。代价是表要设计得克制别为每个字符建一列先做字符类归并。下面这张表是一个类 C 小语言的最小可用版本支持整数、浮点、标识符、单字符运算符和 !开头的双字符运算符。# lexer.py —— 表驱动扫描器最长匹配 单步回退 from dataclasses import dataclass dataclass class Token: kind: str # NUM / ID / OP / KW / EOF value: str line: int col: int def char_class(ch): 把 50 多个字符归并成 6 个类状态表才不会爆炸 if ch.isdigit(): return d if ch.isalpha() or ch _: return a if ch in \t\r\n: return s if ch in !: return m # 可能组成双字符运算符的头 if ch .: return p return o # 其它单字符符号 # 状态 0 为初态ACCEPT 记录走到这个状态时已识别出的 token 类型 TRANS { 0: {d: 1, a: 2, m: 3, s: 0}, 1: {d: 1, p: 4}, # 整数部分遇到小数点转 4 2: {d: 2, a: 2}, # 标识符 3: {m: 33}, # 双字符运算符的第二位 4: {d: 4}, # 小数部分 } ACCEPT {1: NUM, 2: ID, 3: OP, 33: OP, 4: NUM} # 状态 3 单独接受时只有 合法! 和 靠切片后查表兜底 LEGAL_OP {, , !, , , , }表建好之后主循环只做三件事走表、记接受点、回退切词。这里的33是刻意留的双位状态表示“已经多吃了一个字符”回退时不会把它当成单字符运算符。LEGAL_OP是第二道闸门因为这种组合在表里也会走到 33但它不在语言规范里必须在切词之后拦下来否则错误会一路传到语法分析器报出来的位置完全对不上。def scan(src): toks, i, line, col [], 0, 1, 1 n len(src) while i n: ch src[i] if ch in \t\r\n: line, col (line 1, 1) if ch \n else (line, col 1) i 1 continue start, start_col i, col state, last 0, None while i n: nxt TRANS.get(state, {}).get(char_class(src[i])) if nxt is None: break state, i, col nxt, i 1, col 1 if state in ACCEPT: last (i, state) # 只记最后一个接受点 if last is None: raise SyntaxError(f{line}:{col} 无法识别的字符 {ch!r}) i, state last # 回退到最后一个接受位置 col start_col (i - start) # 列号跟着回退量修正 lexeme src[start:i] kind ACCEPT[state] if kind OP and lexeme not in LEGAL_OP: raise SyntaxError(f{line}:{start_col} 非法运算符 {lexeme!r}) toks.append(Token(kind, lexeme, line, start_col)) toks.append(Token(EOF, , line, col)) return toks这段代码里唯一容易被忽略的参数是last。如果只保留“当前状态”一旦走进死胡同就没法退回123abc这种输入会直接吞成一个大 token。改成记录最后一个接受位置之后123会在状态 1 被接受abc从回退点重新开始扫错误定位也能精到列。2.2 关键字、注释和 Token 的位置信息关键字最常见的错误做法是给每个关键字单独建一条分支。正确做法是让它们先按标识符识别再查一张保留字哈希表if、while、int、float这些在kind ID之后一次性替换成KW。好处是标识符状态机只有一条路径加关键字只是往表里加一行扫描性能不受影响。注释则有两种处理思路。一是预处理阶段整段剥离代码量最小但行号会错乱后面语法报错定位全飘二是在状态机里加两个状态/后面看一位是/就吃到行尾是*就吃到*/。我一般用第二种因为课设的报错定位在评分里权重不低行号飘了会被扣。位置信息别只存行号列号也存。原因很现实单行里的a b ;这类错误只报行号等于没报。Token里带上line和col语法分析器报错时直接把两个都打出来调试时间能省一大半。2.3 错误恢复一次报五个错比报一个错有用新手最容易写成“遇到第一个非法字符就sys.exit()”。这在评测用例里很吃亏因为输入文件里往往埋了好几处错误只报一个等于只拿一处分。常见做法是遇到无法识别的字符跳过它记录一条错误继续扫下一个 token最后统一输出错误列表。跳过时要注意别陷入死循环——跳过之后必须让i前进至少一位。另外错误恢复出来的 token 流可以带上一个ERR类型语法分析器遇到ERR时直接同步到下一个分号再继续这样一次运行就能把整份代码的问题全暴露出来省去反复改反复跑的来回。3. 语法分析LL(1) 预测表与 SLR(1) 项目集两套怎么选语法分析是课设里最花时间的一章也是答辩最爱问的一章。很多人卡在这里不是因为不会算 FIRST/FOLLOW而是不知道该用哪套方法写到一半发现文法不支持推倒重来。3.1 先看你的文法长什么样再决定用 LL 还是 LR判断标准其实很粗暴如果语言的表达式文法是分层写好的E → T E、T → F T没有左递归、没有左公因子那 LL(1) 递归下降是最省事的代码短、调试直观、出错位置好定位。如果文法里到处都是左递归E → E T | T或者语句部分有大量公共前缀那 SLR(1) 更合适它能直接吃左递归不用改写文法少了一层“改写之后语义对不上”的风险。课程设计里两种都会被要求我的建议是先写 LL(1) 把流程跑通再补一份 SLR(1) 做对比。LL(1) 的递归下降可以直接在递归函数里顺手建 AST 和做语义动作改起来快SLR(1) 的价值在于让你真正理解“项目集、闭包、GOTO”这套东西答辩时能讲清楚移进-归约冲突从哪来。要注意一个坑把左递归文法改写掉之后运算符的结合性和优先级必须靠文法层次重新体现。E → T E、E → T E | ε这一套写出来是左结合的但如果你把E写成E → T E就变成右结合了1-2-3会算成1-(2-3)。这个错误在测试用例里不一定暴露但一算长表达式就翻车。3.2 FIRST / FOLLOW 到预测分析表一次算对的做法FIRST 集的迭代算法没什么好讲的关键是两个细节空产生式ε要单独处理序列的 FIRST 要能“穿透”——只有当前符号可空时才继续看下一个符号。FOLLOW 集里 90% 的错误都出在同一条规则上对A → αBβ如果β可空那么FOLLOW(A)必须并入FOLLOW(B)。漏了这一步预测表就会出现空洞运行时抛KeyError。# ll1.py —— FIRST / FOLLOW / 预测分析表 EPS ε G { # 已消除左递归、提完左公因子的表达式文法 S: [(id, , E, ;)], E: [(T, E)], E: [(, T, E), (EPS,)], T: [(F, T)], T: [(*, F, T), (EPS,)], F: [(id,), (num,), ((, E, ))], } NT set(G) TERM {s for ps in G.values() for p in ps for s in p if s not in NT and s ! EPS} def first_of(seq, FIRST): 求一个符号串的 FIRST遇到可空符号继续往后看 out set() for sym in seq: if sym EPS: return out | {EPS} out | FIRST[sym] - {EPS} if EPS not in FIRST[sym]: return out return out | {EPS} FIRST {A: set() for A in NT} for A in NT: for p in G[A]: FIRST[A].add(p[0]) # 终结符或 ε 直接入集 while True: # 迭代到不动点 changed False for A in NT: for p in G[A]: add first_of(p, FIRST) - FIRST[A] if add: FIRST[A] | add changed True if not changed: break FOLLOW {A: set() for A in NT} FOLLOW[S].add($) # 起始符的 FOLLOW 放结束符 while True: changed False for A in NT: for p in G[A]: for k, B in enumerate(p): if B not in NT: continue rest p[k 1:] fs first_of(rest, FIRST) add fs - {EPS} if EPS in fs: # β 可空FOLLOW(A) 并入 FOLLOW(B) add | FOLLOW[A] if add - FOLLOW[B]: FOLLOW[B] | add changed True if not changed: break # 填表冲突时立刻断言炸出来别等运行时 M {A: {} for A in NT} for A in NT: for p in G[A]: fs first_of(p, FIRST) for a in fs - {EPS}: assert a not in M[A], fLL(1) 冲突M[{A}][{a}] M[A][a] p if EPS in fs: for b in FOLLOW[A]: assert b not in M[A], fLL(1) 冲突M[{A}][{b}] M[A][b] p这段代码里first_of是复用的核心FIRST表和FOLLOW表都靠它。参数seq传入的是产生式右部的剩余部分空元组时返回{EPS}正好对应“到末尾了整串可空”。断言放在建表阶段而不是分析阶段是为了让冲突在初始化时就暴露——运行时才炸你根本不知道是哪个非终结符出的问题。如果断言真的炸了先检查两件事是不是漏了消除左递归是不是漏了提取左公因子。LL(1) 冲突几乎只有这两个来源剩下的属于文法本身不适合 LL(1)得换 LR。3.3 SLR(1)闭包、GOTO 和冲突检测SLR(1) 的代码量比 LL(1) 大但结构非常规整项目用(产生式编号, 点的位置)表示闭包函数把点后面是非终结符的项目继续展开GOTO 函数先移点再求闭包。核心就是把项目集规范族做出来然后按 FOLLOW 集填归约项。# slr.py —— 项目集规范族 ACTION/GOTOG0 为未改写的左递归文法 prods [(A, p) for A in G0 for p in G0[A]] # 扁平化下标即产生式编号 index {pr: i for i, pr in enumerate(prods)} def closure(items): 点后面是非终结符就把该非终结符的所有产生式加进来 out, stack set(items), list(items) while stack: pi, dot stack.pop() _, rhs prods[pi] if dot len(rhs) and rhs[dot] in G0: for j, (lhs, _) in enumerate(prods): if lhs rhs[dot] and (j, 0) not in out: out.add((j, 0)) stack.append((j, 0)) return frozenset(out) def goto(items, sym): return closure({(pi, dot 1) for pi, dot in items if dot len(prods[pi][1]) and prods[pi][1][dot] sym}) states, queue [closure({(0, 0)})], [0] trans {} while queue: # BFS 展开规范族 s queue.pop() syms {prods[pi][1][dot] for pi, dot in states[s] if dot len(prods[pi][1])} for sym in syms: t goto(states[s], sym) if t not in states: states.append(t) queue.append(len(states) - 1) trans[(s, sym)] states.index(t) ACTION, GOTO {}, {} for s, st in enumerate(states): for pi, dot in st: A, rhs prods[pi] if dot len(rhs): # 移进项 sym rhs[dot] if sym in G0: GOTO[(s, sym)] trans[(s, sym)] else: ACTION[(s, sym)] (shift, trans[(s, sym)]) else: # 归约项 if A S: ACTION[(s, $)] (accept,) else: for a in FOLLOW[A]: key (s, a) assert key not in ACTION, f冲突 {key} ACTION[key] (reduce, pi)trans存的是状态编号用states.index(t)查会退化成线性扫描规模小的时候无所谓真要做大就换成字典按冻结集合查。assert key not in ACTION是移进-归约冲突的探针一旦触发说明文法有二义性或者 FOLLOW 集算错了别急着改代码先回去看文法。3.4 分析过程里的错误恢复不管用哪种方法分析过程都要能报错、能继续。LL(1) 的做法是查表失败时跳到 FOLLOW 集里的同步符号通常选;或}丢弃当前 token 直到能对上SLR(1) 的做法是从状态栈里弹出若干层直到某个状态对当前 token 有合法动作。这两种恢复都会产生“错误级联”一次输入报出十几个错。实用技巧是设一个错误计数报错后强制跳过至少一个 token 再继续避免在同一个位置反复报。答辩时这属于加分项因为能说明你真的跑过坏输入。4. 语义与四元式符号表、类型提升和回填链语法树建出来只是骨架真正让程序“能算”的是语义分析加中间代码。这一段代码量不大但逻辑最绕尤其是布尔表达式的回填几乎每个人都要在这上面栽一次。4.1 符号表作用域链比哈希更重要符号表有两种做法全局一张表加作用域标记或者每个作用域一张表、用父指针串成链。课程设计规模小我推荐后者因为进出作用域就是push和pop配一个栈结构代码短且不容易漏。class Scope: def __init__(self, parentNone): self.parent parent self.syms {} # name - (type, offset) def declare(self, name, typ): if name in self.syms: # 只查本层允许内层遮蔽外层 raise NameError(f重复定义{name}) self.syms[name] (typ, len(self.syms)) def lookup(self, name): s self while s: # 沿作用域链一路往上找 if name in s.syms: return s.syms[name] s s.parent raise NameError(f未声明{name})declare只查本层是刻意的{ int a; { float a; } }在大多数语言里合法内层遮蔽外层。如果连外层一起查就会误报重复定义这是新手最常写错的一行。4.2 类型检查把提升规则做成表别写成 if 嵌套表达式的类型检查本质是查一张二维表。整数和浮点混合运算往浮点提升布尔不能参与算术赋值两边要兼容。写成if left int and right float这种嵌套三五个类型还行一加数组和指针就崩了。左操作数右操作数结果类型说明intintint整数运算除法截断intfloatfloat右操作数提升floatintfloat左操作数提升floatfloatfloat直接运算bool任意报错布尔不参与算术任意void报错函数调用返回值检查表驱动的好处是错误信息可以统一生成cannot apply to (int, void)比一堆分支里各写一句要一致得多。除法那一格要单独标注整数除零和浮点除零的语义不同前者在解释执行阶段应该直接抛错后者按语言规范处理。4.3 四元式生成与布尔表达式的回填四元式就是(op, arg1, arg2, result)。算术和赋值直接发射麻烦的是跳转——生成if和while的时候条件成立要跳到哪儿这个目标地址在生成那一刻还不知道得等后面的代码发完再补上这就是回填。quads [] def emit(op, aNone, bNone, rNone): quads.append([op, a, b, r]) return len(quads) - 1 # 返回四元式下标作为回填句柄 def backpatch(lst, target): 把 lst 里所有待填的四元式目标地址改成 target for q in lst: quads[q][3] targetemit返回下标这一点很关键回填的时候你手里拿的不是地址是一串下标等目标确定了一次性刷进去。backpatch的参数target通常是len(quads)也就是“下一条要生成的指令”这样跳转就落在正确位置。布尔表达式要维护真假两个出口链。a b这种简单条件真出口就是当前四元式的下一条假出口挂到链上and和or则是把左半边的假出口或真出口接到右半边的开头。这里的顺序一旦写反条件会永远只走一半现象是if (a 0 b 0)只判断了a而且不报错——属于最难查的那类问题。def gen_cond(node): 返回 (truelist, falselist)两个都是待回填的四元式下标列表 if node.op and: lt, lf gen_cond(node.left) rt, rf gen_cond(node.right) backpatch(lf, len(quads)) # 左边为真才继续判右边 return lt rt, rf if node.op or: lt, lf gen_cond(node.left) rt, rf gen_cond(node.right) backpatch(lt, len(quads)) # 左边为假才继续判右边 return rt, lf rf # 关系运算生成条件跳转真假各挂一条链 t emit(j, node.left.name, node.right.name) f emit(jmp) return [t], [f]backpatch(lf, len(quads))这一句就是短路求值的落点左边为真时直接跳到右边的第一条指令为假时走falselist一路跳到整个条件之外。and和or的差别只在于把哪条链接过去但接错了整个控制流就反了。4.4 用一个两百行的虚拟机把四元式跑起来四元式生成完最后一步是解释执行。写一个while循环配pc遇到跳转就改pc遇到运算就从环境里取值、算完写回。def execute(quads, outprint): env, pc, step {}, 0, 0 while pc len(quads): step 1 if step 1_000_000: # 死循环保护课设必备 raise RuntimeError(执行步数超限疑似死循环) op, a, b, r quads[pc] pc 1 if op label: continue elif op jmp: pc r elif op jf: # 条件为假才跳 pc r if not env.get(a, a) else pc elif op print: out(env.get(a, a)) elif op : env[r] env.get(a, a) elif op in (, -, *, /): x, y env.get(a, a), env.get(b, b) if op / and y 0: raise ZeroDivisionError(整数除零) env[r] {: x y, -: x - y, *: x * y, /: int(x / y)}[op] else: raise ValueError(f未知指令 {op})env.get(a, a)这个写法是为了同时支持变量名和字面量变量在环境里能取到值字面量取不到就原样返回。步数保护看着多余但真跑起来的时候回填错了会变成无限跳转没有这个上限程序就卡死在那儿你连日志都看不到。5. 避坑与排查五个在凌晨两点才暴露的细节这一节里的每一条都是血泪经验不是理论推演。共同点是程序不报错或者报错位置完全误导必须靠打印中间结果才能定位。5.1 词法与语法交界的三个坑坑一被切成和。现象是if (a b)解析成a ( b)语法分析报“意外的 ”。原因是扫描器没做最长匹配遇到就立刻返回根本没看下一位。解决方式是记录最后一个接受位置走不动了再回退切词同时在切完词后校验LEGAL_OP非法组合当场报错而不是往后传。坑二递归下降直接栈溢出。现象是程序刚跑就段错误栈回溯里同一层函数刷了几百遍。原因是文法里保留了左递归E → E T递归下降第一件事就是调自己永远进不去。解决分两步先用算法消除左递归再检查改写后有没有破坏结合性实在不想改就换 SLR(1)它天然支持左递归。坑三预测表里出现空洞运行时KeyError。现象是大部分输入能过只有含空语句或空参数的用例挂。原因基本锁定在 FOLLOW 集A → αBβ且β可空时忘了把FOLLOW(A)并进FOLLOW(B)。定位方法是把FIRST、FOLLOW两张表打出来和手算结果逐行比对别靠猜。5.2 语义与代码生成的两个坑坑四作用域只push不pop内层变量泄漏到外层。现象是同一个变量名在不同块里第二次定义时报“重复定义”或者块外能访问到块内的局部变量。原因很直白解析到{时建了新作用域解析到}时忘了恢复父作用域。解决办法是把作用域进出绑定在块语句的入口和出口用try/finally保证异常路径也能pop。坑五短路求值的真假链接反条件只判一半。现象最隐蔽if (a 0 b 0)在a 0时行为正确a 0时却不检查b而且没有任何报错。原因是gen_cond里and分支回填的是lt而不是lf。排查手段是把四元式列表整段打印出来人工对一遍跳转目标看假出口到底落在哪。这类问题没有捷径就是要把中间结果拉出来看。6. 用黄金用例把流水线钉死三层验证与一个后悔药习惯代码写完之后光靠“跑通一个样例”是不够的因为很多错误只在特定输入组合下才出现。我一般准备一组固定的黄金用例分三层验证每层看的东西不一样。层次观察对象失败时的典型症状词法token 流类型、值、行列号运算符被拆开、关键字没识别、列号飘语法AST 结构或分析栈轨迹结合性反了、语句漏解析、报错位置错语义符号表快照、类型错误信息重复定义误报、作用域泄漏中间代码四元式列表跳转目标错、临时变量复用冲突执行程序标准输出条件只走一半、整数除法结果不对第一层是 token 快照。把a 1 2.5;这种输入扫一遍把 token 列表按kind:value:line:col打出来和手写的期望值做 diff。这一步能挡住绝大多数词法问题而且成本极低。第二层是四元式快照。挑三个典型程序一个只有赋值和算术一个带if-else嵌套一个带while循环。把四元式列表完整打印人工核对跳转目标。如果嫌麻烦就写一个小的diff脚本把当前输出和一份确认过的基线文件比对改代码之后先跑它。第三层是执行结果比对。准备一组带预期输出的用例比如阶乘、斐波那契、冒泡排序、带短路求值的条件判断跑完直接比 stdout。这一步最像“真测试”但它的定位能力最弱——结果错了你只知道错了不知道错在哪。所以顺序不能反先过前两层再过这一层。下面这个脚本把三层串起来用法就是python run_tests.py cases/任何一个用例失败都会打印出卡在哪一层。# run_tests.py —— 三层验证的胶水代码 import sys, pathlib def check_case(src_path): src src_path.read_text(encodingutf-8) toks scan(src) # 第一层词法 ast parse(toks) # 第二层语法 语义 quads gen(ast) # 第三层中间代码 got [] execute(quads, outgot.append) # 执行把输出收集起来 expect src_path.with_suffix(.out).read_text(encodingutf-8).split() assert got expect, f{src_path.name}: 期望 {expect}实际 {got} ok 0 for p in sorted(pathlib.Path(sys.argv[1]).glob(*.src)): try: check_case(p) ok 1 except Exception as e: print(f[FAIL] {e}) print(f{ok} 个用例通过)这段脚本本身没什么技术含量价值在于把“改完代码跑一下”这件事的成本压到一条命令。课设最后两天你会反复改回填和类型检查没有这套东西每次改完都靠手动输入样例一天下来能浪费几个小时。最后一个习惯算是我自己的后悔药每改一处扫描器或回填逻辑先把上面这组用例全跑一遍再继续往下写哪怕只改了一行常量。编译前端各阶段耦合太紧词法里一个字符类的改动可能到你执行阶段才以“结果差一”的形式暴露出来。从那以后我每次动状态表或者跳转链都强制走一遍三层验证宁可贵三十秒也不要半夜对着四元式列表数下标。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/23 18:02:12 · 阅读 1.2k 编译原理课程设计：从词法分析到四元式解释执行
简介《北邮编译原理课程设计》面向学习编译器构造的高校学生与自学者以 Pascal 到目标代码的完整实现为主线覆盖词法分析、语法分析、语义分析、符号表管理、错误处理、中间代码与代码生成等核心环节。压缩包共 83 个文件约 123KB包含 21 个 h 头文件、19 个 cpp 源文件、8 个 pas 示例、8 个 asm 汇编及 bin、rez、rc、vcxproj 等工程与资源文件便于对照阅读编译流程和工程组织。已有 1195 人学习下载适合用作课程设计参考与编译原理实践补强。读者可从中梳理 Pascal 编译器各阶段的实现思路观察虚拟机、汇编编辑器与测试用例的配合方式并借鉴符号表、错误报告、三地址码及优化相关设计提升系统级编程与问题拆解能力。1. 从字符流到四元式一份编译原理课程设计真正要交付的流水线某高校的编译原理课程设计评分表上写着词法、语法、语义、中间代码四栏但真正决定能不能按时交差的是最后一步源程序喂进去四元式跑出来屏幕上打印出正确结果。我见过太多人 FIRST/FOLLOW 算得飞快一动手就卡在“分析表怎么变成代码”文法写得出来却在递归下降里被左递归撑爆调用栈。这条流水线每一段都有自己的玄学词法的最长匹配、语法的冲突消解、语义的作用域进出、代码生成的跳转回填任何一个环节松动一点前面全白做。下面按我实际交付的顺序从字符流一路拆到解释执行。2. 词法分析把正则压成一张可回退的转移表词法是整条流水线里性价比最高的一段写好了后面全顺写歪了后面天天在调“为什么这个 token 少了半个字符”。课程设计一般不允许直接调 lex/flex 生成要求你手写扫描器并且能讲清楚状态转移所以选型上没什么可犹豫的——手写但要用表驱动而不是一堆 if-else 堆出来否则改一个运算符就要动五处代码。2.1 表驱动和 if-else 堆砌差别在后期改文法的时候常见做法有两种。第一种是纯手写分支遇到数字就一直吃数字遇到字母就一直吃字母遇到运算符就查一张两字符的表。这种写法前期最快二十分钟能出活但一旦语言规范里加了浮点数、十六进制、字符串转义分支就会互相打架最长匹配很容易被破坏。第二种是状态转移表把“当前状态 字符类”映射到“下一个状态”另外维护一张“哪些状态是接受态”的表。扫描时一路走记录最后一次落在接受态的位置走不动了就回退到那个位置切出一个 token。这就是最长匹配maximal munch的标准实现也是教材里 DFA 识别标识符那套东西的工程版本。我一般选第二种理由很实在表是数据改语言只要改表回退逻辑只写一次不会因为新增一个运算符就漏掉而且答辩时能直接把表画出来和 NFA 到 DFA 的子集构造对上。代价是表要设计得克制别为每个字符建一列先做字符类归并。下面这张表是一个类 C 小语言的最小可用版本支持整数、浮点、标识符、单字符运算符和 !开头的双字符运算符。# lexer.py —— 表驱动扫描器最长匹配 单步回退 from dataclasses import dataclass dataclass class Token: kind: str # NUM / ID / OP / KW / EOF value: str line: int col: int def char_class(ch): 把 50 多个字符归并成 6 个类状态表才不会爆炸 if ch.isdigit(): return d if ch.isalpha() or ch _: return a if ch in \t\r\n: return s if ch in !: return m # 可能组成双字符运算符的头 if ch .: return p return o # 其它单字符符号 # 状态 0 为初态ACCEPT 记录走到这个状态时已识别出的 token 类型 TRANS { 0: {d: 1, a: 2, m: 3, s: 0}, 1: {d: 1, p: 4}, # 整数部分遇到小数点转 4 2: {d: 2, a: 2}, # 标识符 3: {m: 33}, # 双字符运算符的第二位 4: {d: 4}, # 小数部分 } ACCEPT {1: NUM, 2: ID, 3: OP, 33: OP, 4: NUM} # 状态 3 单独接受时只有 合法! 和 靠切片后查表兜底 LEGAL_OP {, , !, , , , }表建好之后主循环只做三件事走表、记接受点、回退切词。这里的33是刻意留的双位状态表示“已经多吃了一个字符”回退时不会把它当成单字符运算符。LEGAL_OP是第二道闸门因为这种组合在表里也会走到 33但它不在语言规范里必须在切词之后拦下来否则错误会一路传到语法分析器报出来的位置完全对不上。def scan(src): toks, i, line, col [], 0, 1, 1 n len(src) while i n: ch src[i] if ch in \t\r\n: line, col (line 1, 1) if ch \n else (line, col 1) i 1 continue start, start_col i, col state, last 0, None while i n: nxt TRANS.get(state, {}).get(char_class(src[i])) if nxt is None: break state, i, col nxt, i 1, col 1 if state in ACCEPT: last (i, state) # 只记最后一个接受点 if last is None: raise SyntaxError(f{line}:{col} 无法识别的字符 {ch!r}) i, state last # 回退到最后一个接受位置 col start_col (i - start) # 列号跟着回退量修正 lexeme src[start:i] kind ACCEPT[state] if kind OP and lexeme not in LEGAL_OP: raise SyntaxError(f{line}:{start_col} 非法运算符 {lexeme!r}) toks.append(Token(kind, lexeme, line, start_col)) toks.append(Token(EOF, , line, col)) return toks这段代码里唯一容易被忽略的参数是last。如果只保留“当前状态”一旦走进死胡同就没法退回123abc这种输入会直接吞成一个大 token。改成记录最后一个接受位置之后123会在状态 1 被接受abc从回退点重新开始扫错误定位也能精到列。2.2 关键字、注释和 Token 的位置信息关键字最常见的错误做法是给每个关键字单独建一条分支。正确做法是让它们先按标识符识别再查一张保留字哈希表if、while、int、float这些在kind ID之后一次性替换成KW。好处是标识符状态机只有一条路径加关键字只是往表里加一行扫描性能不受影响。注释则有两种处理思路。一是预处理阶段整段剥离代码量最小但行号会错乱后面语法报错定位全飘二是在状态机里加两个状态/后面看一位是/就吃到行尾是*就吃到*/。我一般用第二种因为课设的报错定位在评分里权重不低行号飘了会被扣。位置信息别只存行号列号也存。原因很现实单行里的a b ;这类错误只报行号等于没报。Token里带上line和col语法分析器报错时直接把两个都打出来调试时间能省一大半。2.3 错误恢复一次报五个错比报一个错有用新手最容易写成“遇到第一个非法字符就sys.exit()”。这在评测用例里很吃亏因为输入文件里往往埋了好几处错误只报一个等于只拿一处分。常见做法是遇到无法识别的字符跳过它记录一条错误继续扫下一个 token最后统一输出错误列表。跳过时要注意别陷入死循环——跳过之后必须让i前进至少一位。另外错误恢复出来的 token 流可以带上一个ERR类型语法分析器遇到ERR时直接同步到下一个分号再继续这样一次运行就能把整份代码的问题全暴露出来省去反复改反复跑的来回。3. 语法分析LL(1) 预测表与 SLR(1) 项目集两套怎么选语法分析是课设里最花时间的一章也是答辩最爱问的一章。很多人卡在这里不是因为不会算 FIRST/FOLLOW而是不知道该用哪套方法写到一半发现文法不支持推倒重来。3.1 先看你的文法长什么样再决定用 LL 还是 LR判断标准其实很粗暴如果语言的表达式文法是分层写好的E → T E、T → F T没有左递归、没有左公因子那 LL(1) 递归下降是最省事的代码短、调试直观、出错位置好定位。如果文法里到处都是左递归E → E T | T或者语句部分有大量公共前缀那 SLR(1) 更合适它能直接吃左递归不用改写文法少了一层“改写之后语义对不上”的风险。课程设计里两种都会被要求我的建议是先写 LL(1) 把流程跑通再补一份 SLR(1) 做对比。LL(1) 的递归下降可以直接在递归函数里顺手建 AST 和做语义动作改起来快SLR(1) 的价值在于让你真正理解“项目集、闭包、GOTO”这套东西答辩时能讲清楚移进-归约冲突从哪来。要注意一个坑把左递归文法改写掉之后运算符的结合性和优先级必须靠文法层次重新体现。E → T E、E → T E | ε这一套写出来是左结合的但如果你把E写成E → T E就变成右结合了1-2-3会算成1-(2-3)。这个错误在测试用例里不一定暴露但一算长表达式就翻车。3.2 FIRST / FOLLOW 到预测分析表一次算对的做法FIRST 集的迭代算法没什么好讲的关键是两个细节空产生式ε要单独处理序列的 FIRST 要能“穿透”——只有当前符号可空时才继续看下一个符号。FOLLOW 集里 90% 的错误都出在同一条规则上对A → αBβ如果β可空那么FOLLOW(A)必须并入FOLLOW(B)。漏了这一步预测表就会出现空洞运行时抛KeyError。# ll1.py —— FIRST / FOLLOW / 预测分析表 EPS ε G { # 已消除左递归、提完左公因子的表达式文法 S: [(id, , E, ;)], E: [(T, E)], E: [(, T, E), (EPS,)], T: [(F, T)], T: [(*, F, T), (EPS,)], F: [(id,), (num,), ((, E, ))], } NT set(G) TERM {s for ps in G.values() for p in ps for s in p if s not in NT and s ! EPS} def first_of(seq, FIRST): 求一个符号串的 FIRST遇到可空符号继续往后看 out set() for sym in seq: if sym EPS: return out | {EPS} out | FIRST[sym] - {EPS} if EPS not in FIRST[sym]: return out return out | {EPS} FIRST {A: set() for A in NT} for A in NT: for p in G[A]: FIRST[A].add(p[0]) # 终结符或 ε 直接入集 while True: # 迭代到不动点 changed False for A in NT: for p in G[A]: add first_of(p, FIRST) - FIRST[A] if add: FIRST[A] | add changed True if not changed: break FOLLOW {A: set() for A in NT} FOLLOW[S].add($) # 起始符的 FOLLOW 放结束符 while True: changed False for A in NT: for p in G[A]: for k, B in enumerate(p): if B not in NT: continue rest p[k 1:] fs first_of(rest, FIRST) add fs - {EPS} if EPS in fs: # β 可空FOLLOW(A) 并入 FOLLOW(B) add | FOLLOW[A] if add - FOLLOW[B]: FOLLOW[B] | add changed True if not changed: break # 填表冲突时立刻断言炸出来别等运行时 M {A: {} for A in NT} for A in NT: for p in G[A]: fs first_of(p, FIRST) for a in fs - {EPS}: assert a not in M[A], fLL(1) 冲突M[{A}][{a}] M[A][a] p if EPS in fs: for b in FOLLOW[A]: assert b not in M[A], fLL(1) 冲突M[{A}][{b}] M[A][b] p这段代码里first_of是复用的核心FIRST表和FOLLOW表都靠它。参数seq传入的是产生式右部的剩余部分空元组时返回{EPS}正好对应“到末尾了整串可空”。断言放在建表阶段而不是分析阶段是为了让冲突在初始化时就暴露——运行时才炸你根本不知道是哪个非终结符出的问题。如果断言真的炸了先检查两件事是不是漏了消除左递归是不是漏了提取左公因子。LL(1) 冲突几乎只有这两个来源剩下的属于文法本身不适合 LL(1)得换 LR。3.3 SLR(1)闭包、GOTO 和冲突检测SLR(1) 的代码量比 LL(1) 大但结构非常规整项目用(产生式编号, 点的位置)表示闭包函数把点后面是非终结符的项目继续展开GOTO 函数先移点再求闭包。核心就是把项目集规范族做出来然后按 FOLLOW 集填归约项。# slr.py —— 项目集规范族 ACTION/GOTOG0 为未改写的左递归文法 prods [(A, p) for A in G0 for p in G0[A]] # 扁平化下标即产生式编号 index {pr: i for i, pr in enumerate(prods)} def closure(items): 点后面是非终结符就把该非终结符的所有产生式加进来 out, stack set(items), list(items) while stack: pi, dot stack.pop() _, rhs prods[pi] if dot len(rhs) and rhs[dot] in G0: for j, (lhs, _) in enumerate(prods): if lhs rhs[dot] and (j, 0) not in out: out.add((j, 0)) stack.append((j, 0)) return frozenset(out) def goto(items, sym): return closure({(pi, dot 1) for pi, dot in items if dot len(prods[pi][1]) and prods[pi][1][dot] sym}) states, queue [closure({(0, 0)})], [0] trans {} while queue: # BFS 展开规范族 s queue.pop() syms {prods[pi][1][dot] for pi, dot in states[s] if dot len(prods[pi][1])} for sym in syms: t goto(states[s], sym) if t not in states: states.append(t) queue.append(len(states) - 1) trans[(s, sym)] states.index(t) ACTION, GOTO {}, {} for s, st in enumerate(states): for pi, dot in st: A, rhs prods[pi] if dot len(rhs): # 移进项 sym rhs[dot] if sym in G0: GOTO[(s, sym)] trans[(s, sym)] else: ACTION[(s, sym)] (shift, trans[(s, sym)]) else: # 归约项 if A S: ACTION[(s, $)] (accept,) else: for a in FOLLOW[A]: key (s, a) assert key not in ACTION, f冲突 {key} ACTION[key] (reduce, pi)trans存的是状态编号用states.index(t)查会退化成线性扫描规模小的时候无所谓真要做大就换成字典按冻结集合查。assert key not in ACTION是移进-归约冲突的探针一旦触发说明文法有二义性或者 FOLLOW 集算错了别急着改代码先回去看文法。3.4 分析过程里的错误恢复不管用哪种方法分析过程都要能报错、能继续。LL(1) 的做法是查表失败时跳到 FOLLOW 集里的同步符号通常选;或}丢弃当前 token 直到能对上SLR(1) 的做法是从状态栈里弹出若干层直到某个状态对当前 token 有合法动作。这两种恢复都会产生“错误级联”一次输入报出十几个错。实用技巧是设一个错误计数报错后强制跳过至少一个 token 再继续避免在同一个位置反复报。答辩时这属于加分项因为能说明你真的跑过坏输入。4. 语义与四元式符号表、类型提升和回填链语法树建出来只是骨架真正让程序“能算”的是语义分析加中间代码。这一段代码量不大但逻辑最绕尤其是布尔表达式的回填几乎每个人都要在这上面栽一次。4.1 符号表作用域链比哈希更重要符号表有两种做法全局一张表加作用域标记或者每个作用域一张表、用父指针串成链。课程设计规模小我推荐后者因为进出作用域就是push和pop配一个栈结构代码短且不容易漏。class Scope: def __init__(self, parentNone): self.parent parent self.syms {} # name - (type, offset) def declare(self, name, typ): if name in self.syms: # 只查本层允许内层遮蔽外层 raise NameError(f重复定义{name}) self.syms[name] (typ, len(self.syms)) def lookup(self, name): s self while s: # 沿作用域链一路往上找 if name in s.syms: return s.syms[name] s s.parent raise NameError(f未声明{name})declare只查本层是刻意的{ int a; { float a; } }在大多数语言里合法内层遮蔽外层。如果连外层一起查就会误报重复定义这是新手最常写错的一行。4.2 类型检查把提升规则做成表别写成 if 嵌套表达式的类型检查本质是查一张二维表。整数和浮点混合运算往浮点提升布尔不能参与算术赋值两边要兼容。写成if left int and right float这种嵌套三五个类型还行一加数组和指针就崩了。左操作数右操作数结果类型说明intintint整数运算除法截断intfloatfloat右操作数提升floatintfloat左操作数提升floatfloatfloat直接运算bool任意报错布尔不参与算术任意void报错函数调用返回值检查表驱动的好处是错误信息可以统一生成cannot apply to (int, void)比一堆分支里各写一句要一致得多。除法那一格要单独标注整数除零和浮点除零的语义不同前者在解释执行阶段应该直接抛错后者按语言规范处理。4.3 四元式生成与布尔表达式的回填四元式就是(op, arg1, arg2, result)。算术和赋值直接发射麻烦的是跳转——生成if和while的时候条件成立要跳到哪儿这个目标地址在生成那一刻还不知道得等后面的代码发完再补上这就是回填。quads [] def emit(op, aNone, bNone, rNone): quads.append([op, a, b, r]) return len(quads) - 1 # 返回四元式下标作为回填句柄 def backpatch(lst, target): 把 lst 里所有待填的四元式目标地址改成 target for q in lst: quads[q][3] targetemit返回下标这一点很关键回填的时候你手里拿的不是地址是一串下标等目标确定了一次性刷进去。backpatch的参数target通常是len(quads)也就是“下一条要生成的指令”这样跳转就落在正确位置。布尔表达式要维护真假两个出口链。a b这种简单条件真出口就是当前四元式的下一条假出口挂到链上and和or则是把左半边的假出口或真出口接到右半边的开头。这里的顺序一旦写反条件会永远只走一半现象是if (a 0 b 0)只判断了a而且不报错——属于最难查的那类问题。def gen_cond(node): 返回 (truelist, falselist)两个都是待回填的四元式下标列表 if node.op and: lt, lf gen_cond(node.left) rt, rf gen_cond(node.right) backpatch(lf, len(quads)) # 左边为真才继续判右边 return lt rt, rf if node.op or: lt, lf gen_cond(node.left) rt, rf gen_cond(node.right) backpatch(lt, len(quads)) # 左边为假才继续判右边 return rt, lf rf # 关系运算生成条件跳转真假各挂一条链 t emit(j, node.left.name, node.right.name) f emit(jmp) return [t], [f]backpatch(lf, len(quads))这一句就是短路求值的落点左边为真时直接跳到右边的第一条指令为假时走falselist一路跳到整个条件之外。and和or的差别只在于把哪条链接过去但接错了整个控制流就反了。4.4 用一个两百行的虚拟机把四元式跑起来四元式生成完最后一步是解释执行。写一个while循环配pc遇到跳转就改pc遇到运算就从环境里取值、算完写回。def execute(quads, outprint): env, pc, step {}, 0, 0 while pc len(quads): step 1 if step 1_000_000: # 死循环保护课设必备 raise RuntimeError(执行步数超限疑似死循环) op, a, b, r quads[pc] pc 1 if op label: continue elif op jmp: pc r elif op jf: # 条件为假才跳 pc r if not env.get(a, a) else pc elif op print: out(env.get(a, a)) elif op : env[r] env.get(a, a) elif op in (, -, *, /): x, y env.get(a, a), env.get(b, b) if op / and y 0: raise ZeroDivisionError(整数除零) env[r] {: x y, -: x - y, *: x * y, /: int(x / y)}[op] else: raise ValueError(f未知指令 {op})env.get(a, a)这个写法是为了同时支持变量名和字面量变量在环境里能取到值字面量取不到就原样返回。步数保护看着多余但真跑起来的时候回填错了会变成无限跳转没有这个上限程序就卡死在那儿你连日志都看不到。5. 避坑与排查五个在凌晨两点才暴露的细节这一节里的每一条都是血泪经验不是理论推演。共同点是程序不报错或者报错位置完全误导必须靠打印中间结果才能定位。5.1 词法与语法交界的三个坑坑一被切成和。现象是if (a b)解析成a ( b)语法分析报“意外的 ”。原因是扫描器没做最长匹配遇到就立刻返回根本没看下一位。解决方式是记录最后一个接受位置走不动了再回退切词同时在切完词后校验LEGAL_OP非法组合当场报错而不是往后传。坑二递归下降直接栈溢出。现象是程序刚跑就段错误栈回溯里同一层函数刷了几百遍。原因是文法里保留了左递归E → E T递归下降第一件事就是调自己永远进不去。解决分两步先用算法消除左递归再检查改写后有没有破坏结合性实在不想改就换 SLR(1)它天然支持左递归。坑三预测表里出现空洞运行时KeyError。现象是大部分输入能过只有含空语句或空参数的用例挂。原因基本锁定在 FOLLOW 集A → αBβ且β可空时忘了把FOLLOW(A)并进FOLLOW(B)。定位方法是把FIRST、FOLLOW两张表打出来和手算结果逐行比对别靠猜。5.2 语义与代码生成的两个坑坑四作用域只push不pop内层变量泄漏到外层。现象是同一个变量名在不同块里第二次定义时报“重复定义”或者块外能访问到块内的局部变量。原因很直白解析到{时建了新作用域解析到}时忘了恢复父作用域。解决办法是把作用域进出绑定在块语句的入口和出口用try/finally保证异常路径也能pop。坑五短路求值的真假链接反条件只判一半。现象最隐蔽if (a 0 b 0)在a 0时行为正确a 0时却不检查b而且没有任何报错。原因是gen_cond里and分支回填的是lt而不是lf。排查手段是把四元式列表整段打印出来人工对一遍跳转目标看假出口到底落在哪。这类问题没有捷径就是要把中间结果拉出来看。6. 用黄金用例把流水线钉死三层验证与一个后悔药习惯代码写完之后光靠“跑通一个样例”是不够的因为很多错误只在特定输入组合下才出现。我一般准备一组固定的黄金用例分三层验证每层看的东西不一样。层次观察对象失败时的典型症状词法token 流类型、值、行列号运算符被拆开、关键字没识别、列号飘语法AST 结构或分析栈轨迹结合性反了、语句漏解析、报错位置错语义符号表快照、类型错误信息重复定义误报、作用域泄漏中间代码四元式列表跳转目标错、临时变量复用冲突执行程序标准输出条件只走一半、整数除法结果不对第一层是 token 快照。把a 1 2.5;这种输入扫一遍把 token 列表按kind:value:line:col打出来和手写的期望值做 diff。这一步能挡住绝大多数词法问题而且成本极低。第二层是四元式快照。挑三个典型程序一个只有赋值和算术一个带if-else嵌套一个带while循环。把四元式列表完整打印人工核对跳转目标。如果嫌麻烦就写一个小的diff脚本把当前输出和一份确认过的基线文件比对改代码之后先跑它。第三层是执行结果比对。准备一组带预期输出的用例比如阶乘、斐波那契、冒泡排序、带短路求值的条件判断跑完直接比 stdout。这一步最像“真测试”但它的定位能力最弱——结果错了你只知道错了不知道错在哪。所以顺序不能反先过前两层再过这一层。下面这个脚本把三层串起来用法就是python run_tests.py cases/任何一个用例失败都会打印出卡在哪一层。# run_tests.py —— 三层验证的胶水代码 import sys, pathlib def check_case(src_path): src src_path.read_text(encodingutf-8) toks scan(src) # 第一层词法 ast parse(toks) # 第二层语法 语义 quads gen(ast) # 第三层中间代码 got [] execute(quads, outgot.append) # 执行把输出收集起来 expect src_path.with_suffix(.out).read_text(encodingutf-8).split() assert got expect, f{src_path.name}: 期望 {expect}实际 {got} ok 0 for p in sorted(pathlib.Path(sys.argv[1]).glob(*.src)): try: check_case(p) ok 1 except Exception as e: print(f[FAIL] {e}) print(f{ok} 个用例通过)这段脚本本身没什么技术含量价值在于把“改完代码跑一下”这件事的成本压到一条命令。课设最后两天你会反复改回填和类型检查没有这套东西每次改完都靠手动输入样例一天下来能浪费几个小时。最后一个习惯算是我自己的后悔药每改一处扫描器或回填逻辑先把上面这组用例全跑一遍再继续往下写哪怕只改了一行常量。编译前端各阶段耦合太紧词法里一个字符类的改动可能到你执行阶段才以“结果差一”的形式暴露出来。从那以后我每次动状态表或者跳转链都强制走一遍三层验证宁可贵三十秒也不要半夜对着四元式列表数下标。希望帮到你。本文还有配套的精品资源点击获取