语法分析实现与实验报告：递归下降与FIRST/FOLLOW集实战指南

简介：一份语法分析实验报告配套代码包，内含C++实现与实验文档，主要面向编译原理课程学习者及需要动手实现解析器的开发者。资源系统梳理了上下文无关文法、LL与LR分析方法、递归下降解析、抽象语法树构建以及错误检测等核心主题，并从文法定义出发，逐步讲解解析器设计思路，最后给出可运行的C++代码与对应输出结果。实验报告中详细说明了产生式定义、终结符与非终结符划分、预测分析表构造以及递归下降子程序的设计方法，代码部分采用模块化组织，注释清晰，便于理解与二次修改。压缩包共4个文件，其中cpp源码负责核心逻辑，docx文档为完整实验报告，txt保存运行样例，exe程序可直接执行验证；整个包仅453KB，轻量简洁。已有3106人学习浏览，源码与报告配合使用，能够帮助读者将语法分析理论落实到实际代码中，也可作为课程实验或毕业设计的实用参考。

1. 语法分析实验报告：为什么老师反复强调“不要只交代码”

编译原理课程里，词法分析还可以靠正则表达式蒙混过关，到了语法分析，代码和报告哪个更重要立刻见分晓。“语法分析实验报告（含代码）”这个要求，不是让你把源码贴在 PDF 末尾就交差，而是逼你同时回答两个问题：这个分析器按什么文法来写？它遇到非法输入时又会做什么？对正在赶实验的学生、第一次带实验的助教，以及想找一份能复现的参考实现的人来说，搞清楚“极简文法 → 可运行代码 → 报告论证”这条线，比背一百行别人的代码都有用。

这个实验适合投入时间的地方也在这：语法分析器的核心思想其实很稳定，无外乎递归下降或表驱动两种路线，但报告能不能拿高分，取决于你有没有把“为什么这样设计”讲明白。把文法、代码、测试三个环节打通写，新手能一步步跑起来，熟手能直接对照参数和边界去优化，这份报告才有价值。

2. 语法分析的两种主流实现：手写递归下降与 YACC/Bison，先选型再动手

语法分析器不是只有一种写法，但实验报告能写多厚，取决于你选哪条路。多数学校给的文法规模不大，手写递归下降够用；少数课设要求支持完整的类 C 语句集，那可能得交一份 Bison 版本。选型这件事决定了后面所有章节怎么写，也直接决定报告里是“贴满代码”还是“讲清过程”。

2.1 递归下降：每个非终结符对应一个函数，课程实验最容易讲清楚

递归下降是“每个非终结符写一个函数”的直观做法。比如一个简化表达式文法：

E -> E + T | E - T | T T -> T * F | T / F | F F -> NUM | ( E )

对应到代码里就是parse_expr、parse_term、parse_factor三个函数。parse_expr内部先调parse_term，再循环处理+和-；parse_term再调parse_factor，处理*和/。这种按层次下降的写法天然表达了运算符优先级：乘法比加法结合得更紧，因为parse_term在调用链上离终结符更近。

它对实验报告最大的好处是映射关系透明。老师看报告时，能按文法的每个产生式逐个找到对应函数，调用关系图可以直接画出来，甚至能标出哪一行代码处理了哪条规则。很多学生写递归下降报告能拿高分，就是因为这个“一一对应”让人无法怀疑代码是抄来的。另外，出错定位也很实在：只要在peek和advance两个函数里打点，就能知道分析到哪个 token 时失败了。

递归下降的代价是必须手工消除左递归。上面的文法直接照抄成函数会死循环，parse_expr一进来又调parse_expr，直接栈溢出。所以我在报告里一般会先把文法改写成等价的E -> T { (+|-) T }这种形式，说明“将左递归改成循环”这一步，再贴代码。

2.2 YACC/Bison 方案：适合大文法，但报告要补“冲突处理”章节

另一条路是用 Bison 这类生成器。写一个.y文件，声明 token、优先级和产生式，工具自动生成 LALR(1) 分析表和驱动代码。比如表达式计算器只需几行规则，工具会把状态机建好，出错时还会给出冲突警告。这是工业界的常见做法，处理几百条产生式的大型文法时，手写递归下降会累到怀疑人生，Bison 反而省时省力。

但放到课程实验报告里，Bison 有个致命问题：它像个黑匣子，把分析过程全吞了。你写不出“状态如何转移、栈如何压入”的过程描述，报告的可写内容只剩下两类——一是规则声明怎么写的，二是y.output文件里的 shift/reduce 冲突怎么解决。

我在负责课设检查时，见过不少同学交 Bison 版本，报告里只有用%left '+' '-'、%left '*' '/'声明优先级，再贴几张y.output的冲突片段。这本身没错，变量和流程都在工具里，你确实只能写这些。但注意，老师通常希望你至少解释清楚：为什么加乘法优先级后冲突数从 2 变成 0？%nonassoc和%left有什么区别？把这两个问题的答案补进报告，Bison 版本才算完整。

2.3 选型对比表：两周实验时间够不够用，就看这几项

我的建议是：如果你的实验只要求“支持四则运算和括号”或“支持 if/while 语句块”，两周上机时间，选递归下降。理由很简单，代码行数可控，报告里能讲的东西多，即使出问题也能靠读代码快速定位。如果老师明确要求用 LEX/YACC 或文法很大，那必须用 Bison，但报告务必花一整节写冲突处理过程，别让它变成纯规则贴片。

3. 用 Python 手写递归下降分析器：从 token 接口到表达式解析的完整示例代码

选型定了，就看怎么落地。以“四则运算 + 括号”为例，我用 Python 写一个最小可跑的语法分析器。整套代码分两层：词法层把字符串变成 token，语法层消费 token 构建语法树。下面的实现可以直接抄进实验报告作为附录，但报告正文里要对每一层做解释。

3.1 词法与语法之间的解耦边界：先定义一个不依赖键盘输入的 token 流

语法分析器不应该关心输入是来自键盘、文件还是网络，它只消费一个 token 流。所以第一步先把词法分析器写清楚，让语法层只依赖Token的两个字段kind和value。

class Token: def __init__(self, kind, value): self.kind = kind # token 类型：'NUM' 或 '+ - * / ( )' self.value = value # token 值：数字值或符号本身 class Lexer: def __init__(self, text): self.text = text self.pos = 0 def next_token(self): # 跳过空白字符，换行和空格不会混进语法分析 while self.pos < len(self.text) and self.text[self.pos].isspace(): self.pos += 1 if self.pos >= len(self.text): return None # EOF 标记，用 None 表示 ch = self.text[self.pos] if ch.isdigit(): start = self.pos # 连续数字一起切分，避免 "123" 被拆成三个 token while self.pos < len(self.text) and self.text[self.pos].isdigit(): self.pos += 1 return Token('NUM', int(self.text[start:self.pos])) if ch in '+-*/()': self.pos += 1 return Token(ch, ch) raise ValueError('无法识别的字符：' + ch) def tokenize(text): lexer = Lexer(text) tokens = [] while True: tok = lexer.next_token() if tok is None: break tokens.append(tok) return tokens

这段代码的逻辑说明：Token只保留类型和值两个字段，kind用来让语法层判断，value用来保存数字值；Lexer 用self.pos记录扫描位置，遇到空白直接跳过。参数方面，两个核心点是：数字连续切分，避免“12ab”这种输入出现歧义；非法字符串直接抛ValueError，这份错误在报告里归为词法错误，与语法错误分开讨论。

3.2 递归下降核心代码：parse_expr、parse_term、parse_factor 三层排布

词法层把字符串变成 token 列表后，语法层真正开始工作。下面这段是完整分析器：

class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): # 返回当前 token，读到末尾返回 None，避免越界崩溃 if self.pos < len(self.tokens): return self.tokens[self.pos] return None def advance(self): # 消费当前 token 并返回它 tok = self.peek() if tok is not None: self.pos += 1 return tok def expect(self, kind): # 验证当前 token 种类，不匹配时抛出带位置信息的错误 tok = self.peek() if tok is None or tok.kind != kind: got = 'EOF' if tok is None else tok.kind raise SyntaxError(f'位置 {self.pos} 期望 {kind}，实际是 {got}') self.pos += 1 return tok # expr ::= term { (+|-) term } def parse_expr(self): left = self.parse_term() while self.peek() is not None and self.peek().kind in ('+', '-'): op = self.advance() right = self.parse_term() left = ('BinOp', op.kind, left, right) return left # term ::= factor { (*|/) factor } def parse_term(self): left = self.parse_factor() while self.peek() is not None and self.peek().kind in ('*', '/'): op = self.advance() right = self.parse_factor() left = ('BinOp', op.kind, left, right) return left # factor ::= NUM | '(' expr ')' def parse_factor(self): tok = self.peek() if tok is None: raise SyntaxError('输入意外结束，期望数字或左括号') if tok.kind == 'NUM': self.advance() return ('Num', tok.value) if tok.kind == '(': self.advance() expr = self.parse_expr() self.expect(')') return expr raise SyntaxError(f'期望数字或左括号，实际是 {tok.kind}') def parse(text): tokens = tokenize(text) parser = Parser(tokens) tree = parser.parse_expr() if parser.peek() is not None: raise SyntaxError('解析完成后还有多余输入：' + parser.peek().kind) return tree

逻辑说明：parse_expr先调parse_term拿到左侧操作数，再用 while 循环处理连续出现的+、-，每次循环把旧的结果作为左子树，新解析的 term 作为右子树，拼成一个('BinOp', op, left, right)元组。parse_term的结构与它完全对称，只是把操作符换成*、/。parse_factor只处理一个数字或一个括号包裹的完整表达式，数字直接返回叶子节点，括号则递归向下调parse_expr。

参数说明：peek和advance分别对应“不消费地观看”和“消费当前 token”，这是递归下降的两个基础操作；expect(')')专门处理“必须出现右括号”的情形，如果缺括号，错误信息会明确说出位置。最外层的parse函数在分析完表达式后还会检查是否还有多余 token，保证像1+2 3这样的输入能被发现。返回值不是计算结果而是语法树元组，这样报告里可以打印出分析过程，也能单独写一个树形输出函数。

3.3 实验报告里的示例代码讲解与附录代码格式

代码写完后，报告怎么安排内容是个实际问题。正文部分一般只放三样东西：一是parse()这个入口函数的调用方式，二是运行正确输入的一次输出结果，三是错误输入时的异常信息。完整源码放到附录，附录里按“词法层 → 语法层 → 测试代码”三块组织。

讲到示例代码讲解时，我习惯对每个函数写三行注释：输入是什么、正常输出是什么、异常抛什么。比如parse_factor的注释可以写“输入：当前 token 为 NUM 或 '('；输出：叶子节点或子树；异常：遇到其他 token 抛 SyntaxError”。这种方式老师一眼能看清你的边界设计，比自己临场编一段流程描述靠谱得多。

附录代码格式有四个硬要求：等宽字体（Consolas 或 Courier New）、行号、UTF-8 编码、粘贴时选择“只保留文本”。很多同学在 Word 里贴代码后，引号被自动替换成全角，编译直接失败，这一条我放到第 5 章单独讲。实验报告里的“含代码”不是简单贴截图，而是要让读报告的人能把代码复制到编辑器里直接运行。

4. 报告里必写的 FIRST 集、FOLLOW 集与预测分析表：手算过程与参数设定

递归下降代码是“怎么做”，但报告里还需要回答“为什么这么做”。FIRST 集和 FOLLOW 集是为表驱动分析准备的，即使你手写递归下降，也建议把它们算一遍。原因是：递归下降里while循环的终止条件、报错时该跳过哪些 token，本质上都依赖这两个集合。

为了让计算过程可复现，我把第 2 章那个左递归文法改写成 LL(1) 版本：

E -> T E' E' -> + T E' | - T E' | ε T -> F T' T' -> * F T' | / F T' | ε F -> NUM | ( E )

4.1 FIRST 集与 FOLLOW 集的手算顺序：从终结符出发，按产生式扫描

很多实验报告把两个集合直接写成结果，没有过程，这是容易被扣分的地方。手算要按顺序来。

先算 FIRST 集。规则很简单：看每个非终结符最右侧的可能推导结果，遇到终结符就加入，能推出空串 ε 也要记录。从最底层的F开始，F -> NUM | ( E )，所以FIRST(F) = {NUM, (}。T -> F T'右部以F开头，所以FIRST(T) = FIRST(F) = {NUM, (}。同理E -> T E'得到FIRST(E) = {NUM, (}。E'的产生式右部以+或-开头，还能推 ε，所以FIRST(E') = {+, -, ε}。T'同理，FIRST(T') = {*, /, ε}。

再算 FOLLOW 集。这里有一个关键约束：只有出现在产生式右部的非终结符，才需要算 FOLLOW。从开始符号开始，约定$一定属于FOLLOW(E)，因为输入串的结束符就是$。然后扫描每一条产生式：

• 在F -> ( E )中，E后面跟着右括号，所以)加入FOLLOW(E)，得到FOLLOW(E) = {), $}。
• 在E -> T E'中，T后面是E'，所以FIRST(E')的非 ε 部分{+, -}加入FOLLOW(T)；又因为E'可推 ε，所以FOLLOW(E)也要并入FOLLOW(T)，得到FOLLOW(T) = {+, -, ), $}。
• 在T -> F T'中，F后面是T'，FIRST(T')的非 ε 部分{*, /}并入FOLLOW(F)，FOLLOW(T)整体也并入，得到FOLLOW(F) = {*, /, +, -, ), $}。
• E'和T'分别出现在右部末尾，直接继承左侧非终结符的 FOLLOW，得到FOLLOW(E') = FOLLOW(E) = {), $}，FOLLOW(T') = FOLLOW(T) = {+, -, ), $}。

报告里把这几步按顺序写出来，比只贴结果更能证明你理解理论基础。我当时自己的血泪经验是：FOLLOW 集最容易算错的是“右部末尾的继承规则”，很多人漏算FOLLOW(E)并入FOLLOW(T')这一步，导致表格少几个单元格。

4.2 预测分析表的构造与空白单元格：错误处理的设计依据

有了两个集合，就能填预测分析表。表的行是非终结符，列是终结符，每个单元格写产生式。下面这个表是简化版，只列了表格的完整结构，列方向省略了*和/（它们的填法与+、-对称）。

填写规则是：如果FIRST(NUM) = {NUM}，那么F行NUM列写F -> NUM；如果ε在FIRST(E')里，就要看FOLLOW(E')，所以E'行的)列和$列都写E' -> ε。表格里的空白单元格不是“没有内容”，而是“错误项”——在这位置输入任何 token 都构成语法错误。

这一步对递归下降的意义是什么？当你写expect(')')时，你其实就是在查表：如果当前 token 不是)，查表发现E'行)列是E' -> ε，说明右括号可能是一个合法的“当前分析结束”信号。报告里把表和代码对应起来，老师就知道你不是随手写了个while循环。

4.3 递归下降代码里用得上的错误恢复参数：同步符号与最大错误数

预测分析表还有一个实际用途：设计错误恢复。我一般会在报告里给分析器加两个参数——同步符号集合和最大错误数。

class ErrorReporter: def __init__(self, max_errors=5): self.errors = 0 self.max_errors = max_errors def report(self, msg): self.errors += 1 print('[错误]', msg) if self.errors >= self.max_errors: raise RuntimeError('错误数量超过上限，停止分析') # 同步符号：遇到这些 token 时，跳过当前分析状态重新同步 SYNC = {')', '$'} def recover(self): # 跳过直到同步符号，再继续分析 while self.peek() is not None and self.peek().kind not in SYNC: self.advance()

同步符号的选法有讲究：一般取当前非终结符的 FOLLOW 集中的终结符，)和$在表达式文法里是天然的同步点。max_errors防止错误恢复陷入无限循环，设为 5 打住。脚本里这两个参数写在报告里，比只贴基础代码看起来完整得多。

5. 语法分析实验常见避坑指南：六个典型翻车现象与解决路径

下面这些坑是我在实验指导和复查报告时反复遇到的，每一条都按“现象 → 原因 → 解决”写。你在跑代码时如果遇到类似问题，直接对照处理。

5.1 死循环直到栈溢出：左递归文法直接照抄进递归下降

现象：parse()一执行，程序报RecursionError: maximum recursion depth exceeded，根本停不下来。原因是把E -> E + T原封不动写成parse_expr，函数第一步又调parse_expr，形成永远无法消耗 token 的左递归。解决：改写成expr ::= term { (+|-) term }的 while 循环版本，让每次循环至少消费一个运算符和一个 term。报告里要把“左递归改写”单独列一步写，这是老师检查理解程度的关键点。

5.2 优先级反转：term 和 factor 的调用顺序写反

现象：输入1+2*3，程序返回 9 而不是 7，相当于算成了(1+2)*3。原因很直接，parse_expr里误把parse_factor当成下一层，导致*永远等不到属于自己的因子。解决：严格保持expr -> term -> factor三层结构，跨层调用就是优先级错位。验证方法是用第 6 章的语法树打印函数，看树里*节点是不是比+节点更靠近叶子。

5.3 输入末尾崩溃：peek 没有做边界判断

现象：空字符串或1+这类缺操作数的输入，程序报IndexError: list index out of range，而不是一个明确的语法错误。原因：peek()直接用tokens[self.pos]，当self.pos等于 token 列表长度时越界。解决：peek()先判断self.pos < len(self.tokens)，越界返回None；parse_factor开头对None单独给一条“输入意外结束”的异常信息。这条写进报告能体现你对边界情况的考虑。

5.4 空白符和分号处理混乱：把词法职责带进了语法分析

现象：输入里换行后，分析器把换行当成一个 token，导致表达式解析失败。原因：Lexer 没有过滤空白符，语法层被迫处理本不该处理的字符。解决：在词法分析器里把空白字符全部跳过，语法层只关心有效 token。语法分析器里处理空白是常见的架构失误，报告里写“词法分析与语法分析的职责边界”这一段时正好用上这个反面案例。

5.5 环境报错误当成代码错误：“由于找不到 msvcp140.dll 无法继续执行代码”

现象：用 C++ 写的分析器在自己机器上编译运行正常，换到另一台 Windows 机器，双击可执行程序弹窗报“由于找不到 msvcp140.dll 无法继续执行代码”，于是有人开始怀疑是不是语法分析逻辑写错了。原因：这跟代码无关，是目标机器缺少 VC++ 运行库，程序动态链接msvcp140.dll失败。解决：在目标机器安装对应的 Visual C++ Redistributable，或在项目属性里把运行库改为静态链接/MT。遇到这类报错先检查环境，别把时间浪费在调试 parser 上。

5.6 附录代码被 Word “自动修复”：引号变全角、行号错位

现象：从实验报告里复制代码回编辑器，直接编译报错，仔细一看是双引号变成了全角引号。原因：Word 默认开启“智能引号”替换，英文引号被自动改成中文引号，代码当然跑不了。解决：粘贴代码时用“只保留文本”选项，附录正文用等宽字体，在报告末尾注明源码采用 UTF-8 编码。这个坑极其常见，却能让一份完整报告直接翻车。

6. 验证一个语法分析器是否及格：四个测试样例和一个语法树打印函数

代码写完了，怎么验证它真的对？只测正确输入远远不够。我习惯写一个十几行的语法树打印函数，再加四个测试样例覆盖优先级、括号、结合性和错误恢复。

6.1 用 12 行打印一棵语法树

def dump_tree(node, indent=0): if node[0] == 'Num': print(' ' * indent + str(node[1])) elif node[0] == 'BinOp': print(' ' * indent + node[1]) # 运算符 dump_tree(node[2], indent + 2) # 左子树 dump_tree(node[3], indent + 2) # 右子树 else: print(' ' * indent + str(node))

node是三元组('BinOp', 运算符, 左子树, 右子树)或二元组('Num', 值)。函数按缩进输出树的层次，看优先级是否正确，一眼就能定位问题。

6.2 四个测试样例：对应优先级、括号、结合性、错误恢复

前三个样例跑通只能算及格，第四个样例才是拉开差距的地方。我当时因为只测了正确输入，没测非法输入，报告被助教退回，要求补上错误恢复分析。后来把第 4 章的同步符号和max_errors参数加进报告，才算完整。如果你能做到对错误输入既“报错”又“不崩溃”，这份实验报告的含金量就高于大多数只贴正确输出的作业了。希望帮到你。

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