使用cel-python遍历CEL AST并构建有序条件栈的方法

我正在使用cel-python库中的celparser.py解析CEL表达式并生成AST。解析完成后，我需要遍历该AST并构建一个以最内层条件为栈顶的条件栈。例如，给定以下CEL表达式：

(a.name == 'Jon' && (c.role == 'lead' || c.region == 'US')) ? b.salary : c.bonus

我期望得到的栈内容如下：

c.role == 'lead'
c.region == 'US'
c.role == 'lead' || c.region == 'US'
a.name == 'Jon' && (c.role == 'lead' || c.region == 'US')

请问实现该AST遍历与栈构建的最优方法是什么？

核心逻辑：深度优先后序遍历 #

要让最内层条件处于栈顶，核心是先处理所有子表达式，再处理当前表达式。深度优先遍历的后序遍历正好匹配这个需求：递归遍历完所有子节点后，再将当前表达式加入栈，这样最内层的原子条件会被最先压入栈，随后是逐层向外的组合条件，最终栈的顺序完全符合预期。

具体实现步骤 #

1. 节点类型识别：cel-python生成的AST会为不同表达式分配对应节点类，重点关注三类节点：
   • 原子条件：如a.name == 'Jon'这类比较表达式
   • 组合逻辑条件：&&、||这类二元逻辑运算表达式
   • 条件表达式?:：仅处理其前置的布尔判断部分（即?:左侧的表达式）
2. 递归遍历与压栈：
   • 遇到组合逻辑表达式（&&/||）：先递归遍历左、右子节点，最后将当前组合表达式的字符串形式压入栈。
   • 遇到原子条件表达式：直接将其字符串形式压入栈。
   • 遇到条件表达式：仅递归遍历其条件判断节点，忽略分支结果部分。
3. AST节点转字符串：实现辅助函数，将AST节点还原为可读的CEL表达式字符串，比如把属性访问节点转成a.name，字面量转成带引号的字符串等。

代码示例 #

from celparser import parse  # 按cel-python实际导入方式调整

# 根据cel-python实际AST节点结构适配，以下为模拟定义
class ASTNodeTypes:
    BinaryExpr = 'BinaryExpr'
    ConditionalExpr = 'ConditionalExpr'
    Attribute = 'Attribute'
    Identifier = 'Identifier'
    Literal = 'Literal'

class ASTWalker:
    def __init__(self):
        self.condition_stack = []

    def traverse(self, node):
        node_type = type(node).__name__
        # 处理条件表达式，仅遍历判断部分
        if node_type == ASTNodeTypes.ConditionalExpr:
            self.traverse(node.condition)
        # 处理二元逻辑表达式（&&、||）
        elif node_type == ASTNodeTypes.BinaryExpr and node.op in ('&&', '||'):
            self.traverse(node.left)
            self.traverse(node.right)
            expr_str = f"({self.node_to_str(node.left)} {node.op} {self.node_to_str(node.right)})"
            self.condition_stack.append(expr_str)
        # 处理原子比较条件（==、!=、>等）
        elif node_type == ASTNodeTypes.BinaryExpr and node.op in ('==', '!=', '>', '<', '>=', '<='):
            expr_str = f"{self.node_to_str(node.left)} {node.op} {self.node_to_str(node.right)}"
            self.condition_stack.append(expr_str)

    def node_to_str(self, node):
        node_type = type(node).__name__
        if node_type == ASTNodeTypes.Literal:
            return repr(node.value)  # 自动处理字符串引号、数字格式
        elif node_type == ASTNodeTypes.Attribute:
            return f"{self.node_to_str(node.obj)}.{node.attr}"
        elif node_type == ASTNodeTypes.Identifier:
            return node.name
        # 其他节点类型按需扩展
        else:
            return str(node)

# 使用示例
cel_expression = "(a.name == 'Jon' && (c.role == 'lead' || c.region == 'US')) ? b.salary : c.bonus"
ast_root = parse(cel_expression)
walker = ASTWalker()
walker.traverse(ast_root)

# 输出栈内容（顺序与预期一致）
for cond in walker.condition_stack:
    print(cond)

注意事项 #

• 需根据cel-python库实际返回的AST节点结构，调整代码中的节点类型判断和属性访问方式（比如节点的op、left、right等属性名称可能略有不同）。
• 若需严格匹配示例中不包含单独a.name == 'Jon'的结果，可在遍历原子条件时增加判断：仅当原子条件的父节点是组合表达式，且该组合表达式的另一个子节点也是组合表达式时才压栈。是否加入单独原子条件可根据实际需求调整。

内容的提问来源于stack exchange，提问作者Pradhiksha Kannan