递归下降子程序 Python 实现：手写 Parser 解析习题4.2表达式文法

递归下降子程序 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. 记忆化Memoizationfrom functools import lru_cache class Parser: lru_cache(maxsizeNone) 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来说手写递归下降解析器仍是最佳入门选择。