Simple expression parser example using Boost::Spirit?

Stick it to THE MAN picture Stick it to THE MAN · Feb 28, 2010 · Viewed 10.7k times · Source

Is anyone aware of an online resource where I can find out how to write a simple expression parser using Boost::Spirit?.

I do not necessarily need to evaluate the expression, but I need to parse it and be able to return a boolean to indicate whether the expression is parsable or not (e.g. brackets not matching etc).

I need the parser to be able recognise function names (e.g. foo and foobar), so this would also be a useful example to help me learn writing BNF notation.

The expressions will be normal arithmetic equations, i.e. comprising of the following symbols:

  1. opening/closing brackets
  2. arithmetic operators
  3. recognized function names, and check for their required arguments

Answer

John Zwinck picture John Zwinck · Feb 28, 2010

Here's some old Spirit prototype code I had laying around:

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

Try running it and entering a line like:

=COUNTIF(J2:J36, "Abc")