如何用Python编写抽象语法树的访问者模式？

Question

我的同事建议我编写一个访问者模式来导航 AST。谁能告诉我更多如何开始写它？

据我了解，AST 中的每个节点都会有 visit() 方法（？），该方法会以某种方式被调用（从哪里？）。我的理解就这样结束了。

为了简化一切，假设我有节点 Root、Expression、Number、Op 并且树如下所示：

       Root
        |
       Op(+)
      /   \
     /     \
 Number(5)  \
             Op(*)
             /   \
            /     \
           /       \
       Number(2)   Number(444)

谁能想到访问者模式将如何访问这棵树来产生输出：

 5 + 2 * 444

谢谢，Boda Cydo。

Answer 1

维基百科对访客模式如何工作有一个很好的概述，尽管他们使用的示例实现是在Java中。不过，您可以轻松地将其移植到 Python，不是吗？

基本上，您想要实现双重调度的机制。 AST 中的每个节点都需要实现一个 accept() 方法（而不是 visit() 方法）。该方法采用访问者对象作为参数。在此 accept() 方法的实现中，您调用访问者对象的 visit() 方法（每种 AST 节点类型都会有一个方法；在 Java 中，您可以将使用参数重载，在 Python 中我想你可以使用不同的 visit_*() 方法）。然后，将使用正确的节点类型作为参数来分派正确的访问者。

Answer 2

请参阅 文档 了解 ast.NodeVisitor< /code>，例如，一种粗略的可能性可能是：

import ast

class MyVisitor(ast.NodeVisitor):
  def visit_BinaryOp(self, node):
    self.visit(node.left)
    print node.op,
    self.visit(node.right)
  def visit_Num(self, node):
    print node.n,

当然，即使在需要的地方，这也不会发出括号等，所以实际上还有更多的工作要做，但是，这是一个开始;-)。

Answer 3

我在互联网上最常遇到的用 Python 实现访问者模式的两种变体：

• 对 Gamma 等人的设计模式书中的示例进行一对一翻译。
• 使用附加模块进行双分派

设计模式书籍中的翻译示例

此变体使用数据结构类中的 accept() 方法以及访问者中相应的 visit_Type() 方法。

数据结构

class Operation(object):
    def __init__(self, op, arg1, arg2):
        self.op = op
        self.arg1 = arg1
        self.arg2 = arg2
    def accept(self, visitor):
        visitor.visitOperation(self)

class Integer(object):
    def __init__(self, num):
        self.num = num
    def accept(self, visitor):
        visitor.visitInteger(self)

class Float(object):
    def __init__(self, num):
        self.num = num
    def accept(self, visitor):
        visitor.visitFloat(self)
    
expression = Operation('+', Integer('5'),
                            Operation('*', Integer('2'), Float('444.1')))

Infix Print Visitor

class InfixPrintVisitor(object):
    def __init__(self):
        self.expression_string = ''
    def visitOperation(self, operation):
        operation.arg1.accept(self)
        self.expression_string += ' ' + operation.op + ' '
        operation.arg2.accept(self)
    def visitInteger(self, number):
        self.expression_string += number.num
    def visitFloat(self, number):
        self.expression_string += number.num

Prefix Print Visitor

class PrefixPrintVisitor(object):
    def __init__(self):
        self.expression_string = ''
    def visitOperation(self, operation):
        self.expression_string  += operation.op + ' '
        operation.arg1.accept(self)
        self.expression_string  += ' '
        operation.arg2.accept(self)
    def visitInteger(self, number):
        self.expression_string += number.num
    def visitFloat(self, number):
        self.expression_string += number.num

测试

infixPrintVisitor = InfixPrintVisitor()
expression.accept(infixPrintVisitor)
print(infixPrintVisitor.expression_string)
prefixPrintVisitor = PrefixPrintVisitor()
expression.accept(prefixPrintVisitor)
print(prefixPrintVisitor.expression_string)

输出

5 + 2 * 444.1
+ 5 * 2 444.1

使用附加模块

这变体使用 @functools.singledispatch() 装饰器（自 Python v3.4 起在 Python 标准库中可用）。

数据结构

class Operation(object):
    def __init__(self, op, arg1, arg2):
        self.op = op
        self.arg1 = arg1
        self.arg2 = arg2
    
class Integer(object):
    def __init__(self, num):
        self.num = num

class Float(object):
    def __init__(self, num):
        self.num = num
    
expression = Operation('+', Integer('5'), 
                            Operation('*', Integer('2'), Float('444.1')))

Infix Print Visitor

from functools import singledispatch

@singledispatch
def visitor_print_infix(obj):
    pass
@visitor_print_infix.register(Operation)
def __(operation):
    return visitor_print_infix(operation.arg1) + ' ' \
               + operation.op + ' ' \
               + visitor_print_infix(operation.arg2)
@visitor_print_infix.register(Integer)
@visitor_print_infix.register(Float)
def __(number):
    return number.num

Prefix Print Visitor

from functools import singledispatch

@singledispatch
def visitor_print_prefix(obj):
    pass
@visitor_print_prefix.register(Operation)
def __(operation):
    return operation.op + ' ' \
               + visitor_print_prefix(operation.arg1) + ' ' \
               + visitor_print_prefix(operation.arg2)
@visitor_print_prefix.register(Integer)
@visitor_print_prefix.register(Float)
def __(number):
    return number.num

测试

print(visitor_print_infix(expression))
print(visitor_print_prefix(expression))

输出

5 + 2 * 444.1
+ 5 * 2 444.1

我喜欢的原因这个变体是它消除了accept()方法并将数据结构与访问者中实现的操作完全分离。使用新元素扩展数据结构不需要更改访问者。默认情况下，访问者会忽略未知的元素类型（请参阅带有 pass 关键字的定义）。此方法的缺点是 singledispatch 装饰器不能直接与实例方法一起使用，尽管 有多种方法可以使其发挥作用。 注意：从Python 3.8开始functools .singledispatchmethod() 提供与 functools.singledispatch() 相同的功能，但用于实例方法。

对于 v3.4 之前的 Python multimethods 模块可以像 singledispatch 装饰器一样使用。多方法模块的一个缺点是，应用于给定数据结构元素的访问者方法的选择不仅基于元素的类型，而且还基于声明方法的顺序。对于具有复杂继承层次结构的数据结构来说，以正确的顺序保持方法定义可能很麻烦并且容易出错。