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

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

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

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

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

открывающие/закрывающие скобки
арифметические операторы
распознанные имена функций и проверка их необходимых аргументов

Ответ 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")

Ответ 2

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

Ответ 3

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