上下文无关文法 (CFG) 实战：3步构建无二义性四则运算语法树

上下文无关文法实战：三步构建无二义性四则运算语法树

在编程语言和数学表达式处理中，上下文无关文法（CFG）扮演着至关重要的角色。它不仅是编译原理的理论基础，更是解决实际语法解析问题的利器。本文将以四则运算表达式为例，展示如何设计无二义性的CFG，并通过Python代码实现语法树的构建。

1. 理解上下文无关文法基础

上下文无关文法由四个部分组成：

  • 终结符（Terminals）：构成语言基本元素的符号，如数字、运算符
  • 非终结符（Non-terminals）：表示语法结构的变量
  • 产生式规则（Productions）：定义非终结符如何展开
  • 开始符号（Start symbol）：语法分析的起点

四则运算的简单文法可能如下：

Expr → Expr + Term | Expr - Term | Term Term → Term * Factor | Term / Factor | Factor Factor → ( Expr ) | number

这种分层结构有效解决了运算符优先级问题：

  • Factor处理括号和基本单元
  • Term处理乘除运算
  • Expr处理加减运算

2. 消除二义性的关键技巧

原始文法E → E + E | E * E | (E) | number存在二义性，无法确定运算顺序。通过引入层级结构消除二义性：

# 优先级从低到高分层 grammar = { 'Expr': [['Expr', '+', 'Term'], ['Expr', '-', 'Term'], ['Term']], 'Term': [['Term', '*', 'Factor'], ['Term', '/', 'Factor'], ['Factor']], 'Factor': [['(', 'Expr', ')'], ['number']] }

结合性处理方案：

  • 左递归实现左结合（如Expr → Expr + Term）
  • 右递归实现右结合（如Expr → Term + Expr）

3. Python实现语法树构建

以下是完整的语法解析器实现：

import re class TreeNode: def __init__(self, value): self.value = value self.children = [] def add_child(self, node): self.children.append(node) def __str__(self, level=0): ret = " " * level + repr(self.value) + "\n" for child in self.children: ret += child.__str__(level+1) return ret class Parser: def __init__(self, expression): self.tokens = re.findall(r'\d+|[()+*/-]', expression) self.current_token = None self.next_token() def next_token(self): if self.tokens: self.current_token = self.tokens.pop(0) else: self.current_token = None return self.current_token def parse(self): tree = self.parse_expr() if self.current_token is not None: raise SyntaxError("Unexpected token") return tree def parse_expr(self): node = self.parse_term() while self.current_token in ('+', '-'): op = self.current_token self.next_token() right = self.parse_term() new_node = TreeNode(op) new_node.add_child(node) new_node.add_child(right) node = new_node return node def parse_term(self): node = self.parse_factor() while self.current_token in ('*', '/'): op = self.current_token self.next_token() right = self.parse_factor() new_node = TreeNode(op) new_node.add_child(node) new_node.add_child(right) node = new_node return node def parse_factor(self): if self.current_token == '(': self.next_token() node = self.parse_expr() if self.current_token != ')': raise SyntaxError("Expected ')'") self.next_token() return node elif self.current_token.isdigit(): node = TreeNode(self.current_token) self.next_token() return node else: raise SyntaxError("Unexpected token") # 示例使用 expression = "(1+2)*3" parser = Parser(expression) syntax_tree = parser.parse() print(syntax_tree)

输出结果示例：

'*' '+' '1' '2' '3'

4. 文法设计与调试技巧

常见问题排查表：

问题现象可能原因解决方案
无法识别括号表达式Factor规则未正确定义检查Factor → ( Expr )规则
运算符优先级错误层级结构不正确确保乘除在加减上层
右结合变成左结合递归方向错误将左递归改为右递归

扩展支持更多运算符：

# 添加指数运算（右结合） grammar['Term'].append(['Factor', '^', 'Term'])

通过这种结构化方法，我们可以逐步构建复杂的语法解析器，同时保持代码的可维护性和扩展性。