Les transformations de l'arbre via Motif Visiteur

Question

(Avertissement: ces exemples sont donnés dans le cadre de la construction d'un compilateur, mais cette question est tout au sujet de la structure des visiteurs et ne nécessite aucune connaissance de la théorie du compilateur.) Je vais à travers la mise en œuvre du compilateur moderne d'Andrew Appel en Java pour essayer de me enseigner la théorie compilateur (donc pas, ce n'est pas devoirs) et je vais avoir du mal à comprendre comment il veut utiliser le modèle des visiteurs pour transformer un AST à un arbre IR. (Note: Je fais cela en Python pour que je puisse apprendre Python aussi, ce qui explique pourquoi les exemples à venir ne sont pas en Java.) Si je comprends bien, la visite et accepte les méthodes dans le modèle des visiteurs sont vides tapée par la conception, donc si j'ai quelque chose comme

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)

alors je voudrais être en mesure d'écrire une méthode de visiteur comme

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

qui se traduirait par les deux expressions de l'enfant dans IR, puis les relier à l'binop représentant l'expression plus. Bien sûr, cela est impossible à moins que je modifie toutes les fonctions acceptent de revenir informations supplémentaires, et qui est aussi en désordre parce que parfois vous voulez juste un visiteur d'impression qui ne retourne rien. Pourtant, ce texte insiste sur le fait qu'un visiteur est la bonne façon d'aller, et en Java à ce qui signifie qu'il peut se faire sans la flexibilité de Python. Je ne peux pas penser à des solutions qui ne sont pas incroyablement hacky - quelqu'un peut me éclairer sur la conception prévue

Answer 1

Un analyseur SAX est une sorte de visiteur. Pour éviter d'ajouter une valeur de retour à la méthode, vous pouvez utiliser une pile:

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

Regardez le code source de CE compilateur . Je pense que le gars a utilisé modèle des visiteurs.

Answer 3

Caveat: Je n'ai pas lu ce livre

.

La méthode peut être vide typé, mais en Java (que le livre a été écrit pour), il fait également partie d'un objet. Ainsi, la méthode de visiteur peut construire la structure dans une variable membre local, maintenant ainsi le contexte nécessaire entre les appels.

Ainsi, par exemple, votre visiteur d'impression serait annexe à un StringBuilder qui est maintenu en tant que variable membre (ou comme une variable locale finale dans une méthode qui a créé l'objet visiteur - c'est assez commun en Java, où la création petits objets de la classe interne anonyme est une habitude commune).

En python, vous pouvez laisser l'accès de la même méthode de visiteur une variable non-méthode locale pour maintenir le contexte et construire la structure. Par exemple, la fermeture, ou un petit objet.

Mise à jour - petit morceau de code ajouté comme exemple de commentaire ci-dessous

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

ou

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

La première est plus jolie (mais encore un exemple de code merdique commentaire), mais la seconde vous permettrait de garder le type de retour de vide si vous avez vraiment besoin de.