提升精神如何从父节点访问子节点（叶子）-Java 学习之路

我想评估布尔表达式，例如a = b＆s <9或仅仅a = b，只有比较运算符（不包括逻辑运算符，如|，＆和！） . 我们可以有以下AST：

要么

&
              / \  
             /   \
            =     <
           / \    /\
          /   \  /  \
          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

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

我以二进制或者为例：

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)

提升精神如何从父节点访问子节点（叶子）

1 Answer

Related