如何在Python中为抽象语法树编写访问者模式？
我的同事建议我写一个访问者模式来遍历抽象语法树（AST）。有没有人能告诉我该怎么开始写呢？
根据我的理解，AST中的每个节点都会有一个visit()方法（？），这个方法会在某个地方被调用（从哪里调用呢？）。这就是我目前的理解了。
为了简化问题，假设我有一些节点，比如Root、Expression、Number、Op，树的结构大致是这样的：
Root
|
Op(+)
/ \
/ \
Number(5) \
Op(*)
/ \
/ \
/ \
Number(2) Number(444)
有没有人能想出访问者模式是如何遍历这个树并产生输出的呢：
5 + 2 * 444
谢谢，Boda Cydo。
3 个回答
我在网上遇到的实现访问者模式的两种常见方式：
- 直接翻译自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')))
中缀打印访问者
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 3.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 装饰器不能直接用于实例方法，尽管 有办法让它工作。注意： 从Python 3.8开始，functools.singledispatchmethod() 提供了与 functools.singledispatch() 相同的功能，但适用于实例方法。
对于Python 3.4之前的版本，可以使用 multimethods 模块，类似于singledispatch装饰器。multimethods模块的一个缺点是，应用于特定数据结构元素的访问者方法不仅根据元素的类型选择，还根据方法声明的顺序选择。对于具有复杂继承层次的数据结构，保持方法定义的正确顺序可能会很麻烦且容易出错。
可以查看这份文档，里面讲的是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,
当然，这个例子在需要加括号的地方并没有加括号等等，所以实际上还有更多的工作要做，但这算是一个开始;-).