Retrieving AST from boost::spirit parser

Question

After I've read the tutorials on boost::spirit, I quite liked it because of the parser combinator syntax. Making a parser is so easy.

Unfortunately, the tutorials were not as exact on the matter of getting a complex data structure out of the parser. I am trying to get to the Kaleidoscope AST.

Anyway, here be my AST code:

#ifndef __AST_HPP__
#define __AST_HPP__

#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/variant/recursive_variant.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/variant/apply_visitor.hpp>
#include <string>
#include <vector>

namespace ast {

struct add;
struct sub;
struct mul;
struct div;
struct func_call;
template<typename OpTag> struct binary_op;

typedef boost::variant<double, std::string, boost::recursive_wrapper<binary_op<
        add>>, boost::recursive_wrapper<binary_op<sub>>,
        boost::recursive_wrapper<binary_op<mul>>, boost::recursive_wrapper<
                binary_op<div>>, boost::recursive_wrapper<func_call>>
        expression;

template<typename OpTag>
struct binary_op {
    expression left;
    expression right;

    binary_op(const expression & lhs, const expression & rhs) :
        left(lhs), right(rhs) {
    }
};

struct func_call {
    std::string callee;
    std::vector<expression> args;

    func_call(const std::string func, const std::vector<expression> &args) :
        callee(func), args(args) {
    }
};

struct prototype {
    std::string name;
    std::vector<std::string> args;

    prototype(const std::string &name, const std::vector<std::string> &args) :
        name(name), args(args) {
    }
};

struct function {
    prototype proto;
    expression body;

    function(const prototype &proto, const expression &body) :
        body(body), proto(proto) {
    }
};

}
    #endif

I've omitted the BOOST_FUSION_ADAPT_STRUCT parts, but they are there.

And this my expression parser:

#ifndef __PARSER_HPP__
#define __PARSER_HPP__

#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/include/adapt_struct.hpp>

#include "ast.hpp"

namespace parser {

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;

template<typename Iterator>
struct expression: qi::grammar<Iterator, ast::expression(), ascii::space_type> {
    expression() :
        expression::base_type(expr) {
        using qi::lit;
        using qi::lexeme;
        using ascii::char_;
        using ascii::string;
        using ascii::alnum;
        using ascii::alpha;
        using qi::double_;
        using namespace qi::labels;

        using phoenix::at_c;
        using phoenix::push_back;

        number %= lexeme[double_];
        varname %= lexeme[alpha >> *(alnum | '_')];

        binop
                = (expr >> '+' >> expr)[_val = ast::binary_op<ast::add>(_1, _3)]
                        | (expr >> '-' >> expr)[_val
                                = ast::binary_op<ast::sub>(_1, _3)]
                        | (expr >> '*' >> expr)[_val
                                = ast::binary_op<ast::mul>(_1, _3)]
                        | (expr >> '/' >> expr)[_val
                                = ast::binary_op<ast::div>(_1, _3)];

        expr %= number | varname | binop;
    }

    qi::rule<Iterator, ast::expression(), ascii::space_type> expr;
    qi::rule<Iterator, ast::expression(), ascii::space_type> binop;
    qi::rule<Iterator, std::string, ascii::space_type> varname;
    qi::rule<Iterator, double, ascii::space_type> number;
};

}

#endif

The problem I have is that it seems to have a problem with the resulting ast::expression. The compiled throws out more than 200 lines of complex template errors. I suspect it is something with the way I tried to get the information out of the binop rule, but I am not sure.

Can anyone help?

Answer 1

You are trying to call ast::binary_op's constructor using Boost Phoenix placeholders. They don't mix well. You need to use a lazy call to the ast::binary_op constructor. This is provided in Phoenix by using construct :

binop = (expr >> '+' >> expr) [_val = construct< ast::binary_op<ast::add> >(_1, _2)]
      | (expr >> '-' >> expr) [_val = construct< ast::binary_op<ast::sub> >(_1, _2)]
      | (expr >> '*' >> expr) [_val = construct< ast::binary_op<ast::mul> >(_1, _2)]
      | (expr >> '/' >> expr) [_val = construct< ast::binary_op<ast::div> >(_1, _2)] ;

Also, I think you only need the _1 and _2 placeholders, as the '+','-',... are converted to qi::lit (litteral) thus having no attribute.

I also noted a couple of missing parenthesis in varname and number rules :

qi::rule<Iterator, std::string(), ascii::space_type> varname;
//                            ^^          
qi::rule<Iterator, double(), ascii::space_type> number;
//                       ^^

Boost Spirit Qi is very powerful, but also very hard to debug. When I started to use it, I found these Boost Spirit Applications very useful.

I hope this will be helpful, as I'm not a Boost Spirit expert.