Boost :: Spirit :: Qi autorules - 避免重複複製AST數據結構

我一直在使用Qi和Karma對幾種小語言進行一些處理。大部分語法都很小（20-40條規則）。我幾乎只能使用autorules，所以我的分析樹完全由變體，結構體和std :: vectors組成。Boost :: Spirit :: Qi autorules - 避免重複複製AST數據結構

這種設置對於一般情況下的偉大工程：
1）分析的東西（齊），
2）讓未成年人操作的解析樹（訪問者），並
3）輸出的東西（噶瑪）。

但是，我擔心如果我想對語法樹進行復雜的結構更改（如移動大的子樹），會發生什麼情況。請看下面的玩具例子：

一種使用autorules S-EXPR式邏輯表達式語法...

// Inside grammar class; rule names match struct names... 
pexpr %= pand | por | var | bconst; 
pand %= lit("(and ") >> (pexpr % lit(" ")) >> ")"; 
por %= lit("(or ") >> (pexpr % lit(" ")) >> ")"; 
pnot %= lit("(not ") >> pexpr >> ")";

...這將導致解析樹表示，看起來像這樣...

struct var { 
    std::string name; 
}; 
struct bconst { 
    bool val; 
}; 

struct pand; 
struct por; 
struct pnot;        

typedef boost::variant<bconst, 
         var, 
         boost::recursive_wrapper<pand>, 
         boost::recursive_wrapper<por>, 
         boost::recursive_wrapper<pnot> > pexpr; 
struct pand { 
    std::vector<pexpr> operands;      
}; 

struct por { 
    std::vector<pexpr> operands;      
}; 

struct pnot { 
    pexpr victim; 
}; 

// Many Fusion Macros here

假設我有一個解析樹看起來是這樣的：

 pand 
    /... \ 
    por  por 
/\ /\ 
var var var var

（T他省略號的意思是「許多類似形狀的更多的孩子爲pand。」）

現在，假設我想否定每個por節點，從而使最終的結果是：

 pand 
    /... \ 
    pnot  pnot 
    |  | 
    por  por 
/\ /\ 
var var var var

的直接的方法是是，對於每個子樹por：
- 創建pnot節點
（拷貝por在施工）;
- 在pand節點
（副本pnot節點及其por子樹）中重新分配適當的向量時隙。

或者，我可以構建一個單獨的向量，然後替換（交換）向量批發，消除第二輪複製。

與基於指針的樹表示相比，所有這些看起來都很麻煩，這將允許插入pnot節點而不需要複製現有節點。我的問題：

有沒有辦法避免使用autorule兼容數據結構的複製樹操作？我是否應該咬緊牙關，只使用非自動編譯來構建基於指針的AST（例如，http://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/）？

來源

2011-01-10 phooji

複製子樹不應該像您所假設的那樣昂貴，因爲recursive_variant本質上是一個shared_ptr的包裝。我相信，這不僅是最好的，也是最簡單的解決方案。

來源

2011-01-10 23:51:32 hkaiser

感謝您的見解。我沒有太注意變體的實現。我運行了一個快速實驗來驗證哪些操作會導致複製： - 在兩個現有節點之間插入一個節點會導致數量不變的副本操作（它不會隨插入之下的子樹的大小而增長）; - 大部分複製都是由矢量調整尺寸引起的這樣說的話，可能很好的方式是支持池分配的基於指針的AST節點，而不需要樣板語義操作。該設置的一個很好的特性是可以使用節點地址作爲廉價的獨特散列。 – phooji 2011-01-12 06:47:28

Boost :: Spirit :: Qi autorules - 避免重複複製AST數據結構

回答

相關問題