助推精神如何從父節點訪問子節點（葉）

Question

我想評估布爾表達式，例如a = b & s < 9或者僅僅使用比較運算符（不包括邏輯運算符，如| &和！）。我們可以有以下AST：

  = 
     /\ 
     / \ 
      a b 

或

   & 
      /\ 
      / \ 
      =  < 
     /\ /\ 
     / \/\ 
      a b s 9 

葉子節點的值。離開節點的父節點始終是比較運算符，如=，！=，<，>，> =，< =。比較節點的父節點是邏輯運算符|，&和！。我想從父節點訪問值節點（葉），然後將這些值傳遞給另一個函數（稍後將實現）。解析步驟是可以的。

如何從父節點訪問值節點（樹葉）。 我使用的例子在： How to calculate boolean expression in Spirit

和 Boolean expression (grammar) parser in c++ 這是從這些環節所採取的評估代碼：

 

    struct eval : boost::static_visitor<bool> 
{ 
    eval() {} 

    // 
    bool operator()(const var& v) const 
    { 
     std::cout<<"feuille:\n"<<v<<std::endl; 
     return true; 
    } 

    bool operator()(const binop<op_and>& b) const 
    { 
     recurse(b.oper1) && recurse(b.oper2); 
    } 
    bool operator()(const binop<op_or>& b) const 
    { 
     recurse(b.oper1) || recurse(b.oper2); 
    } 
    bool operator()(const unop<op_not>& u) const 
    { 
     return !recurse(u.oper1); 
    } 

    //------------adding others operators---------------------------- 
    bool operator()(const binop<op_equal>& u) const 
    { 
     // will be implemented later 
     return true; 
    } 

    bool operator()(const binop<op_not_equal>& u) const 
    { 
     // will be implemented later 
     return true; 
    } 

    bool operator()(const binop<op_less>& u) const 
    { 
     // will be implemented later 
     return true; 
    } 

    bool operator()(const binop<op_less_equal>& u) const 
    { 
     // will be implemented later 
     return true; 
    } 

    bool operator()(const binop<op_greater>& u) const 
    { 
     // will be implemented later 
     return true; 
    } 
    bool operator()(const binop<op_greater_equal>& u) const 
    { 
     // will be implemented later 
     return true; 
    } 

謝謝。任何建議都是值得歡迎的。

Answer 1

你看過現有操作員的其他評估過載嗎？你有沒有注意到他們他們得到了他們的操作數的值（其實可能是子表達式）？

讓我把二進制或爲例：

bool operator()(const binop<op_or>& b) const 
{ 
    return recurse(b.oper1) || recurse(b.oper2); 
} 

正如你所看到的，它只是適用於||兩個操作數的值。該值未在AST ^[1]中找到。所以，我們把每個操作數當作一個表達式，並且遞歸地調用它的eval方法。

因爲表達式類型是一個變種，呼籲eval實際應用訪問者到變種，我had already written the helpful wrapper that does this so it's easy to recurse：

private: 
template<typename T> 
    bool recurse(T const& v) const 
    { return boost::apply_visitor(*this, v); } 

所以，不知道你的語法的休息，但假設你延長它與現有語法相同：

bool operator()(const binop<op_equal>& u) const { 
    return recurse(b.oper1) == recurse(b.oper2); 
} 

會是正確的。需要注意的是一個聰明的宏，你可以非常快速地完成：

struct eval : boost::static_visitor<value> { 

    // terminal 
    value operator()(const var& v) const { 
     std::cout<<"feuille:\n"<<v<<std::endl; 
     return true; // TODO get value from var 
    } 

    // unary operator 
    value operator()(const unop<op_not>& u) const { return !recurse(u.oper1); } 

    /* 
    * binary operators 
    */ 
#define EXPR_DEF_BINOP(tag, op) \ 
    value operator()(const binop<tag>& u) const { \ 
     return recurse(b.oper1) op recurse(b.oper2); \ 
    } 

    EXPR_DEF_BINOP(op_and,   &&) 
    EXPR_DEF_BINOP(op_equal,   ==) 
    EXPR_DEF_BINOP(op_greater,  >) 
    EXPR_DEF_BINOP(op_greater_equal, >=) 
    EXPR_DEF_BINOP(op_less,   <) 
    EXPR_DEF_BINOP(op_less_equal, <=) 
    EXPR_DEF_BINOP(op_not_equal,  !=) 
    EXPR_DEF_BINOP(op_or,   ||) 

#undef EXPR_DEF_BINOP 

    private: 
    template<typename T> 
     value recurse(T const& v) const 
     { return boost::apply_visitor(*this, v); } 
}; 

一些更多的注意事項：

• 我添加了一個TODO到葉子節點評價函數

• 我改變的類型到value（從bool）。這是因爲你的語法支持非布爾表達式，否則運算符<=和>=就沒有意義了。^[2]，所以你將有不同類型的值（太）：

  using value = variant<bool, int32_t>; 
  

  我會留下，其餘爲你

---

^[1]記住AST =抽象語法樹：它是源的1：1表示。 （「半例外」是文字，但你仍然需要告訴評價者如何使用文字的值。）

^[2]無疑

• a<b可能暗示!a && b
• a>b可能意味着!b && a
• a!=b可能意味着a XOR b
• a==b暗示!(a XOR b)