Using Boost Spirit 2.1+ to evaluate constant arithmetic expressions
I used Boost Program_options for my research code's input parsing requirements. As expected, it works well. For floating point quantities, I've found having to specify 4.18879020478639 for 4π/3 is a bit cumbersome. When specifying arguments on the command line, I could use any one of a number of hacks to perform floating point arithmetic in bash. But that didn't help me when taking input from response files. I wanted an arithmetic expression utility that could process a C-like grammar. Long double accuracy was a requirement. I looked around a bit. GNU libmatheval and muParser appeared to be good fits but looked to be double precision-only. Though straightforward, I decided against combining the Shunting-yard algorithm with some in-place RPN logic because I wasn't enthusiastic about either finding or writing an appropriate (and admittedly toy simple) lexer.
Already having a Boost pre-requisite in my code, I decided to try out Boost Spirit since it could provide a header-only, precision-agnostic solution. Spirit has gone through a lot of significant revisions and many articles seemed to be written for the older Spirit Classic. The latest official reference manual gave several excellent examples that almost fit. I adapted Spirit's calc3.cpp and roman.cpp sample grammars to accomplish what I wanted. I added ** as an operator for exponentiation and pi as a built-in constant. I also added a smattering of special functions (e.g. exp). The task required about 150 lines of Spirit-based code. Further extensions should be fairly straightforward.
My sample code does the following:
- Declares X-macros for the unary and binary functions built into the grammar.
- Declares Boost Phoenix-ready functors for the unary and binary functions.
- Declares expression::grammar consisting of the rules expression, term, factor, and primary.
- Declares a helper called parse to hide needing boost::spirit::ascii::space when performing whitespace-agnostic parsing.
- Declares a small test macro called EXPRTEST to reduce test case boilerplate.
- Runs a collection of tests to ensure the parser is behaving as expected.
A less hideous version is presented further below.
///////////////////////////////////////////////
// Ensure Boost Spirit version is high enough.
// Compilation errors are astounding otherwise.
///////////////////////////////////////////////
#include <boost/version.hpp>
#if BOOST_VERSION < 104100
#error "Require at least Spirit 2.1 from at least Boost 1.41"
#endif
//////////////////////////////////////////////////////////////////
// Implementation uses X macros to reduce boilerplate.
// See http://drdobbs.com/blogs/cpp/228700289 for X macro details.
//////////////////////////////////////////////////////////////////
#include <cmath>
#include <limits>
#include <boost/math/constants/constants.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/qi.hpp>
namespace expression {
#define EXPRESSION_FORALL_UNARY_FUNCTIONS(apply) \
apply(abs) \
apply(acos) \
apply(asin) \
apply(atan) \
apply(ceil) \
apply(cos) \
apply(cosh) \
apply(exp) \
apply(floor) \
apply(log) \
apply(log10) \
apply(sin) \
apply(sinh) \
apply(sqrt) \
apply(tan) \
apply(tanh)
#define EXPRESSION_FORALL_BINARY_FUNCTIONS(apply) \
apply(pow) \
apply(atan2)
namespace detail {
#define DECLARE_UNARY_FUNCTOR(name) \
struct name ## _ \
{ \
template <typename X> struct result { typedef X type; }; \
\
template <typename X> X operator()(X x) const \
{ \
using namespace std; \
return name(x); \
} \
};
EXPRESSION_FORALL_UNARY_FUNCTIONS(DECLARE_UNARY_FUNCTOR)
#undef DECLARE_UNARY_FUNCTOR
#define DECLARE_BINARY_FUNCTOR(name) \
struct name ## _ \
{ \
template <typename X, typename Y> struct result { typedef X type; }; \
\
template <typename X, typename Y> X operator()(X x, Y y) const \
{ \
using namespace std; \
return name(x, y); \
} \
};
EXPRESSION_FORALL_BINARY_FUNCTIONS(DECLARE_BINARY_FUNCTOR)
#undef DECLARE_BINARY_FUNCTOR
} // end namespace detail
template <typename FPT, typename Iterator>
struct grammar
: boost::spirit::qi::grammar<
Iterator, FPT(), boost::spirit::ascii::space_type
>
{
boost::spirit::qi::rule<
Iterator, FPT(), boost::spirit::ascii::space_type
> expression, term, factor, primary;
grammar() : grammar::base_type(expression)
{
namespace constants = boost::math::constants;
#define DECLARE_PHOENIX_FUNCTION(name) \
boost::phoenix::function<detail::name ## _> name;
EXPRESSION_FORALL_UNARY_FUNCTIONS(DECLARE_PHOENIX_FUNCTION)
EXPRESSION_FORALL_BINARY_FUNCTIONS(DECLARE_PHOENIX_FUNCTION)
#undef DECLARE_PHOENIX_FUNCTION
using boost::spirit::qi::real_parser;
using boost::spirit::qi::real_policies;
real_parser<FPT,real_policies<FPT> > real;
using boost::spirit::qi::_1;
using boost::spirit::qi::_2;
using boost::spirit::qi::no_case;
using boost::spirit::qi::_val;
expression =
term [_val = _1]
>> *( ('+' >> term [_val += _1])
| ('-' >> term [_val -= _1])
)
;
term =
factor [_val = _1]
>> *( ('*' >> factor [_val *= _1])
| ('/' >> factor [_val /= _1])
)
;
factor =
primary [_val = _1 ]
>> *( ("**" >> factor [_val = pow(_val, _1)])
)
;
#define STRINGIFY(s) #s
#define UNARY_FUNCTION_RULE(name) \
| no_case[STRINGIFY(name)] >> '(' >> expression [_val = name(_1)] >> ')'
#define BINARY_FUNCTION_RULE(name) \
| ( no_case[STRINGIFY(name)]>> '(' \
>> expression >> ',' >> expression >> ')' )[_val = name(_1,_2)]
primary =
real [_val = _1]
| '(' >> expression [_val = _1] >> ')'
| ('-' >> primary [_val = -_1])
| ('+' >> primary [_val = _1])
| no_case["pi"] [_val = constants::pi<FPT>()]
EXPRESSION_FORALL_UNARY_FUNCTIONS(UNARY_FUNCTION_RULE)
EXPRESSION_FORALL_BINARY_FUNCTIONS(BINARY_FUNCTION_RULE)
;
#undef UNARY_RULE
#undef BINARY_RULE
#undef STRINGIFY
}
};
#undef EXPRESSION_FORALL_UNARY_FUNCTIONS
#undef EXPRESSION_FORALL_BINARY_FUNCTIONS
template <typename FPT, typename Iterator>
bool parse(Iterator &iter,
Iterator end,
const grammar<FPT,Iterator> &g,
FPT &result)
{
return boost::spirit::qi::phrase_parse(
iter, end, g, boost::spirit::ascii::space, result);
}
} // end namespace expression
/////////////
// Test cases
/////////////
#include <string>
#include <boost/math/special_functions/fpclassify.hpp>
#define BOOST_TEST_MODULE expression
#include <boost/test/included/unit_test.hpp>
const expression::grammar<double,std::string::const_iterator> eg;
const double close_enough = std::numeric_limits<double>::epsilon();
#define EXPRTEST(casename, expr, expected) \
BOOST_AUTO_TEST_CASE( casename ) \
{ \
const std::string s = expr; \
std::string::const_iterator iter = s.begin(); \
std::string::const_iterator end = s.end(); \
double result; \
BOOST_REQUIRE(parse(iter, end, eg, result)); \
BOOST_CHECK(iter == end); \
BOOST_CHECK_CLOSE(result, (expected), close_enough); \
}
EXPRTEST(literal1, "1.234", 1.234)
EXPRTEST(literal2, "4.2e2", 420)
EXPRTEST(literal3, "5e-01", 0.5)
EXPRTEST(literal4, "-3", -3)
EXPRTEST(literal5, "pi", boost::math::constants::pi<double>())
EXPRTEST(basicop1, " 2 +\t3\n", 5) // Whitespace ignored
EXPRTEST(basicop2, " 2 -\t3\n", -1)
EXPRTEST(basicop3, " 2 *\t3\n", 6)
EXPRTEST(basicop4, " 2 /\t3\n", 2./3.) // Double division
EXPRTEST(basicop5, " 2 ** 3\n", 8)
EXPRTEST(pemdas1, "2*3+4*5", 2*3+4*5)
EXPRTEST(pemdas2, "2*(3+4)*5", 2*(3+4)*5)
EXPRTEST(pemdas3, "2**3+4", std::pow(2,3)+4)
EXPRTEST(pemdas4, "2**2**-3", std::pow(2.,std::pow(2.,-3.)))
EXPRTEST(unary1, "-(2)", -2)
EXPRTEST(unary2, "-(-2)", 2)
EXPRTEST(unary3, "+(-2)", -2)
EXPRTEST(unary4, "+(+2)", 2)
EXPRTEST(func_abs, "abs (-1.0)", std::abs(-1.0))
EXPRTEST(func_acos, "acos( 1.0)", std::acos(1.0))
EXPRTEST(func_asin, "asin( 1.0)", std::asin(1.0))
EXPRTEST(func_atan, "atan( 1.0)", std::atan(1.0))
EXPRTEST(func_ceil, "ceil( 0.5)", std::ceil(0.5))
EXPRTEST(func_cos, "cos ( 1.0)", std::cos(1.0))
EXPRTEST(func_cosh, "cosh( 1.0)", std::cosh(1.0))
EXPRTEST(func_exp, "exp ( 1.0)", std::exp(1.0))
EXPRTEST(func_floor, "floor(0.5)", std::floor(0.5))
EXPRTEST(func_log, "log ( 1.0)", std::log(1.0))
EXPRTEST(func_log10, "log10(0.5)", std::log10(0.5))
EXPRTEST(func_sin, "sin ( 1.0)", std::sin(1.0))
EXPRTEST(func_sinh, "sinh( 1.0)", std::sinh(1.0))
EXPRTEST(func_sqrt, "sqrt( 1.0)", std::sqrt(1.0))
EXPRTEST(func_tan, "tan ( 1.0)", std::tan(1.0))
EXPRTEST(func_tanh, "tanh( 1.0)", std::tanh(1.0))
EXPRTEST(func_pow, "pow (2.0, 3.0)", std::pow(2.0,3.0))
EXPRTEST(func_atan2, "atan2(2.0, 3.0)", std::atan2(2.0,3.0))
BOOST_AUTO_TEST_CASE( parse_inf )
{
const std::string s = "inf";
std::string::const_iterator iter = s.begin();
std::string::const_iterator end = s.end();
double result;
BOOST_REQUIRE(parse(iter, end, eg, result));
BOOST_CHECK(iter == end);
BOOST_CHECK((boost::math::isinf)(result));
}
BOOST_AUTO_TEST_CASE( parse_infinity )
{
const std::string s = "infinity";
std::string::const_iterator iter = s.begin();
std::string::const_iterator end = s.end();
double result;
BOOST_REQUIRE(parse(iter, end, eg, result));
BOOST_CHECK(iter == end);
BOOST_CHECK((boost::math::isinf)(result));
}
BOOST_AUTO_TEST_CASE( parse_nan )
{
const std::string s = "nan";
std::string::const_iterator iter = s.begin();
std::string::const_iterator end = s.end();
double result;
BOOST_REQUIRE(parse(iter, end, eg, result));
BOOST_CHECK(iter == end);
BOOST_CHECK((boost::math::isnan)(result));
}
Updated 9 Jan 2012: During a second pass motivated by reducing compilation times, I removed the X-macro nastiness and replaced it with some
qi::symbols-based logic. The code in the anonymous namespace could likely be removed if I could figure out the right boost::phoenix::bind hoodoo to use to replace lazy_ufunc_ and lazy_bfunc_ (any suggestions?). I have not yet measured the difference in either memory footprint or runtime performance. Compilation time and memory is greatly reduced for both GNU and Intel compilers. The same unit tests from before continue to pass against the following version:
#include <cmath>
#include <limits>
#include <iterator>
#include <boost/spirit/version.hpp>
#if !defined(SPIRIT_VERSION) || SPIRIT_VERSION < 0x2010
#error "At least Spirit version 2.1 required"
#endif
#include <boost/math/constants/constants.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/qi.hpp>
namespace expression {
namespace { // anonymous
struct lazy_pow_
{
template <typename X, typename Y>
struct result { typedef X type; };
template <typename X, typename Y>
X operator()(X x, Y y) const
{
return std::pow(x, y);
}
};
struct lazy_ufunc_
{
template <typename F, typename A1>
struct result { typedef A1 type; };
template <typename F, typename A1>
A1 operator()(F f, A1 a1) const
{
return f(a1);
}
};
struct lazy_bfunc_
{
template <typename F, typename A1, typename A2>
struct result { typedef A1 type; };
template <typename F, typename A1, typename A2>
A1 operator()(F f, A1 a1, A2 a2) const
{
return f(a1, a2);
}
};
} // end namespace anonymous
template <typename FPT, typename Iterator>
struct grammar
: boost::spirit::qi::grammar<
Iterator, FPT(), boost::spirit::ascii::space_type
>
{
// symbol table for constants like "pi"
struct constant_
: boost::spirit::qi::symbols<
typename std::iterator_traits<Iterator>::value_type,
FPT
>
{
constant_()
{
this->add
("pi", boost::math::constants::pi<FPT>() )
;
}
} constant;
// symbol table for unary functions like "abs"
struct ufunc_
: boost::spirit::qi::symbols<
typename std::iterator_traits<Iterator>::value_type,
FPT (*)(FPT)
>
{
ufunc_()
{
this->add
("abs" , (FPT (*)(FPT)) std::abs )
("acos" , (FPT (*)(FPT)) std::acos )
("asin" , (FPT (*)(FPT)) std::asin )
("atan" , (FPT (*)(FPT)) std::atan )
("ceil" , (FPT (*)(FPT)) std::ceil )
("cos" , (FPT (*)(FPT)) std::cos )
("cosh" , (FPT (*)(FPT)) std::cosh )
("exp" , (FPT (*)(FPT)) std::exp )
("floor" , (FPT (*)(FPT)) std::floor)
("log" , (FPT (*)(FPT)) std::log )
("log10" , (FPT (*)(FPT)) std::log10)
("sin" , (FPT (*)(FPT)) std::sin )
("sinh" , (FPT (*)(FPT)) std::sinh )
("sqrt" , (FPT (*)(FPT)) std::sqrt )
("tan" , (FPT (*)(FPT)) std::tan )
("tanh" , (FPT (*)(FPT)) std::tanh )
;
}
} ufunc;
// symbol table for binary functions like "pow"
struct bfunc_
: boost::spirit::qi::symbols<
typename std::iterator_traits<Iterator>::value_type,
FPT (*)(FPT, FPT)
>
{
bfunc_()
{
this->add
("pow" , (FPT (*)(FPT, FPT)) std::pow )
("atan2", (FPT (*)(FPT, FPT)) std::atan2)
;
}
} bfunc;
boost::spirit::qi::rule<
Iterator, FPT(), boost::spirit::ascii::space_type
> expression, term, factor, primary;
grammar() : grammar::base_type(expression)
{
using boost::spirit::qi::real_parser;
using boost::spirit::qi::real_policies;
real_parser<FPT,real_policies<FPT> > real;
using boost::spirit::qi::_1;
using boost::spirit::qi::_2;
using boost::spirit::qi::_3;
using boost::spirit::qi::no_case;
using boost::spirit::qi::_val;
boost::phoenix::function<lazy_pow_> lazy_pow;
boost::phoenix::function<lazy_ufunc_> lazy_ufunc;
boost::phoenix::function<lazy_bfunc_> lazy_bfunc;
expression =
term [_val = _1]
>> *( ('+' >> term [_val += _1])
| ('-' >> term [_val -= _1])
)
;
term =
factor [_val = _1]
>> *( ('*' >> factor [_val *= _1])
| ('/' >> factor [_val /= _1])
)
;
factor =
primary [_val = _1]
>> *( ("**" >> factor [_val = lazy_pow(_val, _1)])
)
;
primary =
real [_val = _1]
| '(' >> expression [_val = _1] >> ')'
| ('-' >> primary [_val = -_1])
| ('+' >> primary [_val = _1])
| no_case[constant] [_val = _1]
| (no_case[ufunc] >> '(' >> expression >> ')')
[_val = lazy_ufunc(_1, _2)]
| (no_case[bfunc] >> '(' >> expression >> ','
>> expression >> ')')
[_val = lazy_bfunc(_1, _2, _3)]
;
}
};
template <typename FPT, typename Iterator>
bool parse(Iterator &iter,
Iterator end,
const grammar<FPT,Iterator> &g,
FPT &result)
{
return boost::spirit::qi::phrase_parse(
iter, end, g, boost::spirit::ascii::space, result);
}
} // end namespace expression
![[FSF Associate Member]](http://1.bp.blogspot.com/_Q-Q3vIxb_KE/TQuZ_5PYnqI/AAAAAAAABBU/HhvxUa5jnrI/s1600/FSFMember9255.png){kind=small}
0 comments:
Post a Comment