huhu
Blog 布尔逻辑表达式取反

布尔逻辑表达式取反

huhu · 约 13 分钟

最近有这样一个需求，我需要对一个复合字符串 PHP 逻辑表达式进行取反，得到取反后的字符串逻辑表达式，例子如下：

// 原表达式
"NOT (!wp_verify_nonce($json_api->query->nonce, $nonce_id)) AND NOT (!validate_username($username) || in_array($username, $invalid_usernames))AND NOT (!validate_username($username) || in_array($username, $invalid_usernames))",

// 取反后的表达式
"(wp_verify_nonce($json_api->query->nonce, $nonce_id)) AND (validate_username($username) && (!in_array($username, $invalid_usernames))) AND (validate_username($username) && (!in_array($username, $invalid_usernames)))",

由于我需要进行批量操作，所以需要一个程序能够自动化实现这种转化。首先的想法是，先考虑如何使用 Python 实现简单的字符串逻辑表达式取反操作，比如：

Original expression: (!(!A || !(B && C)) && (D || !E))

Negated expression: ((!A || !(B && C)) || (!D && E))

如果能够实现上述功能，那就可以先将字符串 PHP 逻辑表达式进行抽象，转化为符号表达的逻辑表达式，然后再进行取反，最后通过第一步骤的字典再映射回去。所以，重点是实现符号字符串逻辑表达式的取反操作。

符号字符串逻辑表达式的 AST 抽象

处理逻辑表达式并不是简单的从左到右进行处理，逻辑表达式中的运算符有不同的优先级：

  1. 括号 ()

    • 最高优先级

    • 用于改变默认的运算顺序

    • 可以嵌套使用

  2. 非（NOT）

    • 一元运算符

    • 对操作数取反

    • 符号表示：¬, !, NOT, ~

  3. 与（AND）

    • 二元运算符

    • 所有操作数为真时结果为真

    • 符号表示：∧, &&, AND, ·

  4. 或（OR）

    • 二元运算符

    • 任一操作数为真时结果为真

    • 符号表示：∨, ||, OR, +

所以需要想一种办法，先将逻辑表达式抽象出一个运算优先级分明的表示，比如针对之前提到的例子 (!(!A || !(B && C)) && (D || !E)) ，最外层的运算符应该是第二个 && ，即表达式的结果一定是左侧表达式 !(!A || !(B && C)) 的结果和右侧表达式 (D || !E) 的结果的 && 操作。然后同理，可以同样处理左右两侧表达式，有些像数据机构中的树的算法思想，所以可不可以将其转化为一棵树呢？

https://blog.51cto.com/u_16213467/11832658

https://blog.51cto.com/u_16213467/11832658

我先搜索有没有类似的实现，发现有一个博客介绍到将字符串逻辑表达式转化为 AST，也就是抽象语法树，但是并没有给出具体的输入输出例子，也不清楚得到的 AST 是什么样的？所以我直接给 AI 提了这个需求，得到的答案如下（当然经过了多次修改哈 🤪）:

# 语法解析（Parsing）
# 定义简单的递归下降解析器
# Grammar (简化版):
# EXPR := TERM { 'or' TERM }
# TERM := FACTOR { 'and' FACTOR }
# FACTOR := 'not' FACTOR | VARIABLE | '(' EXPR ')'
# VARIABLE := 字母开头的标识符

def parse_expression(tokens, pos=0):
    node, pos = parse_term(tokens, pos)
    while pos < len(tokens) and tokens[pos] == "or":
        op = tokens[pos]
        right, pos = parse_term(tokens, pos + 1)
        node = ("or", node, right)
    return node, pos


def parse_term(tokens, pos=0):
    node, pos = parse_factor(tokens, pos)
    while pos < len(tokens) and tokens[pos] == "and":
        op = tokens[pos]
        right, pos = parse_factor(tokens, pos + 1)
        node = ("and", node, right)
    return node, pos


def parse_factor(tokens, pos=0):
    if pos < len(tokens) and tokens[pos] == "not":
        # not FACTOR
        node, pos = parse_factor(tokens, pos + 1)
        return ("not", node), pos
    elif pos < len(tokens) and tokens[pos] == "(":
        # (EXPR)
        node, pos = parse_expression(tokens, pos + 1)
        if pos >= len(tokens) or tokens[pos] != ")":
            raise ParseError("Missing closing parenthesis")
        return node, pos + 1
    else:
        # variable
        if pos < len(tokens):
            t = tokens[pos]
            # 简单判断是变量
            if t not in ("and", "or", "not", "(", ")"):
                return t, pos + 1
        raise ParseError("Unexpected token at factor")


def parse(expr):
    tokens = tokenize(expr)
    print("tokens:", tokens)
    node, pos = parse_expression(tokens, 0)
    if pos != len(tokens):
        raise ParseError("Extra tokens after valid expression")
    return node

文法规则

文法规则是一组用于描述特定语言结构的规则。它们定义了如何将语言中的不同元素组合在一起形成有效的语句或表达式。可以将文法规则想象成语言的“骨架”，它决定了句子如何被构建。

在当前的实现中，文法规则用于定义被解析的语言的语法。解析器根据这些规则检查输入的语句是否符合语法，并构建相应的内部表示（ AST）。

# Grammar (简化版):
# EXPR := TERM { 'or' TERM }
# TERM := FACTOR { 'and' FACTOR }
# FACTOR := 'not' FACTOR | VARIABLE | '(' EXPR ')'
# VARIABLE := 字母开头的标识符

  • EXPR := TERM { 'or' TERM }: 一个 EXPR (表达式) 由一个 TERM (项) 开始，后面可以跟零个或多个由 “or” 连接的 TERM。 这表示 “or” 运算具有最低的优先级。{} 表示大括号内的内容可以重复零次或多次。

  • TERM := FACTOR { 'and' FACTOR }: 一个 TERM (项) 由一个 FACTOR (因子) 开始，后面可以跟零个或多个由 “and” 连接的 FACTOR。这表示 “and” 运算的优先级高于 “or”。

  • FACTOR := 'not' FACTOR | VARIABLE | '(' EXPR ')': 一个 FACTOR (因子) 可以是 “not” 后跟一个 FACTOR，或者是一个 VARIABLE (变量)，或者是一个由括号包围的 EXPR。这表示 “not” 运算具有最高的优先级，而括号可以用来改变运算顺序。

  • VARIABLE := 字母开头的标识符: 一个 VARIABLE (变量) 是一个以字母开头的标识符（这里简化了，实际上标识符的规则更复杂）。

递归下降解析器

递归下降解析器是一种自顶向下的解析器，它通过为文法规则中的每个非终结符 (non-terminal) 编写一个函数来实现解析。这些函数相互递归调用，以匹配输入字符串中的结构，就像文法规则所描述的那样。

  • 特点:

    • 易于理解和实现: 递归下降解析器的结构通常与文法规则非常相似，因此相对容易理解和实现。

    • 递归性质: 解析过程是递归的，因为函数会相互调用来解析子结构。

    • 自顶向下: 解析从文法的起始符号（在本例中是 EXPR）开始，然后逐步向下解析到更小的组成部分。

当前代码如何实现递归下降？

parse 函数及其子函数 (parse_expression, parse_term, parse_factor) 共同构成了一个递归下降解析器，用于解析逻辑表达式。它们的工作原理如下：

  • 与文法规则的对应关系:

    • parse_expression 对应文法规则 EXPR := TERM { 'or' TERM }

    • parse_term 对应文法规则 TERM := FACTOR { 'and' FACTOR }

    • parse_factor 对应文法规则 FACTOR := 'not' FACTOR | VARIABLE | '(' EXPR ')'

  • 递归调用: 这些函数根据文法规则相互递归调用。例如：

    • parse_expression 调用 parse_term 来解析 “or” 运算符两侧的项。

    • parse_term 调用 parse_factor 来解析 “and” 运算符两侧的因子。

    • parse_factor 在遇到括号时会调用 parse_expression 来解析括号内的表达式，形成递归。

  • 自顶向下解析: 解析从 parse 函数开始，它调用 parse_expression，然后 parse_expression 调用 parse_term，parse_term 调用 parse_factor，形成自顶向下的解析过程。

  • 处理优先级和结合性: 通过函数的调用顺序和循环结构，解析器隐式地处理了运算符的优先级和结合性。例如，parse_expression 在循环中处理 “or”，而 parse_term 在循环中处理 “and”，这确保了 “and” 的优先级高于 “or”。

  • 构建 AST: 在递归调用的过程中，每个函数都构建 AST 的一部分，并将部分结果返回给调用它的函数。最终，parse 函数返回完整的 AST。

总之，这组函数实现了一个递归下降解析器，它根据给定的文法递归地解析逻辑表达式。每个函数负责解析特定类型的语法结构（表达式、项、因子），并根据需要递归调用其他函数。最终可以将输入的表达式，转化为类似如下优先级清晰的逻辑表达式：

# ('and', ('not', ('or', ('not', 'A'), ('not', ('and', 'B', 'C')))), ('or', 'D', ('not', 'E')))
('and', 
	('not', 
		('or', 
			('not', 'A'), 
			('not', ('and', 
								'B', 
								'C'
							)
			)
		)
	), 
	('or', 
		'D', 
		('not', 'E')
	)
)

所以，有无已有的第三库实现？🧐

对于这中通用的规则处理或者解析，我相信丰富的 Python 生态肯定已有相关的实现！通过搜索发现，能够实现转化 AST 需求的解析器还挺多，就是复杂度的区别。

ast 标准库

首先是 Python 中的 ast 标准库，没想到可以直接进行转换！ ast 可以直接接收一个逻辑表达式并转化为 AST：

tree = ast.parse(expr, mode="eval")

  1. mode="eval"：指定解析模式为”eval”：

    • 输入的字符串将被解析为一个可求值的表达式

    • 与其他模式相比（如”exec”用于执行语句，“single”用于交互式输入），“eval”模式专门用于处理单个表达式

  2. 返回值：返回一个ast.Expression对象，这个对象包含了表达式的语法树结构，可以通过.body属性访问具体的语法树节点

例如，如果输入表达式是 "A and B"，生成的AST会包含：

  • 一个BoolOp节点（表示布尔运算）

  • 运算符And

  • 两个Name节点（分别代表A和B）

不得不说，即使知道某一个 Python 库，也只是知道常用的操作，像这些不看文档都发现不了，不得不说，AI 真香 😋

在得到 AST 之后，只需要写一个遍历即可：

class LogicTransformer(ast.NodeTransformer):
    def visit_BoolOp(self, node):
        if isinstance(node.op, ast.And):
            return (
                "and",
                self.visit(node.values[0]),
                self.visit(node.values[1]),
            )
        elif isinstance(node.op, ast.Or):
            return (
                "or",
                self.visit(node.values[0]),
                self.visit(node.values[1]),
            )
        return node

    def visit_UnaryOp(self, node):
        if isinstance(node.op, ast.Not):
            return ("not", self.visit(node.operand))
        return node

    def visit_Name(self, node):
        return node.id

你看，又有好东西，还有 ast.NodeTransformer ，不对，我确实好像没咋用过 python 的 ast 模块，肤浅了肤浅了🙈，真优雅~

lark

https://github.com/lark-parser/lark

Lark 是一个用于 Python 的现代解析库，专注于易用性、性能和模块化设计。它能够解析任何上下文无关文法（Context-Free Grammar），并且提供了多种解析算法供选择，包括 Earley、 LALR(1) 和 CYK。 lark 能够根据文法自动构建解析树（Parse Tree），无需额外的构建代码。

嗯，好多名词没看懂，但是 get 到了重点， lark 库是天生的根据文法规则构建解析树的圣体。那肯定更优雅！ lark 的使用包括：定义文法规则；定义解析器（可选）。

parser = Lark(grammar, parser="lalr", transformer=TreeBuilder())
parsed_expr = parser.parse(expression)

# 文法规则
grammar = """
    ?start: expr           # 定义起始规则，问号表示这是一个内联规则（不会在树中创建额外节点）

    ?expr: term                            # expr 可以是一个 term
         | expr "or" term    -> or_expr    # 或者是 expr or term 的形式
         | expr "||" term     -> or_expr   # 支持 || 作为 or 的替代
    
    ?term: factor                          # term 可以是一个 factor
         | term "and" factor -> and_expr   # 或者是 term and factor 的形式
         | term "&&" factor   -> and_expr  # 支持 && 作为 and 的替代
    
    ?factor: "not" factor    -> not_factor # factor 可以是 not factor
           | "!" factor      -> not_factor # 支持 ! 作为 not 的替代
           | "(" expr ")"    -> paren_expr # 或者是括号包围的表达式
           | variable                      # 或者是一个变量
    
    variable: /[A-Za-z_][A-Za-z0-9_]*/     # 变量名的正则表达式规则

    %import common.WS                      # 导入预定义的空白字符规则
    %ignore WS                             # 忽略解析中的空白字符
"""

  1. 最顶层是 expr，处理 or 运算

  2. 中间层是 term，处理 and 运算

  3. 底层是 factor，处理 not 运算、括号和变量

这种层次结构确保了运算符优先级：not > and > or

# TreeBuilder 解析器
class TreeBuilder(Transformer):
    def not_factor(self, children):
        # 处理否定表达式，如 "not A" 或 "!A"
        # 返回一个元组 ("not", child)
        return ("not", children[0])

    def paren_expr(self, children):
        # 处理括号表达式，如 "(A)"
        # 直接返回括号内的表达式
        return children[0]

    def and_expr(self, children):
        # 处理与运算，如 "A and B" 或 "A && B"
        # 返回一个元组 ("and", left_expr, right_expr)
        return ("and", children[0], children[1])

    def or_expr(self, children):
        # 处理或运算，如 "A or B" 或 "A || B"
        # 返回一个元组 ("or", left_expr, right_expr)
        return ("or", children[0], children[1])

    def variable(self, children):
        # 处理变量名，如 "A", "foo" 等
        # 返回变量的实际值
        return children[0].value

TreeBuilder 的作用是将解析树转换为简单的抽象语法树（AST）。

  1. 当解析器遇到语法规则中定义的模式时，会调用对应的方法

  2. 每个方法接收一个 children 参数，包含该规则的所有子节点

  3. 方法返回一个简化的表示形式，通常是元组

例如，对于表达式 "not (A && B)":

  1. variable 方法处理 A 和 B，返回它们的值

  2. and_expr 方法处理 A && B，返回 ("and", "A", "B")

  3. not_factor 方法处理整个表达式，返回 ("not", ("and", "A", "B"))

还有一些第三方库，暂时就没有尝试了，感觉 lark 就很优雅了，就先列举一下：

  1. pyparsing : https://github.com/pyparsing/pyparsing/

  2. funcparserlib : https://github.com/vlasovskikh/funcparserlib

基于 AST 的逻辑表达式取反

有了 AST，对 AST 中的节点进行取反操作，就相当于对一颗二叉树执行德摩根定律，完全可以套用二叉树的递归算法进行处理，这就很方便了：

def negate_expression(expr):
    if isinstance(expr, str):  # Variable
        return ("not", expr)

    op = expr[0]
    if op == "not":
        return expr[1]  # Remove the not
    elif op == "and":
        # not (A and B) = (not A) or (not B)
        return ("or", negate_expression(expr[1]), negate_expression(expr[2]))
    elif op == "or":
        # not (A or B) = (not A) and (not B)
        return ("and", negate_expression(expr[1]), negate_expression(expr[2]))
    else:
        raise ValueError(f"Unknown operator: {op}")

函数采用递归的方式处理这个表达式。函数会不断地调用自身来处理表达式的子部分，直到遇到最基本的节点元素——变量。

  1. 基本情况 - 变量: 如果遇到一个变量（字符串），函数会在它前面加上 "not" 来表示取反，并返回结果。

  2. 操作符处理: 如果遇到一个操作符（元组），函数会根据操作符的类型进行不同的处理：

    • "not": 如果是 "not" 操作符，函数会直接返回被取反的子表达式，相当于去除了一层 "not"。

    • "and" 和 "or": 如果是 "and" 或 "or" 操作符，函数会应用德摩根定律。函数会将当前的 "and" 或 "or" 操作符替换成对应的 "or" 或 "and"，然后递归地对两个子表达式进行取反操作。

至此，大部分核心操作已经完成，现在可以输入一个字符串逻辑表达式，得到取反后的字符串逻辑表达式，验证如下：

Original expression: ((A && !B) || (!(C && D) && (E || !F)) || !(G && H))
Original AST: ('or', ('or', ('and', 'A', ('not', 'B')), ('and', ('not', ('and', 'C', 'D')), ('or', 'E', ('not', 'F')))), ('not', ('and', 'G', 'H')))

Negated AST: ('and', ('and', ('or', ('not', 'A'), 'B'), ('or', ('and', 'C', 'D'), ('and', ('not', 'E'), 'F'))), ('and', 'G', 'H'))
Negated expression: (((!A) || B) && ((C && D) || ((!E) && F))) && (G && H)

-----------------------------------

Original expression: (A && B && !C) || (D && !E && F) || (!G && H)
Original AST: ('or', ('or', ('and', ('and', 'A', 'B'), ('not', 'C')), ('and', ('and', 'D', ('not', 'E')), 'F')), ('and', ('not', 'G'), 'H'))

Negated AST: ('and', ('and', ('or', ('or', ('not', 'A'), ('not', 'B')), 'C'), ('or', ('or', ('not', 'D'), 'E'), ('not', 'F'))), ('or', 'G', ('not', 'H')))
Negated expression: ((((!A) || (!B)) || C) && (((!D) || E) || (!F))) && (G || (!H))

-----------------------------------

Original expression: !(!(A || B) && !(C && D)) || (!E && F)
Original AST: ('or', ('not', ('and', ('not', ('or', 'A', 'B')), ('not', ('and', 'C', 'D')))), ('and', ('not', 'E'), 'F'))

Negated AST: ('and', ('and', ('not', ('or', 'A', 'B')), ('not', ('and', 'C', 'D'))), ('or', 'E', ('not', 'F')))
Negated expression: ((!(A || B)) && (!(C && D))) && (E || (!F))

非常的牛啊，我自己算都得一会，唯一的瑕疵就是有些多余的括号，但无伤大雅，而且这些例子都比较复杂了，真实的需求并不需要这么复杂逻辑表达式。

PHP 逻辑表达式抽象为符号逻辑表达式

现在剩下来的工作就是如何将 PHP 逻辑表达式抽象为符号逻辑表达式，比如：

Original expression: (!validate_username($username) || in_array($username, $invalid_usernames) && username_exists($username) || isset($username))

Simplified expression: (!A || B && C || D)

在实现时，使用的是正则匹配，通过正则表达式识别到 PHP 中的数据结构等，然后进行 tokenize。目前的要求如下：

  • 识别逻辑运算符：&&, ||, !, (, )

  • 处理复杂的 PHP 表达式，包括：

    • 函数调用：function_name($param)

    • 变量访问：$variable

    • 对象属性访问：$obj->property

    • 数组访问：array[index]

    • 比较表达式：===, !==, ==, !=, >=, <=

    • 能处理嵌套的括号结构

这些规则都是根据测试用例不断添加的，这也是我在这种情况下不太喜欢用正则的原因，因为不够 general。然后为每个唯一的操作数分配一个大写字母（A-Z），并建立双向映射。最终实现结果如下：

原始表达式: (!validate_username($username) || in_array($username, $invalid_usernames) && username_exists($username) || isset($username))

标记化后的 tokens: ['(', '!', 'validate_username($username)', '||', 'in_array($username, $invalid_usernames)', '&&', 'username_exists($username)', '||', 'isset($username)', ')']

替换后的 tokens: ['(', '!', 'A', '||', 'B', '&&', 'C', '||', 'D', ')']

简化后的表达式: (!A || B && C || D)

操作数映射: {'validate_username($username)': 'A', 'in_array($username, $invalid_usernames)': 'B', 'username_exists($username)': 'C', 'isset($username)': 'D'}

占位符映射回原操作数: {'A': 'validate_username($username)', 'B': 'in_array($username, $invalid_usernames)', 'C': 'username_exists($username)', 'D': 'isset($username)'}

总结

Ok，大致的就这些，并不是复杂的一个问题，但是刚开始处理的时候，由于太过依赖 AI，就直接将最开始的需求交给了它，然后反复的 chat、debug，但越改越乱，最后给出的更改基本上都是只适用于给出的这些用例，很气哦，浪费时间。所以还是自己先调研一下，想出一个大致的思路，然后让 AI 结合我进行 Coding，逻辑理清楚之后，一会就实现了~

So，需要推理或者思考的算法逻辑问题可以先思考一下（想不到可以调研类似实现或者给 o1 头脑风暴试试），有一个大致的路线，再交给 AI 实现，这样不仅节约时间，而且还能使用下自己的🧠，别退化了哈哈哈

目录 共 10 节

评论

访客
⌘ / Ctrl + Enter 发送

发送后直接公开 · 访客昵称未经认证

正在读取评论…