Boost:: анализатор выражений духа

Question

У меня есть еще одна проблема с моим анализатором boost::spirit.

template<typename Iterator>
struct expression: qi::grammar<Iterator, ast::expression(), ascii::space_type> {
    expression() :
        expression::base_type(expr) {
        number %= lexeme[double_];
        varname %= lexeme[alpha >> *(alnum | '_')];

        binop = (expr >> '+' >> expr)[_val = construct<ast::binary_op<ast::add>>(_1,_2)]
              | (expr >> '-' >> expr)[_val = construct<ast::binary_op<ast::sub>>(_1,_2)]
              | (expr >> '*' >> expr)[_val = construct<ast::binary_op<ast::mul>>(_1,_2)]
              | (expr >> '/' >> expr)[_val = construct<ast::binary_op<ast::div>>(_1,_2)] ;

        expr %= number | varname | binop;
    }

    qi::rule<Iterator, ast::expression(), ascii::space_type> expr;
    qi::rule<Iterator, ast::expression(), ascii::space_type> binop;
    qi::rule<Iterator, std::string(), ascii::space_type> varname;
    qi::rule<Iterator, double(), ascii::space_type> number;
};

Это был мой парсер. Разобрал "3.1415" а также "var" просто отлично, но когда я попытался разобрать "1+2" это говорит мне parse failed, Затем я попытался изменить binop Правило для

    binop = expr >>
           (('+' >> expr)[_val = construct<ast::binary_op<ast::add>>(_1, _2)]
          | ('-' >> expr)[_val = construct<ast::binary_op<ast::sub>>(_1, _2)]
          | ('*' >> expr)[_val = construct<ast::binary_op<ast::mul>>(_1, _2)]
          | ('/' >> expr)[_val = construct<ast::binary_op<ast::div>>(_1, _2)]);

Но теперь он, конечно, не в состоянии построить АСТ, потому что _1 а также _2 установлены по-разному. Я видел только что-то вроде _r1 упоминается, но в качестве повышения-новичка я не совсем понимаю, как boost::phoenix а также boost::spirit взаимодействуют между собой.

Как это решить?

Answer 1

Мне не совсем понятно, чего вы пытаетесь достичь. Самое главное, вас не беспокоит ассоциативность операторов? Я просто покажу простые ответы, основанные на использовании правой рекурсии - это приводит к анализу левоассоциативных операторов.

Прямой ответ на ваш видимый вопрос будет жонглировать fusion::vector2<char, ast::expression> - что не очень весело, особенно в лямбда- семантических акциях Феникса. (Я покажу ниже, как это выглядит).

Между тем я думаю, что вы должны прочитать о Духе документы

• здесь, в старых документах Духа (устранение левой рекурсии); Хотя синтаксис больше не применяется, Spirit по-прежнему генерирует LL-парсеры рекурсивного спуска, поэтому концепция, лежащая в основе левой рекурсии, по-прежнему применяется. Код ниже показывает, что это применимо к Spirit Qi
• здесь: примеры ци содержат три calculator примеры, которые должны дать вам подсказку о том, почему ассоциативность операторов имеет значение, и как вы бы выразили грамматику, которая отражает ассоциативность бинарных операторов. Очевидно, он также показывает, как поддерживать выражения в скобках, чтобы переопределить порядок оценки по умолчанию.

Код:

У меня есть три версии кода, который работает, анализируя ввод, как:

std::string input("1/2+3-4*5");

в ast::expression сгруппированы как (используя BOOST_SPIRIT_DEBUG):

<expr>
  ....
  <success></success>
  <attributes>[[1, [2, [3, [4, 5]]]]]</attributes>
</expr>

Ссылки на код здесь:

• step_ # 1_reduce_semantic_actions.cpp
• step_ # 2_drop_rule.cpp
• step_ # 0_vector2.cpp

Шаг 1: уменьшить семантические действия

Во-первых, я бы избавился от альтернативных выражений разбора для каждого оператора; это приводит к чрезмерному откату назад ¹. Кроме того, как вы узнали, это усложняет грамматику. Итак, вот более простой вариант, который использует функцию для семантического действия:

_{¹ проверьте это с помощью BOOST_SPIRIT_DEBUG!}

static ast::expression make_binop(char discriminant, 
     const ast::expression& left, const ast::expression& right)
{
    switch(discriminant)
    {
        case '+': return ast::binary_op<ast::add>(left, right);
        case '-': return ast::binary_op<ast::sub>(left, right);
        case '/': return ast::binary_op<ast::div>(left, right);
        case '*': return ast::binary_op<ast::mul>(left, right);
    }
    throw std::runtime_error("unreachable in make_binop");
}

// rules:
number %= lexeme[double_];
varname %= lexeme[alpha >> *(alnum | '_')];

simple = varname | number;
binop = (simple >> char_("-+*/") >> expr) 
    [ _val = phx::bind(make_binop, qi::_2, qi::_1, qi::_3) ]; 

expr = binop | simple;

Шаг 2: Удалить лишние правила, используйте _val

Как видите, это может снизить сложность. Это всего лишь маленький шаг, чтобы удалить промежуточный продукт binop (который стал довольно избыточным):

number %= lexeme[double_];
varname %= lexeme[alpha >> *(alnum | '_')];

simple = varname | number;
expr = simple [ _val = _1 ] 
    > *(char_("-+*/") > expr) 
            [ _val = phx::bind(make_binop, qi::_1, _val, qi::_2) ]
    > eoi;

Как вы видете,

• в пределах expr правило, _val Ленивый заполнитель используется в качестве псевдо-локальной переменной, которая накапливает binops. Через правила, вы должны будете использовать qi::locals<ast::expression> за такой подход. (Это был ваш вопрос относительно _r1).
• теперь есть явные точки ожидания, делающие грамматику более устойчивой
• expr правило больше не должно быть авто-правилом (expr = вместо expr %=)

Шаг 0: Бороться с типами слияния напрямую

Наконец, для забавы, позвольте мне показать, как вы могли бы обработать предложенный вами код, а также смещающиеся привязки _1, _2 и т. Д.:

static ast::expression make_binop(
        const ast::expression& left, 
        const boost::fusion::vector2<char, ast::expression>& op_right)
{
    switch(boost::fusion::get<0>(op_right))
    {
        case '+': return ast::binary_op<ast::add>(left, boost::fusion::get<1>(op_right));
        case '-': return ast::binary_op<ast::sub>(left, boost::fusion::get<1>(op_right));
        case '/': return ast::binary_op<ast::div>(left, boost::fusion::get<1>(op_right));
        case '*': return ast::binary_op<ast::mul>(left, boost::fusion::get<1>(op_right));
    }
    throw std::runtime_error("unreachable in make_op");
}

// rules:
expression::base_type(expr) {
number %= lexeme[double_];
varname %= lexeme[alpha >> *(alnum | '_')];

simple = varname | number;
binop %= (simple >> (char_("-+*/") > expr)) 
    [ _val = phx::bind(make_binop, qi::_1, qi::_2) ]; // note _2!!!

expr %= binop | simple;

Как видите, не так весело писать make_binop функционировать таким образом!