递归下降子程序 Python 实现：手写 Parser 解析表达式文法
1. 从理论到实践的跨越
当我们谈论编译原理时，很多人脑海中浮现的是晦涩难懂的数学符号和抽象概念。但今天，我们将打破这种刻板印象，用Python代码将编译原理中最经典的递归下降分析法具象化。不同于教科书上的纯理论推导，本文会带你用不到200行代码实现一个能实际解析加减运算的语法分析器。
递归下降分析法的核心思想很简单：为文法中的每个非终结符编写一个对应的解析函数。这些函数会相互调用，形成一种"下降"的解析过程。想象你在解一道数学题时，先把大问题拆解成小问题，再逐个击破——这正是递归下降的精髓。
在开始编码前，我们需要明确几个关键概念：
- 终结符：不能再被拆分的语法单元，如数字、运算符
- 非终结符：可以由其他符号组成的语法结构，如表达式
- FIRST集：一个非终结符可能推导出的首个终结符集合
- FOLLOW集：可能跟随在某个非终结符后的终结符集合
2. 表达式文法解析
我们以王原生《编译原理》习题4.2的表达式文法为例：
E → TE' E' → +E | ε T → FT' T' → T | ε F → PF' F' → *F' | ε P → (E) | a | b | ∧这个文法虽然看起来复杂，但拆解后其实很直观：
- E代表表达式，由项T和后续表达式E'组成
- E'处理加法运算
- T代表项，由因子F和后续项T'组成
- F代表因子，由基本单元P和后续因子F'组成
- P是最基本的单元，可以是括号表达式或变量
关键点：这个文法是LL(1)的，意味着我们只需要向前看一个token就能确定使用哪个产生式，无需回溯。
3. Python实现核心架构
我们先搭建解析器的骨架代码：
class Parser: def __init__(self, tokens): self.tokens = tokens self.current = 0 self.errors = [] def parse(self): try: return self.E() except ParseError as e: self.errors.append(str(e)) return None def E(self): """表达式 E → TE'""" left = self.T() return self.E_prime(left) def E_prime(self, left): """E' → +E | ε""" if self.match('+'): operator = self.previous() right = self.E() return Binary(left, operator, right) return left # 其他方法类似...这个架构有几个关键设计：
- Token流处理：将输入字符串转换为token序列
- 错误恢复：遇到错误时记录而非直接崩溃
- 递归调用：各非终结符对应的函数相互调用
4. 完整递归下降实现
下面是完整的解析器实现，包含所有非终结符的处理：
import sys from enum import Enum, auto class TokenType(Enum): NUMBER = auto() PLUS = auto() STAR = auto() LEFT_PAREN = auto() RIGHT_PAREN = auto() IDENTIFIER = auto() EOF = auto() class Token: def __init__(self, type, lexeme, literal, line): self.type = type self.lexeme = lexeme self.literal = literal self.line = line class Expr: pass class Binary(Expr): def __init__(self, left, operator, right): self.left = left self.operator = operator self.right = right class Grouping(Expr): def __init__(self, expression): self.expression = expression class Literal(Expr): def __init__(self, value): self.value = value class Variable(Expr): def __init__(self, name): self.name = name class Parser: def __init__(self, tokens): self.tokens = tokens self.current = 0 def parse(self): try: return self.expression() except ParseError: return None def expression(self): return self.E() def E(self): left = self.T() return self.E_prime(left) def E_prime(self, left): if self.match(TokenType.PLUS): operator = self.previous() right = self.E() return Binary(left, operator, right) return left def T(self): left = self.F() return self.T_prime(left) def T_prime(self, left): if self.check(TokenType.STAR): operator = self.advance() right = self.T() return Binary(left, operator, right) return left def F(self): left = self.P() return self.F_prime(left) def F_prime(self, left): if self.match(TokenType.STAR): operator = self.previous() right = self.F_prime(left) # 右递归处理 return Binary(left, operator, right) return left def P(self): if self.match(TokenType.LEFT_PAREN): expr = self.expression() self.consume(TokenType.RIGHT_PAREN, "Expect ')' after expression.") return Grouping(expr) if self.match(TokenType.IDENTIFIER): return Variable(self.previous().literal) if self.match(TokenType.NUMBER): return Literal(self.previous().literal) raise self.error(self.peek(), "Expect expression.") # 辅助方法... def match(self, *types): for type in types: if self.check(type): self.advance() return True return False def check(self, type): if self.is_at_end(): return False return self.peek().type == type def advance(self): if not self.is_at_end(): self.current += 1 return self.previous() def is_at_end(self): return self.peek().type == TokenType.EOF def peek(self): return self.tokens[self.current] def previous(self): return self.tokens[self.current - 1] def consume(self, type, message): if self.check(type): return self.advance() raise self.error(self.peek(), message) def error(self, token, message): print(f"[line {token.line}] Error at '{token.lexeme}': {message}") return ParseError()5. 词法分析与FIRST/FOLLOW集
递归下降分析器的正确性依赖于FIRST和FOLLOW集。让我们计算关键非终结符的集合：
FIRST集计算：
FIRST(E) = FIRST(T) = FIRST(F) = FIRST(P) = { '(', identifier, number } FIRST(E') = { '+', ε } FIRST(T') = { '*', ε } FIRST(F') = { '*', ε }FOLLOW集计算：
FOLLOW(E) = { ')', EOF } FOLLOW(E') = FOLLOW(E) = { ')', EOF } FOLLOW(T) = FIRST(E') ∪ FOLLOW(E') = { '+', ')', EOF } FOLLOW(T') = FOLLOW(T) = { '+', ')', EOF } FOLLOW(F) = FIRST(T') ∪ FOLLOW(T') = { '*', '+', ')', EOF } FOLLOW(F') = FOLLOW(F) = { '*', '+', ')', EOF } FOLLOW(P) = FIRST(F') ∪ FOLLOW(F') = { '*', '+', ')', EOF }这些集合决定了何时选择ε产生式。例如在E'中，当看到')'或EOF时选择ε，因为它们在FOLLOW(E')中。
6. 测试与验证
让我们测试解析器处理不同表达式的情况：
# 测试用例 test_cases = [ ("a + b", True), ("a * b + c", True), ("a * (b + c)", True), ("a +", False), # 不完整表达式 ("(a + b", False) # 括号不匹配 ] for src, should_pass in test_cases: scanner = Scanner(src) tokens = scanner.scan_tokens() parser = Parser(tokens) expr = parser.parse() if (expr is not None) == should_pass: print(f"✓ Test passed: {src}") else: print(f"✗ Test failed: {src}") if expr is None: print(" Got None, expected parse tree") else: print(" Got parse tree, expected None")输出示例：
✓ Test passed: a + b ✓ Test passed: a * b + c ✓ Test passed: a * (b + c) ✗ Test failed: a + Got None, expected parse tree ✗ Test failed: (a + b Got None, expected parse tree7. 错误处理与恢复
良好的错误处理能让解析器更健壮。我们在Parser类中添加错误恢复机制：
class Parser: def __init__(self, tokens): self.tokens = tokens self.current = 0 self.had_error = False def synchronize(self): """错误恢复：跳过当前语句""" self.advance() while not self.is_at_end(): if self.previous().type == TokenType.SEMICOLON: return if self.peek().type in ( TokenType.CLASS, TokenType.FUN, TokenType.VAR, TokenType.FOR, TokenType.IF, TokenType.WHILE, TokenType.PRINT, TokenType.RETURN ): return self.advance() def error(self, token, message): if token.type == TokenType.EOF: report(token.line, " at end", message) else: report(token.line, f" at '{token.lexeme}'", message) return ParseError()这种同步恢复策略能帮助解析器在遇到错误后继续分析后续代码，而非直接停止。
8. 性能优化与实践技巧
虽然递归下降解析器直观易懂，但在处理复杂文法时可能遇到性能问题。以下是几个优化方向：
1. 记忆化（Memoization）：
from functools import lru_cache class Parser: @lru_cache(maxsize=None) def E(self): left = self.T() return self.E_prime(left)2. 尾递归优化： 对于右递归的产生式（如F' → *F' | ε），可改写为循环：
def F_prime(self, left): while self.match(TokenType.STAR): operator = self.previous() right = self.F() left = Binary(left, operator, right) return left3. 预读缓存：
def __init__(self, tokens): self.tokens = tokens self.current = 0 self.lookahead = [None] * 3 # 3个token的预读缓存 self.fill_lookahead()递归下降分析法虽然简单，但能处理大多数LL(1)文法。当需要处理更复杂的文法时，可以考虑使用更强大的解析器生成工具如ANTLR。但对于学习编译原理和实现小型DSL来说，手写递归下降解析器仍是最佳入门选择。
