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

parsing compiler-construction

Question

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 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.

Answer 1

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 ;-).

Answer 2

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 de 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.

Answer 3

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

Básicamente, desea 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 un 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.