Boost Spirit x3条件(三元)运算符解析器

问题描述

我需要从数学表达式构建一个抽象的语法树，以后我需要将特定于域的对象链接在一起作为计算树.我发现表达式解析器库 https://github.com/hmenke/boost_matheval 是一个很好的起点.

I need to build an abstract syntax tree from mathematical expression that I later need to link domain specific objects together as a calculation tree. I found the expression parser library https://github.com/hmenke/boost_matheval as an excellent starting point.

在我的用例中，我需要支持三元条件表达式 condition?true_exp:false_exp .到目前为止，解析器能够解析诸如 1 +(2 + abs(x))或 min(x，1 + y)之类的表达式.但是，我需要使用如下语法:(x> y?1:0)*(y-z).

In my use case I need to have support for ternary conditional expressions condition ? true_exp : false_exp. As of now the parser is able to parse expressions such as 1 + (2 + abs(x)) or min(x,1+y). However I would need to have syntax such as this: (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 .这不符合任何条件.如果我将条件定义为此

However this does not parse correctly. The start rule consumes the condition and recursively tries to parse what is left: ? true_exp : false_exp. This does not match to anything. If I would define the condition as this

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

解析将适用于诸如 if(x> y，x，y)的表达式-但这不是标准的三元条件?:

the parsing would work for expression such as if(x > y, x , y) - however this is not the standard ternary conditional ?:

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

Here is how the ast attributes and declared symbol definitions look like

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精神的经验的人可以指导我如何正确定义三元条件，将不胜感激.

The more complete grammar and the definition of ast attributes is below. It would be highly appreciated if somebody more experienced with Boots spirit could guide me how to define the ternary conditional correctly.

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
)

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

Here is how the AST is traversed using boost static visitor to evaluate the expression with a variable symbol table

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

推荐答案

条件不是主表达式.

实际上，它是一个带后缀标记的三元表达式.

In fact, it is an infix-notated ternary expression.

这会导致 primary 规则表现出左递归(根据定义，它会归结为 expression .)

This causes the primary rule to exhibit left-recursion (it descends into expression by definition).

您可能应该做的就是像对待其他中缀运算符一样对待三元运算符，这样做的好处还在于明确了相对运算符的优先级.

What you should probably do is to just treat the ternary operator as you do the other infix operators, which has the added benefit of being explicit about relative operator precedence.

浏览一下编程语言中的常见用法后，我建议采取以下措施:

Glancing at usual precendences in programming languages, I'd suggest something like:

auto const expression_def =
    conditional
    ;

auto const conditional_def =
    logical >> -('?' > expression > ':'> expression)
    ;

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

(当然还要从 primary_def 中将其删除).

(and of course removing it from primary_def).

//#define BOOST_SPIRIT_X3_DEBUG
//#define DEBUG_SYMBOLS
#include <iostream>
#include <iomanip>
#include <boost/spirit/home/x3.hpp>
namespace x3 = boost::spirit::x3;

namespace ast {
    using expression     = x3::unused_type;
    using unary_op       = x3::unused_type;
    using binary_op      = x3::unused_type;
    using conditional_op = x3::unused_type;
    using operand        = x3::unused_type;
}
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::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"};

    template <typename Tag>
    static auto make_sym(std::initializer_list<char const*> elements) {
#ifdef DEBUG_SYMBOLS
        static x3::symbols<x3::unused_type> instance;
        static auto name = boost::core::demangle(typeid(Tag*).name());
        for (auto el : elements)
            instance += el;
        return x3::rule<Tag> {name.c_str()} = instance;
#else
        x3::symbols<x3::unused_type> instance;
        for (auto el : elements)
            instance += el;
        return instance;
#endif
    }

    static const auto logical_op        = make_sym<struct logical_op_>({"and","or","xor"});
    static const auto equality_op       = make_sym<struct equality_op_>({"=","!="});
    static const auto relational_op     = make_sym<struct relational_op_>({"<","<=",">",">="});
    static const auto additive_op       = make_sym<struct additive_op_>({"+","-"});
    static const auto multiplicative_op = make_sym<struct multiplicative_op_>({"*","/"});
    static const auto unary_op          = make_sym<struct unary_op_>({"!","-","~"}); // TODO FIXME interference with binop?
    static const auto ufunc             = make_sym<struct ufunc_>({"gamma","factorial","abs"});
    static const auto bfunc             = make_sym<struct bfunc_>({"pow","min","max"});
    static const auto constant          = make_sym<struct constant_>({"pi","e","tau"});
    static const auto variable_def      = make_sym<struct variable_def_>({"a","b","c","d","x","y","z"});

    // Rule defintions
    auto const expression_def =
        conditional
        ;

    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 >> *( '^' > 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
        | constant
        | variable
        ;

    BOOST_SPIRIT_DEFINE(
            expression,
            logical,
            equality,
            relational,
            additive,
            multiplicative,
            factor,
            primary,
            unary,
            binary,
            conditional,
            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::expression 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)"

注释

我认为您的语法有相对较高的期望点.也许可以，只是观察一下即可.

NOTES

I think your grammar has relatively many expectation points. That might be ok, just an observation.

此外，您的语法有几个域名领域.您可能应该采取预防措施来匹配部分名称(例如，如果存在 aa ，则您不希望过早地使用变量 a ).

Also, your grammar has a couple of domains for names. You should probably take precautions to match partial names (e.g., if aa exists, you don't want to a variable a prematurely).

这篇关于Boost Spirit x3条件(三元)运算符解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！