简介这是一份编译原理课程中自上而下语法分析的实验资源聚焦递归下降分析法适合正在学习编译原理、需要完成类似实验或理解语法分析实现的学生。资源以单个doc文档形式提供压缩包大小约80KB内容包含实验目的、题目要求、改造后的文法、各非终结符的FIRST集与FOLLOW集以及完整的Java递归下降分析程序代码和运行结果。文档对直接左递归和间接左递归的消除、LL(1)文法验证等关键步骤做了演示文法规则中涵盖声明语句块、可执行语句块、表达式等典型结构。递归下降程序采用A、M、P、D、N、Q、E、G、T、H、F等函数对应各非终结符进行解析并结合词法分析器扩展了float关键字的识别单词种别编码26帮助读者掌握从文法改造到程序实现的完整流程。已有531人学习过该资源可用于实验参考、报告撰写或复习备考。1. 递归下降分析自顶向下语法分析里最好上手也最容易翻车的一种写法第一次在编译原理实验里写自上而下的语法分析时多数人的感受是递归下降分析Recursive Descent Parsing看起来简单——一个非终结符对应一个函数照着产生式抄代码就能跑。真正动手才发现左递归会让程序在第一个用例就死循环优先级写错会让 23*4 算出 20而错误恢复更是玄学一句报错信息能把调试时间拖到半夜。这篇笔记把递归下降分析从文法设计到代码实现、从左递归消除到错误恢复完整走一遍最后落到一个能直接提交到编译原理实验的四则运算分析器并给出验证思路。适合刚做完课程实验但想搞清楚每行代码为什么这样写的人也适合要给别人讲清楚这段代码的助教和工程师。2. 自上而下分析的执行逻辑为什么递归下降能对应到文法2.1 自顶向下分析、推导树和递归下降三者的关系自顶向下分析top-down parsing的核心动作是从开始符号出发反复选择产生式把当前的非终结符替换成产生式右部直到所有叶子都是终结符并且和输入 token 序列一致。以四则运算文法为例对输入23*4推导过程大致是 E → T E → F T E → 2 T E → 2 E → 2 T E → 2 F T E → 2 3 T E → 2 3 * F T E → 2 3 * 4。这个推导过程倒过来看是一棵语法树根是 E叶子是数字和运算符。递归下降分析是这个思路的手工实现每个非终结符对应一个函数函数体就是该非终结符各个产生式的顺序执行。需要匹配终结符时调用一个类似match(PLUS)的操作去消费 token需要推导下一个非终结符时直接调用对应的函数。这样做的好处是“文法即代码”每个函数的名字就是非终结符的名字函数调用栈就是推导路径调试的时候看到expr() - term() - factor()就知道分析器正在尝试哪条产生式。这里和 LL(1) 分析有很强的对应关系。LL(1) 表驱动分析用一张二维表存储“当前非终结符 当前输入 token → 选用哪条产生式”外加一个显式栈模拟推导。递归下降不做这张表而是把表的行拆成了 if-else 分支进入一个非终结符函数后靠当前 token 判断该进入哪个分支。两者的选择依据完全一样区别在于递归下降把状态机和栈换成了编程语言的函数调用栈更直观但也就继承了调用栈的深度限制。2.2 FIRST 集合决定一个递归下降函数怎么选择分支递归下降函数写出来的第一步是确定每个非终结符的每个分支各在什么情况下进入。判断依据就是 FIRST 集合从某个符号出发能够推导出的所有可能开头的终结符集合。进入函数时当前 token 落在哪个分支的 FIRST 里就执行哪个分支。以factor为例文法 F → ( E ) | NUMBER它的 FIRST(F) { (, NUMBER }。因此 factor() 的逻辑就是当前 token 是(就走左括号分支是数字就走数字分支两者都不是就报语法错误。这不是什么玄学是文法直接翻译过来的。如果某个非终结符的两个分支 FIRST 集合存在交集说明这个文法不能直接用递归下降实现通常需要提取左公因子。典型的例子是悬空 elsestmt → if expr then stmt | if expr then stmt else stmt两个分支的 FIRST 都是if直接写代码时看到if不知道该走哪个分支。改写为 stmt → if expr then stmt else_partelse_part → else stmt | ε递归下降就好写了而 else 分支到底是归哪个 if也在else_part这个结构里天然解决。这类改写是自顶向下语法分析里最常见的预处理步骤。在我们即将实现的四则运算文法里FIRST 集合如下表。注意 E 的两个非空分支 FIRST 分别是{}和{-}互不相交因此expr_prime里可以直接用两个独立的 if如果写成if kind in (PLUS, MINUS)也是安全的因为这两个 token 不可能同时出现。非终结符FIRST 集合含义E{ (, NUMBER }表达式只能以数字或左括号开头E{ , -, ε }表达式后缀要么是运算符开头要么直接结束T{ (, NUMBER }项和表达式一样最终落到因子T{ *, /, ε }项后缀要么是乘除号要么结束F{ (, NUMBER }因子只能数字或括号表达式2.3 空产生式和 FOLLOW 集合什么时候什么都不匹配有 ε 分支的非终结符是递归下降里最容易写错的地方。还是看 E → T E | - T E | ε当 expr_prime() 进入后发现当前 token 既不是也不是-应该返回还是不返回答案取决于当前 token 是否在 FOLLOW(E) 里。FOLLOW(E) 是“在所有推导过程中可能紧跟在 E 后面的终结符集合”。对我们的文法E 只出现在 E 的末尾而 E 可能出现在括号里或者输入末尾所以 FOLLOW(E) { ), END }。也就是说当 expr_prime() 看到)或 END 时应该走 ε 分支直接返回如果看到的是 NUMBER 或(说明输入里有问题比如23 4这种两个表达式粘连应当报错而不是默默结束。实际代码里递归下降通常不显式查 FOLLOW 集合而是用“if 都不匹配就 return”隐式完成 ε 分支。这确实能跑但理解 FOLLOW 集合还是有必要的它决定了出错时该报错还是该认为当前表达式已经结束。实验报告里要求写 FIRST/FOLLOW 集合不只是为了应付理论题也是为了让这段隐式逻辑落到纸面上方便排查。2.4 为什么手写递归下降而不是用表驱动或 LR(1)编译原理课程里通常先讲 LL(1) 分析表再讲 LR(1)很多同学会问既然有表驱动这种通用方案为什么实验还要求手写递归下降我的看法是表驱动的 LL(1) 把选择逻辑集中到了一张二维表和一个驱动循环里代码通用但出错时很难定位——你看到的是栈顶符号和输入符号还得反查是哪个非终结符卡住像看一个黑匣子。递归下降则把每一步选择显式写在代码里单步调试时直接走进对应的 if 分支错误位置天然精确到函数和 token。LR(1) 能处理的文法范围比 LL(1) 大比如左递归文法可以直接用不需要改写。但 LR(1) 分析器的状态机手工构造太复杂实验课里通常用 yacc 这类工具生成不利于理解语法分析的核心思想。递归下降的工程价值也比较高很多解析 JSON、配置文件、DSL 的库都是手写递归下降而不是套用生成器。如果你交实验用的是 Java这套逻辑的 Java 版不过就是把 Python 的 if 分支换成 switch把返回值换成 double 或 AST 节点文法处理完全一致。所以我一般建议实验先做递归下降把“非终结符 ↔ 函数”这个映射关系吃透后面看任何 LL/LR 工具都顺眼得多。3. 递归下降分析的最小 Python 实现四则运算器的完整代码3.1 先设计文法消除左递归、留好 ε 分支写代码之前先把文法确定下来这一步跳过会踩大坑。四则运算带优先级最自然的文法写法如下E → E T | E - T | TT → T * F | T / F | FF → ( E ) | NUMBER这个文法能表达优先级但它不适合递归下降。原因在于 E 的产生式右部最左符号还是 E左递归会让expr()函数一进入就再次调用自己永不停止。需要按标准办法消除左递归形如 A → Aα | β 的产生式改写为 A → βAA → αA | ε。改写后的四则运算文法为E → T EE → T E | - T E | εT → F TT → * F T | / F T | εF → ( E ) | NUMBER这里我特意把和-拆成了 E 的两个独立分支把*和/拆成了 T 的两个独立分支而不是写成( | -) T E。虽然合并写法也能跑但拆开后 FIRST 集合更清楚后面错误恢复和报错信息也更好定位。NUMBER 按浮点数处理先不考虑变量和一元负号保持最小可运行。3.2 词法接口分析器只依赖 peek 和 match语法分析器不关心 token 是怎么切出来的它只需要两个操作peek() 看当前 token 不消费match() 确认当前 token 类型并消费。词法器把输入字符串变成 token 数组并用一个 END token 作为结束哨兵这样分析器不会数组越界。import re from dataclasses import dataclass # ---------- 词法部分 ---------- dataclass class Token: kind: str # NUMBER PLUS MINUS STAR SLASH LPAREN RPAREN END text: str # 原始文本NUMBER 时是数字字符串 pos: int # 在源串中的起始位置 _NUM_RE re.compile(r\d(\.\d)?) def tokenize(source): tokens [] i 0 while i len(source): c source[i] if c.isspace(): i 1 continue if c.isdigit(): m _NUM_RE.match(source, i) tokens.append(Token(NUMBER, m.group(), i)) i m.end() continue if c in -*/(): kind {: PLUS, -: MINUS, *: STAR, /: SLASH, (: LPAREN, ): RPAREN}[c] tokens.append(Token(kind, c, i)) i 1 continue raise SyntaxError(fposition {i}: unexpected char {c!r}) tokens.append(Token(END, , len(source))) return tokens这段词法器只处理数字、四则运算符和括号。数字用的正则\d(\.\d)?可以匹配2、2.5不能匹配.5和1.2.3对实验场景足够。位置 pos 记的是 token 在源串里的起始下标后面报错信息会用到。空白字符直接跳过不会被当成语法单位。注意我把运算符映射写成了字典而不是一长串 if-elif这样新增 token 类型时只需要在字典加一项词法器主体不用动。分析器的 peek 和 match 在 3.3 节一起给出。3.3 核心递归函数与运行结果语法分析器如下一个非终结符一个方法方法名和文法左部一致。factor 是最底层直接消费数字或括号。# ---------- 语法分析部分 ---------- class Parser: def __init__(self, tokens, traceFalse): self.tokens tokens self.pos 0 self.trace trace def peek(self): return self.tokens[self.pos] def advance(self): t self.tokens[self.pos] self.pos 1 return t def match(self, kind): if self.peek().kind kind: return self.advance() raise SyntaxError( fposition {self.peek().pos}: expect {kind}, got {self.peek().kind}) def expr(self): E - T E return self.expr_prime(self.term()) def expr_prime(self, acc): E - T E | - T E | ε if self.trace: print(fexpr_prime sees {self.peek().kind} at {self.peek().pos}) if self.peek().kind PLUS: self.advance() right self.term() return self.expr_prime(acc right) if self.peek().kind MINUS: self.advance() right self.term() return self.expr_prime(acc - right) return acc # ε 分支 def term(self): T - F T return self.term_prime(self.factor()) def term_prime(self, acc): T - * F T | / F T | ε if self.peek().kind STAR: self.advance() right self.factor() return self.term_prime(acc * right) if self.peek().kind SLASH: self.advance() right self.factor() return self.term_prime(acc / right) return acc def factor(self): F - ( E ) | NUMBER if self.peek().kind NUMBER: return float(self.advance().text) if self.peek().kind LPAREN: self.advance() val self.expr() self.match(RPAREN) return val raise SyntaxError( fposition {self.peek().pos}: expect NUMBER or LPAREN, fgot {self.peek().kind}) def calc(source, traceFalse): tokens tokenize(source) parser Parser(tokens, trace) result parser.expr() if parser.peek().kind ! END: raise SyntaxError( fposition {parser.peek().pos}: unexpected trailing f{parser.peek().kind}) return result if __name__ __main__: for s in [23*4, 8-3-2, (23)*(4-1), 2]: try: print(f{s} {calc(s)}) except SyntaxError as e: print(f{s} - SyntaxError: {e})运行这段代码的输出是23*4 14.0 8-3-2 3.0 (23)*(4-1) 15.0 2 - SyntaxError: position 2: expect NUMBER or LPAREN, got END这里有一个关键设计expr_prime和term_prime的第一个参数acc是累积值。对8-3-2expr_prime的处理过程是先用8作为 acc遇到-时取到右操作数3递归调用expr_prime(8-3)下一层遇到-取右操作数2递归调用expr_prime(5-2)最终得到 3。这样减法从左往右计算避免了右递归文法天然带来的右结合问题。如果你把expr_prime的返回值直接写成right而不是acc right8-3-2就会算出 7这是很多教材代码的经典坑第 5 章会再展开。提示这段代码一次只分析一个表达式。如果实验要求一次读入多行建议把每一行单独调用calc()不要试图在一个 token 流里塞多个表达式否则你需要为语句列表单独设计文法。4. 从“能算结果”到“能交作业”左递归消除、错误恢复与 AST 构建4.1 左递归会让递归下降直接死循环先改文法前面说过带左递归的文法会让函数无限调用自己但实际实验里很多人还是会踩原因是把课本上的表达式文法原样抄进了代码。出现这种现象说明对“左递归为什么不能用于自顶向下分析”还没有建立直觉。自顶向下分析的每一步都要用当前输入 token 决定下一步推导而 A → Aα 这个产生式的最左符号还是 A分析器在还没有消费任何输入的情况下又回到同一个状态于是永远停在原地。通用的消除办法是A → Aα | β 改写为 A → βAA → αA | ε。其中 α 不能是空串。对 E → E T | Tβ 就是Tα 是 T改写得到 E → T EE → T E | ε。如果一条规则里有多个左递归项比如 A → Aα | Aβ | γ需要分别展开成 A → αA | βA | ε。间接左递归更隐蔽一些比如 A → B cB → A d二者互相依赖表面上没有直接左递归实际推导时 A ⇒ B c ⇒ A d c还是左递归。消除间接左递归的做法是给非终结符排个序逐个把右部最左的非终结符替换成它的产生式最后再消除直接左递归。这些流程在编译原理教材第三章的课后题里很常见实验前手推一两道题会有帮助。一个容易忽视的点是消除左递归改写的是文法但文法改写了语义未必自动保持。E - - T E会让减号在语法树上呈右递归结构如果直接按教材教的“返回右子树”构建减法就变右结合。我们的做法是在递归函数里用累加参数做语义修正这是工程上常见的把“文法改写”和“语义动作”分开处理的方式。4.2 错误恢复与同步连续输入多行表达式时别卡死在第一行第 3 章的calc()遇到语法错误会直接抛异常这是正确行为但实验里往往要求分析器报错后还能继续处理后续输入。比如读入一个测试文件里面有一行是12不应该让整个程序崩溃。这时需要给分析器加错误恢复。最常用的是 panic-mode 恢复当某个 match 失败时放弃从当前非终结符开始的分析把输入流跳过直到遇到一个“同步标记”才重新开始分析。同步标记通常选择层次清晰的终结符比如分号、右括号、END。下面的synchronize方法就是一种实现def synchronize(self, sync_kinds(END, RPAREN)): # 出错后一直跳到同步标记处保证至少消费一个 token while self.peek().kind not in sync_kinds: self.advance()在调用端用 try/except 包住expr()捕获异常后执行 synchronizedef parse_until_ends(tokens): parser Parser(tokens) results [] while parser.peek().kind ! END: try: results.append(parser.expr()) if parser.peek().kind ! END: raise SyntaxError( fposition {parser.peek().pos}: unexpected {parser.peek().kind}) except SyntaxError as e: print(error:, e) parser.synchronize() return results这里的同步集合选得比较保守只有 END 和 RPAREN。选 RPAREN 的原因是如果错误发生在括号表达式内部右括号是一个明确的边界跳过它能让分析器继续往下读。实际文法的同步集合一般还要加入语句终结符比如分号。我自己做实验时更倾向于把“一条语句一个分析器”作为默认设计这样每行输入独立分析错误恢复也简单——本行出错就只报本行下一行重新开始。只有要求必须在一个 token 流里解析多条语句时才需要同步集合这种复杂机制。注意同步集合不要选得过大。如果把 NUMBER 也放进同步集合分析器会把真正的表达式开头当作错误噪声吞掉导致后续错误全部漏报。宁可错报一条也不要吞掉一条。4.3 如果想要语法树而不是结果值把语义动作换掉递归下降分析器返回浮点数能通过实验的计算器要求但很多编译原理实验的下一阶段是符号表和中间代码分析器需要产出语法树。此时应该把“递归下降的骨架”和“语义动作”分开。骨架是每个非终结符函数确定产生式分支调用下一层按顺序匹配终结符。语义动作是遇到数字建叶子节点遇到运算符建二元节点。AST 节点可以这样定义dataclass class Num: value: float dataclass class BinOp: op: str left: object right: object对应地factor()里把return float(...)改成return Num(float(...))括号分支不变expr_prime()改为拼接节点def expr_prime(self, left): if self.peek().kind in (PLUS, MINUS): op self.advance().kind right self.term() return self.expr_prime(BinOp(op, left, right)) return left注意这个版式对8-3-2生成的树是BinOp(-, BinOp(-, 8, 3), 2)依然是左结合。原因是每一层都把新运算符放在更外层左边的旧结果整体成为新节点的左子树。这和教材里说的“右递归文法生成右结合树”并不矛盾——教材讲的是直接按产生式原样建树而我们在这里改变了语义动作的拼接方向。理解这个区别才能在实验报告里把结合性问题讲清楚而不是只说“我调了一下就对了”。5. 递归下降分析最常翻车的 5 个细节与排查思路5.1 减法变成右结合结果对不上现象输入8-3-2期望输出 3实际输出 7括号也没写错文法也没写错。原因右递归产生式E - - T E天然把减号变成右结合。如果不做语义修正直接把expr_prime写成return self.expr_prime(right)那么8-3-2会被解释成8-(3-2)。解决像 3.3 节那样使用累加参数acc把左操作数一直带到递归深处每次计算acc - right而不是right。这个技巧同样适用于除法。排错时可以打开traceTrue看递归调用顺序如果发现第二次进入expr_prime时 acc 是 5 而不是 8说明累积参数写漏了。5.2 优先级颠倒23*4 算出 20现象简单测试都过一到混合运算就错23*4得到 20 而不是 14。原因优先级是通过“谁在上层、谁在下层”实现的。正确的层级是 expr 在最上层调用 termterm 调用 factor如果图省事把expr直接拆成factor (|-) factor乘法就没有机会先于加法被处理。解决严格留出三层结构。expr 层只认加减term 层只认乘除factor 层只认数字和括号。凡是遇到处理的地方右侧操作数必须调 term 而不是 factor处理*的地方右侧操作数必须调 factor。记住一句话优先级越高的运算符离 factor 越近。5.3 失败后不消费 token程序卡在死循环现象输入2之后程序不报错退出而是反复打印同一行错误信息或者 CPU 飙到 100%。原因某个分支判断失败后既没有抛异常也没有让self.pos前进外层循环每次拿到同一个 token 重试。例如把expr_prime写成看到 PLUS 就进分支但分支里term()失败后异常被吞掉然后循环又回到 expr_prime 入口。解决保证“一条执行路径要么消费至少一个 token要么显式返回”。在递归版本里进入 PLUS 分支后先self.advance()消费运算符再调term()在循环版本里每轮循环的入口处必须已经消费了一个操作符。最容易犯的错是把peek()当match()用忘记调advance()。发现死循环时先看self.pos是否变化这一步能定位九成问题。5.4 括号不匹配时报错位置指向错误现象输入(23错误信息说 END 处期望 RPAREN输入23)错误信息反而报 trailing tokens。位置虽然没有越界但没有指出最关键的“左括号没闭合”。原因factor()在见到 LPAREN 后调expr()直到expr()完整消费23后才去match(RPAREN)此时已经是 END报错位置自然在末尾。对用户来说他们想知道左括号在哪个位置开的。解决在进入 LPAREN 分支时记录左括号 pos构造专门的异常类型携带这个上下文。比如自定ParseError(msg, pos)在factor()里写成if self.peek().kind LPAREN: open_pos self.peek().pos self.advance() val self.expr() try: self.match(RPAREN) except SyntaxError as e: raise ParseError(fleft paren at {open_pos} never closed; {e}, open_pos)这样输出会变成left paren at 0 never closed; position 4: expect RPAREN, got END一眼就能定位到括号配对问题。5.5 长表达式把调用栈压爆现象用脚本生成一条一万个数字相加的表达式程序直接 RecursionError或者 Java 版抛 StackOverflowError。原因递归下降对每个二元运算符都形成一层函数调用右递归文法会在运行时叠出与操作数数量成正比的栈深度。Python 默认递归限制只有 1000 层超长表达式必炸。解决把尾递归改成 while 循环。以expr_prime为例def expr_prime(self, left): while self.peek().kind in (PLUS, MINUS): op self.advance().kind right self.term() left BinOp(op, left, right) if build_ast else left right return left这个循环版本没有递归任意长度的连续加减都能处理而且每轮把新运算符放在外层仍然保持左结合。对term_prime做同样处理。需要注意循环版本的下降方向没变right仍然通过term()取优先级不受影响。不要为了省事用sys.setrecursionlimit硬抬栈上限那只适合课堂演示不适合真正工程。6. 实验做完之后的进阶功课用对拍验证、留出符号表接口、把递归下降到工程代码6.1 用随机表达式对拍比手写例子更能暴露问题手写测试用例只能覆盖你想到的情况随机生成表达式再和系统计算器对拍能更快暴露优先级和结合性的边角问题。下面这段代码生成一万个随机四则表达式用 Python 的 eval 做基准逐条对比import random def random_expr(depth0): if depth 3 or random.random() 0.3: return str(random.randint(0, 9)) op random.choice([, -, *, /]) return f({random_expr(depth 1)}{op}{random_expr(depth 1)}) for _ in range(10000): s random_expr() try: mine calc(s) ref eval(s) except (SyntaxError, ZeroDivisionError): continue if abs(mine - ref) 1e-9: print(mismatch:, s, mine, ref) breakrandom_expr通过深度限制控制表达式规模30% 概率提前生成数字叶子避免全是嵌套导致跑太慢。对拍只能证明“算出来的值对”不能证明语法树结构完全符合预期如果要验证结构可以顺手把 AST 序列化打印和手推的树做比对。6.2 给符号表留出接口别在语法分析阶段顺手建表编译原理实验做到语法分析之后下一站通常是符号表和中间代码。很多同学会把“遇到变量就登记”的逻辑直接写进factor()里语法分析和语义分析混成一团。我一般习惯在分析器里只产出 AST符号表放到语义分析阶段单独遍历 AST 来构建。这样改文法的时候不需要碰符号表改符号表的时候也不会破坏语法分析。如果实验报告要求展示符号表内容可以写一个独立的遍历函数按 AST 节点顺序输出变量名和类型和分析阶段完全解耦。6.3 一个我长期保留的检查习惯每次写完递归下降分析先不急着跑对拍而是把文件开头的产生式注释再人肉推一遍拿一个简单输入从开始符号出发按 FIRST 集合选分支确认每条路径要么消费 token 要么以 ε 返回。这个动作花不了两分钟但能提前发现大部分左递归和优先级问题。代码提交到编译原理实验之前我会把traceTrue打开跑两个用例看到expr_prime、term_prime的调用顺序和推导过程一致才认为分析器结构是对的。我吃过最大的亏是把左递归文法直接抄进函数在递归入口打印调试信息结果终端刷了几万行才想起来是文法本身的问题。后来给自己定了条规矩先写文法后写代码先算 FIRST后写 if。这条规矩让我少加了很多班希望你也能用上。本文还有配套的精品资源点击获取