简介：这份编译原理实验资料面向计算机专业学生及编译器初学者，聚焦自上而下语法分析中的递归下降分析法，帮助读者掌握从文法改造到程序实现的完整流程。资源包内含1个doc文档，约80KB，以实验报告形式呈现，涵盖实验目的、文法规则定义、消除左递归后的产生式、各非终结符的FIRST集与FOLLOW集计算，以及完整的Java递归下降分析程序代码。读者可从中获得一套可运行的实验方案：先对含左递归的文法进行改造并验证其LL(1)性质，再结合词法分析器（新增float关键字识别，种别编码26）构造递归下降分析程序，代码中清晰定义了A、M、P、D、N、Q、E、G、T等递归函数，并附有运行结果与解析失败标志处理逻辑。目前已有531人学习下载，适合需要完成编译原理实验、理解语法分析关键环节的读者参考与复用。
1. 递归下降分析到底在算什么：从一次实验翻车说起
很多人第一次做编译原理实验，看到「自上而下的语法分析-递归下降分析」这个题目，第一反应是照着课本把文法抄下来，然后一个非终结符写一个函数，跑通就交。我当年也是这么干的，结果在验收环节被问了一句「你这个函数为什么能保证不回溯」，当场卡壳。递归下降分析的核心不是「写函数」，而是「用程序的调用栈去模拟文法推导过程」——每个非终结符对应一个函数，函数体就是该非终结符所有产生式的选择逻辑，函数调用即推导，函数返回即归约。它解决的是「给定一个 Token 串，判断它是否属于某个文法定义的语言」这个问题，适合所有需要手写解析器的场景：配置文件解析、DSL 解释器、表达式求值、教学实验。这篇笔记把实验拆成可复现的步骤，从文法改造到代码落地再到结果验证，每一步都给出参数和踩坑记录，新手能照着跑，熟手能看到边界条件在哪。
2. 文法预处理：为什么你的递归下降函数会无限递归
2.1 左递归消除：直接左递归和间接左递归的处理差异
递归下降分析最怕的就是左递归。假设文法里有E -> E + T | T，你写出来的函数parseE()第一件事就是调用parseE()，程序直接栈溢出。这不是代码写错了，是文法本身不适合自上而下分析。常见做法是先做左递归消除，把E -> E + T | T改写成E -> T E'和E' -> + T E' | ε。直接左递归的消除有固定公式：对于A -> Aα | β，改成A -> βA'、A' -> αA' | ε。间接左递归要麻烦一些，比如A -> Bc | d、B -> Ab | e，需要先做代入再消除。我一般会写一个小的文法预处理脚本，把产生式读进来，自动检测并消除直接左递归，间接左递归手动处理，因为实验规模的文法通常不超过十个非终结符，手动代入反而更可控。
# 直接左递归消除：输入产生式列表，输出改写后的产生式 def eliminate_direct_left_recursion(productions): """ productions: dict, key为非终结符, value为产生式右部列表 返回改写后的productions和新增的非终结符 """ new_productions = {} new_nonterminals = {} for nt, rules in productions.items(): # 分离左递归产生式和非左递归产生式 recursive = [r for r in rules if r.startswith(nt)] non_recursive = [r for r in rules if not r.startswith(nt)] if not recursive: new_productions[nt] = rules continue # 构造新非终结符 nt'，注意避免命名冲突 new_nt = nt + "'" while new_nt in productions or new_nt in new_nonterminals: new_nt += "'" # A -> βA' new_productions[nt] = [r + new_nt for r in non_recursive] # A' -> αA' | ε new_rules = [] for r in recursive: suffix = r[len(nt):] # 去掉开头的A new_rules.append(suffix + new_nt) new_rules.append('ε') new_nonterminals[new_nt] = new_rules new_productions.update(new_nonterminals) return new_productions这段代码的关键参数是recursive和non_recursive的分离逻辑。注意r.startswith(nt)这个判断在非终结符名有前缀关系时会误判，比如E和E'同时存在时，E'开头的产生式会被误认为E的左递归。解决办法是在文法设计阶段就避免用单字母加撇号这种命名，改用E_rest或E_tail这类不会前缀冲突的名字。另一个参数是ε的表示，代码里用字符串'ε'，实际解析时要单独处理，不能当成普通终结符去匹配 Token。
2.2 提取左公因子：让 FIRST 集帮你做选择
消除左递归之后，下一个问题是同一个非终结符的多个产生式有公共前缀。比如S -> if E then S | if E then S else S，你写parseS()的时候，看到if这个 Token 无法立刻决定走哪条产生式，只能回溯。回溯在递归下降里是性能杀手，实验规模小的时候看不出来，一旦 Token 流长了就是指数级爆炸。常见做法是提取左公因子，把公共前缀提出来：S -> if E then S S'、S' -> else S | ε。提取之后，每个非终结符的产生式要么以不同终结符开头，要么以 ε 开头，这样就能用 FIRST 集做唯一选择。FIRST 集的计算是递归下降的标配，我一般会在代码里硬编码一个FIRST字典，因为实验文法通常固定，动态计算反而增加调试复杂度。
# FIRST集和FOLLOW集的硬编码示例（针对表达式文法） FIRST = { 'E': {'(', 'id'}, 'E_tail': {'+', 'ε'}, 'T': {'(', 'id'}, 'T_tail': {'*', 'ε'}, 'F': {'(', 'id'}, } FOLLOW = { 'E': {')', '$'}, 'E_tail': {')', '$'}, 'T': {'+', ')', '$'}, 'T_tail': {'+', ')', '$'}, 'F': {'*', '+', ')', '$'}, }参数说明：FIRST集用于判断当前非终结符在遇到某个 Token 时应该选哪条产生式；FOLLOW集用于处理 ε 产生式——当FIRST集里没有当前 Token 时，如果当前 Token 在FOLLOW集里，就选 ε 产生式。$表示输入结束符。这两个集合的正确性直接决定解析器能否正确工作，建议在实验报告里附上计算过程，验收时经常被问。
2.3 递归下降函数的骨架：每个非终结符一个函数
文法改造完成后，代码结构就清晰了。每个非终结符对应一个函数，函数签名统一为parseXxx()，返回值为bool或Node（如果需要建语法树）。函数内部先取当前 Token，然后根据FIRST集做switch或if-else分支，匹配成功则消费 Token 并递归调用其他非终结符，匹配失败则返回False或抛异常。我一般会维护一个全局的 Token 流指针pos，消费 Token 就是pos += 1，取当前 Token 就是tokens[pos]。这个设计简单直接，但要注意边界条件：pos越界时要返回结束符$，否则会数组越界。
# 递归下降解析器骨架 class Parser: def __init__(self, tokens): self.tokens = tokens # Token列表，最后一项为'$' self.pos = 0 def current(self): if self.pos < len(self.tokens): return self.tokens[self.pos] return '$' def match(self, expected): if self.current() == expected: self.pos += 1 return True return False def parseE(self): # E -> T E_tail if self.current() in FIRST['E']: if not self.parseT(): return False return self.parseE_tail() return False def parseE_tail(self): # E_tail -> + T E_tail | ε if self.current() == '+': self.match('+') if not self.parseT(): return False return self.parseE_tail() elif self.current() in FOLLOW['E_tail']: return True # ε产生式 return False逻辑说明：parseE()先检查当前 Token 是否在FIRST['E']里，如果是则调用parseT()，然后调用parseE_tail()。parseE_tail()检查当前 Token 是否为+，如果是则消费+并递归；否则检查是否在FOLLOW['E_tail']里，如果是则选 ε 产生式直接返回True。参数tokens需要预处理，在末尾追加$作为结束标记。这个骨架可以直接扩展到任意 LL(1) 文法，只要文法改造正确，代码几乎不需要改动。
3. 从 Token 流到语法树：递归下降的完整实现路径
3.1 词法分析器的接口约定：Token 结构设计
递归下降分析器的输入是 Token 流，所以词法分析器的输出格式必须和语法分析器约定好。我一般用三元组(type, value, line)表示一个 Token，type是类别（如id、num、+、(），value是原始字符串，line是行号用于报错。词法分析器可以用手写状态机，也可以用正则表达式，实验里为了聚焦语法分析，通常直接给一个 Token 列表或者从文件读。注意type和value的区分：对于关键字和运算符，type和value可以相同；对于标识符和数字，type是类别，value是具体内容。递归下降里做匹配时，用type还是value取决于文法设计——如果文法里区分了id和num，就用type匹配；如果文法里直接写了+、*这些符号，就用value匹配。
# Token结构示例 tokens = [ ('id', 'x', 1), ('+', '+', 1), ('num', '3', 1), ('*', '*', 1), ('(', '(', 1), ('id', 'y', 1), (')', ')', 1), ('$', '$', 1), ]参数说明：type用于语法分析器的分支判断，value用于构建语法树节点和报错信息，line用于定位错误。如果实验要求输出语法树，建议在parseXxx()函数里返回节点对象，而不是简单的bool。节点对象包含type（非终结符名）和children（子节点列表），叶子节点就是 Token。
3.2 语法树构建：在递归返回时组装节点
如果实验只要求判断「能否解析」，返回bool就够了。但大多数实验要求输出语法树或推导过程，这时候需要在递归返回时组装节点。我一般把parseXxx()的返回值改成Node对象，匹配失败返回None。每个函数在成功匹配后，创建一个Node，type设为当前非终结符名，children设为所有子节点的列表。对于 ε 产生式，创建一个type为'ε'的叶子节点。这样最终parseE()返回的就是整棵语法树的根节点。
class Node: def __init__(self, type_, children=None): self.type = type_ self.children = children or [] def __repr__(self): if not self.children: return self.type return f"{self.type}({', '.join(repr(c) for c in self.children)})" def parseE(self): if self.current()[0] in FIRST['E']: t = self.parseT() if t is None: return None et = self.parseE_tail() if et is None: return None return Node('E', [t, et]) return None逻辑说明：parseE()在成功解析T和E_tail后，返回一个Node('E', [t, et])。这样整棵树的形状和文法推导过程完全对应。参数children的顺序就是产生式右部的顺序，不能颠倒。如果实验要求输出最左推导，可以在每次创建节点时打印当前使用的产生式，或者用栈模拟推导过程。
3.3 错误恢复：遇到非法 Token 时怎么报错才有用
递归下降分析器遇到非法 Token 时，最简单的做法是直接返回False或抛异常，但这样报错信息只有「解析失败」四个字，调试时很痛苦。我一般会在match()函数里加错误记录，当期望的 Token 和当前 Token 不匹配时，记录期望值、实际值和行号，然后抛出一个自定义异常。异常里包含这些信息，上层捕获后打印出来。如果实验要求错误恢复，可以在异常捕获后跳过当前 Token 继续解析，但递归下降的错误恢复比较麻烦，实验里通常不做要求。
class ParseError(Exception): def __init__(self, expected, actual, line): self.expected = expected self.actual = actual self.line = line super().__init__(f"Line {line}: expected {expected}, got {actual}") def match(self, expected): if self.current()[0] == expected: self.pos += 1 return True raise ParseError(expected, self.current()[0], self.current()[2])参数说明：expected是文法里期望的 Token 类型，actual是实际读到的 Token 类型，line是行号。这个异常在parseE()等函数里不需要捕获，让它一路抛到顶层，顶层统一打印。注意current()[2]取的是行号，前提是 Token 结构是(type, value, line)三元组。
4. 避坑与排查：递归下降实验里最容易翻车的五个点
4.1 现象：程序栈溢出，报 RecursionError
原因：文法里存在左递归，parseE()直接或间接调用了自己，没有消费任何 Token 就进入下一层递归。解决：检查文法，用 2.1 节的脚本消除直接左递归，间接左递归手动代入。验证方法：在parseE()入口打印当前 Token，如果连续多次打印同一个 Token，说明卡在左递归里了。
4.2 现象：解析结果正确但语法树形状不对
原因：Node的children顺序和产生式右部不一致，或者 ε 产生式没有创建节点。解决：对照文法逐条检查每个parseXxx()函数里Node的构造顺序，ε 产生式也要返回一个Node('ε')，不能返回None或空列表。验证方法：用一个小规模输入（如x）手动推导语法树，和程序输出对比。
4.3 现象：遇到+和*混合表达式时结果错误
原因：FIRST集和FOLLOW集写错了，导致parseE_tail()在遇到*时错误地选了 ε 产生式，把*留给了上层。解决：重新计算FIRST和FOLLOW集，特别注意FOLLOW集里要包含)和$。验证方法：用x + y * z这种混合表达式测试，看语法树里*是否在+的子树里。
4.4 现象：Token 流末尾没有$，解析到最后数组越界
原因：词法分析器输出没有追加结束符，current()在pos等于len(tokens)时返回了None或抛异常。解决：在 Token 列表末尾手动追加('$', '$', -1)，或者在current()里判断pos >= len(tokens)时返回'$'。验证方法：打印tokens列表，确认最后一项是$。
4.5 现象：实验验收时被问「为什么用递归下降而不是 LL(1) 预测分析表」
原因：递归下降和 LL(1) 预测分析表本质上是等价的，都是自上而下分析，区别在于递归下降用程序调用栈，预测分析表用显式栈。递归下降的代码更直观，适合手写；预测分析表更适合自动生成。回答时可以说：递归下降的每个函数对应一个非终结符，函数调用关系就是推导关系，调试时可以直接在函数里打断点，比查表更直观。这个问题的坑在于不要贬低另一种方法，说「适合实验规模」即可。
5. 进阶技巧：用递归下降做表达式求值和一个验证习惯
递归下降分析器不仅能判断语法，还能在解析过程中直接求值。做法是在Node里加一个value字段，叶子节点（数字）的value就是数值，非叶子节点的value在递归返回时计算。比如parseE()返回的节点，value等于parseT()的value加上parseE_tail()的value。这样一遍解析就能算出结果，不需要先建树再遍历。这个技巧在写计算器或 DSL 解释器时非常实用，实验里如果要求「计算表达式结果」，用这个方法比建树后再求值少写一半代码。
def parseE(self): if self.current()[0] in FIRST['E']: t = self.parseT() if t is None: return None et = self.parseE_tail() if et is None: return None node = Node('E', [t, et]) node.value = t.value + et.value # 在解析时直接求值 return node return None def parseT(self): if self.current()[0] in FIRST['T']: f = self.parseF() if f is None: return None tt = self.parseT_tail() if tt is None: return None node = Node('T', [f, tt]) node.value = f.value * tt.value return node return None参数说明：node.value的计算依赖子节点的value，所以必须保证子节点先计算完成。对于E_tail -> + T E_tail，value等于T.value + E_tail.value；对于 ε 产生式，value设为 0（加法单位元）或 1（乘法单位元），取决于上下文。这个设计的关键是 ε 产生式的单位元选择，加法用 0，乘法用 1，写错了结果会差很多。
验证方法上，我有一个习惯：每写完一个parseXxx()函数，就用最小输入测一次。比如写完parseF()，用x和(x)测；写完parseT()，用x * y测；写完parseE()，用x + y * z测。这样一旦出错，能立刻定位到是哪个函数的问题，不用在完整输入里大海捞针。这个习惯帮我省了很多调试时间，也推荐给你。另外，实验报告里建议附上三组测试用例：一组正确输入、一组缺少右括号、一组运算符连续出现，分别验证正常解析、错误报错和错误恢复。验收时老师通常会挑错误用例问，提前准备好能省很多事。希望帮到你。
本文还有配套的精品资源，点击获取
