python - 如何在抽象语法树上递归执行 "tree walk"？

Question

我的语言的简单赋值示例:

x = 3 ->

这是解析后生成的 AST(在 Python 中):

[('statement', ('assignment', 'x', ('assignment_operator', '='), ('expr', ('term', ('factor', '3')))), '->')]

我怎样才能递归访问任何可能的深度，以便在最微不足道的情况下打印所有这些深度？ (或将文本转换成其他内容？)。是否有执行此操作的特定算法？如果有，您有什么具体的 Material 推荐吗？

Answer 1

要遍历树，只需使用堆栈或队列(取决于您是想深度优先还是呼吸优先)。

对于遇到的每个节点，将子节点压入堆栈或队列，然后从数据结构中取出下一项进行处理并重复。

例如，首先呼吸可能是这样的:

from collections import deque

def walk(node):
    queue = deque([node])
    while queue:
        node = queue.popleft()
        if isinstance(node, tuple):
            queue.extend(node[1:])  # add the children to the queue
        yield node

这会为您的树生成以下行走顺序:

>>> for node in walk(tree[0]):
...     print(node[0] if isinstance(node, tuple) else node)
...
statement
assignment
->
x
assignment_operator
expr
=
term
factor
3

你的数据结构有点乱，混合了不同长度的元组。您可能希望使用 nametuple class使内容形式化一点。