Пример простого парсера выражений с использованием Boost :: Spirit?

Question

Кто-нибудь знает об онлайн-ресурсе, где я могу узнать, как написать простой синтаксический анализатор выражений, используя Boost :: Spirit?.

Мне не обязательно оценивать выражение, но мне нужно разобрать его и иметь возможность вернуть логическое значение, чтобы указать, является ли выражение анализируемым или нет (например, скобки не соответствуют и т. Д.).

Мне нужен синтаксический анализатор, чтобы иметь возможность распознавать имена функций (например, foo и foobar), поэтому это также будет полезным примером, который поможет мне научиться писать нотации BNF.

Выражения будут нормальными арифметическими уравнениями, т.е. состоящими из следующих символов:

1. открывающие / закрывающие скобки
2. арифметические операторы
3. распознает имена функций и проверяет их обязательные аргументы

Answer 1

Вот какой-то старый прототип кода Spirit, который у меня был:

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

Попробуйте запустить его и ввести строку вроде:

=COUNTIF(J2:J36, "Abc")

Answer 2

Текущая версия Spirit (V2.x) содержит целую серию примеров калькуляторов от очень простого до полноценного интерпретатора мини-c.Вы должны взглянуть туда, поскольку они являются идеальной отправной точкой для написания вашего собственного синтаксического анализатора выражений.

Answer 3

Я не уверен, что это тоже можно назвать простым, но я использовал эту ури-грамматику, доступную по http://code.google.com/p/uri-grammar/source/browse/trunk/src/uri/grammar.hpp. Это может быть не тривиально , но, по крайней мере, что-то с этим что вы, наверное, уже поняли (URI). При чтении этих грамматик лучше всего читать снизу вверх, поскольку именно здесь обычно определяются наиболее общие токены.