Syntaxbaum CAS

Mechanics

Visitoren brauchen nicht unbedingt Rückgabewerte, die können als weitere Member implementiert werden.

SimplifyVisitor visitor;
root->accept(visitor);
auto newRoot = visitor.simplifiedRoot();

Was in welcher Reihenfolge aufgerufen wird, könnte z.B. die Implementierung von accept des jeweiligen Knoten wissen.

henriknikolas

Ich habe nochmal lange über das Problem nachgedacht und bin zu folgendem Ergebnis gekommen:
Die Reihenfolge, in der die Visitor aufgerufen werden variert von Visitor zu Visitor. Ein SimplifyVisitor zum Beispiel brucht eine andere Reihenfolge als ein PrintVisitor. Deshalb müsste der Visitor jeweils stuern, wer oder was in welcher Reihenfolge besucht wird. Dafür brauche ich dann aber wieder Zugriff auf die Repräsentation(zum Beispiel durch Überladen des Indexoperators).
Da macht es doch dann wirklich keinen Unterschied mehr, ob ich schreibe

void SimplifyVisitor::visit(SumNode* t)
{
    SimplifyVisitor v1, v2;
    t[0]->accept(v1);
    t[1]->accept(v2);
    //weitere Aktionen...
}

oder

void simplify(Node* t)
{
    //Basisfälle für Ganzzahlen, Brüche, Symbole

    if(t->type() = Node_Type::SUM)
    {
        simplify(dynamic_cast<SumNode*>(t)[0]);  //okay, mit der Indexschreibweise siehts doch etwas unschön aus
        simplify(dynamic_cast<SumNode*>(t)[1]);
    }
    //weitere Fälle...

}

?
Brauche ich in diesem Fall das Visitor Pattern wirklich noch, also bietet es mir einen Vorteil es zu verwenden?

Mechanics

henriknikolas schrieb:

Brauche ich in diesem Fall das Visitor Pattern wirklich noch

Ja. Ist immer noch viel schöner, als dynamic_cast und irgendwelche type() Aufrufe.
Und der Aufruf wäre wahrscheinlich eher

t[0]->accept(this);

und nicht ein anderer Visitor, wobei sich das natürlich von Fall zu Fall unterscheiden kann.

Mit einem PostOrderVisitor und PreOrderVisitor als Basisklasse musst du dich nicht einmal um die Traversierung kümmern. Du sparst insgesamt viel Code und es wird sicher nicht langsamer.

Und wie gesagt, auf SumNode würde ich verzichten, wenn du nur 5 Typen hast, wird es viel übersichtlicher.

henriknikolas

Das mit dem Preorder / Posorder / Inorder als Basisklasse ist wirklich schlau!

Die Frage, die ich jetzt noch hätte, wäre wie ein visitor für eine Funktion wie
equal aussieht, also wo ein Baum mit einem anderen verglichen wird.
Als Member der jeweiligen Knoten wäre das einfach, aber wie man das als Visitor machen kann verstehe ich irgendwie nicht.

Ginge das, wäre das echt nützlich, denn dann könnte ich mir die ganzen dynamic_cast bei einer Funktion, die überprüft ob zwei Knoten richtig geordnet sind, sparen!

Vielen Dank nochmal!!!
Paul

henriknikolas

Habe es jetzt doch hingekriegt:

class equal_visitor : public visitor
{
    bool same;
    const Node* right_side;
public:
    equal_visitor(const Node* r) : right_side(r), same(false) {}

    //left_side mit right_side vergleichen und das Ergebnis in same speichern
    virtual void visit(const Sum* left_side)
    {
        if(right_side->get_type() != NodeType::SUM)
        {
            same = false;
            return;
        }

        //"Sicherung" von right_side anlegen, um es später wiederherzustellen
        const Node* tmp = right_side;
        const Sum* right = dynamic_cast<const Sum*>(right_side);

        for(int i = 0; i < left_side->number_of_operands(); ++i)
        {
            //der i-te Operand der ursprünglich rechten Seite wird neue rechte Seite
            right_side = right->get_operand(i);
            //den i-ten Operanden der linken Seite mit der rechten Seite (also dem
            //i-ten Operanden der ursprünglichen rechten Seite) vergleichen
            left_side->get_operand(i)->accept(*this);

            //Für den Fall, dass beide Seiten nicht übereinstimmen, die rechte Seite "wiederherstellen"
            if(!same)
            {
                right_side = tmp;
                same = false;
                return;
            }
        }

        //alle Operanden haben übereingestimmt
        same = true;
        //die rechte Seite "wiederherstellen"
        right_side = tmp;

    }
    virtual void visit(const Int* left_side)
    {
        if(right_side->get_type() != NodeType::INT)
        {
            same = false;
            return;
        }

        same = (left_side->get_val() == dynamic_cast<const Int*>(right_side)->get_val());
    }
    bool equal()
    {
        return same;
    }
};

Ist das grundsätzlich richtig oder kann man das noch verbessern? In dem Buch was ich mir zu Entwurfsmustern ausgeliehen habe war solch ein Fall leider nicht drin wo man eine Operation hat, die auf 2 Objekte angewendet wird / 2 Objekte verwendet.

Gruß
Paul

Sehr schön, so hätte ich es auch gemacht.

Gibt noch ein paar Geschmackssachen, z.B. hätte ich im Konstruktor same=true gesetzt (weil das der logische Default-Wert ist: Es ist gleich bis eine Stelle gefunden wurde, an der es nicht gleich ist -- dann sparst du dir ein same=true im Code), die Sicherung der RHS kannst du dir in einen RAII-Guard verpacken, das eine same=false ist überflüssig und der dynamic_cast ist eigentlich ein static_cast (ich hätte eine eigene cast-Funktion geschrieben, die in einem assert den Typ überprüft).

Das kannst du jetzt noch in eine globale Funktion equal verpacken und den equal_visitor im Source-File verstecken, dann kann es niemand falsch verwenden.

Da du schon die get_type()-Methode in allen AST-Knoten hast noch einen Hinweis wie du den visitor schneller bekommst: Schreib dir eine accept-Methode mit einem switch/case nach get_type im Basis-Visitor. Dann brauchst du kein accept in den AST-Knoten und ein Dispatch fällt weg. Zusätzlich kannst du den Basis-Visitor noch als CRTP schreiben, dann brauchst du kein virtual und der zweite Dispatch fällt weg. Aber das würde ich erst machen, wenn deine AST-Hierarchie fertig steht.

henriknikolas

Vielen vielen Dank für die ganzen Verbesserungsvorschläge!!!

meintest du das mit der accept-Methode so:

class visitor
{
protected:
    virtual void visit_sum(const Sum*) = 0;
    virtual void visit_int(const Int*) = 0;
    //weitere

public:
    void accept(const Node* t)
    {
       switch(t->get_type())
       {
       case NodeType::INT:
          visit_int(static_cast<const Int*>(t));
          break;
        //und so weiter...
        }
    }
}

Oder habe ich das falsch verstanden?
Ansonsten vielen Dank nochmal!
Gruß
Paul
};

Genau. Der grosse Geschwindigkeitsvorteil ergibt sich allerdings erst durch CRTP, weil dann alles geinlined werden kann:

template <typename T>
class visitor {
  T& get() { return *static_cast<T*>(this); }
public:
  void dispatch(Node const* n) { // oder accept
    switch (n->get_type()) {
    case NodeType::INT:
       get().visit(static_cast<const Int*>(t)); // sucht sich den passenden Overload raus
       break;
    ...
    }
  }
};

class xyz_visitor : visitor<xyz_visitor> {
  void visit(const Int *i) { ... } 
  void visit(const Sum *s) { ... } 
  ...
};

Weiterer Vorteil ist, dass du nicht alle Methoden bereitstellen musst, wenn es z.B. einen ConstantNode gibt, von dem IntNode und FractionNode erben, könntest du nur ein visit für ConstantNode anbieten.

Üblicherweise gibt get_type auch direkt eine Membervariable zurück und ist keine virtuelle Funktion, das macht es noch ein bisschen schneller.

Aber das sind Mikrooptimierungen.

henriknikolas

Das ist wirklich alles sehr sehr interessant, vielen Dank!
Kannst du mir ein Buch empfehlen, wo solche Sachen beschrieben werden?
Gruß
Paul