使用python中的生成器对树进行深度优先遍历

Question

目前，我正在用Python为Python的一小部分编写编译器。我已经成功地构造了一个语法树，但是我在编码树遍历时遇到了一些问题（这对于生成代码是必不可少的）。首先，我将向您展示我的数据结构：

class AbstractSyntaxTree(object):
    def __init__(self, startSymbol):
        self.root = Node(startSymbol, val=None)
        self.nodes = [self.root]

    def addNode(self, name, val, parentId):
        parent = self.nodes[parentId]
        self.nodes.append(Node(name=name, val=val, parent=parent))
        return len(self.nodes)-1

    def getLastId(self):
        return len(self.nodes)-1

    def __iter__(self):
        for node in self.root:
            yield node

这是我的节点定义：

^{pr2}$

我的解析器是一个递归下降解析器，其中每个语法符号都是一个调用其他语法符号的函数。program是我的开始符号。在

def program(self, indentLvl=0):
    parent = self.synTree.getLastId()
    if self.smellAndConsume(TOK.EOF, parentId=parent): return
    self.smellAndConsume(TOK.NEWL, parentId=parent)
    self.synTree.addNode(name=VAR.statement, val=None, parentId=parent)
    self.statement()
    while self.accept and not self.isConsumable(TOK.EOF):
        self.consume(TOK.NEWL, parentId=parent)
        self.synTree.addNode(name=VAR.statement, val=None, parentId=parent)
        self.statement()
    self.consume(TOK.EOF, parentId=parent)

现在很好奇，如果在成功解析之后，我能够通过使用在Node和AbstractSyntaxTree中定义的__iter__生成器对语法树中的所有节点进行迭代，从而打印出语法树中的所有节点。但是

def test_tree_traversal():
    for node in miniPyGrammar.synTree:
        print(node)

不会打印所有节点！当我调试代码时，我意识到，我的根节点在它的子节点列表中没有任何子节点，尽管我用根节点id调用了addNode。有人知道这里发生了什么吗？在

如果您需要更多信息或代码片段，请随时询问。在

编辑：我刚刚找到了解决方案（尽管我仍然觉得这里发生的事情很奇怪。）此代码现在按预期运行：

def test_tree_traversal(code):
    grammar = Grammar()
    grammar.parse(code)
    for node in grammar.synTree:
        print(node)

def execute_tests():
    for name, code in programs.items():
        parse_test(name, code)
        test_tree_traversal(code)

在我有一个全局语法对象并执行测试之前，我会对该语法调用parse，之后我运行test_tree_traversal，它访问语法对象synTree。奇怪的是，在两次调用之间，垃圾回收删除了AST中的一些节点。为什么我认为是垃圾收集？因为这种行为是不确定的。在

编辑：这是容易出错的代码： 注意，唯一的区别是我在执行测试之前实例化了一个新的语法对象。Grammar有一个方法“parse”，如果程序语法正确，则返回true，并构造一个可以通过语法.synTree. 在

miniPyGrammar = Grammar()

def parse_test(
    programName: str,
    programCode: str):
    success = miniPyGrammar.parse(programCode)
    if success:
        print('{} is a valid miniPyProgram :)'.format(programName))
    else:
        print('{} is not a valid miniPyProgram'.format(programName))
    print(miniPyGrammar.synTree)

def tree_traversal(code):
    for node in miniPyGrammar.synTree:
        print(node)

def execute_tests():
    for name, code in programs.items():
        parse_test(name, code)
        tree_traversal(code)

if __name__ == '__main__':
    execute_tests()

Answer 1

我建议使用Visitor pattern，而不是在树上迭代。这种方法允许您轻松地模块化抽象语法树遍历。在

注意，使用这种方法，您必须为树中的每个节点类型创建特定的类。例如，可以为运算符节点使用Operator类，为函数调用节点使用FunctionCall类，等等

下面是一个非常简单的AST的vistor模式示例，应该可以让您开始使用它。AST由运算符的Operator节点和数字的Number节点组成：

class Node:
    pass


class Operator(Node):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right


class Number(Node):
    def __init__(self, value):
        self.value = value


class AstWalker:
    def visit(self, node):
        name = 'visit_' + node.__class__.__name__
        vistor = getattr(self, name, self.missing)
        vistor(node)

    def missing(self, node):
        name = node.__class__.__name__
        raise Exception('No visitor method for node type: ' + name)

    def visit_Operator(self, node):
        print('operator:', node.op)
        self.visit(node.left)
        self.visit(node.right)

    def visit_Number(self, node):
        print('number:', node.value)


# The ast represents the expression:
#
# (1 * 5) - (3 / 5)
#
ast = Operator(op='-',
        left=Operator(op='*', 
                   left=Number(1), 
                   right=Number(5)
        ),

        right=Operator(op='/', 
                   left=Number(3), 
                   right=Number(5)
        )
)

walker = AstWalker()
walker.visit(ast)

上述代码的输出为：

^{pr2}$

上面代码中有趣的部分是AstWalker类。在这里我们实现了模式。这是一个简短的总结。在

visit方法是上述代码的核心。这就是魔法发生的地方。长话短说，visit接受一个参数node。这将是Operator节点或Number。然后使用node.__class__.__name__获取节点类的名称。如您所见，我使用visit作为名称的前缀，因为树中每个节点的visitor方法都访问了visit_Operator和{}。在

最后在self.visit中，我使用getattr从类中获取正确的访问者方法。如果节点是Numbergetattr将返回visit_Number方法。这同样适用于Operator。然后调用visitor方法并传入node。在

如果我们发现传入的node对象没有visitor方法，我们返回self.missing并调用它。self.missing简单报告我们遇到的节点对象没有visitor方法。在

如上所述，每个visitor方法接受一个参数node。当前节点正在访问。在上面的例子中，我只打印每个node的属性。但是可以很容易地修改它来生成字节码。在