如何在抽象语法树上递归执行"树步行"？

Question

我的语言分配的简单示例:

x = 3 ->

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

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

我怎样才能递归访问任何可能的深度,以便在最简单的情况下打印所有这些深度？(或者将文本转换成其他内容？).这样做有特定的算法吗？如果有,您是否推荐任何特定材料？

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类来稍微形式化内容.