Как проверить алгебраические утверждения с помощью boost::spirit?

Я пытаюсь расширить пример калькулятора, чтобы вместо разбора и оценки алгебраического выражения синтаксический анализатор определял, является ли алгебраическое утверждение истинным или нет. Под этим я подразумеваю такие операторы, как 1 + 5 * 5 - 10 = 19 - 3 (желаемый результат синтаксического анализа - true) и 3 - 1 = 9 (желаемый результат синтаксического анализа - false).

Должен признаться, я новичок в boost::spirit, и в данный момент все это ошеломляет. Тем не менее, я чувствую, что понимаю пример с калькулятором достаточно хорошо, чтобы, по крайней мере, продвинуться вперед.

Используя предоставленный пример в качестве отправной точки, грамматика выглядит следующим образом:

calculator() : calculator::base_type(expression)
{
    using qi::uint_;
    using qi::_val;
    using qi::_1;

    expression =
        term                    [_val = _1]
            >> *( ('+' >> term  [_val = _val + _1])
                | ('-' >> term  [_val = _val - _1])
                );

        term =
            factor                [_val = _1]
            >> *( ('*' >> factor  [_val = _val * _1])
                | ('/' >> factor  [_val = _val / _1])
                );

        factor =
            uint_                 [_val = _1]
            |   '(' >> expression [_val = _1] >> ')'
            |   ('-' >> factor    [_val = -_1])
            |   ('+' >> factor    [_val = _1]);
}

где я опустил макросы отладки для краткости.

Чтобы ограничить масштаб проблемы, я решил разрешить только один знак равенства для каждого оператора. Поскольку бессмысленно (по крайней мере, в обычном смысле) размещать знаки равенства внутри пары закрытых скобок, я также решил не разрешать скобки. Это упрощает factor-анализатор, позволяя удалить необязательный '(' >> expression [_val = _1] >> ')'.

На данный момент я немного застрял. Прежде всего, мне нужно, чтобы синтаксический анализатор принимал один знак равенства. Во-вторых, мне нужны семантические действия для оценки левой (LHS) и правой части (RHS) оператора по отдельности, прежде чем, наконец, выполнить сравнение (по крайней мере, это то, что я думаю, нужно сделать).

Мне интересно, будет ли самым простым подходом построить два отдельных синтаксических анализатора, один LHS и один RHS, разделенные третьим синтаксическим анализатором, соответствующим знаку равенства. Два синтаксических анализатора LHS и RHS должны быть идентичными, за исключением семантического действия, которое, очевидно, должно разделить входные данные на две разные категории, чтобы их можно было окончательно сравнить.

Прежде чем пытаться написать два отдельных парсера LHS и RHS, я хотел узнать, как модифицировать исходный парсер так, чтобы он сохранял оцененные выражения в локальной переменной. (Я даже не уверен, что это был бы жизнеспособный путь куда угодно, но это похоже на шаг в правильном направлении.)

Вот что я пробовал:

int result;

expression =
    term                            [result = _1]
    >> *(   ('+' >> term            [result = result + _1])
        |   ('-' >> term            [result = result - _1])
        );

но это заставляет мой компилятор (компилятор Apple LLVM 4.2, Xcode 4.6) сходить с ума, крича на меня, что

Присвоение 'int' из несовместимого типа 'const 1 + 5 * 5 - 10 = 19 - 3type' (он же 'константный актер‹ аргумент ‹ 0 > >')

Оглядываясь назад, это, конечно, имеет смысл, поскольку _val никогда не был привязан к int в первую очередь (в конце концов, парсеры AFAIU должны быть универсальными). Другими словами, мне нужно выяснить, как определить тип, который будет использоваться для временного хранения оцененного проанализированного выражения.

Вопрос: может ли кто-нибудь подтолкнуть меня в правильном направлении? Разделение на LHS и RHS кажется правильным?

Любое предложение очень ценится!


person conciliator    schedule 27.02.2013    source источник
comment
Кстати, вы могли бы (не рекомендуется) назначить result с помощью [phoenix::ref(result) = _1]. Однако см. мой ответ, qi::locals<> и проблемы времени жизни/повторного входа с переменной result   -  person sehe    schedule 28.02.2013


Ответы (1)


Если вы спросите меня, самое простое, что могло бы сработать, это http://liveworkspace.org/code/1fvc8x$0

equation = (expression >> "=" >> expression) [ _val = _1 == _2 ];

Это проанализирует два выражения, и возвращенный атрибут будет bool, указывающим, оцениваются ли оба выражения как одно и то же значение.

Демонстрационная программа

int main()
{
    doParse("1 + 2 * 3 = 7");
    doParse("1 + 2 * 3 = 8");
}

отпечатки

parse success
result: true
parse success
result: false

Пример программы

#include <boost/fusion/adapted.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>

namespace qi    = boost::spirit::qi;
namespace phx   = boost::phoenix;

typedef unsigned attr_t;

template <typename It, typename Skipper = qi::space_type>
    struct calculator : qi::grammar<It, bool(), Skipper>
{
    calculator() : calculator::base_type(equation)
    {
        using qi::uint_;
        using qi::_val;
        using qi::_1;
        using qi::_2;

        equation = (expression >> "=" >> expression) [ _val = _1 == _2 ];

        expression =
            term                    [_val = _1]
                >> *( ('+' >> term  [_val = _val + _1])
                    | ('-' >> term  [_val = _val - _1])
                    );

            term =
                factor                [_val = _1]
                >> *( ('*' >> factor  [_val = _val * _1])
                    | ('/' >> factor  [_val = _val / _1])
                    );

            factor =
                uint_                 [_val = _1]
                |   '(' >> expression [_val = _1] >> ')'
                |   ('-' >> factor    [_val = -_1])
                |   ('+' >> factor    [_val = _1]);
    }

  private:
    qi::rule<It, unsigned(), Skipper> expression, term, factor;
    qi::rule<It, bool(), Skipper> equation;
};

bool doParse(const std::string& input)
{
    typedef std::string::const_iterator It;
    auto f(begin(input)), l(end(input));

    calculator<It, qi::space_type> p;
    bool result;

    try
    {
        bool ok = qi::phrase_parse(f,l,p,qi::space,result);
        if (ok)   
        {
            std::cout << "parse success\n";
            std::cout << "result: " << std::boolalpha << result << "\n";
        }
        else      std::cerr << "parse failed: '" << std::string(f,l) << "'\n";

        if (f!=l) std::cerr << "trailing unparsed: '" << std::string(f,l) << "'\n";
        return ok;
    } catch(const qi::expectation_failure<It>& e)
    {
        std::string frag(e.first, e.last);
        std::cerr << e.what() << "'" << frag << "'\n";
    }

    return false;
}

int main()
{
    doParse("1 + 2 * 3 = 7");
    doParse("1 + 2 * 3 = 8");
}
person sehe    schedule 27.02.2013
comment
Спасибо сехе! Что я могу сказать? Это просто красиво - и даже поддерживает скобки. :) - person conciliator; 28.02.2013