Hier ist ein kurzer Stich bei einem typsicheren boost::variant basierten AST.
Ich habe eine einfache "strukturerhaltende Transformation" eingefügt, die einfach die Art der Daten ändert, die in jedem AST-Knoten gespeichert sind. Theoretisch können Sie jedoch eine beliebige astFunc schreiben, die beide eine strukturelle und datenbasierte Transformation der Knoten ausführt - schreiben Sie einfach eine type_list10, die die gültigen Typen in jedem Knoten vor und nach enthält.
template<typename... Ts>
struct type_list {};
// specialize data_type to store something special in your AST node:
// (by default, an entry means "the type of the data")
tempalte<typename T>
struct data_type { typedef T type; };
template<typename T>
using DataType = typename data_type<T>::type;
template<template<typename>class F, typename typelist>
struct map_types;
template<template<typename>class F, template<typename...>L, typename... Ts>
struct map_types<F, L<Ts...>> {
typedef L< F<Ts>... > type;
};
template<template<typename>class F, typename typelist>
using MapTypes = typename map_types<F, typelist>::type;
template<template<typename...>class F, typename typelist>
struct apply_list;
template<template<typename...>class F, template<typename...>class L, typename... Ts>
struct apply_list<F, L<Ts...>> {
typedef F<Ts...> type;
};
template<template<typename...>class F, typename typelist>
using ApplyList = typename apply_list<F, typelist>::type;
template<typename typelist>
using Var = ApplyList< boost::variant, MapTypes<DataType, typelist> >;
template<typename type_list>
struct AST_Node {
typedef std::unique_ptr<AST_Node> upAST_Node;
std::vector<upAST_Node> children;
Var<type_list> data;
template<typename T>
AST_Node(T&& t):data(std::forward<T>(t)) {}
};
template<typename type_list>
using upAST_Node = typename AST_Node<type_list>::upAST_Node;
template<typename before_types, typename after_types>
using typeFunc = std::function< Var<after_types>(Var<before_types>) >;
template<typename before_types, typename after_types>
using astFunc = std::function< upAST_Node<after_types>(upAST_Node<before_types>) >;
template<typename before_types, typename after_types>
astFunc<before_types, after_types> elementWiseTransform(typeFunc<before_types, after_types> func) {
return [func](upAST_Node<before_types> before)->upAST_Nodes<after_types> {
upAST_Node<after_types> after(new AST_Node<after_types>(func(before)));
after->children.reserve(before->children.size());
for(auto& child: before->children) {
after->children.push_back(elementWiseTransform(func)(std::move(child)));
}
return after;
};
}
Jetzt ist das nur ein Anfang.
Sie könnten weiter gehen und haben jede Art von Knoten einen anderen Satz von Arten von Kindern oder sogar eine andere Nummer. Erstellen Sie einfach Merkmalsklassen für jeden Knotentyp wie meine data_type, z. B. children_types. Dann verwenden Sie eine ähnliche Technik wie ich Var definiert, um den Typ Ihrer Kinder zu definieren. Grundsätzlich haben Sie eine variant von std::vector< AST_Node<ChildType<type_list_element>>> über eine Verkettung von MapTypes. Heck du könntest die std::vector der Kinder und die data zusammen in einer Variante bündeln.
erlaubt Dies würde Ihnen eine Zuordnung für einen einzelnen AST_Node Typen, aggregieren sie alle zusammen und erzeugt einen AST_Node<before, after> Funktors (was zu einem anderen AST_Node Typ macht) zu schreiben, die dann über den Baum gehen würden. Einige der Funktoren würden nur mit den Daten arbeiten, dann die Elternlogik übernehmen für Kinder übernehmen, einige würden ganze Teilbäume transformieren, einige würden mit den Daten arbeiten und verhindern, dass die Elternlogik über die Kinder läuft.
Diese Technik wird knifflig, weil Sie Besucher der Boost-Variante aus Ihren individuellen Funktionen auf eine Weise synthetisieren müssen, die es nicht erfordert, alle zusammen zu stapeln. Wenn Sie here betrachten, werden Sie ein paar Techniken sehen, wie man eine Menge von std::function<T(U)> nimmt und sie in einen Funktor verwandelt, der eine der Vereinigungen von U nimmt. Toss in etwas Arbeit, um die Vereinigung der Rückgabetypen zu berechnen (eine einfache type_list mit doppelten Typen entfernt, dann gepumpt in eine boost::variant, könnte es tun) - so ein "fusionierter Funktor" wäre ein gültiger Besucher.
Und jetzt können Sie „neu zuordnen ein AST-Knoten vom Typ operator_add“ functors schreiben, und „einen AST-Knoten vom Typ operator_mult neu zuordnen“, und ein paar andere, binden sie zusammen in einen Mega-Funktor, werfen sie in einem AST Traversal-Algorithmus, und haben es einen AST-Baum ausspucken mit einigen Typen in andere Typen umgewandelt ...
Aber das wäre eine Menge Arbeit.
Oh, und wir könnten wollen "Phase Tagging", wo eine Phase 1 und Phase 2 AST sind verschiedene Arten. Wir könnten jeden Typ in der type_list mit seiner Phase markieren, oder wir könnten einfach den AST Baum selbst markieren. Heck, wir könnten die Phasen für die AST unter Verwendung sonst unbenutzter struct s benennen und eine Progression durch Phasen als einen Typ definieren, um Funktor einzufügen, der in der Signatur von astFunc<before_phase, before_types, after_phase, after_types> angewandt und durchgesetzt wird.
Das ist also nicht schlecht. Wir erstellen eine type_list von Knotentypen. Diese Typen müssen nicht die tatsächlich gespeicherten Daten sein. Aber es kann sein.
Wir erstellen eine data_type Merkmalsklasse, die jeden Knotentyp auf die gespeicherten Daten abbildet. Wir erstellen eine child_types Merkmalsklasse, die jeden Knotentyp auf die type_list der untergeordneten ASTs abbildet.
Jede AST_Node speichert eine variant<AST_Concrete_Node<Ts>...>. AST_Concrete_Node enthält eine DataType<T> data; und eine MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children; (aka, std::vector< AST_Node<ChildrenTypes...> >, aber das kann man nicht direkt leicht sagen).
Als nächstes sind AST_Concrete_Node<T> Transformationsfunktionen in einem kniffligen Bit der Template-Metaprogrammierung in Boost-Varianten-Besucher zusammengefügt. Dieser Schritt ist wirklich schwierig, aber ich denke machbar. Zusätzliche Arbeit wird getan, damit nicht erwähnte Typen übersprungen werden, also müssen wir nicht ständig "oh, und wir wollen Knoten X nicht transformieren" sagen, sondern müssen sagen "wenn wir Knoten Y treffen, nicht Verwandle seine Kinder ".
An dieser Stelle werde ich sagen, dass ich schwadroniere auf - das nicht vorher getan zu haben, werden die Probleme, die in einer konkreten Durchführung dieses Durcheinander von Typgymnastik angetroffen werden, meine Fähigkeit überwältigen, darüber abstrakt zu denken . Aber die Idee ist hoffentlich nützlich - wir haben Typ-sichere Knoten-Typ-Transformationen, die wir aggregieren und eine typsichere Baum-Transformation erzeugen. Der Baum ist nicht nur ein abstrakter Baum von universellen Varianten, sondern ein Baum, in dem jeder Knoten weiß, welche Typen in seinen Kindern erlaubt sind, die rekursiv dasselbe wissen. Wir könnten sogar "das muss genau 3 Kinder haben, von denen die erste eine int ist, die zweite ist eine Bob, und die dritte ist eine double" wenn wir weit genug in das Kaninchenloch gingen.
Nette Frage, +1. –
Was ist falsch an einem generischen Baumknoten, der einen Typ, ein Literal und einen Vektor von Kindern enthält? –
Welche Typeinschränkungen sollten in Phase A auftreten, die in Phase B nicht auftreten sollten? Gibt es Einschränkungen bezüglich der Art von Parsing, die Sie zulassen möchten? Sind Sie mit der theoretischen Möglichkeit eines Laufzeitfehlers an kontrollierten Punkten in Ordnung? (Nehmen wir einmal an, in Phase 1 könnten Ihre Knoten sowohl 'Foo' als auch fünfzehn andere Typen enthalten, aber in Phase2 sollte das nicht der Fall sein. Wäre es okay, wenn Sie einen Punkt haben, an dem Sie' Foo' als Option entfernen aus dem Baum, in dem es einen Laufzeitfehler gibt, wenn Sie das nicht bereits getan haben?) – Yakk