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

简介这份资源是面向计算机专业学生的编译原理实验配套文档聚焦语法分析程序的设计与实现适合正在完成实验二、需要参考完整实现思路与代码的学习者。文档以算术表达式简化子集为分析对象系统梳理了实验目的、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自底向上能处理绝大多数程序设计语言的文法包括左递归。代价是状态机构造复杂冲突排查需要看项目集。路线方向能处理左递归典型冲突适合场景递归下降自顶向下否需改写回溯失控手写解析器、表达式LL(1)自顶向下否FIRST/FOLLOW 冲突教学文法、配置语言LR(1)/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, visitedNone): 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[dot1:] # 计算 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 resultfirst_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, dot1, 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, transitionsstates是项目集列表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, indent0): # 按缩进打印语法树便于和手推结果对照 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 项目集构造完先打印状态数对不对分析表生成后先用最短输入跑一遍。语法分析的错误往往在前面就埋下了越晚发现改起来越痛。希望帮到你。本文还有配套的精品资源点击获取