c++ - Boost Spirit x3条件(三元)运算符解析器(后续问题)

Question

这个问题是针对

Boost Spirit x3 conditional (ternary) operator parser

原始问题上下文没有显示ast属性(我不好!)，因此答案无法考虑所有 Activity 部分。现在，此问题说明ast属性的外观以及如何使用ast通过符号表评估表达式。

因此，接下来的问题是正确拼写的三元条件应该如何改变ast类型以及条件和表达式如何相互作用(根据我的理解，由于它将从主要对象中删除，因此现在不属于x3::variant的一部分)解析器选择)

这是ast属性和声明的符号定义的样子

namespace x3 = boost::spirit::x3;

namespace ast {

struct nil {};
struct unary_op;
struct binary_op;
struct conditional_op;
struct expression;

struct operand : x3::variant<
                 nil
                 , double
                 , std::string
                 , x3::forward_ast<unary_op>
                 , x3::forward_ast<binary_op>
                 //, x3::forward_ast<conditional_op> // conditional_op not here?
                 , x3::forward_ast<expression>
                 > {
    using base_type::base_type;
    using base_type::operator=;
};

struct unary_op {
    double (*op)(double);
    operand rhs;
};

struct binary_op {
    double (*op)(double, double);
    operand lhs;
    operand rhs;
};

/*
struct conditional_op {
    operand lhs;
    operand rhs_true;
    operand rhs_false;
};
*/

struct conditional_op {
    expression lhs;
    // how the exact type is spelled?
    optional<expression, expression> maybe_rhs;
};

struct operation {
    double (*op)(double, double);
    operand rhs;
};

// what is the type of expression ?
struct expression {
    conditional_op conditional;
};

/*
struct expression {
    operand lhs;
    std::list<operation> rhs;
};
*/

} // namespace ast

struct constant_ : x3::symbols<double> {
    constant_() {
        add
            ("e"      , boost::math::constants::e<double>())
            ("pi"     , boost::math::constants::pi<double>())
            ;
    }
} constant;

struct ufunc_ : x3::symbols<double (*)(double)> {
    ufunc_() {
        add
            ("abs"   , static_cast<double (*)(double)>(&std::abs))
            ;
    }
} ufunc;

struct bfunc_ : x3::symbols<double (*)(double, double)> {
    bfunc_() {
        add
            ("max"  , static_cast<double (*)(double, double)>(&std::fmax))
            ;
    }
} bfunc;

struct unary_op_ : x3::symbols<double (*)(double)> {
    unary_op_() {
        add
            ("+", static_cast<double (*)(double)>(&math::plus))
            ("-", static_cast<double (*)(double)>(&math::minus))
            ("!", static_cast<double (*)(double)>(&math::unary_not))
            ;
    }
} unary_op;

struct additive_op_ : x3::symbols<double (*)(double, double)> {
    additive_op_() {
        add
            ("+", static_cast<double (*)(double, double)>(&math::plus))
            ("-", static_cast<double (*)(double, double)>(&math::minus))
            ;
    }
} additive_op;

struct multiplicative_op_ : x3::symbols<double (*)(double, double)> {
    multiplicative_op_() {
        add
            ("*", static_cast<double (*)(double, double)>(&math::multiplies))
            ("/", static_cast<double (*)(double, double)>(&math::divides))
            ("%", static_cast<double (*)(double, double)>(&std::fmod))
            ;
    }
} multiplicative_op;

struct logical_op_ : x3::symbols<double (*)(double, double)> {
    logical_op_() {
        add
            ("&&", static_cast<double (*)(double, double)>(&math::logical_and))
            ("||", static_cast<double (*)(double, double)>(&math::logical_or))
            ;
    }
} logical_op;

struct relational_op_ : x3::symbols<double (*)(double, double)> {
    relational_op_() {
        add
            ("<" , static_cast<double (*)(double, double)>(&math::less))
            ("<=", static_cast<double (*)(double, double)>(&math::less_equals))
            (">" , static_cast<double (*)(double, double)>(&math::greater))
            (">=", static_cast<double (*)(double, double)>(&math::greater_equals))
            ;
    }
} relational_op;

struct equality_op_ : x3::symbols<double (*)(double, double)> {
    equality_op_() {
        add
            ("==", static_cast<double (*)(double, double)>(&math::equals))
            ("!=", static_cast<double (*)(double, double)>(&math::not_equals))
            ;
    }
} equality_op;

struct power_ : x3::symbols<double (*)(double, double)> {
    power_() {
        add
            ("**", static_cast<double (*)(double, double)>(&std::pow))
            ;
    }
} power;

下面是更完整的语法和ast属性的定义(根据 Boost Spirit x3 conditional (ternary) operator parser中的答案进行了修改)

struct expression_class;
struct logical_class;
struct equality_class;
struct relational_class;
struct additive_class;
struct multiplicative_class;
struct factor_class;
struct primary_class;
struct unary_class;
struct binary_class;
struct conditional_class;
struct variable_class;

// Rule declarations

auto const expression     = x3::rule<expression_class    , ast::expression    >{"expression"};
auto const logical        = x3::rule<logical_class       , ast::expression    >{"logical"};
auto const equality       = x3::rule<equality_class      , ast::expression    >{"equality"};
auto const relational     = x3::rule<relational_class    , ast::expression    >{"relational"};
auto const additive       = x3::rule<additive_class      , ast::expression    >{"additive"};
auto const multiplicative = x3::rule<multiplicative_class, ast::expression    >{"multiplicative"};
auto const factor         = x3::rule<factor_class        , ast::expression    >{"factor"};
auto const primary        = x3::rule<primary_class       , ast::operand       >{"primary"};
auto const unary          = x3::rule<unary_class         , ast::unary_op      >{"unary"};
auto const binary         = x3::rule<binary_class        , ast::binary_op     >{"binary"};
auto const conditional    = x3::rule<conditional_class   , ast::conditional_op>{"conditional"};
auto const variable       = x3::rule<variable_class      , std::string        >{"variable"};

// Rule defintions
/* This is a bit of magic to me. Does this definition now say that expression 
   itself is now initializer list constructible from the conditional (which is spelled below)?
*/
auto const expression_def =
    conditional
    ;

/* now ast::conditional_op type should be constructible from an initialization list consisting 
   of of an expression and optional<tuple<expression,expression>> ? How these types should be 
   spelled in the struct? There is a circular reference between expression and conditional :D ? 
*/  
auto const conditional_def =
    logical >> -('?' > expression > ':'> expression)
    ;

auto const logical_def =
    equality >> *(logical_op > equality)
    ;

auto const equality_def =
    relational >> *(equality_op > relational)
    ;

auto const relational_def =
    additive >> *(relational_op > additive)
    ;

auto const additive_def =
    multiplicative >> *(additive_op > multiplicative)
    ;

auto const multiplicative_def =
    factor >> *(multiplicative_op > factor)
    ;

auto const factor_def =
    primary >> *( power > factor )
    ;

auto const unary_def =
    ufunc > '(' > expression > ')'
    ;

auto const binary_def =
    bfunc > '(' > expression > ',' > expression > ')'
    ;

auto const primary_def =
      x3::double_
    | ('(' > expression > ')')
    | (unary_op > primary)
    | binary
    | unary
 // | conditional // by removing the conditional from primary implies the type of x3::variant changes
    | variable
    ;

BOOST_SPIRIT_DEFINE(
    expression,
    logical,
    equality,
    relational,
    additive,
    multiplicative,
    factor,
    primary,
    unary,
    binary,
    conditional,
    variable
)

这是使用boost静态访问者遍历AST以使用可变符号表评估表达式的方式

namespace ast {

// Evaluator

struct Evaluator {
    using result_type = double;

    explicit Evaluator(std::map<std::string, double> sym);

    double operator()(nil) const;

    double operator()(double n) const;

    double operator()(std::string const &c) const;

    double operator()(operation const &x, double lhs) const;

    double operator()(unary_op const &x) const;

    double operator()(binary_op const &x) const;

    double operator()(conditional_op const &x) const;

    double operator()(expression const &x) const;

  private:
    std::map<std::string, double> st;
};

Evaluator::Evaluator(std::map<std::string, double> sym) 
: st(std::move(sym)) {}

double Evaluator::operator()(nil) const {
    BOOST_ASSERT(0);
    return 0;
}

double Evaluator::operator()(double n) const { return n; }

double Evaluator::operator()(std::string const &c) const {
    auto it = st.find(c);
    if (it == st.end()) {
        throw std::invalid_argument("Unknown variable " + c);
    }
    return it->second;
}

double Evaluator::operator()(operation const &x, double lhs) const {
    double rhs = boost::apply_visitor(*this, x.rhs);
    return x.op(lhs, rhs);
}

double Evaluator::operator()(unary_op const &x) const {
    double rhs = boost::apply_visitor(*this, x.rhs);
    return x.op(rhs);
}

double Evaluator::operator()(binary_op const &x) const {
    double lhs = boost::apply_visitor(*this, x.lhs);
    double rhs = boost::apply_visitor(*this, x.rhs);
    return x.op(lhs, rhs);
}

double Evaluator::operator()(conditional_op const &x) const {
    return static_cast<bool>(boost::apply_visitor(*this, x.lhs)) 
        ? boost::apply_visitor(*this, x.rhs_true) 
        : boost::apply_visitor(*this, x.rhs_false);
}

double Evaluator::operator()(expression const &x) const {
    double state = boost::apply_visitor(*this, x.lhs);
    for (operation const &oper : x.rhs) {
        state = (*this)(oper, state);
    }
    return state;
}

} // namespace ast

Answer 1

因此，公开的顶级属性是expression，坦率地说，它根本不表示表达式。

相反，它表示表达式输入语法的虚假单位，可能被称为“operation_chain”。

这也将使您难以使用AST进行语义上正确的转换(例如表达式评估)，因为诸如操作优先级之类的关键信息未在其中进行编码。

In fact, if we're not careful it's very possible that this information - if present in the input - would be lost. I think it's possible in practice to go from your AST and reconstruct the operation tree with dependent operations in order of their precedence. But I usually err on the safe side of explicitly modeling the expression tree to reflect the operation dependencies.

就是说， conditional_op不是链式二进制操作，因此不适合该模型。我建议使“顶层”规则改为公开 ast::operand(这样就可以同时适合 conditional_op或 expression)。

但是，由于我们以“惰性”方式检测条件，因此需要一些语义操作才能实际构建适当的属性:

auto const conditional_def =
    logical [([](auto& ctx) { _val(ctx) = _attr(ctx); })]
    >> -('?' > expression > ':' > expression) [make_conditional_op]
    ;

第一个语义 Action 是直截了当的，第二个语义 Action 变得足够大以至于无法对其进行定义:

auto make_conditional_op = [](auto& ctx) {
    using boost::fusion::at_c;
    x3::_val(ctx) = ast::conditional_op {
        x3::_val(ctx),
        at_c<0>(x3::_attr(ctx)),
        at_c<1>(x3::_attr(ctx)) };
};

仍然直截了当但笨拙。注意，原因是我们根据可选分支的存在公开了不同的类型。

这就是所有工作的总和:

Live On Coliru

//#define BOOST_SPIRIT_X3_DEBUG
//#define DEBUG_SYMBOLS
#include <iostream>
#include <functional>
#include <iomanip>
#include <list>
#include <boost/fusion/adapted/struct.hpp>
#include <boost/math/constants/constants.hpp>
#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/home/x3/support/ast/variant.hpp>
namespace x3 = boost::spirit::x3;

namespace ast {

    struct nil {};
    struct unary_op;
    struct binary_op;
    struct conditional_op;
    struct expression;

    using UnFunc = std::function<double(double)>;
    using BinFunc = std::function<double(double, double)>;

    struct operand : x3::variant<
             nil
           , double
           , std::string
           , x3::forward_ast<unary_op>
           , x3::forward_ast<binary_op>
           , x3::forward_ast<conditional_op>
           , x3::forward_ast<expression> >
    {
        using base_type::base_type;
        using base_type::operator=;
    };

    struct unary_op {
        UnFunc op;
        operand rhs;
    };

    struct binary_op {
        BinFunc op;
        operand lhs;
        operand rhs;
    };

    struct conditional_op {
        operand lhs;
        operand rhs_true;
        operand rhs_false;
    };

    struct operation {
        BinFunc op;
        operand rhs;
    };

    struct expression {
        operand lhs;
        std::list<operation> rhs;
    };

} // namespace ast

BOOST_FUSION_ADAPT_STRUCT(ast::expression, lhs, rhs)
BOOST_FUSION_ADAPT_STRUCT(ast::operation, op, rhs)
BOOST_FUSION_ADAPT_STRUCT(ast::conditional_op, lhs, rhs_true, rhs_false)
BOOST_FUSION_ADAPT_STRUCT(ast::binary_op, op, lhs, rhs)
BOOST_FUSION_ADAPT_STRUCT(ast::unary_op, op, rhs)

namespace P {

    struct ehbase {
        template <typename It, typename Ctx>
        x3::error_handler_result on_error(It f, It l, x3::expectation_failure<It> const& e, Ctx const& /*ctx*/) const {
            std::cout << std::string(f,l) << "\n"
                      << std::setw(1+std::distance(f, e.where())) << "^"
                      << "-- expected: " << e.which() << "\n";
            return x3::error_handler_result::fail;
        }
    };

    struct expression_class     : ehbase {};
    struct logical_class        : ehbase {};
    struct equality_class       : ehbase {};
    struct relational_class     : ehbase {};
    struct additive_class       : ehbase {};
    struct multiplicative_class : ehbase {};
    struct factor_class         : ehbase {};
    struct primary_class        : ehbase {};
    struct unary_class          : ehbase {};
    struct binary_class         : ehbase {};
    struct conditional_class    : ehbase {};
    struct variable_class       : ehbase {};

    // Rule declarations
    auto const expression     = x3::rule<expression_class    , ast::operand       >{"expression"};
    auto const conditional    = x3::rule<conditional_class   , ast::operand       >{"conditional"};
    auto const primary        = x3::rule<primary_class       , ast::operand       >{"primary"};
    auto const logical        = x3::rule<logical_class       , ast::expression    >{"logical"};
    auto const equality       = x3::rule<equality_class      , ast::expression    >{"equality"};
    auto const relational     = x3::rule<relational_class    , ast::expression    >{"relational"};
    auto const additive       = x3::rule<additive_class      , ast::expression    >{"additive"};
    auto const multiplicative = x3::rule<multiplicative_class, ast::expression    >{"multiplicative"};
    auto const factor         = x3::rule<factor_class        , ast::expression    >{"factor"};
    auto const unary          = x3::rule<unary_class         , ast::unary_op      >{"unary"};
    auto const binary         = x3::rule<binary_class        , ast::binary_op     >{"binary"};
    auto const variable       = x3::rule<variable_class      , std::string        >{"variable"};

    struct constant_ : x3::symbols<double> {
        constant_() {
            this->add
                ("e"      , boost::math::constants::e<double>())
                ("pi"     , boost::math::constants::pi<double>())
                ;
        }
    } constant;

    struct ufunc_ : x3::symbols<ast::UnFunc> {
        ufunc_() {
            this->add
                ("abs"   , &std::abs<double>)
                ;
        }
    } ufunc;

    struct bfunc_ : x3::symbols<ast::BinFunc> {
        bfunc_() {
            this->add
                ("max"  , [](double a,double b){ return std::fmax(a,b); })
                ("min"  , [](double a,double b){ return std::fmin(a,b); })
                ("pow"  , [](double a,double b){ return std::pow(a,b); })
                ;
        }
    } bfunc;

    struct unary_op_ : x3::symbols<ast::UnFunc> {
        unary_op_() {
            this->add
                ("+", [](double v) { return +v; })
                ("-", std::negate{})
                ("!", [](double v) { return !v; })
                ;
        }
    } unary_op;

    struct additive_op_ : x3::symbols<ast::BinFunc> {
        additive_op_() {
            this->add
                ("+", std::plus{})
                ("-", std::minus{})
                ;
        }
    } additive_op;

    struct multiplicative_op_ : x3::symbols<ast::BinFunc> {
        multiplicative_op_() {
            this->add
                ("*", std::multiplies<>{})
                ("/", std::divides<>{})
                ("%", [](double a, double b) { return std::fmod(a, b); })
                ;
        }
    } multiplicative_op;

    struct logical_op_ : x3::symbols<ast::BinFunc> {
        logical_op_() {
            this->add
                ("&&", std::logical_and{})
                ("||", std::logical_or{})
                ;
        }
    } logical_op;

    struct relational_op_ : x3::symbols<ast::BinFunc> {
        relational_op_() {
            this->add
                ("<" , std::less{})
                ("<=", std::less_equal{})
                (">" , std::greater{})
                (">=", std::greater_equal{})
                ;
        }
    } relational_op;

    struct equality_op_ : x3::symbols<ast::BinFunc> {
        equality_op_() {
            this->add
                ("==", std::equal_to{})
                ("!=", std::not_equal_to{})
                ;
        }
    } equality_op;

    struct power_ : x3::symbols<ast::BinFunc> {
        power_() {
            this->add
                ("**", [](double v, double exp) { return std::pow(v, exp); })
                ;
        }
    } power;

    auto const variable_def = x3::lexeme[x3::alpha >> *x3::alnum];

    // Rule defintions
    auto const expression_def =
        conditional
        ;

    auto make_conditional_op = [](auto& ctx) {
        using boost::fusion::at_c;
        x3::_val(ctx) = ast::conditional_op {
            x3::_val(ctx),
            at_c<0>(x3::_attr(ctx)),
            at_c<1>(x3::_attr(ctx)) };
    };

    auto const conditional_def =
        logical [([](auto& ctx) { _val(ctx) = _attr(ctx); })]
        >> -('?' > expression > ':' > expression) [make_conditional_op]
        ;

    auto const logical_def =
        equality >> *(logical_op > equality)
        ;

    auto const equality_def =
        relational >> *(equality_op > relational)
        ;

    auto const relational_def =
        additive >> *(relational_op > additive)
        ;

    auto const additive_def =
        multiplicative >> *(additive_op > multiplicative)
        ;

    auto const multiplicative_def =
        factor >> *(multiplicative_op > factor)
        ;

    auto const factor_def =
        primary >> *( power > factor )
        ;

    auto const unary_def 
        = (unary_op > primary)
        | (ufunc > '(' > expression > ')')
        ;

    auto const binary_def =
        bfunc > '(' > expression > ',' > expression > ')'
        ;

    auto const primary_def =
        x3::double_
        | ('(' > expression > ')')
        //| (unary_op > primary)
        | binary
        | unary
        | constant
        | variable
        ;

    BOOST_SPIRIT_DEFINE(expression)
    BOOST_SPIRIT_DEFINE(logical)
    BOOST_SPIRIT_DEFINE(equality)
    BOOST_SPIRIT_DEFINE(relational)
    BOOST_SPIRIT_DEFINE(additive)
    BOOST_SPIRIT_DEFINE(multiplicative)
    BOOST_SPIRIT_DEFINE(factor)
    BOOST_SPIRIT_DEFINE(primary)
    BOOST_SPIRIT_DEFINE(unary)
    BOOST_SPIRIT_DEFINE(binary)
    BOOST_SPIRIT_DEFINE(conditional)
    BOOST_SPIRIT_DEFINE(variable)
}

int main() {
    for (std::string const input : {
           "x+(3**pow(2,8))",
           "1 + (2 + abs(x))",
           "min(x,1+y)",
           "(x > y ? 1 : 0) * (y - z)",
           "min(3**4,7))",
           "3***4",
           "(3,4)",
        })
    {
        std::cout << " ===== " << std::quoted(input) << " =====\n";
        auto f = begin(input), l = end(input);
        ast::operand out;
        if (phrase_parse(f, l, P::expression, x3::space, out)) {
            std::cout << "Success\n";
        } else {
            std::cout << "Failed\n";
        }
        if (f!=l) {
            std::cout << "Unparsed: " << std::quoted(std::string(f,l)) << "\n";
        }
    }
}

列印

 ===== "x+(3**pow(2,8))" =====
Success
 ===== "1 + (2 + abs(x))" =====
Success
 ===== "min(x,1+y)" =====
Success
 ===== "(x > y ? 1 : 0) * (y - z)" =====
Success
 ===== "min(3**4,7))" =====
Success
Unparsed: ")"
 ===== "3***4" =====
3***4
   ^-- expected: factor
Failed
Unparsed: "3***4"
 ===== "(3,4)" =====
(3,4)
  ^-- expected: ')'
Failed
Unparsed: "(3,4)"

我觉得应该有可能

更优雅(Boost Spirit: "Semantic actions are evil"?)

在语义上对表达式进行更多建模

但是可悲的是我没有时间去做，所以现在就这样:)