简介这份编译原理实验资料面向计算机专业学生及编译器初学者聚焦自上而下语法分析中的递归下降分析法帮助读者掌握从文法改造到程序实现的完整流程。资源包内含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)表示一个 Tokentype是类别如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。每个函数在成功匹配后创建一个Nodetype设为当前非终结符名children设为所有子节点的列表。对于 ε 产生式创建一个type为ε的叶子节点。这样最终parseE()返回的就是整棵语法树的根节点。class Node: def __init__(self, type_, childrenNone): 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__(fLine {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_tailvalue等于T.value E_tail.value对于 ε 产生式value设为 0加法单位元或 1乘法单位元取决于上下文。这个设计的关键是 ε 产生式的单位元选择加法用 0乘法用 1写错了结果会差很多。验证方法上我有一个习惯每写完一个parseXxx()函数就用最小输入测一次。比如写完parseF()用x和(x)测写完parseT()用x * y测写完parseE()用x y * z测。这样一旦出错能立刻定位到是哪个函数的问题不用在完整输入里大海捞针。这个习惯帮我省了很多调试时间也推荐给你。另外实验报告里建议附上三组测试用例一组正确输入、一组缺少右括号、一组运算符连续出现分别验证正常解析、错误报错和错误恢复。验收时老师通常会挑错误用例问提前准备好能省很多事。希望帮到你。本文还有配套的精品资源点击获取