如何使用Python识别语法表达式中的递归引用与循环节点

实现思路 #

• 该问题本质是有向图的强连通分量（SCC）检测：将每条语法规则作为图的节点，规则A引用规则B则添加一条A指向B的有向边，存在循环引用的规则必然属于同一个强连通分量。
• 采用Tarjan算法实现SCC检测：仅需单次深度优先遍历即可识别所有强连通分量，时间复杂度为O(N+E)，N为规则总数，E为引用关系总数，性能适配绝大多数语法规则集场景。
• 结果过滤逻辑：如果需要包含自递归（规则自己引用自己），保留所有大小≥1的SCC即可；如果仅需检测多节点互相引用的循环，仅保留大小≥2的SCC即可。

可运行代码实现 #

def find_recursive_cycles(graph: dict[str, set[str]]) -> list[set[str]]:
    index = 0
    indices = {}
    low = {}
    on_stack = set()
    stack = []
    result = []

    def strongconnect(node: str):
        nonlocal index
        indices[node] = index
        low[node] = index
        index += 1
        stack.append(node)
        on_stack.add(node)

        # 遍历当前节点的所有邻接节点
        for neighbor in graph.get(node, set()):
            if neighbor not in indices:
                strongconnect(neighbor)
                low[node] = min(low[node], low[neighbor])
            elif neighbor in on_stack:
                low[node] = min(low[node], indices[neighbor])

        # 找到一个强连通分量
        if low[node] == indices[node]:
            scc = set()
            while True:
                scc_node = stack.pop()
                on_stack.remove(scc_node)
                scc.add(scc_node)
                if scc_node == node:
                    break
            # 过滤非循环分量：仅保留自递归或多节点循环
            if len(scc) > 1 or (len(scc) == 1 and next(iter(scc)) in graph.get(next(iter(scc)), set())):
                result.append(scc)

    # 遍历所有未访问的节点
    for node in graph:
        if node not in indices:
            strongconnect(node)
    
    return result


# 测试用例1：单组三节点循环
data1 = {
    'expr': {'term'},
    'term': {'factor'},
    'factor': {'expr'},
}
print(find_recursive_cycles(data1))  # 输出：[{'expr', 'term', 'factor'}]

# 测试用例2：多组独立循环 + 无递归节点
data2 = {
    'a': {'b'},
    'b': {'a'},
    'c': {'d'},
    'd': {'e'},
    'e': {'c'},
    'f': {'g'},
    'g': set(),
    'h': {'h'}  # 自递归
}
print(find_recursive_cycles(data2))  # 输出：[{'a', 'b'}, {'c', 'd', 'e'}, {'h'}]

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