如何在 Python 中编写抽象语法树的访问者模式？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2525677/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to write the Visitor Pattern for Abstract Syntax Tree in Python?
提问by bodacydo
My collegue suggested me to write a visitor pattern to navigate the AST. Can anyone tell me more how would I start writing it?
我的同事建议我编写一个访问者模式来导航 AST。谁能告诉我更多我将如何开始写作？
As far as I understand, each Node in AST would have visit()method (?) that would somehow get called (from where?). That about concludes my understanding.
据我了解，AST 中的每个节点都会有visit()方法 (?) 以某种方式被调用（从哪里？）。我的理解到此结束。
To simplify everything, suppose I have nodes Root, Expression, Number, Opand the tree looks like this:
为了简化一切，假设我有节点Root, Expression, Number，Op树看起来像这样：
Root
|
Op(+)
/ \
/ \
Number(5) \
Op(*)
/ \
/ \
/ \
Number(2) Number(444)
Can anyone think of how the visitor pattern would visit this tree to produce output:
谁能想到访问者模式将如何访问这棵树以产生输出：
5 + 2 * 444
Thanks, Boda Cydo.
谢谢，博达·西多。
采纳答案by Santa
Wikipedia has a great overview of how the Visitor pattern works, although the sample implementation that they use is in Java. You can easily port that to Python, though, no?
Wikipedia对访问者模式的工作原理有很好的概述，尽管它们使用的示例实现是用 Java 编写的。不过，您可以轻松地将其移植到 Python 中，不是吗？
Basically, you want to implement a mechanism for double dispatch. Each node in your AST would need to implement an accept()method (NOT a visit()method). The method takes, as an argument, a visitor object. In the implementation of this accept()method, you call a visit()method of the visitor object (there will be one for each AST node type; in Java, you'll use parameter overloading, in Python I suppose you can use different visit_*()methods). The correct visitor will then be dispatched with the correct Node type as argument.
基本上，您想要实现双重调度机制。AST 中的每个节点都需要实现一个accept()方法（不是visit()方法）。该方法将访问者对象作为参数。在这个accept()方法的实现中，你调用了一个visit()访问者对象的方法（每个AST节点类型都会有一个方法；在Java中，你将使用参数重载，在Python中我想你可以使用不同的visit_*()方法）。然后将使用正确的节点类型作为参数分派正确的访问者。
回答by Alex Martelli
See the docsfor ast.NodeVisitor, e.g. a crude possibility might be:
请参阅该文档的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,
of course this doesn't emit parentheses even where needed, etc, so there's actually more work done, but, it's a start;-).
当然，即使在需要的地方，这也不会发出括号等，因此实际上还有更多工作要做，但是，这是一个开始；-)。
回答by SergiyKolesnikov
The two variants to implement the Visitor pattern in Python that I encountered on the Internet most often:
我在网上最常遇到的在 Python 中实现访问者模式的两种变体：
- One-to-one translation of the example from the Desigh Patterns book by Gamma et al.
- Using additional modules for double-dispatch
- Gamma 等人的 Desigh Patterns 一书中的示例的一对一翻译。
- 使用附加模块进行双分派
Translated Example from the Desigh Patterns Book
Desigh Patterns 书中的翻译示例
This variant uses accept()methods in the data structure classes and corresponding visit_Type()methods in the visitors.
该变体使用accept()数据结构类中的visit_Type()方法和访问者中的相应方法。
The data structure
数据结构
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
Infix 打印访问者
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
Test
测试
infixPrintVisitor = InfixPrintVisitor()
expression.accept(infixPrintVisitor)
print(infixPrintVisitor.expression_string)
prefixPrintVisitor = PrefixPrintVisitor()
expression.accept(prefixPrintVisitor)
print(prefixPrintVisitor.expression_string)
Output
输出
5 + 2 * 444.1
+ 5 * 2 444.1
Using additional modules
使用附加模块
This variant uses @functools.singledispatch()decorator (available in the Python Standard Library since Python v3.4).
此变体使用@functools.singledispatch()装饰器（自 Python v3.4 起可在 Python 标准库中使用）。
The data structure
数据结构
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
Infix 打印访问者
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
Test
测试
print(visitor_print_infix(expression))
print(visitor_print_prefix(expression))
Output
输出
5 + 2 * 444.1
+ 5 * 2 444.1
The reason I prefer this variant is that it eliminates the accept()methods and completely separates the data structure from the operations implemented in the visitors. Extending the data structure with new elements does not require changing the visitors. The visitors ignore the unknown element types by default (see the definitions with the passkeyword). A drawback of this method is that singledispatchdecorator cannot be used with instance methods directly, although, there are ways to make it work.
我更喜欢这个变体的原因是它消除了accept()方法并将数据结构与访问者中实现的操作完全分开。使用新元素扩展数据结构不需要更改访问者。默认情况下，访问者会忽略未知元素类型（请参阅pass关键字的定义）。这种方法的一个缺点是singledispatch装饰器不能直接与实例方法一起使用，尽管有一些方法可以使它工作。
For Python before v3.4 multimethodsmodule can be used similar to the singledispatch decorator. One drawback of the multimethods module is that the visitor method that is applied to a given data-structure element is selected not only based on the element's type but also on the order in which the methods are declared. Keeping the method definitions in the right order can be cumbersome and error prone for data structures with a complex inheritance hierarchy.
对于 v3.4 之前的 Python，可以使用类似于 singledispatch 装饰器的multimethods模块。multimethods 模块的一个缺点是，应用于给定数据结构元素的访问者方法的选择不仅基于元素的类型，还基于方法声明的顺序。对于具有复杂继承层次结构的数据结构，以正确的顺序保持方法定义可能很麻烦且容易出错。
