在C++中表示一個多遍抽象語法樹（AST）？

Question

我目前正在探索設計一個在多個階段轉換其AST的編譯器。這個想法是，從分析樹開始，每一遍都會轉換樹，直到生成的AST得到優化，並且在生成中間代碼所需的樹的每個節點（在此例中爲LLVM IR）中包含所有必需的信息。通過樹可能會大大改變其結構，例如通過operator precedence parsing將操作符和操作數列表更改爲有序操作的層次結構。請注意，通行證可能會使部分結構完全不變。因此，我的問題是我如何最好（閱讀：最簡單，儘可能少的重複）代表一個在C++中有多箇中間表示的AST？我希望每個階段的AST版本的節點類型在編譯時尊重它們的不兼容性。我認爲關鍵的問題是我應該如何表示結構中不通過通關的部分，同時避免重複性代碼？我想這是編譯器作者過去多次解決的問題。

請注意，我目前在我的AST中使用Boost Variant而不是正常的運行時多態性，並且希望解決方案也與其兼容。

Answer 1

這是一個基於AST的類型安全的boost::variant的快速刺戳。

我包含了一個簡單的「結構保留變換」，它簡單地改變了存儲在每個AST節點中的數據類型。然而，從理論上講，你可以編寫一個任意的astFunc，它們都執行節點的基於結構和數據的轉換 - 只需編寫一個type_list，其中包含前後每個節點中的有效類型。

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

現在，這只是一個開始。

你可以走得更遠了，每種類型的節點都有一組不同的子類型，甚至不同的數字。只需爲我的data_type中的每種類型節點創建traits類，如children_types。然後使用類似的技術來定義Var來定義你的孩子的類型。基本上，通過鏈接MapTypes可以獲得variant的std::vector< AST_Node<ChildType<type_list_element>>>。你可以將兒童的std::vector和data合併爲一個變體。

這將允許您編寫一個個人AST_Node類型的映射（這使得另一個AST_Node類型），將它們聚集在一起並生成一個函數，然後將遍歷該樹。有些函子會對數據進行操作，只有讓父邏輯接管孩子，一些會轉換整個子樹，一些會對數據進行操作，並停止父邏輯運行在孩子身上。

該技巧變得棘手，因爲您必須以不需要將它們堆疊在一起的方式綜合來自各個功能的提升變體訪問者。如果你看here，你會看到一些關於如何使用一堆std::function<T(U)>的技巧，並將它們變成一個函子，它可以使用U中的任何一個。折騰一些工作來計算返回類型的聯合（一個簡單的type_list刪除重複類型，然後抽入boost::variant，可能會這樣做） - 這樣的「合併函數」將是一個有效的訪問者。

現在，您可以編寫「重新映射operator_add類型的AST節點」函子，並「重新映射operator_mult類型的AST節點」等幾個函數，將它們組合成一個超級函子，將它們放在AST遍歷算法，並且它將一些類型轉換爲其他類型的AST樹映射出來...

但是，這將是很多工作。

哦，我們可能需要「階段標記」，階段1和階段2 AST是不同的類型。我們可以在type_list的階段標記每種類型，或者我們可以標記AST樹本身。哎呀，我們可以使用其他未使用的struct s來命名AST的階段，並將階段的階段定義爲類型函數的類型，並在astFunc<before_phase, before_types, after_phase, after_types>的簽名中應用和執行。

所以這並不壞。我們創建了一個節點類型的type_list。這些類型不一定是存儲的實際數據。但它可以。

我們創建了一個data_type特徵類，它將每個節點類型映射到存儲的數據。我們創建一個child_types traits類，它將每個節點類型映射到子AST的type_list。

每個AST_Node存儲一個variant<AST_Concrete_Node<Ts>...>。 AST_Concrete_Node包含一個DataType<T> data;和一個MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children;（又名，std::vector< AST_Node<ChildrenTypes...> >，但您不能直接輕鬆地說）。

接下來，AST_Concrete_Node<T>轉換函數在模板元編程的一些棘手問題中連接在一起，形成提升變體訪問者。這一步真的很棘手，但我認爲可行。額外的工作是爲了避免未提及的類型，所以我們不必經常說「哦，我們不想改變節點X」，而是必須說「如果我們打到節點Y，不要改變孩子「。

在這一點上，我要說我在喋喋不休 - 以前沒有這樣做過，在具體實施這種類型的體操混亂中遇到的問題將壓倒我抽象地推理它的能力。但這個想法有希望有用 - 我們有類型安全的節點類型轉換，我們聚合在一起並生成類型安全的樹轉換。樹不僅僅是一個通用變體的抽象樹，而是一棵樹，每個節點都知道它的子元素允許的類型，它遞歸地知道相同的類型。我們甚至可以處理「如果我們進入兔子洞的距離足夠遠，那麼」必須有三個孩子，其中第一個是int，第二個是Bob，第三個是double「。

Answer 2

AST節點本身並不需要大量的複雜性。我認爲所有這些AST節點機器都只是矯枉過正。

AST的問題不是節點類型安全;其樹形狀安全。 AST代表（大概）某種語言L的某個有效實例。理想情況下，您希望AST上的轉換生成其他有效的AST（語言L的實例）。通過保證任何一個節點具有有效類型，您都不會保證這一點;你只能通過保證任何樹形補丁產生有效的樹來做到這一點。如果樹操作是原子操作（例如，「改變節點」，「替換孩子」，「替換父母」）並且單獨應用，則這是非常困難的;經過幾個這樣的步驟後，你可以說什麼關於樹？

使用一種樹重寫事務，例如，，語言結構對語言L有效的源到源轉換，以及適用於該轉換的地方。

最標準program transformation systems做到這一點。他們通過持有L語法模型並檢查提出的轉換是否良好類型來實現這一點。這確保了語言L到語言L的轉換保持良好形式。

如果轉換從一種語言A映射到另一種語言B，則這很難得到正確的結果;如果應用了某些轉換，通常會得到一種混合類型的樹，這兩種語言在任何一種語言中都不合法。小心，可以定義一組轉換，將A語言的所有子樹映射到B語言，並將其詳盡應用;那麼您希望生成的樹適合於B.您可以確保在混合樹中插入B補丁時，如果它與另一個B補丁相鄰，則生成的複合B補丁很好形成。這可以使用相同風格的語法檢查。

使用這些想法，您可以構建一個系統，通過一系列「表示法」（語言A，B，C ...）映射AST，並且相信結果樹是良好的形狀。這個想法概括爲圖形重寫。