如何修改布尔表达式文法并基于语法树生成SymPy布尔表达式？

我想要实现一个用于数字电路设计的复杂布尔逻辑表达式解析器，但目前遇到了问题。我当前的文法如下：

start: equation

equation: SYMBOL
        | expression

expression: nottk

nottk: "!" SYMBOL

and: expression "*" expression


SYMBOL: /[A-Za-z]/

我知道这份文法并不完整，但原本想先让周边代码能正常运行。目前我使用Transformer将符号转换为SymPy符号，代码如下：

class SymbolTransformer(Transformer):
    def SYMBOL(self, token: Token):
        """Converts every symbol into a sympy symbol"""
        return token.update(value=sympy.symbols(f'{token.value}'))

我尝试用Transformer实现全部逻辑，但由于非终结符的工作机制不同，未能成功。现咨询：应如何修改我的文法，或采用何种方式基于语法树生成SymPy表达式？

第一步：修正文法结构 #

现有文法存在几个核心问题：

1. and是Python关键字，不能用作非终结符名称，需改用and_expr这类合法命名
2. 缺少正确的递归结构，无法处理多层嵌套或连续运算的复杂表达式
3. 未定义运算符优先级（布尔逻辑中优先级通常为：非>与>或），且未覆盖完整的布尔运算类型

以下是修正后的完整文法（以Lark语法为例，适配主流解析器框架）：

start: expr

expr: or_expr
or_expr: and_expr ( "+" and_expr )*   # 或运算，优先级最低
and_expr: not_expr ( "*" not_expr )* # 与运算，优先级中等
not_expr: "!" not_expr | SYMBOL      # 非运算，优先级最高，支持嵌套非（如!!A）

SYMBOL: /[A-Za-z]/

该文法通过分层结构天然实现了运算符优先级，同时支持嵌套表达式和连续的与/或运算。

第二步：扩展Transformer生成SymPy表达式 #

利用SymPy提供的sympy.Not、sympy.And、sympy.Or构建布尔表达式，为每个非终结符实现对应的处理方法：

from lark import Transformer, Token
import sympy

class BoolExprTransformer(Transformer):
    def SYMBOL(self, token: Token):
        return sympy.symbols(token.value)
    
    def not_expr(self, items):
        # items要么是["!", not_expr]，要么是[SYMBOL]
        if len(items) == 2:
            return sympy.Not(items[1])
        return items[0]
    
    def and_expr(self, items):
        # items结构为[not_expr, "*", not_expr, "*", not_expr, ...]
        operands = [items[i] for i in range(0, len(items), 2)]
        return sympy.And(*operands)
    
    def or_expr(self, items):
        # 逻辑同and_expr，提取所有运算数
        operands = [items[i] for i in range(0, len(items), 2)]
        return sympy.Or(*operands)
    
    def expr(self, items):
        return items[0]

第三步：测试解析流程 #

结合解析器与Transformer，即可将布尔表达式字符串转换为SymPy对象：

from lark import Lark

# 初始化解析器（GRAMMAR为上面修正后的文法字符串）
parser = Lark(GRAMMAR, parser="lalr")
transformer = BoolExprTransformer()

# 测试示例
test_expr = "!A*B+C*!D"
tree = parser.parse(test_expr)
sympy_expr = transformer.transform(tree)

print(sympy_expr)  # 输出：And(Not(A), B) | And(C, Not(D))

关键注意点 #

• 文法分层是确保运算符优先级正确的核心，避免出现A*B+C被误解析为A*(B+C)这类歧义
• Transformer的方法名必须与文法中的非终结符严格对应，处理时需明确语法树的结构（如and_expr的items是运算数与运算符交替出现）
• 若需支持括号、常量0/1等扩展语法，只需在文法中添加对应规则，再在Transformer中补充处理逻辑即可

内容的提问来源于stack exchange，提问作者Stefan Schmelz