Ejemplo de analizador de expresiones simples usando Boost :: Spirit?

Question

¿Alguien está al tanto de un recurso en línea donde puedo averiguar cómo escribir un analizador de expresiones simples usando Boost :: Spirit ?.

No necesariamente necesito evaluar la expresión, pero necesito analizarla y poder devolver un valor booleano para indicar si la expresión es analizable o no (por ejemplo, los corchetes no coinciden, etc.).

Necesito que el analizador pueda reconocer los nombres de las funciones (por ejemplo, foo y foobar), así que esto también sería un ejemplo útil para ayudarme a aprender a escribir la notación BNF.

Las expresiones serán ecuaciones aritméticas normales, es decir que comprenden de los siguientes símbolos:

1. de apertura/soportes de cierre
2. operadores aritméticos
3. nombres de las funciones reconocidas, y comprobar sus argumentos necesarios

Answer 1

Aquí hay un viejo código de prototipo de Spirit que tuve por ahí:

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <exception> 
#include <iterator> 
#include <sstream> 
#include <list> 

#include <boost/spirit.hpp> 
#include <boost/shared_ptr.hpp> 

using namespace std; 
using namespace boost::spirit; 
using namespace boost; 

void g(unsigned int i) 
{ 
    cout << "row: " << i << endl; 
} 

struct u 
{ 
    u(const char* c): s(c) {} 
    void operator()(const char* first, const char* last) const 
    { 
     cout << s << ": " << string(first, last) << endl; 
    } 
private: 
    string s; 
}; 


struct Exp 
{ 
}; 

struct Range: public Exp 
{ 
}; 

struct Index: public Exp 
{ 
}; 

struct String: public Exp 
{ 
}; 

struct Op 
{ 
    virtual ~Op() = 0; 
    virtual string name() = 0; 
}; 

Op::~Op() {} 

struct CountIf: public Op 
{ 
    string name() { return "CountIf"; } 
}; 

struct Sum: public Op 
{ 
    string name() { return "Sum"; } 
}; 

struct Statement 
{ 
    virtual ~Statement() = 0; 
    virtual void print() = 0; 
}; 

Statement::~Statement() {} 

struct Formula: public Statement 
{ 
    Formula(const char* first, const char* last): s(first, last), op(new CountIf) 
    { 
     typedef rule<phrase_scanner_t> r_t; 

     r_t r_index  = (+alpha_p)[u("col")] >> uint_p[&g]; 
     r_t r_range  = r_index >> ':' >> r_index; 
     r_t r_string = ch_p('\"') >> *alnum_p >> '\"'; 
     r_t r_exp  = r_range | r_index | r_string; // will invoke actions for index twice due to range 
     r_t r_list  = !(r_exp[u("arg")] % ','); 
     r_t r_op  = as_lower_d["countif"] | as_lower_d["sum"]; 
     r_t r_formula = r_op >> '(' >> r_list >> ')'; 

     cout << s << ": matched: " << boolalpha << parse(s.c_str(), r_formula, space_p).full << endl; 
    } 
    void print() { cout << "Formula: " << s << "/" << op->name() << endl; } 
private: 
    string s; 
    shared_ptr<Op> op; 
    list<shared_ptr<Exp> > exp_list; 
}; 

struct Comment: public Statement 
{ 
    Comment(const char* first, const char* last): comment(first, last) {} 
    void print() {cout << "Comment: " << comment << endl; } 
private: 
    string comment; 
}; 


struct MakeFormula 
{ 
    MakeFormula(list<shared_ptr<Statement> >& list_): list(list_) {} 
    void operator()(const char* first, const char* last) const 
    { 
     cout << "MakeFormula: " << string(first, last) << endl; 
     list.push_back(shared_ptr<Statement>(new Formula(first, last))); 
    } 
private: 
    list<shared_ptr<Statement> >& list; 
}; 

struct MakeComment 
{ 
    MakeComment(list<shared_ptr<Statement> >& list_): list(list_) {} 
    void operator()(const char* first, const char* last) const 
    { 
     cout << "MakeComment: " << string(first, last) << endl; 
     list.push_back(shared_ptr<Statement>(new Comment(first, last))); 
    } 
private: 
    list<shared_ptr<Statement> >& list; 
}; 


int main(int argc, char* argv[]) 
try 
{ 
    //typedef vector<string> v_t; 
    //v_t v(argv + 1, argv + argc); 
    // copy(v.begin(), v.end(), ostream_iterator<v_t::value_type>(cout, "\n")); 

    string s; 
    getline(cin, s); 

    //  =COUNTIF(J2:J36, "Abc") 

    typedef list<shared_ptr<Statement> > list_t; 
    list_t list; 

    typedef rule<phrase_scanner_t> r_t; 

    r_t r_index  = (+alpha_p)[u("col")] >> uint_p[&g]; 
    r_t r_range  = r_index >> ':' >> r_index; 
    r_t r_string = ch_p('\"') >> *alnum_p >> '\"'; 
    r_t r_exp  = r_range | r_index | r_string; // will invoke actions for index twice due to range 
    r_t r_list  = !(r_exp[u("arg")] % ','); 
    r_t r_op  = as_lower_d["countif"] | as_lower_d["sum"]; 
    r_t r_formula = r_op >> '(' >> r_list >> ')'; 
    r_t r_statement = (ch_p('=') >> r_formula [MakeFormula(list)]) 
        | (ch_p('\'') >> (*anychar_p)[MakeComment(list)]) 
        ; 

    cout << s << ": matched: " << boolalpha << parse(s.c_str(), r_statement, space_p).full << endl; 

    for (list_t::const_iterator it = list.begin(); it != list.end(); ++it) 
    { 
     (*it)->print(); 
    } 
} 
catch(const exception& ex) 
{ 
    cerr << "Error: " << ex.what() << endl; 
} 

intenta ejecutarlo y entrando en una línea como:

=COUNTIF(J2:J36, "Abc") 

Answer 2

No estoy seguro de si esto califica tan simple tampoco, pero he utilizado este URI-gramática disponible en http://code.google.com/p/uri-grammar/source/browse/trunk/src/uri/grammar.hpp. Puede que no sea trivial, pero al menos está analizando algo que probablemente ya comprenda (URI). Al leer estas gramáticas, es mejor leer de abajo hacia arriba, ya que es donde se suelen definir los tokens más genéricos.

Answer 3

La versión actual de Spirit (V2.x) contiene toda una serie de ejemplos de calculadora desde el muy simple hasta un intérprete de mini-c completo. Deberías echar un vistazo allí ya que son un punto de partida perfecto para escribir tu propio analizador de expresiones.