Mi colega me sugirió escribir un visitante patrón para navegar por la AST. ¿Alguien puede decirme más, ¿cómo puedo empezar a escribir esto?

Tan lejos como yo lo entiendo, cada uno de los Nodos del AST habría visit() método (?) que de alguna manera se llama (de donde?). Que concluye acerca de mi comprensión.

Para simplificar las cosas, supongamos que tengo nodos Root, Expression, Number, Op y el árbol se parece a esto:

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

Puede alguien pensar de cómo el visitante patrón de visitar este árbol para producir la salida:

 5 + 2 * 444

Gracias, Boda Cydo.

  • Añadido python etiqueta
InformationsquelleAutor bodacydo | 2010-03-26

3 Comentarios

  1. 10

    Wikipedia tiene una gran visión de conjunto de cómo el Visitante patrón funciona, aunque en el ejemplo de aplicación que utilizan en Java. Usted puede fácilmente puerto que a Python, sin embargo, no?

    Básicamente, usted desea implementar un mecanismo para doble de envío. Cada nodo del AST sería necesario implementar un accept() método (NO visit() método). El método toma como argumento, un visitante de un objeto. En la aplicación de este accept() método, usted llamar a un visit() método de la visita objeto (habrá uno para cada nodo del AST tipo; en Java, se utiliza el parámetro de la sobrecarga, en Python supongo que puede utilizar diferentes visit_*() métodos). La correcta visitante entonces será enviado con el correcto tipo de Nodo como argumento.

  2. 10

    Ver el docs para ast.NodeVisitor, por ejemplo, un crudo posibilidad 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 emiten paréntesis, incluso cuando sea necesario, etc, por lo que, de hecho, hay más trabajo por hacer, pero es un comienzo;-).

  3. 4

    Las dos variantes para implementar el Visitante patrón en Python que me encontré en Internet con más frecuencia:

    • Uno-a-uno la traducción del ejemplo de la Desigh Patrones libro Gamma et al.
    • El uso de módulos adicionales para el doble de la expedición

    Traducido Ejemplo de la Desigh Patrones Libro

    Esta variante utiliza accept() métodos en los datos de la estructura de clases y la correspondiente visit_Type() métodos 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 De Impresión 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 De Impresión 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

    El uso de módulos adicionales

    Esta variante utiliza @functools.singledispatch() decorador (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 De Impresión 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 De Impresión 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 prefieren esta variante es que se elimina la accept() métodos y separa completamente la estructura de datos de las operaciones realizadas en los visitantes. La ampliación de la estructura de datos con nuevos elementos no requiere cambio de los visitantes. Los visitantes ignorar el desconocido tipos de elemento por defecto (ver las definiciones con el pass palabra clave). Un inconveniente de este método es que singledispatch decorador no se puede utilizar con métodos de instancia directamente, aunque, hay maneras de hacer que funcione.

    Para Python antes de v3.4 multimethods módulo puede ser utilizado similar a la singledispatch decorador. Uno de los inconvenientes de la multimethods módulo es que el visitante método que se aplica a una determinada estructura de datos es el elemento seleccionado no sólo se basa en el elemento del tipo, sino que también en el orden en que los métodos se declaran. Mantener las definiciones de método en el orden correcto puede ser muy tedioso y propenso a errores para las estructuras de datos con una compleja jerarquía de herencia.

Dejar respuesta

Please enter your comment!
Please enter your name here