查找Python递归引用

Question

我试图在一组给定的语法表达式中找到递归引用。 以下是一个例子：

expr   :  term
term   :  factor
factor :  expr

但我不知道如何解决这些循环。 我试图识别给定字典中的所有递归循环，该字典描述语法中的规则引用

给定下面的树，每个节点都应该被标识为递归的，因为有一个来自expr -> term -> factor -> expr...的循环

data = {
    'expr': {'term'},
    'term': {'factor'},
    'factor': {'expr'},
}

（当存在多个互连环路时，它还应返回所有循环的节点）

我不确定如何解决哪些节点在循环，我在网上查找了一下，发现：https://github.com/we-like-parsers/pegen_experiments/blob/master/pegen/sccutils.py 但我不明白它是如何解决类似问题的

任何帮助都将不胜感激！：）

Answer 1

可以将语法视为图形并检查循环：

import re
s = """
expr   :  term
term   :  factor
factor :  expr
"""
g = [re.split('\s+:\s+', i) for i in filter(None, s.split('\n'))]
def check_cycle(n, c = []):
   if n in c:
      return True
   return any(check_cycle(b, c+[n]) for a, b in g if a == n)

result = {a:check_cycle(a) for a, _ in g}

输出：

{'expr': True, 'term': True, 'factor': True}