Ambiguous function call grammar

alternative.cpp

#define BOOST_SPIRIT_DEBUG
#include <iostream>
#include <iterator>
#include <string>

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted.hpp>
#include <boost/optional.hpp>

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

struct addition_t;
struct call_t;
struct unary_t;
typedef double number_t;

typedef boost::variant<
    number_t,
    boost::recursive_wrapper<call_t>,
    boost::recursive_wrapper<unary_t>,
    boost::recursive_wrapper<addition_t>
    > expression_t;

struct term_t
{
    char binop;
    expression_t rhs;

    friend std::ostream& operator<<(std::ostream& os, const term_t& a) 
        { return os << a.binop << ' ' << a.rhs; }
};

struct addition_t
{
    expression_t lhs;
    std::vector<term_t> terms;

    friend std::ostream& operator<<(std::ostream& os, const addition_t& a) 
        { 
           os << "(" << a.lhs << ' ';
           for (auto& e : a.terms) os << e << ' ';
           return os << ")"; 
        }
};

struct call_t
{
    std::string id;
    std::vector<expression_t> args;

    friend std::ostream& operator<<(std::ostream& os, const call_t& a)
        { os << a.id << "("; for (auto& e : a.args) os << e << ", "; return os << ")"; }
};

struct unary_t
{
    char unop;
    expression_t operand;

    friend std::ostream& operator<<(std::ostream& os, const unary_t& a)
        { return os << "(" << a.unop << ' ' << a.operand << ")"; }
};

BOOST_FUSION_ADAPT_STRUCT(term_t,     (char,binop)(expression_t, rhs));
BOOST_FUSION_ADAPT_STRUCT(addition_t, (expression_t, lhs)(std::vector<term_t>, terms));
BOOST_FUSION_ADAPT_STRUCT(call_t,     (std::string, id)(std::vector<expression_t>, args));
BOOST_FUSION_ADAPT_STRUCT(unary_t,    (char, unop)(expression_t, operand));

template <typename Iterator>
struct mini_grammar : qi::grammar<Iterator, expression_t(), qi::space_type> 
{
    qi::rule<Iterator, std::string(),  qi::space_type> id;
    qi::rule<Iterator, expression_t(), qi::space_type> expression, simple;
    qi::rule<Iterator, addition_t(),   qi::space_type> addition;
    qi::rule<Iterator, term_t(),       qi::space_type> term;
    qi::rule<Iterator, number_t(),     qi::space_type> number;
    qi::rule<Iterator, call_t(),       qi::space_type> call;
    qi::rule<Iterator, unary_t(),      qi::space_type> unary;

    mini_grammar() : mini_grammar::base_type(expression) 
    {
        expression = addition | simple;

        addition = simple >> +term;

        term = qi::char_("+-") > simple;

        simple = '(' > expression > ')' | call | unary | number;

        call = id >> *expression;

        unary = qi::char_("-+") > expression;

        // terminals
        id = qi::lexeme[+qi::char_("a-z")];
        number = qi::double_;

        BOOST_SPIRIT_DEBUG_NODE(expression);
        BOOST_SPIRIT_DEBUG_NODE(call);
        BOOST_SPIRIT_DEBUG_NODE(addition);
        BOOST_SPIRIT_DEBUG_NODE(term);
        BOOST_SPIRIT_DEBUG_NODE(simple);
        BOOST_SPIRIT_DEBUG_NODE(unary);
        BOOST_SPIRIT_DEBUG_NODE(id);
        BOOST_SPIRIT_DEBUG_NODE(number);
    }
};

std::string read_input(std::istream& stream) {
    return std::string(
        std::istreambuf_iterator<char>(stream),
        std::istreambuf_iterator<char>());
}

int main() {
    std::cin.unsetf(std::ios::skipws);
    std::string const code = read_input(std::cin);
    auto begin = code.begin();
    auto end = code.end();

    try {
        mini_grammar<decltype(end)> grammar;
        qi::space_type space;

        std::vector<expression_t> script;
        bool ok = qi::phrase_parse(begin, end, *(grammar > ';'), space, script);

        if (begin!=end)
            std::cerr << "Unparsed: '" << std::string(begin,end) << "'\n";

        std::cout << std::boolalpha << "Success: " << ok << "\n";

        if (ok)
        {
            for (auto& expr : script)
                std::cout << "AST: " << expr << '\n';
        }
    }
    catch (qi::expectation_failure<decltype(end)> const& ex) {
        std::cout << "Failure; parsing stopped after \""
                  << std::string(ex.first, ex.last) << "\"\n";
    }
}

Makefile

all:mini alternative

CPPFLAGS+=-std=c++0x
CPPFLAGS+=-g -O0

%.o:%.cpp
	g++ $(CPPFLAGS) $^ -o $@ $(LDFLAGS)

mini.cpp

//#define BOOST_SPIRIT_DEBUG
#include <iostream>
#include <iterator>
#include <string>

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted.hpp>
#include <boost/optional.hpp>

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

struct addition_t;
struct call_t;
struct unary_t;
typedef double number_t;

typedef boost::variant<
    number_t,
    boost::recursive_wrapper<call_t>,
    boost::recursive_wrapper<unary_t>,
    boost::recursive_wrapper<addition_t>
    > expression_t;

struct addition_t
{
    expression_t lhs;
    char binop;
    expression_t rhs;

    friend std::ostream& operator<<(std::ostream& os, const addition_t& a) 
        { return os << "(" << a.lhs << ' ' << a.binop << ' ' << a.rhs << ")"; }
};

struct call_t
{
    std::string id;
    std::vector<expression_t> args;

    friend std::ostream& operator<<(std::ostream& os, const call_t& a)
        { os << a.id << "("; for (auto& e : a.args) os << e << ", "; return os << ")"; }
};

struct unary_t
{
    char unop;
    expression_t operand;

    friend std::ostream& operator<<(std::ostream& os, const unary_t& a)
        { return os << "(" << a.unop << ' ' << a.operand << ")"; }
};

BOOST_FUSION_ADAPT_STRUCT(addition_t, (expression_t, lhs)(char,binop)(expression_t, rhs));
BOOST_FUSION_ADAPT_STRUCT(call_t,     (std::string, id)(std::vector<expression_t>, args));
BOOST_FUSION_ADAPT_STRUCT(unary_t,    (char, unop)(expression_t, operand));

void append_term(expression_t& lhs, char op, expression_t operand)
{
    lhs = addition_t { lhs, op, operand };
}

template <typename Iterator>
struct mini_grammar : qi::grammar<Iterator, expression_t(), qi::space_type> 
{
    qi::rule<Iterator, std::string(),  qi::space_type> id;
    qi::rule<Iterator, expression_t(), qi::space_type> addition, expression, simple;
    qi::rule<Iterator, number_t(),     qi::space_type> number;
    qi::rule<Iterator, call_t(),       qi::space_type> call;
    qi::rule<Iterator, unary_t(),      qi::space_type> unary;

    mini_grammar() : mini_grammar::base_type(expression) 
    {
        expression = addition | simple;

        addition = simple [ qi::_val = qi::_1 ] >> 
           +(  
               (qi::char_("+-") > simple) [ phx::bind(&append_term, qi::_val, qi::_1, qi::_2) ] 
            );

        simple = '(' > expression > ')' | call | unary | number;

        call = id >> *expression;

        unary = qi::char_("-+") > expression;

        // terminals
        id = qi::lexeme[+qi::char_("a-z")];
        number = qi::double_;

        BOOST_SPIRIT_DEBUG_NODE(expression);
        BOOST_SPIRIT_DEBUG_NODE(call);
        BOOST_SPIRIT_DEBUG_NODE(addition);
        BOOST_SPIRIT_DEBUG_NODE(simple);
        BOOST_SPIRIT_DEBUG_NODE(unary);
        BOOST_SPIRIT_DEBUG_NODE(id);
        BOOST_SPIRIT_DEBUG_NODE(number);
    }
};

std::string read_input(std::istream& stream) {
    return std::string(
        std::istreambuf_iterator<char>(stream),
        std::istreambuf_iterator<char>());
}

int main() {
    std::cin.unsetf(std::ios::skipws);
    std::string const code = read_input(std::cin);
    auto begin = code.begin();
    auto end = code.end();

    try {
        mini_grammar<decltype(end)> grammar;
        qi::space_type space;

        std::vector<expression_t> script;
        bool ok = qi::phrase_parse(begin, end, *(grammar > ';'), space, script);

        if (begin!=end)
            std::cerr << "Unparsed: '" << std::string(begin,end) << "'\n";

        std::cout << std::boolalpha << "Success: " << ok << "\n";

        if (ok)
        {
            for (auto& expr : script)
                std::cout << "AST: " << expr << '\n';
        }
    }
    catch (qi::expectation_failure<decltype(end)> const& ex) {
        std::cout << "Failure; parsing stopped after \""
                  << std::string(ex.first, ex.last) << "\"\n";
    }
}

Sample input

1 + 2;
f (+a) (-b) c;
a + b;
a + ++--4 - a 4 5;
a + b - c + d - e;
1 + 2 - 3 + 4 - 5;