python - 查找 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 但我无法理解它如何解决类似的问题。

任何帮助，将不胜感激！:)

标签： pythonpython-3.xparsing

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}