Условный (троичный) оператор синтаксического анализа Boost Spirit x3 - PullRequest
Новая
       28

Условный (троичный) оператор синтаксического анализа Boost Spirit x3

2 голосов
/ 19 января 2020

Мне нужно построить абстрактное синтаксическое дерево из математического выражения, которое позже мне понадобится связать доменные спецификации c объектов вместе в дерево вычислений. Я нашел библиотеку синтаксического анализатора 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 помог мне правильно определить троичное условное выражение. 


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 stati c для оценки выражения с таблицей переменных символов 

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

1 Ответ

1 голос
/ 19 января 2020

Условное выражение не является первичным выражением.

Фактически это троичное выражение с инфиксной нотацией.

Это приводит к тому, что правило primary демонстрирует левую рекурсию (нисходящее в expression по определению).

Что вам, вероятно, следует сделать, это просто обработать троичный оператор так же, как и другие инфиксные операторы, что дает дополнительное преимущество, заключающееся в явном указании относительного приоритета оператора.

Взглянув на обычные приоритеты в языках программирования, я бы предложил что-то вроде: 

auto const expression_def =
    conditional
    ;

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

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

(и, конечно, удалив его из primary_def).

Live Demo

Live On Coliru 

//#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)"

ПРИМЕЧАНИЯ

Я думаю, что ваша грамматика имеет относительно много точек ожидания. Это может быть хорошо, просто наблюдение.

Кроме того, ваша грамматика имеет несколько доменов для имен. Вероятно, вам следует принять меры предосторожности для сопоставления частичных имен (например, если существует aa, вы не хотите преждевременно использовать переменную a).

...