Мне нужно построить абстрактное синтаксическое дерево из математического выражения, которое позже мне понадобится, чтобы связать объекты, зависящие от предметной области, вместе в виде дерева вычислений. Я нашел библиотеку синтаксического анализатора выражений https://github.com/hmenke/boost_matheval как отличную отправную точку. .

В моем случае использования мне нужна поддержка тернарных условных выражений condition ? true_exp : false_exp. На данный момент синтаксический анализатор может анализировать такие выражения, как 1 + (2 + abs(x)) или min(x,1+y). Однако мне понадобится такой синтаксис: (x > y ? 1 : 0) * (y - z).

Я пытался определить правило

auto const conditional_def =
    expression > '?' > expression > ':'> expression
    ;

и расширяя стартовое правило условным

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

Однако это не выполняется правильно. Правило запуска потребляет condition и рекурсивно пытается проанализировать то, что осталось: ? true_exp : false_exp. Это ни к чему не подходит. Если бы я определил условие как это

auto const conditional_def =
    (x3::lit("if") > '(' > expression > ',' > expression > ','> expression > ')')
    ;

синтаксический анализ будет работать для таких выражений, как if(x > y, x , y) - однако это не стандартное тернарное условное выражение ?:

Вот как выглядят атрибуты 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>
                 , 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 operation {
    double (*op)(double, double);
    operand rhs;
};

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 приведены ниже. Был бы очень признателен, если бы кто-нибудь, более опытный в работе с Boots spirit, мог бы подсказать мне, как правильно определить тернарное условное выражение.

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

auto const expression_def =
    logical
    ;

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 conditional_def =
    expression  > '?' > expression > ':'> expression
    ;

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

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

Вот как проходит AST с использованием boost static visitor для оценки выражения с помощью таблицы переменных символов.

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