Here's where I'm stuck.  In the case of the expression (a + b)*(c - d), the addition and subtraction should be replaced by the appropriate sequences before the multiplication gets expanded to yield the final sequence:

See if the following works for you. I try to replace a # b with sum(#_approx(a,b), #_error(a,b)). The display_expr looked correct, but I didn't check very carefully. #include <boost/proto/proto.hpp> #include <iostream> namespace proto = boost::proto; using proto::_; unsigned ids = 0; struct var { unsigned id; var() { id = ids++; } friend std::ostream &operator<<(std::ostream &s, var v) { s << "V" << v.id; return s; } }; struct sum_approx { friend std::ostream &operator<<(std::ostream &s, sum_approx) { s << "sum_approx"; return s; } }; struct sum_error { friend std::ostream &operator<<(std::ostream &s, sum_error) { s << "sum_error"; return s; } }; struct diff_approx { friend std::ostream &operator<<(std::ostream &s, diff_approx) { s << "diff_approx"; return s; } }; struct diff_error { friend std::ostream &operator<<(std::ostream &s, diff_error) { s << "diff_error"; return s; } }; struct prod_approx { friend std::ostream &operator<<(std::ostream &s, prod_approx) { s << "prod_approx"; return s; } }; struct prod_error { friend std::ostream &operator<<(std::ostream &s, prod_error) { s << "prod_error"; return s; } }; struct sum { friend std::ostream &operator<<(std::ostream &s, sum) { s << "sum"; return s; } }; struct grammar : proto::or_< proto::when<proto::plus<grammar, grammar>, proto::_make_function(sum(), proto::_make_function(sum_approx(), grammar(proto::_left), grammar(proto::_right)), proto::_make_function(sum_error(), grammar(proto::_left), grammar(proto::_right)))> ,proto::when<proto::minus<grammar, grammar>, proto::_make_function(sum(), proto::_make_function(diff_approx(), grammar(proto::_left), grammar(proto::_right)), proto::_make_function(diff_error(), grammar(proto::_left), grammar(proto::_right)))> ,proto::when<proto::multiplies<grammar, grammar>, proto::_make_function(sum(), proto::_make_function(prod_approx(), grammar(proto::_left), grammar(proto::_right)), proto::_make_function(prod_error(), grammar(proto::_left), grammar(proto::_right)))> , proto::terminal<var>

{};

typedef proto::terminal<var>::type Var; int main() { Var a, b, c, d; proto::display_expr(grammar()( (a+b)*(c-d) )); }