如何在抽象语法树上递归地执行“树遍历”？

Question

如何在抽象语法树上递归地执行“树遍历”？

8

我的语言中赋值的简单示例：

x = 3 ->

在解析后生成的AST（使用Python）如下：

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

如何递归访问任何可能的深度，以便在最简单的情况下打印所有内容？（或将文本转换为其他格式？）是否有特定的算法来完成这个任务？如果有，您推荐使用哪些材料？

- Ericson Willians

1

为什么不直接使用 ast 模块的功能呢？例如 ast.walk()。 - Martijn Pieters

我之前不知道这个模块的存在。我只知道os.walk()（它是特定用于目录的）。 - Ericson Willians

1

可能这个模块过于特定于Python语法，如果你有自己的语法，那么这个模块可能不适用。 - Martijn Pieters

我有自己的语法。我曾试图在YACC的每个解析规则函数中解释所有内容，但随着它变得越来越复杂（例如条件块），我意识到我需要生成AST，然后从中解释/翻译代码。 - Ericson Willians

1

我对你的元组结构并不完全清楚；我做了一个假设，即除了第一个元素之外的所有内容都是子元素，但你可能想要稍微规范一下内容。 - Martijn Pieters

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martijn Pieters · Accepted Answer

要遍历一棵树，只需使用栈或队列（取决于您是想进行深度优先还是广度优先遍历）。

遇到每个节点时，将其子节点推入栈或队列中，然后取出数据结构中的下一个项目以处理并重复此过程。

例如，广度优先遍历可能会像这样：

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

您的数据结构有些混乱，混合了不同长度的元组。您可能需要考虑使用namedtuple类来更正一下内容。