从 if 语句构建解析树

Question

我的目标是能够判断特定 JSON 对象是否与存储在 .yaml 文件中的一组特定规则相匹配。规则类似于我们可以在 if 语句中找到的东西。例如：

if( A and B OR C):
   #do something

其中A、B、C是一些条件，例如检查JSON对象的某个属性是否大于0（只是一个例子）。

我想构建特定 if 语句的相应解析树。在这样的树中，节点将是逻辑运算符，即 AND 和 OR，叶子将是实际条件。让我们考虑以下情况： (((A and B) OR (C AND B AND D AND E)) AND F)。这将为我们提供以下解析树：

在构建这样一棵树之后，我们将从树的最左侧（或最右侧，无关紧要）开始迭代并开始执行测试。例如，如果我们从树的最左边开始，那将是叶子 A。验证 A 是否满足，如果不满足，则 JSON 对象不匹配规则，因为它的父对象是 AND 运算符，如果匹配，则将转到第二个测试，即条件B。然后检查条件C，B和D等等，直到执行所有测试。

我可以使用什么方法来构建这样的树？是否有我可以用来实现此目的的现有解析器？如果有更好的方法来实现这一点，我很想听听。谢谢！

Answer 1

您确实需要以某种方式解析文本。

我建议依靠正则表达式来标记输入，这样您就可以获得以下标记：

(
)
AND
OR
任何其他情况都将被视为原子条件。

然后迭代这些标记并使用堆栈或递归来构建树。

根据你的其他问题，我看到你使用 Python，所以在 Python 中你可以为每个运算符创建一个 class（OR，AND ) 并让它继承自 list。这样的列表将具有作为成员字符串（树的叶子）或更多 OR 或 AND 列表实例。所以整棵树其实就是一个嵌套的链表结构

以下是您将如何实现那些 list-based classes:

# A generic class from which all operators derive
class Node(list):
    @property
    def label(self):
        return self.__class__.__name__

    def __repr__(self):
        return self.label + super().__repr__()

# Subclass for each operator: no additional logic is needed 
class AND(Node): pass
class OR(Node): pass

这是解析器：

import re

def parse(s):
    # Rely completely on the operators that have been defined as subclasses of Node
    Operators = { cls.__name__ : cls for cls in Node.__subclasses__() }
    # Create a regular expression based on those operator names (AND, OR)
    regex = r"\s*([()]|" + "|".join(fr"\b{operator}\b" for operator in Operators.keys()) + ")\s*"
    # Tokenise the input
    tokens = iter((token for token in re.split(regex, s, flags=re.IGNORECASE) if token))
    
    def dfs(end=")"):
        operator = ""
        operands = []
        while True:
            token = next(tokens, "")
            if not token or token == ")":
                raise ValueError(f"Operand expected, but got '{token}'")
            operands.append(dfs() if token == "(" else token)
            token = next(tokens, "")
            if token == end:
                return Operators[operator](operands) if operator else operands[0]
            utoken = token.upper()
            if utoken in Operators:
                if operator and utoken != operator:
                    raise ValueError("Use parentheses to indicate operator precedence")
                operator = utoken
            else:
                raise ValueError(f"{', '.join(Node.keys())} expected, but got '{token}'")
    return dfs("")

使用方法如下：

# Example run
s = "(((A and B) OR (C AND B AND D AND E)) AND F)"
tree = parse(s)
print(tree)
# Demo on how to address specific nodes in the tree
print(tree.label, tree[0].label, tree[0][0].label, tree[0][0][0])

从 if 语句构建解析树

build a parse tree from if statement

tree

parsing

if-statement