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

Question

我的同事建议我写一个访客模式来导航AST.任何人都可以告诉我更多我将如何开始写它？

据我所知,AST中的每个Node都有visit()方法(？)以某种方式被调用(从哪里？).这总结了我的理解.

为了简化一切,假设我有节点Root,Expression,Number,Op和树是这个样子:

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

任何人都可以想到访问者模式将如何访问此树以产生输出:

 5 + 2 * 444

谢谢,Boda Cydo.

Answer 1

请参阅该文档的ast.NodeVisitor,如粗可能性是:

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 2

维基百科非常了解访问者模式的工作原理,尽管他们使用的示例实现是Java.你可以轻松地将它移植到Python,不是吗？

基本上,您希望实现双重调度的机制.AST中的每个节点都需要实现一个accept()方法(不是visit()方法).该方法采用访问者对象作为参数.在这个accept()方法的实现中,你调用一个visit()visitor对象的方法(每个AST节点类型都有一个;在Java中,你将使用参数重载,在Python中我假设你可以使用不同的visit_*()方法).然后将使用正确的节点类型作为参数调度正确的访问者.

Answer 3

我在互联网上最常遇到的两种变体，用于实现Python中的Visitor模式：

• Gamma等人从Desigh Patterns书中对示例进行了一对一翻译。
• 使用其他模块进行双调度

Desigh模式书的翻译示例

此变体使用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')))

中印打印访客

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

前缀打印访问者

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')))

中印打印访客

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

前缀打印访问者

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装饰器不能直接与实例方法一起使用，尽管有一些方法可以使它工作。

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