Kombinieren heterogener rekursiver Typen, um eine Subsprache zu definieren

Question

Ich versuche, eine grundlegende Sprache zu definieren, um Ausdrücke zu erstellen, die ich selbst aus Code bewerten werde. Solche Ausdrücke werden zur Laufzeit rekursiv definiert. Sie können dies als boolesche Ausdrücke mit elementaren Ausdrücken wie True und False betrachten und auch komplexe Ausdrücke wie die Negation eines Ausdrucks und die Disjunktion und Konjunktion zweier beliebiger Ausdrücke.

Wie bereits erwähnt, sind solche Ausdrücke rekursiv und werden zur Laufzeit erstellt, also denke ich, Vorlagen sind keine Wahl. Was ist der geeignetste Weg, Typisierung und eine Evaluierungsfunktion in C++ 2011 zu diesem Zweck zu implementieren?

Alle Kommentare sind willkommen, da meine Kenntnisse über C++ - Muster und -Funktionen leider noch nicht weit sind.

Beispiel arbeitsfreien Code, was die Tatsache zeigt, dass ich keine externe Darstellung für Ausdrücke (als Strings) benötigen:

struct basic { 
    bool val; 
}; 
struct complex_neg { 
    expression exp; 
}; 
struct complex_and { 
    expression exp1, exp2; 
}; 
struct expression : basic, complex_neg, complex_and { 
    bool eval() { 
     if (dynamic_cast<basic*>(this)) return this->val; 
     else if (dynamic_cast<complex_neg*>(this)) return !this->eval(); 
     else return this->eval() && this->eval(); 
    } 
}; 

Answer 1

Ein guter Start ist ein Baum/gerichteten Graphen Ihrer Ausdrücke zu bauen und Terminals. Siehe Abstract syntax tree.

Und dann bewerten, dass Ausdrucksbaum.

In C++ ist eine der bequemsten Möglichkeiten zum Erstellen eines AST so zu verwenden Boost Spirit, see a good introduction.

Answer 2

Die einfachste Sache, die Sie versuchen könnten, ist Shunting-yard algorithm mit inverser polnischer Notation.

Die meisten professionellen, was Sie tun können, ist boost spirit

Die bad-ass Sie tun können, zu verwenden ist, um sich einen ll-Parser für Ihre spezifische Grammatik zu implementieren. Aber Sie müssen eine Theorie über Sprachparser wissen.