Home Articles

提升精神如何从父节点访问子节点(叶子)

Asked
Viewed 669 times
1

我想评估布尔表达式,例如a = b&s <9或仅仅a = b,只有比较运算符(不包括逻辑运算符,如|,&和!) . 我们可以有以下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;
    }

谢谢 . 任何建议都是受欢迎的 .

1 Answer

  • 0

    您是否查看了现有运营商的其他评估重载?您是否注意到他们如何获得操作数的值(实际上可能是子表达式)?

    我以二进制或者为例:

    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表示 . ("half-exception"将是文字,但您仍需要告诉评估者如何使用文字的值 . )

    [2]可以说

    • a<b 可能意味着 !a && b

    • a>b 可能意味着 !b && a

    • a!=b 可能意味着 a XOR b

    • a==b 可能意味着 !(a XOR b)

Related