Transformacje drzewa przy użyciu wzorca odwiedzającego

Question

(Uwaga: te przykłady podano w kontekście budowania kompilatora, ale to pytanie dotyczy wzorca gościa i nie wymaga znajomości teorii kompilatorów.) Przechodzę przez stronę Andrew Appela Nowoczesna implementacja kompilatora w Javie, aby spróbować nauczyć się teorii kompilatora (więc nie, to nie jest praca domowa) i mam problem ze zrozumieniem, w jaki sposób chce wykorzystać wzorzec Odwiedzający, aby przekształcić AST w drzewo IR. (Uwaga: robię to w Pythonie, więc mogę również nauczyć się Pythona, dlatego nadchodzące przykłady nie są w Javie.) Jak rozumiem, metody odwiedzin i akceptacji w wzorzec Visitor są puste-typowane według projektu, więc jeśli mam coś podobnego

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) 

następnie Chciałbym móc napisać metodę odwiedzających jak

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

co przełożyłoby dwóch wyrażeń dziecko w podczerwieni, a następnie połączyć je z BINOP reprezentujący wyrażenie plus. Oczywiście nie jest to możliwe, dopóki nie zmodyfikuję wszystkich funkcji akceptujących, aby zwrócić dodatkowe informacje, a to jest również kłopotliwe, ponieważ czasami po prostu chcesz drukowanego użytkownika, który niczego nie zwraca. Tekst ten twierdzi jednak, że odwiedzający to właściwa droga, a na tym w Javie, co oznacza, że ​​można to zrobić bez elastyczności Pythona. Nie mogę wymyślić żadnych rozwiązań, które nie są niewiarygodnie hackowe - czy ktoś może mnie oświecić, jeśli chodzi o projekt?

Answer 1

Parser SAX jest rodzajem gościa. Aby uniknąć dodawania wartości zwracanej do metody, można użyć stosu:

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

Zastrzeżenie: nie czytałem tej książki.

Metoda może być void-typowana, ale w Javie (której książka została napisana) jest również częścią obiektu. Tak więc metoda odwiedzająca może budować strukturę w lokalnej zmiennej składowej, zachowując niezbędny kontekst między wywołaniami.

Na przykład użytkownik wydruku będzie dołączał do StringBuilder, który jest przechowywany jako zmienna składowa (lub jako ostateczna lokalna zmienna w metodzie, która utworzyła obiekt odwiedzający - jest to dość powszechne w Javie, gdzie tworzenie małych anonimowych obiektów klasy wewnętrznej jest powszechnym nawykiem).

W pythonie można w podobny sposób pozwolić metodzie odwiedzającej uzyskać dostęp do zmiennej lokalnej bez metody, aby zachować kontekst i zbudować strukturę. Np. Zamknięcie lub mały przedmiot.

Aktualizacja - mały fragment kodu dodaje się jako przykład, z komentarzem poniżej

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

lub

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

Pierwszy ładniejszy (choć nadal słaba komentarz przykład kod), natomiast druga pozwoliłoby ci zachować nieważny typ zwrotu, jeśli naprawdę tego potrzebujesz.

Answer 3

Sprawdź kod źródłowy kompilatora THIS. Myślę, że facet użył wzorca Odwiedzającego.