¿Cómo escribir el patrón de visitante para el árbol de syntax abstracta en Python?

Mi colega me sugirió que escribiera un patrón de visitante para navegar el AST. ¿Alguien puede decirme más cómo podría empezar a escribirlo?

Por lo que yo entiendo, cada Nodo en AST tendría un método visit() (?) Que de alguna manera sería llamado (¿desde dónde?). Eso concluye mi entendimiento.

Para simplificar todo, supongamos que tengo nodos Root , Expression , Number , Op y el árbol tiene este aspecto:

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

¿Alguien puede pensar en cómo el patrón de visitantes visitaría este árbol para producir resultados?

  5 + 2 * 444 

Gracias, Boda Cydo.

    Wikipedia tiene una gran visión general de cómo funciona el patrón de visitante , aunque la implementación de muestra que utilizan está en Java. Sin embargo, puedes trasladar eso fácilmente a Python, ¿no?

    Básicamente, usted quiere implementar un mecanismo para el doble despacho . Cada nodo en su AST necesitaría implementar un método accept() (NO un método visit() ). El método toma, como argumento, un objeto visitante. En la implementación de este método accept() , usted llama al método visit() del objeto visitante (habrá uno para cada tipo de nodo AST; en Java, usará la sobrecarga de parámetros, en Python supongo que puede usar diferentes visit_*() métodos). El visitante correcto se enviará con el tipo de nodo correcto como argumento.

    Consulte la documentación para ast.NodeVisitor , por ejemplo, una posibilidad cruda podría ser:

     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, 

    por supuesto, esto no emite paréntesis incluso cuando es necesario, etc., por lo que en realidad hay más trabajo realizado, pero es un comienzo ;-).

    Las dos variantes para implementar el patrón de visitante en Python que encontré en Internet con mayor frecuencia:

    • Traducción uno a uno del ejemplo del libro Desigh Patterns de Gamma et al.
    • Usando módulos adicionales para doble despacho.

    Ejemplo traducido del libro de patrones Desigh

    Esta variante utiliza los métodos accept() en las clases de estructura de datos y los métodos visit_Type() correspondientes en los visitantes.

    La estructura de datos

     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 Visitante

     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 

    Prefijo Imprimir visitante

     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 

    Prueba

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

    Salida

     5 + 2 * 444.1 + 5 * 2 444.1 

    Usando módulos adicionales

    Esta variante utiliza el @functools.singledispatch() (disponible en la biblioteca estándar de Python desde Python v3.4).

    La estructura de datos

     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 Visitante

     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 

    Prefijo Imprimir visitante

     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 

    Prueba

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

    Salida

     5 + 2 * 444.1 + 5 * 2 444.1 

    La razón por la que prefiero esta variante es que elimina los métodos accept() y separa completamente la estructura de datos de las operaciones implementadas en los visitantes. Extender la estructura de datos con nuevos elementos no requiere cambiar los visitantes. Los visitantes ignoran los tipos de elementos desconocidos de forma predeterminada (consulte las definiciones con la palabra clave pass ). Un inconveniente de este método es que el decorador de singledispatch no se puede usar directamente con los métodos de instancia, aunque hay formas de hacerlo funcionar .

    Para Python antes de v3.4, el módulo de métodos múltiples se puede utilizar de forma similar al decorador de partidas individuales. Un inconveniente del módulo de métodos múltiples es que el método de visitante que se aplica a un elemento de estructura de datos dado se selecciona no solo en función del tipo de elemento sino también en el orden en que se declaran los métodos. Mantener las definiciones de los métodos en el orden correcto puede ser engorroso y propenso a errores para estructuras de datos con una jerarquía de herencia compleja.