c++ - ¿Cómo verificar las afirmaciones algebraicas usando boost:: spirit?

parsing boost-spirit

Question

Estoy intentando ampliar el ejemplo de la calculadora para que, en lugar de analizar y evaluar una expresión algebraica, el analizador determine si una afirmación algebraica es verdadera o no. Con esto quiero decir declaraciones como 1 + 5 * 5 - 10 = 19 - 3 (el resultado del analizador deseado es true ) y 3 - 1 = 9 (el resultado del analizador deseado es false ).

Tengo que admitir que soy nuevo para boost::spirit y que es abrumador en este momento. Sin embargo, creo que entiendo el ejemplo de la calculadora lo suficientemente bueno como para al menos hacer algún progreso.

Usando el ejemplo proporcionado como punto de partida, la gramática se ve así:

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]);
}

donde he soltado las macros de depuración para abreviar.

Para limitar el alcance del problema, he decidido permitir solo un solo signo de igualdad por declaración. Como no tiene sentido (al menos en un sentido regular) que aparezcan signos de igualdad dentro de un par de paréntesis cerrados, he decidido no permitir tampoco los paréntesis. Esto simplifica el factor -parser al permitir la eliminación de la opción opcional ''('' >> expression [_val = _1] >> '')'' .

En este punto, estoy un poco atrapado. Antes que nada, necesito que el analizador acepte un solo signo de igualdad. En segundo lugar, necesito las acciones semánticas para evaluar el lado izquierdo (LHS) y el lado derecho (RHS) de la declaración individualmente, antes de realizar una comparación (o eso es lo que creo que se debe hacer).

Me pregunto si el enfoque más fácil sería construir dos analizadores separados, un LHS y un RHS, separados por un tercer analizador que coincida con el signo de igualdad. Los dos analizadores LHS y RHS deben ser idénticos, a excepción de la acción semántica que, claramente, debe separar la entrada en dos categorías diferentes para que finalmente se puedan comparar.

Antes de tratar de escribir dos analizadores separados LHS y RHS, quería aprender a modificar el analizador original para que almacenara las expresiones evaluadas en una variable local. (Ni siquiera estoy seguro de que sea un camino viable hacia cualquier lado, pero parece un paso en la dirección correcta).

Esto es lo que intenté:

int result;

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

pero esto hace que mi compilador (Apple LLVM compilador 4.2, Xcode 4.6) se vuelva loco, gritándome que

Asignando a ''int'' del tipo incompatible ''const _1_type'' (también conocido como ''const actor <argumento <0>>'')

En retrospectiva, esto tiene sentido, por supuesto, ya que _val nunca estuvo obligado a int en primer lugar (después de todo, los analizadores son AFAIU se supone que son genéricos). En otras palabras, necesito descubrir cómo definir el tipo que se utilizará para almacenar temporalmente la expresión analizada evaluada.

La pregunta es: ¿alguien puede darme un empujón en la dirección correcta? ¿La división en LHS y RHS parece ser el camino a seguir?

¡Cualquier sugerencia sera grandemente apreciada!

Answer 1

Lo más simple que podría funcionar, si me preguntas sería http://liveworkspace.org/code/1fvc8x$0

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

Esto analizará dos expresiones, y el atributo devuelto es un bool que indica si ambas expresiones se evaluaron con el mismo valor.

El programa de demostración

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

huellas dactilares

parse success
result: true
parse success
result: false

Programa de ejemplo

#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");
}