java - Transformaciones de árbol usando patrón de visitante

python tree

Question

(Descargo de responsabilidad: estos ejemplos se dan en el contexto de compilar un compilador, pero esta pregunta tiene que ver con el patrón Visitor y no requiere ningún conocimiento de la teoría del compilador). Estoy revisando la implementación del compilador moderno de Andrew Appel en Java para intentar enseñarme la teoría del compilador (así que no, esto no es tarea) y tengo problemas para entender cómo él quiere usar el patrón Visitor para transformar un AST en un árbol IR. (Nota: estoy haciendo esto en Python para poder aprender Python también, y es por eso que los próximos ejemplos no están en Java). Según tengo entendido, los métodos de visita y aceptación en el patrón de Visitor son de tipo nulo por diseño, así que si tengo algo así

class PlusExp(Exp):
    def __init__(self, exp_left, exp_right):
        self.exp_left = exp_left
        self.exp_right = exp_right

    def accept(self, v):
        v.visit_plus_exp(self)

entonces me gustaría poder escribir un método de visitante como

def visit_plus_exp(self, plus_exp):
    return BINOP(BinOp.PLUS, 
                 plus_exp.exp_left.accept(self), 
                 plus_exp.exp_right.accept(self))

que traduciría las dos expresiones hijo en IR y luego las vincularía con el BINOP que representa la expresión más. Por supuesto, esto no es posible a menos que modifique todas las funciones de aceptación para devolver información adicional, y eso también es complicado porque a veces solo quieres un visitante de impresión que no devuelve nada. Sin embargo, este texto insiste en que un visitante es el camino correcto, y en Java, lo que significa que se puede hacer sin la flexibilidad de Python. No se me ocurre ninguna solución que no sea increíblemente hacky. ¿Alguien puede informarme sobre el diseño previsto?

Answer 1

Advertencia: no he leído ese libro.

El método puede ser de tipo nulo, pero en Java (para el cual se escribió el libro) también es parte de un objeto. Por lo tanto, el método visitante puede construir la estructura en una variable miembro local, manteniendo así el contexto necesario entre las llamadas.

Entonces, por ejemplo, su visitante de impresión se agregaría a un StringBuilder que se mantiene como una variable miembro (o como una variable local final en un método que crea el objeto de visitante; esto es bastante común en Java, donde se crea un pequeño anónimo). objetos de clase interna es un hábito común).

En Python, también podría permitir que el método de visitante acceda a una variable que no sea de método local para mantener el contexto y crear la estructura. Por ejemplo, cierre o un objeto pequeño.

Actualización: pequeño fragmento de código agregado como ejemplo del comentario a continuación

result = new Node();
result.left.add(n1.accept(this)); 
result.right.add(n2.accept(this)); 
return result;

o

result = new Node(); 
this.nextLoc.add(result); 
this.nextLoc = result.left; 
n1.accept(this); 
this.nextLoc = result.right; 
n2.accept(this); 

El primero es más bonito (aunque sigue siendo un código de ejemplo de comentario chiflado), pero el segundo le permite mantener el tipo de retorno anulado si realmente lo necesita.

Answer 2

Mire el código fuente de ESTE compilador. Creo que el chico ha usado el patrón de visitante.

Answer 3

Un analizador SAX es un tipo de visitante. Para evitar agregar un valor de retorno al método, puede usar una pila:

class Visitor {
    Stack<Node> stack = new Stack<Node>();

//    . . .

    void visitPlus(PlusExp pe) {
        pe.left.accept(this);
        pe.right.accept(this);
        Node b = stack.pop();
        Node a = stack.pop();
        stack.push(new BinOp(BinOp.PLUS, a, b));
    }