Reprezentacja wieloprzebiegowego drzewa składni abstrakcyjnej (AST) w C++?

Question

Obecnie badam projektowanie kompilatora, który przekształca jego AST w wielu etapach. Chodzi o to, że począwszy od drzewa analizy, każde przejście przekształca drzewo, aż uzyskana AST jest zoptymalizowana i zawiera wszystkie wymagane informacje w każdym węźle drzewa wymagane do wygenerowania kodu pośredniego (w tym przypadku LLVM IR). Przejście przez drzewo może znacznie zmienić jego strukturę, na przykład zmieniając listę operatorów i operandów na hierarchię uporządkowanych operacji za pośrednictwem operator precedence parsing. Należy pamiętać, że podanie może pozostawić części konstrukcji całkowicie niezmienione.

Moje pytanie brzmi: jak najlepiej (czytać: najłatwiej, z możliwie najmniejszą liczbą powtórzeń) reprezentują AST, który ma wiele pośrednich reprezentacji w C++? Chciałbym, aby typy węzłów z wersji AST każdej fazy, respektowały ich niekompatybilność podczas kompilacji. Uważam, że kluczową kwestią jest to, jak powinienem reprezentować części struktury, które nie zmieniają się między przejściami, unikając powtarzania kodu? Wyobrażam sobie, że jest to problem rozwiązywany wiele razy w przeszłości przez autorów kompilacji.

Zauważ, że obecnie używam Boost Variant zamiast normalnego polimorfizmu czasu pracy w moim AST i chciałbym, aby rozwiązanie było z nim kompatybilne.

Answer 1

Oto szybkie uderzenie w AST opartą na typach boost::variant.

Zawarłem prostą "transformatę zachowującą strukturę", która po prostu zmienia typ danych przechowywanych w każdym węźle AST. Teoretycznie można jednak napisać dowolną wartość astFunc, która zarówno dokonuje strukturalnej, jak i opartej na danych transformacji węzłów - wystarczy napisać type_list, która zawiera poprawne typy w każdym węźle przed i po nim.

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; 
    }; 
} 

To dopiero początek.

Można pójść dalej, a każdy typ węzła ma inny zestaw typów dzieci, a nawet inny numer. Po prostu utwórz klasy cech dla każdego typu węzła, takiego jak mój data_type, na przykład children_types. Następnie użyj podobnej techniki do zdefiniowania, jak zdefiniowałem typ twoich dzieci. Zasadniczo masz variant z std::vector< AST_Node<ChildType<type_list_element>>> za pomocą łańcucha z MapTypes. Heck można połączyć std::vector dzieci i data razem w jednym wariancie.

Pozwoliłoby to napisać mapowania dla indywidualnego AST_Node typu (co sprawia, że ​​do innego AST_Node typu), agregować je wszystkie razem i wygenerować AST_Node<before, after> funktor, który potem chodzić na drzewie. Niektóre funktory działałyby na danych tylko wtedy, gdy logika rodzicielska przejmowałaby dla dzieci, inne przekształcałyby całe poddrzewia, inne działałyby na danych i zatrzymywałyby logikę nadrzędną nad dziećmi.

Technika ta staje się trudna, ponieważ trzeba zsyntetyzować użytkowników wariantów boost z poszczególnych funkcji w sposób, który nie wymaga ich układania. Jeśli spojrzysz na here, zobaczysz kilka technik, jak zebrać kilka std::function<T(U)> i przekształcić je w jeden funktor, który przyjmuje jedną z unii U. Rzuć trochę pracy, aby obliczyć związek zwrotów (prosty type_list z usuniętymi zduplikowanymi typami, a następnie wpompować do boost::variant, może to zrobić) - taki "scalony funktor" byłby ważnym gościem.

A teraz możesz napisać "remapowanie węzła AST o typie operator_add", a "zmapować węzeł AST typu operator_mult", a także kilka innych, związać je razem w mega-funktora, rzucić je w AST Algorytm traversal, i niech wypluje drzewo AST z niektórymi typami przekonwertowanymi na inne typy ...

Ale to byłoby dużo pracy.

Aha, i możemy chcieć "oznaczania fazy", gdzie faza 1 i faza 2 AST to różne typy. Możemy oznaczyć każdy typ w type_list jego fazą lub możemy po prostu oznaczyć samo drzewo AST. Heck, moglibyśmy nazwać fazy dla AST używając nieużywanych struct s i zdefiniować progresję poprzez fazy jako typ do typu funktor, który zostanie zastosowany i wymuszony w sygnaturze astFunc<before_phase, before_types, after_phase, after_types>.

To nie jest złe. Tworzymy type_list typów węzłów. Te typy nie muszą być rzeczywistymi przechowywanymi danymi. Ale może tak być.

Tworzymy klasę cech data_type, która odwzorowuje każdy typ węzła na przechowywane dane. Tworzymy klasę cech child_types, która odwzorowuje każdy typ węzła na listę_typów podrzędnych AST.

Każdy AST_Node przechowuje variant<AST_Concrete_Node<Ts>...>. AST_Concrete_Node zawiera DataType<T> data; i MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children; (aka, std::vector< AST_Node<ChildrenTypes...> >, ale nie można tego bezpośrednio powiedzieć).

Następna, AST_Concrete_Node<T> funkcje transformacji są łączone ze sobą w trudny bit metaprogramowania szablonu do wariantów wariantu doładowania. Ten krok jest naprawdę trudny, ale myślę, że to wykonalne. Dodatkowe prace są wykonywane, aby pominąć wymienione typy, więc nie musimy ciągle mówić "o, a nie chcemy przekształcać węzła X", ale raczej musimy powiedzieć "jeśli trafimy w węzeł Y, nie przekształcić swoje dzieci ".

W tym momencie zamierzam powiedzieć, że jestem blathering - nie robiąc tego wcześniej, problemy napotkane w konkretnej realizacji tego bałaganu typu gimnastyka będzie przerastać moją zdolność do abstrakcyjnego rozumowania na ten temat . Ale pomysł jest miejmy nadzieję przydatny - mamy transformacje typu węzłowego, które łączymy i generujemy bezpieczną dla drzewa transformację. Drzewo nie jest jedynie abstrakcyjnym drzewem uniwersalnych wariantów, ale drzewem, w którym każdy węzeł wie, jakie typy dozwolone są w jego potomkach, które rekursywnie znają to samo. Moglibyśmy nawet obsłużyć "to musi mieć dokładnie 3 dzieci, z których pierwsza to int, druga to Bob, a trzecia to double" jeśli przeszliśmy wystarczająco daleko w króliczej dziurze.

Answer 2

Węzły AST same w sobie nie potrzebują ogromnej złożoności. Myślę, że wszystkie te maszyny węzła AST są po prostu przesadzone.

Problem z AST nie jest związany z bezpieczeństwem węzłów; jego kształt drzewa bezpieczeństwa. AST reprezentuje (przypuszczalnie) pewną ważną instancję jakiegoś języka L. Czego właśnie potrzebujesz do transformacji na AST, aby stworzyć inne ważne AST (wystąpienia języka L). Nie gwarantujesz tego, gwarantując, że każdy węzeł ma poprawny typ; możesz to zrobić tylko przez zagwarantowanie, że jakakolwiek łatka drzewa tworzy ważne drzewo . Jest to bardzo trudne, jeśli operacje drzewa są atomowe (np. "Zmień węzeł", "zastąp dziecko", "zastąp rodzica") i zastosuj osobno; po kilku takich krokach, co dokładnie możesz powiedzieć o drzewie?

Można to lepiej zrobić, wykonując rodzaj operacji przepisywania drzewa, np.transformacje źródło-źródło, których struktura gramatyczna jest poprawna dla języka L i które są stosowane w miejscach, które są ważne dla tej transformacji.

Wykonuje to większość standardu program transformation systems. Osiągają to, utrzymując model gramatyki dla L i sprawdzając, czy proponowane transformacje są dobrze napisane. Zapewnia to, że transformacje języka L na język L pozostają dobrze sformułowane.

To jest trudniejsze do uzyskania, jeśli transformacje mapują z jednego języka A ​​na inny język B; jeśli niektóre z takich transformacji są stosowane, zwykle uzyskuje się drzewo z typami mieszanymi, które nie są legalne w żadnym z tych języków. Z troską można zdefiniować zestaw transformacji, które mapują wszystkie podrasy języka A ​​na język B i stosują je w sposób wyczerpujący; następnie chcesz, aby wynikowe drzewo było dobrze uformowane dla B. Możesz zapewnić, że przez naleganie za każdym razem, gdy wstawka B zostanie wstawiona do drzewa mieszanego, jeśli sąsiaduje z inną opaską B, to otrzymany złożony B-plaster jest dobrze powstały. Możesz to zrobić za pomocą tego samego stylu sprawdzania gramatyki.

Korzystając z tych pomysłów, można zbudować system, który mapuje AST za pomocą szeregu "reprezentacji" (język A, B, C, ...) i ma pewną wiarę, że drzewo wyników jest dobrze ukształtowane. Pomysł ten generalizuje się na przepisywanie wykresów.