Trasformazioni albero utilizzando il pattern visitatore

Question

(Disclaimer: questi esempi vengono forniti nel contesto della creazione di un compilatore, ma questa domanda riguarda esclusivamente il pattern Visitor e non richiede alcuna conoscenza della teoria del compilatore.) Sto esaminando Andrew Appel's Modern Compiler Implementazione in Java per cercare di insegnare a me stesso la teoria del compilatore (quindi no, questo non è compito a casa) e ho difficoltà a capire come vuole usare il pattern Visitor per trasformare un AST in un albero IR. (Nota: lo sto facendo in Python, quindi posso imparare anche Python, ed è per questo che gli esempi imminenti non sono in Java.) A quanto ho capito, i metodi visita e accetta nel pattern Visitor sono vidimati dalla progettazione, quindi se ho qualcosa di simile

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) 

quindi mi piacerebbe essere in grado di scrivere un metodo come

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

visitatore che si tradurrebbe le due espressioni bambino in IR e poi collegarsi con la BINOP che rappresenta l'espressione positiva. Naturalmente, questo non è possibile a meno che non modifico tutte le funzioni di accettazione per restituire informazioni extra, e questo è anche disordinato perché a volte vuoi solo un visitatore di stampa che non restituisca nulla. Tuttavia, questo testo insiste sul fatto che un visitatore è la strada giusta da percorrere, e in Java a ciò, il che significa che può essere fatto senza la flessibilità di Python. Non riesco a pensare ad alcuna soluzione che non sia incredibilmente hacky: qualcuno può illuminarmi sul design previsto?

Answer 1

Un parser SAX è un tipo di visitatore. Per evitare di aggiungere un valore di ritorno al metodo, è possibile utilizzare 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)); 
    } 

Answer 2

Avvertenza: non ho letto quel libro.

Il metodo può essere immatricolato, ma in Java (per il quale è stato scritto il libro) fa anche parte di un oggetto. Quindi, il metodo visitor può creare la struttura in una variabile membro locale, mantenendo così il contesto necessario tra le chiamate.

Quindi, ad esempio, il visitatore di stampa si accoderebbe a un oggetto StringBuilder contenuto come variabile membro (o come variabile locale finale in un metodo che ha creato l'oggetto visitatore), questo è abbastanza comune in Java, dove creare piccoli oggetti di classe interna anonima è un'abitudine comune).

In python, è possibile consentire al metodo visitatore di accedere a una variabile locale non del metodo per mantenere il contesto e creare la struttura. Ad esempio, chiusura, o un piccolo oggetto.

Update - piccola porzione di codice aggiunto come ad esempio dal commento qui sotto

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

Il primo è più bella (anche se ancora scadente commento codice di esempio), ma il secondo ti permetterebbe di mantenere il tipo di reso vuoto se davvero ne avessi bisogno.

Answer 3

Controllare il codice sorgente del compilatore THIS. Penso che il ragazzo abbia usato il pattern Visitor.