编译原理实验：语法分析程序设计与实现全攻略

简介：这份资源是面向计算机专业学生的编译原理实验配套文档，聚焦语法分析程序的设计与实现，适合正在完成实验二、需要参考完整实现思路与代码的学习者。文档以算术表达式简化子集为分析对象，系统梳理了实验目的、BNF文法定义、LL(1)文法改写、预测分析表构造及C++源程序实现，并给出分析栈、剩余串输出与RIGHT/ERROR判定逻辑，可帮助读者掌握算符优先、递归下降、LL(1)、SLR(1)、LR(1)等常用语法分析方法的落地过程。压缩包内共1个doc文件，约127KB，内容涵盖实验步骤、问题分析、源程序与结论，结构完整，便于对照实验要求逐步复现。目前已有143人学习，适合需要快速搭建语法分析框架、理解预测分析表驱动流程及调试错例判别的读者参考。

1. 语法分析程序设计与实现：从词法输出到语法树的最后一公里

很多同学做完词法分析就以为编译器实验已经过半，结果一进语法分析就卡住：Token 流明明打印得整整齐齐，可一写递归下降就栈溢出，一上 LR(1) 就撞见冲突，最后交上去的程序只能跑通老师给的三个样例。语法分析程序设计与实现这件事，本质是把线性的 Token 序列还原成带层级的语法树，同时把「这个句子合不合法」判断清楚。它适合已经写完词法分析、准备做实验二的人，也适合想补编译原理落地能力的人。这一章先把边界划清楚：输入是 Token 流，输出是语法树或错误位置，中间那套推导机制才是你要写的东西。

2. 先选路线：递归下降、LL(1) 还是 LR(1)

动手之前最忌讳直接开写。语法分析有三条主流路线，选错了后面全是返工。我一般会先看文法长什么样，再决定用哪套。

2.1 三条路线的适用边界

递归下降适合文法层次清晰、每个非终结符能对应一个函数的场景，比如表达式、语句、声明这种嵌套结构。它的优点是代码即文法，调试直观；缺点是遇到左递归必须改写，回溯写不好会指数爆炸。

LL(1) 是递归下降的表格化版本，靠预测分析表驱动。它要求文法无左递归、无公共左因子，且 FIRST/FOLLOW 集不能有冲突。适合教学实验里那种规整的小型文法。

LR(1) 系列（含 SLR、LALR）自底向上，能处理绝大多数程序设计语言的文法，包括左递归。代价是状态机构造复杂，冲突排查需要看项目集。

2.2 用 FIRST/FOLLOW 判断你的文法能不能上 LL(1)

选 LL(1) 之前，先算 FIRST 和 FOLLOW。规则不复杂：FIRST(α) 是 α 能推导出的首终结符集合，FOLLOW(A) 是 A 后面可能紧跟的终结符集合。对每个产生式 A → α，如果 α 能推出空串，就把 FOLLOW(A) 并进预测集。

# 计算 FIRST 集的简化实现 def first_of(symbol, grammar, first_sets, visited=None): if visited is None: visited = set() # 终结符的 FIRST 就是它自己 if symbol not in grammar: return {symbol} if symbol in visited: # 防止左递归导致死循环 return set() visited.add(symbol) result = set() for production in grammar[symbol]: if not production: # 空产生式 result.add('ε') continue for sym in production: sym_first = first_of(sym, grammar, first_sets, visited) result |= (sym_first - {'ε'}) if 'ε' not in sym_first: break else: result.add('ε') return result

这段代码的关键在visited集合，它挡住左递归带来的无限递归。grammar用字典表示，键是非终结符，值是产生式右部的列表，每个右部是符号列表。空产生式用空列表表示，返回ε。实际跑的时候，如果某个非终结符的 FIRST 集里同时出现两个候选产生式的首符号，就说明有冲突，LL(1) 走不通，得改文法或者换 LR。

2.3 递归下降的最小骨架

如果文法不复杂，我通常先写递归下降把流程跑通，再考虑要不要换。下面是一个表达式解析的骨架，支持加减和乘除的优先级。

class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): # 返回当前 Token，越界返回 None return self.tokens[self.pos] if self.pos < len(self.tokens) else None def match(self, kind): # 匹配并消费一个指定类型的 Token tok = self.peek() if tok and tok.kind == kind: self.pos += 1 return tok raise SyntaxError(f"期望 {kind}，实际 {tok}") def parse_expr(self): # expr -> term (('+'|'-') term)* node = self.parse_term() while self.peek() and self.peek().kind in ('+', '-'): op = self.match(self.peek().kind) right = self.parse_term() node = ('binop', op.kind, node, right) return node def parse_term(self): # term -> factor (('*'|'/') factor)* node = self.parse_factor() while self.peek() and self.peek().kind in ('*', '/'): op = self.match(self.peek().kind) right = self.parse_factor() node = ('binop', op.kind, node, right) return node def parse_factor(self): # factor -> NUMBER | '(' expr ')' tok = self.peek() if tok and tok.kind == 'NUMBER': self.match('NUMBER') return ('num', tok.value) if tok and tok.kind == '(': self.match('(') node = self.parse_expr() self.match(')') return node raise SyntaxError(f"意外的 Token: {tok}")

peek不消费，match消费并校验，这是递归下降的两个基本动作。parse_expr处理最低优先级，parse_term处理高一级，parse_factor处理括号和数字。每层函数对应文法里的一层优先级，这样写出来的解析器天然支持优先级，不需要额外算符优先表。参数上唯一要注意的是pos的推进必须和match绑定，手动改pos是后面出错的主要来源。

3. 把 LR(1) 项目集构造跑通：状态机不是黑匣子

如果实验要求 LR(1) 或者你想拿高分，就得把项目集规范族构造出来。很多人卡在这里是因为把它当黑匣子，其实它就是「闭包 + 转移」两个操作的循环。

3.1 项目、闭包与 GOTO 的代码化

一个 LR(1) 项目是[产生式, 点的位置, 展望符]。闭包操作是把点后面是非终结符的项目展开，展望符用 FIRST(βa) 算。GOTO 是把点右移一位后求闭包。

def closure(items, grammar, first_sets): # items: set of (lhs, rhs, dot, lookahead) 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: # 点后是非终结符 B = rhs[dot] beta = rhs[dot+1:] # 计算 FIRST(beta + la) lookaheads = first_of_sequence(beta + [la], grammar, first_sets) for prod in grammar[B]: new_item = (B, tuple(prod), 0, la if 'ε' in lookaheads else None) # 实际实现里对每个展望符分别生成项目 for a in lookaheads - {'ε'}: item = (B, tuple(prod), 0, a) if item not in result: result.add(item) changed = True return result

first_of_sequence是 FIRST 集在符号序列上的扩展，遇到能推空的符号就继续往后看。dot是点的位置，la是展望符。闭包要循环到不再新增项目为止，这个changed标志不能省，否则嵌套展开会漏项目。实际写的时候，展望符的传播是最容易出错的地方，建议先用一个小文法手算一遍对照。

3.2 构造状态转移表并识别冲突

有了闭包和 GOTO，就可以从初始项目[S' → S, 0, $]出发，广度优先构造所有状态。

def build_canonical(grammar, first_sets, start_symbol): start_item = (start_symbol + "'", (start_symbol,), 0, '$') I0 = closure({start_item}, grammar, first_sets) states = [I0] transitions = {} queue = [0] while queue: i = queue.pop(0) symbols = set() for lhs, rhs, dot, la in states[i]: if dot < len(rhs): symbols.add(rhs[dot]) for X in symbols: # GOTO(I, X)：移点后求闭包 moved = set() for lhs, rhs, dot, la in states[i]: if dot < len(rhs) and rhs[dot] == X: moved.add((lhs, rhs, dot+1, la)) target = closure(moved, grammar, first_sets) if target not in states: states.append(target) queue.append(len(states) - 1) transitions[(i, X)] = states.index(target) return states, transitions

states是项目集列表，transitions是(状态号, 符号) -> 状态号的映射。构造完之后，对每个状态检查：如果同时存在移进项目和归约项目，就是移进-归约冲突；如果存在两个不同归约项目，就是归约-归约冲突。冲突不一定代表文法错，可能是 LR(1) 够用但 LALR 合并后冲突，这时候要么保留 LR(1) 的细粒度，要么改文法。

3.3 用分析表驱动一次完整归约

分析表分 ACTION 和 GOTO 两部分。ACTION 对终结符，GOTO 对非终结符。驱动循环维护状态栈和符号栈。

def parse(tokens, action, goto_table, productions): state_stack = [0] symbol_stack = ['$'] pos = 0 while True: state = state_stack[-1] tok = tokens[pos] if pos < len(tokens) else ('$', '$') act = action.get((state, tok[0])) if act is None: raise SyntaxError(f"状态 {state} 遇到 {tok} 无动作") if act[0] == 'shift': state_stack.append(act[1]) symbol_stack.append(tok[0]) pos += 1 elif act[0] == 'reduce': lhs, rhs = productions[act[1]] for _ in range(len(rhs)): state_stack.pop() symbol_stack.pop() symbol_stack.append(lhs) state_stack.append(goto_table[(state_stack[-1], lhs)]) elif act[0] == 'accept': return symbol_stack[-1]

shift压状态和符号，reduce按产生式长度弹栈再压左部，accept结束。这里最容易翻车的是归约后 GOTO 用的状态是弹栈之后的新栈顶，不是归约前的状态。参数上productions要按编号索引，ACTION 表里的归约动作存的是产生式编号。

4. 避坑与排查：语法分析实验里最常见的五类翻车

这一章按「现象 → 原因 → 解决」写，都是我在带实验和自测时反复见到的。

4.1 递归下降栈溢出

现象：解析稍长的表达式时程序崩溃，报递归深度超限。原因：文法里有左递归，比如expr -> expr '+' term，递归下降会无限展开。解决：改写文法消除左递归，把expr -> expr '+' term | term改成expr -> term ('+' term)*，代码里用循环代替递归。

4.2 FIRST/FOLLOW 冲突导致 LL(1) 表有多重入口

现象：预测分析表某个格子填了两个产生式，程序不知道该选哪个。原因：两个候选产生式的 FIRST 集相交，或者其中一个能推空且 FOLLOW 相交。解决：提取左公因子，或者把文法改写成 LL(1) 可接受的形式；如果改不动，换 LR 路线。

4.3 LR 项目集里展望符算错

现象：分析表里出现本该没有的归约动作，或者该归约的地方报错。原因：闭包计算时展望符没有正确用 FIRST(βa) 传播，常见的是漏了 β 能推空的情况。解决：单独写一个first_of_sequence函数并用手算小文法验证，确认 β 推空时展望符要并进来。

4.4 移进-归约冲突直接放弃

现象：一看到冲突就认为文法不能用。原因：没区分冲突类型，也没看冲突发生在哪个状态。解决：先定位冲突状态，看是算符优先级问题还是文法二义性。表达式文法可以用优先级和结合性声明解决，不必大改文法。

4.5 错误恢复缺失导致一个错误报一堆

现象：输入里有一个拼写错误，解析器连续报十几条错误。原因：没有错误恢复机制，出错后状态栈没同步。解决：在递归下降里用同步集合跳过 Token，在 LR 里用 error 产生式弹栈到能继续的状态。实验里至少要做到遇错跳过当前语句，别让错误级联。

5. 让语法分析可验证：语法树输出与错误定位的实用技巧

写到这一步，程序能跑通样例了，但怎么证明它真的对？我一般会做两件事：把语法树按缩进打印出来，以及给错误加上行列号。

先看语法树输出。递归下降返回的是嵌套元组，直接打印不好读，写个递归函数按层级缩进。

def print_tree(node, indent=0): # 按缩进打印语法树，便于和手推结果对照 if isinstance(node, tuple): print(' ' * indent + str(node[0])) for child in node[1:]: if isinstance(child, tuple): print_tree(child, indent + 1) else: print(' ' * (indent + 1) + str(child)) else: print(' ' * indent + str(node))

这个函数对('binop', '+', ('num', 1), ('num', 2))会输出层级结构，和你在纸上推的语法树一对照，优先级和结合性对不对一眼就能看出来。参数上indent控制缩进深度，元组第一个元素当节点名，后面当子节点。

错误定位的关键是让 Token 带上行列号。词法分析阶段每个 Token 记line和col，语法分析报错时直接引用。

class Token: def __init__(self, kind, value, line, col): self.kind = kind self.value = value self.line = line self.col = col def __repr__(self): return f"{self.kind}({self.value})@{self.line}:{self.col}"

有了行列号，报错信息就能写成第 3 行第 7 列：期望 ')'，实际遇到 '+'，调试效率比只报 Token 类型高一个量级。验证时我习惯准备三组输入：合法程序、缺右括号、多余运算符，分别看语法树、错误位置、错误恢复是否符合预期。

还有一个容易被忽略的点：把分析过程和结果分开验证。先单独测 FIRST/FOLLOW 计算，再测项目集构造，最后测完整解析。每一层都有独立入口，出问题时能快速定位是哪一层错了，而不是对着整个程序猜。这个习惯在实验验收时特别有用，老师问哪个环节，你能直接跑对应函数演示。

最后说个我自己的教训：别等到全部写完才第一次运行。递归下降写完一个非终结符就测一个，LR 项目集构造完先打印状态数对不对，分析表生成后先用最短输入跑一遍。语法分析的错误往往在前面就埋下了，越晚发现改起来越痛。希望帮到你。

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