Boost Spirit のサンプルにはいくつもの計算機の例があるが、四則演算以外をサポートした簡潔な好例がなく、ここで実装例を紹介する価値はありそうである。
本稿では Spirit V2 での例を紹介していく。
Spirit V2 の基本形
Spirit V2 の基本形は以下のようになる。
#include <iostream> #include <string> //#define BOOST_SPIRIT_DEBUG #include <boost/spirit/include/qi.hpp> namespace qi = boost::spirit::qi; namespace client { template <typename Iterator> struct a_parser : qi::grammar<Iterator> { qi::rule<Iterator> top; a_parser() : a_parser::base_type(top) { top = *~qi::lit('\t'); // ここにパーサ規則を書く BOOST_SPIRIT_DEBUG_NODE(top); } }; } int main() { client::a_parser<std::string::const_iterator> a_parser; std::string str; while (std::getline(std::cin, str)) { std::string::const_iterator it = str.begin(), end = str.end(); bool r = phrase_parse(it, end, a_parser, qi::ascii::space); if (r && it == end) { std::cout << "succeeded" << std::endl; } else { std::cout << "failed:\t" << std::string(it, end) << std::endl; return 1; } } return 0; }
計算機でサポートする演算子
以下の演算子をサポートする実装例を段階的に示そう。
- 単項演算子の単項正負(
+ -
)、単項論理否定&ビット否定(! ~
)、二項演算子の二項加減乗除法(+ - * / %
)、関係等号不等号(< <= > >= == !=
)、ビットシフト(<< >>
)、ビット演算子(& ^ |
)、論理積和(&& ||
) - 三項演算子の三項条件(
?:
) - 変数のサポートおよび単項演算子の前後置増減分(
++ --
)、二項演算子の単純代入(=
)、複合代入(+= -+ *= /= %= &= ^= +=
)およびカンマ演算子(,
)
また、演算は任意の数値型で行えるように実装する。
ここで、int
型における1.と2.の演算についてはiexpr
、3.についてはicalc
というプログラム名をつけるものとする。
ここでは敢えてAST(Abstract Syntax Tree)による例は次節にゆずり、セマンティックアクションで計算機を実装する例を紹介する。セマンティックアクションでは構文解析しながら演算を行うので、例えば、以下のような代入と三項条件の組み合わせについては困難を伴うので、次節の AST でサポートするものとする。
i<j ? i++ : i=j
iexpr.cc
int
型における1.と2.の演算を行う計算機を Spirit V2 で実装すると以下のようになるだろう。
#include <iostream> #include <iomanip> #include <string> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix_operator.hpp> namespace client { namespace qi = boost::spirit::qi; namespace ascii = boost::spirit::ascii; template <typename Iterator, typename T> struct calculator : qi::grammar<Iterator, T(), ascii::space_type> { qi::rule<Iterator, T(), ascii::space_type> expr, t[9], term, fctr; calculator() : calculator::base_type(expr) { using qi::_val; using qi::_1; using qi::_2; using qi::uint_; using qi::hex; using qi::oct; #if !0 /* ternary operator */ expr = t[0][_val = _1] >> *('?' >> expr >> ':' >> expr)[_val = if_else(_val, _1, _2)]; #else expr = t[0][_val = _1]; #endif t[0] = t[1][_val = _1] >> *("||" >> t[1][_val = _val || _1]); t[1] = t[2][_val = _1] >> *("&&" >> t[2][_val = _val && _1]); t[2] = t[3][_val = _1] >> *('|' >> t[3][_val |= _1]); t[3] = t[4][_val = _1] >> *('^' >> t[4][_val ^= _1]); t[4] = t[5][_val = _1] >> *('&' >> t[5][_val &= _1]); t[5] = t[6][_val = _1] >> *("<<" >> t[6][_val <<= _1] | ">>" >> t[6][_val >>= _1]); t[6] = t[7][_val = _1] >> *('<' >> t[7][_val = _val < _1] | '>' >> t[7][_val = _val > _1] | "<=" >> t[7][_val = _val <= _1] | ">=" >> t[7][_val = _val >= _1]); t[7] = t[8][_val = _1] >> *("==" >> t[8][_val = _val == _1] | "!=" >> t[8][_val = _val != _1]); t[8] = term[_val = _1] >> *('+' >> term[_val += _1] | '-' >> term[_val -= _1]); term = fctr[_val = _1] >> *('*' >> fctr[_val *= _1] | '/' >> fctr[_val /= _1] | '%' >> fctr[_val %= _1]); fctr = "0x" >> hex[_val = _1] | '0' >> oct[_val = _1] | uint_[_val = _1] | '(' >> expr[_val = _1] >> ')' | '-' >> fctr[_val = -_1] | '+' >> fctr[_val = _1] | '!' >> fctr[_val = !_1] | '~' >> fctr[_val = ~_1]; } }; } int main(int argc, char *argv[]) { int rv = 0; typedef std::string::const_iterator iterator_type; typedef int value_type; client::calculator<iterator_type, value_type> calc; std::string str; value_type result; while (std::getline(std::cin, str)) { std::string::const_iterator it = str.begin(), end = str.end(); bool r = phrase_parse(it, end, calc, boost::spirit::ascii::space, result); if (r && it == end) { std::cout << "succeeded:\t" << std::endl; std::cout << result << std::endl; } else { std::cout << "failed:\t" << std::string(it, end) << std::endl; rv = !0; } } return rv; }
もし unsigned int
型の演算を行いたければ、main
関数の冒頭を typedef unsigned int value_type;
に書き換えれば良い。
さて、これは Boost Phoenix のおかげで極めて簡便に書かれているが、このまま変数のサポートと代入演算子を導入するのは困難である。よって、Boost Variant による AST の実装に切り換える。
iexpr+variant.cc
#include <iostream> #include <iomanip> #include <string> #include <boost/variant.hpp> #include <vector> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix.hpp> namespace client { struct nulary_op {}; struct unary_op; struct binary_op; struct ternary_op; struct astree { typedef boost::variant< nulary_op, boost::recursive_wrapper<unary_op>, boost::recursive_wrapper<binary_op>, boost::recursive_wrapper<ternary_op>, int > type; typedef type::types types; enum { nulary_op_type, unary_op_type, binary_op_type, ternary_op_type, value_type, }; type expr; int which() const { return expr.which(); } astree() : expr(nulary_op()) {} astree(unary_op const &expr) : expr(expr) {} astree(binary_op const &expr) : expr(expr) {} astree(ternary_op const &expr) : expr(expr) {} astree(unsigned int expr) : expr(expr) {} astree(type const &expr) : expr(expr) {} astree &ternary_conditional(astree const &a, astree const &b); astree &binary_logical_or(astree const &rhs); astree &binary_logical_and(astree const &rhs); astree &binary_bitwise_or(astree const &rhs); astree &binary_bitwise_xor(astree const &rhs); astree &binary_bitwise_and(astree const &rhs); astree &binary_bitshift_left(astree const &rhs); astree &binary_bitshift_right(astree const &rhs); astree &binary_less(astree const &rhs); astree &binary_less_equal(astree const &rhs); astree &binary_greater(astree const &rhs); astree &binary_greater_equal(astree const &rhs); astree &binary_equal_to(astree const &rhs); astree &binary_not_equal_to(astree const &rhs); astree &binary_plus(astree const &rhs); astree &binary_minus(astree const &rhs); astree &binary_multiplies(astree const &rhs); astree &binary_divides(astree const &rhs); astree &binary_modulus(astree const &rhs); astree &unary_negate(); astree &unary_logical_not(); astree &unary_bitwise_not(); }; } // namespace client namespace boost { template <typename T> inline T get(client::astree const &expr) { return boost::get<T>(expr.expr); } } namespace client { enum byte_code { code_negate = 1, code_logical_not, code_bitwise_not, code_plus, code_minus, code_multiplies, code_divides, code_modulus, code_bitshift_left, code_bitshift_right, code_less, code_less_equal, code_greater, code_greater_equal, code_equal_to, code_not_equal_to, code_logical_or, code_logical_and, code_bitwise_or, code_bitwise_xor, code_bitwise_and, code_ternary_conditional, code_value, }; struct ternary_op { ternary_op() {} ternary_op(int op, astree const &c, astree const &a, astree const &b) : op(op), c(c), a(a), b(b) {} int op; astree c, a, b; }; struct binary_op { binary_op() {} binary_op(int op, astree const &lhs, astree const &rhs) : op(op), lhs(lhs), rhs(rhs) {} int op; astree lhs, rhs; }; struct unary_op { unary_op() {} unary_op(int op, astree const &rhs) : op(op), rhs(rhs) {} int op; astree rhs; }; inline astree &astree::ternary_conditional(astree const &a, astree const &b) { expr = ternary_op(code_ternary_conditional, expr, a, b); return *this; } inline astree &astree::binary_logical_or(astree const &rhs) { expr = binary_op(code_logical_or, expr, rhs); return *this; } inline astree &astree::binary_logical_and(astree const &rhs) { expr = binary_op(code_logical_and, expr, rhs); return *this; } inline astree &astree::binary_bitwise_or(astree const &rhs) { expr = binary_op(code_bitwise_or, expr, rhs); return *this; } inline astree &astree::binary_bitwise_xor(astree const &rhs) { expr = binary_op(code_bitwise_xor, expr, rhs); return *this; } inline astree &astree::binary_bitwise_and(astree const &rhs) { expr = binary_op(code_bitwise_and, expr, rhs); return *this; } inline astree &astree::binary_bitshift_left(astree const &rhs) { expr = binary_op(code_bitshift_left, expr, rhs); return *this; } inline astree &astree::binary_bitshift_right(astree const &rhs) { expr = binary_op(code_bitshift_right, expr, rhs); return *this; } inline astree &astree::binary_less(astree const &rhs) { expr = binary_op(code_less, expr, rhs); return *this; } inline astree &astree::binary_less_equal(astree const &rhs) { expr = binary_op(code_less_equal, expr, rhs); return *this; } inline astree &astree::binary_greater(astree const &rhs) { expr = binary_op(code_greater, expr, rhs); return *this; } inline astree &astree::binary_greater_equal(astree const &rhs) { expr = binary_op(code_greater_equal, expr, rhs); return *this; } inline astree &astree::binary_equal_to(astree const &rhs) { expr = binary_op(code_equal_to, expr, rhs); return *this; } inline astree &astree::binary_not_equal_to(astree const &rhs) { expr = binary_op(code_not_equal_to, expr, rhs); return *this; } inline astree &astree::binary_plus(astree const &rhs) { expr = binary_op(code_plus, expr, rhs); return *this; } inline astree &astree::binary_minus(astree const &rhs) { expr = binary_op(code_minus, expr, rhs); return *this; } inline astree &astree::binary_multiplies(astree const &rhs) { expr = binary_op(code_multiplies, expr, rhs); return *this; } inline astree &astree::binary_divides(astree const &rhs) { expr = binary_op(code_divides, expr, rhs); return *this; } inline astree &astree::binary_modulus(astree const &rhs) { expr = binary_op(code_modulus, expr, rhs); return *this; } inline astree &astree::unary_negate() { expr = unary_op(code_negate, expr); return *this; } inline astree &astree::unary_logical_not() { expr = unary_op(code_logical_not, expr); return *this; } inline astree &astree::unary_bitwise_not() { expr = unary_op(code_bitwise_not, expr); return *this; } } namespace client { namespace qi = boost::spirit::qi; namespace ascii = boost::spirit::ascii; template <typename Iterator> struct calculator : qi::grammar<Iterator, astree(), ascii::space_type> { qi::rule<Iterator, astree(), ascii::space_type> expr, t[9], term, fctr; calculator() : calculator::base_type(expr) { using qi::_val; using qi::_1; using qi::_2; using qi::hex; using qi::oct; using qi::uint_; expr = t[0][_val = _1] >> *('?' >> expr >> ':' >> expr)[_val = bind(&astree::ternary_conditional, _val, _1, _2)]; t[0] = t[1][_val = _1] >> *("||" >> t[1][_val = bind(&astree::binary_logical_or, _val, _1)]); t[1] = t[2][_val = _1] >> *("&&" >> t[2][_val = bind(&astree::binary_logical_and, _val, _1)]); t[2] = t[3][_val = _1] >> *('|' >> t[3][_val = bind(&astree::binary_bitwise_or, _val, _1)]); t[3] = t[4][_val = _1] >> *('^' >> t[4][_val = bind(&astree::binary_bitwise_xor, _val, _1)]); t[4] = t[5][_val = _1] >> *('&' >> t[5][_val = bind(&astree::binary_bitwise_and, _val, _1)]); t[5] = t[6][_val = _1] >> *("<<" >> t[6][_val = bind(&astree::binary_bitshift_left, _val, _1)] | ">>" >> t[6][_val = bind(&astree::binary_bitshift_right, _val, _1)]); t[6] = t[7][_val = _1] >> *('<' >> t[7][_val = bind(&astree::binary_less, _val, _1)] | '>' >> t[7][_val = bind(&astree::binary_greater, _val, _1)] | "<=" >> t[7][_val = bind(&astree::binary_less_equal, _val, _1)] | ">=" >> t[7][_val = bind(&astree::binary_greater_equal, _val, _1)]); t[7] = t[8][_val = _1] >> *("==" >> t[8][_val = bind(&astree::binary_equal_to, _val, _1)] | "!=" >> t[8][_val = bind(&astree::binary_not_equal_to, _val, _1)]); t[8] = term[_val = _1] >> *('+' >> term[_val = bind(&astree::binary_plus, _val, _1)] | '-' >> term[_val = bind(&astree::binary_minus, _val, _1)]); term = fctr[_val = _1] >> *('*' >> fctr[_val = bind(&astree::binary_multiplies, _val, _1)] | '/' >> fctr[_val = bind(&astree::binary_divides, _val, _1)] | '%' >> fctr[_val = bind(&astree::binary_modulus, _val, _1)]); fctr = "0x" >> hex[_val = _1] | '0' >> oct[_val = _1] | uint_[_val = _1] | '(' >> expr[_val = _1] >> ')' | '-' >> fctr[_val = bind(&astree::unary_negate, _1)] | '+' >> fctr[_val = _1] | '!' >> fctr[_val = bind(&astree::unary_logical_not, _1)] | '~' >> fctr[_val = bind(&astree::unary_bitwise_not, _1)]; } }; template <typename T> struct calculator_astree_machine { calculator_astree_machine() {} T execute(const astree &ast) { if (ast.which() == astree::value_type || false) { return (T)boost::get<int>(ast); // ! } T lhs, rhs, c, a, b; switch (ast.which()) { case astree::unary_op_type: rhs = execute(boost::get<unary_op>(ast).rhs); switch (boost::get<unary_op>(ast).op) { case code_negate: return -rhs; case code_logical_not: return !rhs; case code_bitwise_not: return ~rhs; } break; case astree::binary_op_type: lhs = execute(boost::get<binary_op>(ast).lhs); rhs = execute(boost::get<binary_op>(ast).rhs); switch (boost::get<binary_op>(ast).op) { case code_plus: return lhs + rhs; case code_minus: return lhs - rhs; case code_multiplies: return lhs * rhs; case code_divides: return lhs / rhs; case code_modulus: return lhs % rhs; case code_bitshift_left: return lhs << rhs; case code_bitshift_right: return lhs >> rhs; case code_less: return lhs < rhs; case code_less_equal: return lhs <= rhs; case code_greater: return lhs > rhs; case code_greater_equal: return lhs >= rhs; case code_equal_to: return lhs == rhs; case code_not_equal_to: return lhs != rhs; case code_logical_or: return lhs || rhs; case code_logical_and: return lhs && rhs; case code_bitwise_or: return lhs | rhs; case code_bitwise_xor: return lhs ^ rhs; case code_bitwise_and: return lhs & rhs; } break; case astree::ternary_op_type: c = execute(boost::get<ternary_op>(ast).c); a = execute(boost::get<ternary_op>(ast).a); b = execute(boost::get<ternary_op>(ast).b); switch (boost::get<ternary_op>(ast).op) { case code_ternary_conditional: return c ? a : b; } break; } return T(0); } }; } // namespace client int main(int argc, char *argv[]) { int rv = 0; typedef std::string::const_iterator iterator_type; typedef int value_type; client::calculator<iterator_type> calc; std::string str; client::astree result; value_type a; while (std::getline(std::cin, str)) { iterator_type it = str.begin(), end = str.end(); bool r = phrase_parse(it, end, calc, boost::spirit::ascii::space, result); client::calculator_astree_machine<value_type> vmachine; a = vmachine.execute(result); if (r && it == end) { std::cout << "succeeded:\t" << std::endl; std::cout << a << std::endl; } else { std::cout << "failed:\t" << std::string(it, end) << std::endl; rv = !0; } } return rv; }
同様に、もし unsigned int
型の演算を行いたければ、main
関数の冒頭を typedef unsigned int value_type;
に書き換えれば良い。
クラス astree
が導入され、その boost::variant
型のメンバ変数 expr
が AST を構成していることがわかるだろう。そしてその AST を calculator_astree_machine::execute
によって再帰的に演算している。
icalc+variant.cc
さて、iexpr+variant.cc
に変数のサポートと代入演算子を導入すると以下のようになるだろう。
#include <iostream> #include <iomanip> #include <string> #include <boost/variant.hpp> #include <vector> #include <map> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix.hpp> namespace client { struct nulary_op {}; struct unary_op; struct binary_op; struct ternary_op; struct astree { typedef boost::variant< nulary_op, boost::recursive_wrapper<unary_op>, boost::recursive_wrapper<binary_op>, boost::recursive_wrapper<ternary_op>, std::string, int > type; typedef type::types types; enum { nulary_op_type, unary_op_type, binary_op_type, ternary_op_type, string_type, value_type, }; type expr; int which() const { return expr.which(); } astree() : expr(nulary_op()) {} astree(unary_op const &expr) : expr(expr) {} astree(binary_op const &expr) : expr(expr) {} astree(ternary_op const &expr) : expr(expr) {} astree(unsigned int expr) : expr(expr) {} astree(type const &expr) : expr(expr) {} astree &ternary_conditional(astree const &a, astree const &b); astree &assignment_direct(astree const &rhs); astree &assignment_summation(astree const &rhs); astree &assignment_difference(astree const &rhs); astree &assignment_product(astree const &rhs); astree &assignment_quotient(astree const &rhs); astree &assignment_remainder(astree const &rhs); astree &assignment_bitshift_left(astree const &rhs); astree &assignment_bitshift_right(astree const &rhs); astree &assignment_bitwise_and(astree const &rhs); astree &assignment_bitwise_xor(astree const &rhs); astree &assignment_bitwise_or(astree const &rhs); astree &prefix_increment(); astree &prefix_decrement(); astree &postfix_increment(); astree &postfix_decrement(); astree &binary_comma(astree const &rhs); astree &binary_logical_or(astree const &rhs); astree &binary_logical_and(astree const &rhs); astree &binary_bitwise_or(astree const &rhs); astree &binary_bitwise_xor(astree const &rhs); astree &binary_bitwise_and(astree const &rhs); astree &binary_bitshift_left(astree const &rhs); astree &binary_bitshift_right(astree const &rhs); astree &binary_less(astree const &rhs); astree &binary_less_equal(astree const &rhs); astree &binary_greater(astree const &rhs); astree &binary_greater_equal(astree const &rhs); astree &binary_equal_to(astree const &rhs); astree &binary_not_equal_to(astree const &rhs); astree &binary_plus(astree const &rhs); astree &binary_minus(astree const &rhs); astree &binary_multiplies(astree const &rhs); astree &binary_divides(astree const &rhs); astree &binary_modulus(astree const &rhs); astree &unary_negate(); astree &unary_logical_not(); astree &unary_bitwise_not(); }; } // namespace client namespace boost { template <typename T> inline T get(client::astree const &expr) { return boost::get<T>(expr.expr); } } namespace client { enum byte_code { code_negate = 1, code_logical_not, code_bitwise_not, code_plus, code_minus, code_multiplies, code_divides, code_modulus, code_bitshift_left, code_bitshift_right, code_less, code_less_equal, code_greater, code_greater_equal, code_equal_to, code_not_equal_to, code_logical_or, code_logical_and, code_bitwise_or, code_bitwise_xor, code_bitwise_and, code_assignment_direct, code_assignment_summation, code_assignment_difference, code_assignment_product, code_assignment_quotient, code_assignment_remainder, code_assignment_bitshift_left, code_assignment_bitshift_right, code_assignment_bitwise_and, code_assignment_bitwise_xor, code_assignment_bitwise_or, code_prefix_increment, code_prefix_decrement, code_postfix_increment, code_postfix_decrement, code_comma, code_ternary_conditional, code_var, code_value, }; struct ternary_op { ternary_op() {} ternary_op(int op, astree const &c, astree const &a, astree const &b) : op(op), c(c), a(a), b(b) {} int op; astree c, a, b; }; struct binary_op { binary_op() {} binary_op(int op, astree const &lhs, astree const &rhs) : op(op), lhs(lhs), rhs(rhs) {} int op; astree lhs, rhs; }; struct unary_op { unary_op() {} unary_op(int op, astree const &rhs) : op(op), rhs(rhs) {} int op; astree rhs; }; inline astree &astree::ternary_conditional(astree const &a, astree const &b) { expr = ternary_op(code_ternary_conditional, expr, a, b); return *this; } inline astree &astree::assignment_direct(astree const &rhs) { expr = binary_op(code_assignment_direct, expr, rhs); return *this; } inline astree &astree::assignment_summation(astree const &rhs) { expr = binary_op(code_assignment_summation, expr, rhs); return *this; } inline astree &astree::assignment_difference(astree const &rhs) { expr = binary_op(code_assignment_difference, expr, rhs); return *this; } inline astree &astree::assignment_product(astree const &rhs) { expr = binary_op(code_assignment_product, expr, rhs); return *this; } inline astree &astree::assignment_quotient(astree const &rhs) { expr = binary_op(code_assignment_quotient, expr, rhs); return *this; } inline astree &astree::assignment_remainder(astree const &rhs) { expr = binary_op(code_assignment_remainder, expr, rhs); return *this; } inline astree &astree::assignment_bitshift_left(astree const &rhs) { expr = binary_op(code_assignment_bitshift_left, expr, rhs); return *this; } inline astree &astree::assignment_bitshift_right(astree const &rhs) { expr = binary_op(code_assignment_bitshift_right, expr, rhs); return *this; } inline astree &astree::assignment_bitwise_and(astree const &rhs) { expr = binary_op(code_assignment_bitwise_and, expr, rhs); return *this; } inline astree &astree::assignment_bitwise_xor(astree const &rhs) { expr = binary_op(code_assignment_bitwise_xor, expr, rhs); return *this; } inline astree &astree::assignment_bitwise_or(astree const &rhs) { expr = binary_op(code_assignment_bitwise_or, expr, rhs); return *this; } inline astree &astree::prefix_increment() { expr = unary_op(code_prefix_increment, expr); return *this; } inline astree &astree::prefix_decrement() { expr = unary_op(code_prefix_decrement, expr); return *this; } inline astree &astree::postfix_increment() { expr = unary_op(code_postfix_increment, expr); return *this; } inline astree &astree::postfix_decrement() { expr = unary_op(code_postfix_decrement, expr); return *this; } inline astree &astree::binary_comma(astree const &rhs) { expr = binary_op(code_comma, expr, rhs); return *this; } inline astree &astree::binary_logical_or(astree const &rhs) { expr = binary_op(code_logical_or, expr, rhs); return *this; } inline astree &astree::binary_logical_and(astree const &rhs) { expr = binary_op(code_logical_and, expr, rhs); return *this; } inline astree &astree::binary_bitwise_or(astree const &rhs) { expr = binary_op(code_bitwise_or, expr, rhs); return *this; } inline astree &astree::binary_bitwise_xor(astree const &rhs) { expr = binary_op(code_bitwise_xor, expr, rhs); return *this; } inline astree &astree::binary_bitwise_and(astree const &rhs) { expr = binary_op(code_bitwise_and, expr, rhs); return *this; } inline astree &astree::binary_bitshift_left(astree const &rhs) { expr = binary_op(code_bitshift_left, expr, rhs); return *this; } inline astree &astree::binary_bitshift_right(astree const &rhs) { expr = binary_op(code_bitshift_right, expr, rhs); return *this; } inline astree &astree::binary_less(astree const &rhs) { expr = binary_op(code_less, expr, rhs); return *this; } inline astree &astree::binary_less_equal(astree const &rhs) { expr = binary_op(code_less_equal, expr, rhs); return *this; } inline astree &astree::binary_greater(astree const &rhs) { expr = binary_op(code_greater, expr, rhs); return *this; } inline astree &astree::binary_greater_equal(astree const &rhs) { expr = binary_op(code_greater_equal, expr, rhs); return *this; } inline astree &astree::binary_equal_to(astree const &rhs) { expr = binary_op(code_equal_to, expr, rhs); return *this; } inline astree &astree::binary_not_equal_to(astree const &rhs) { expr = binary_op(code_not_equal_to, expr, rhs); return *this; } inline astree &astree::binary_plus(astree const &rhs) { expr = binary_op(code_plus, expr, rhs); return *this; } inline astree &astree::binary_minus(astree const &rhs) { expr = binary_op(code_minus, expr, rhs); return *this; } inline astree &astree::binary_multiplies(astree const &rhs) { expr = binary_op(code_multiplies, expr, rhs); return *this; } inline astree &astree::binary_divides(astree const &rhs) { expr = binary_op(code_divides, expr, rhs); return *this; } inline astree &astree::binary_modulus(astree const &rhs) { expr = binary_op(code_modulus, expr, rhs); return *this; } inline astree &astree::unary_negate() { expr = unary_op(code_negate, expr); return *this; } inline astree &astree::unary_logical_not() { expr = unary_op(code_logical_not, expr); return *this; } inline astree &astree::unary_bitwise_not() { expr = unary_op(code_bitwise_not, expr); return *this; } } namespace client { namespace qi = boost::spirit::qi; namespace ascii = boost::spirit::ascii; template <typename Iterator> struct calculator : qi::grammar<Iterator, astree(), ascii::space_type> { qi::rule<Iterator, astree(), ascii::space_type> vars, e[7], expr, t[9], term, fctr; calculator() : calculator::base_type(expr) { using qi::_val; using qi::_1; using qi::_2; using qi::hex; using qi::oct; using qi::uint_; using qi::alpha; using qi::alnum; using qi::lexeme; using qi::as_string; vars = as_string[lexeme[(alpha >> *(alnum | '_'))]]; expr = e[0][_val = _1] >> *(',' >> e[0][_val = bind(&astree::binary_comma, _val, _1)]); e[0] = e[1] | e[2] | e[3] | e[4] | e[5] | e[6]; e[1] = vars[_val = _1] >> ('=' >> e[0][_val = bind(&astree::assignment_direct, _val, _1)]); e[2] = vars[_val = _1] >> ("+=" >> e[0][_val = bind(&astree::assignment_summation, _val, _1)] | "-=" >> e[0][_val = bind(&astree::assignment_difference, _val, _1)]); e[3] = vars[_val = _1] >> ("*=" >> e[0][_val = bind(&astree::assignment_product, _val, _1)] | "/=" >> e[0][_val = bind(&astree::assignment_quotient, _val, _1)] | "%=" >> e[0][_val = bind(&astree::assignment_remainder, _val, _1)]); e[4] = vars[_val = _1] >> ("<<=" >> e[0][_val = bind(&astree::assignment_bitshift_left, _val, _1)] | ">>=" >> e[0][_val = bind(&astree::assignment_bitshift_right, _val, _1)]); e[5] = vars[_val = _1] >> ("&=" >> e[0][_val = bind(&astree::assignment_bitwise_and, _val, _1)] | "^=" >> e[0][_val = bind(&astree::assignment_bitwise_xor, _val, _1)] | "|=" >> e[0][_val = bind(&astree::assignment_bitwise_or, _val, _1)]); e[6] = t[0][_val = _1] >> *('?' >> e[0] >> ':' >> e[0])[_val = bind(&astree::ternary_conditional, _val, _1, _2)]; t[0] = t[1][_val = _1] >> *("||" >> t[1][_val = bind(&astree::binary_logical_or, _val, _1)]); t[1] = t[2][_val = _1] >> *("&&" >> t[2][_val = bind(&astree::binary_logical_and, _val, _1)]); t[2] = t[3][_val = _1] >> *('|' >> t[3][_val = bind(&astree::binary_bitwise_or, _val, _1)]); t[3] = t[4][_val = _1] >> *('^' >> t[4][_val = bind(&astree::binary_bitwise_xor, _val, _1)]); t[4] = t[5][_val = _1] >> *('&' >> t[5][_val = bind(&astree::binary_bitwise_and, _val, _1)]); t[5] = t[6][_val = _1] >> *("<<" >> t[6][_val = bind(&astree::binary_bitshift_left, _val, _1)] | ">>" >> t[6][_val = bind(&astree::binary_bitshift_right, _val, _1)]); t[6] = t[7][_val = _1] >> *('<' >> t[7][_val = bind(&astree::binary_less, _val, _1)] | '>' >> t[7][_val = bind(&astree::binary_greater, _val, _1)] | "<=" >> t[7][_val = bind(&astree::binary_less_equal, _val, _1)] | ">=" >> t[7][_val = bind(&astree::binary_greater_equal, _val, _1)]); t[7] = t[8][_val = _1] >> *("==" >> t[8][_val = bind(&astree::binary_equal_to, _val, _1)] | "!=" >> t[8][_val = bind(&astree::binary_not_equal_to, _val, _1)]); t[8] = term[_val = _1] >> *('+' >> term[_val = bind(&astree::binary_plus, _val, _1)] | '-' >> term[_val = bind(&astree::binary_minus, _val, _1)]); term = fctr[_val = _1] >> *('*' >> fctr[_val = bind(&astree::binary_multiplies, _val, _1)] | '/' >> fctr[_val = bind(&astree::binary_divides, _val, _1)] | '%' >> fctr[_val = bind(&astree::binary_modulus, _val, _1)]); fctr = "0x" >> hex[_val = _1] | '0' >> oct[_val = _1] | uint_[_val = _1] | "++" >> vars[_val = bind(&astree::prefix_increment, _1)] | "--" >> vars[_val = bind(&astree::prefix_decrement, _1)] | vars[_val = bind(&astree::postfix_increment, _1)] >> "++" | vars[_val = bind(&astree::postfix_decrement, _1)] >> "--" | vars[_val = _1] | '(' >> expr[_val = _1] >> ')' | '-' >> fctr[_val = bind(&astree::unary_negate, _1)] | '+' >> fctr[_val = _1] | '!' >> fctr[_val = bind(&astree::unary_logical_not, _1)] | '~' >> fctr[_val = bind(&astree::unary_bitwise_not, _1)]; } }; template <typename T> struct calculator_astree_machine { std::map<std::string, T> &vars; calculator_astree_machine(std::map<std::string, T> &vars) : vars(vars) {} T execute(const astree &ast) { if (ast.which() == astree::value_type || ast.which() == astree::string_type || false) { if (ast.which() == astree::string_type) { if (vars.find(boost::get<std::string>(ast)) == vars.end()) vars[boost::get<std::string>(ast)] = 0; return vars[boost::get<std::string>(ast)]; } return (T)boost::get<int>(ast); // ! } T lhs, rhs, c, a, b; switch (ast.which()) { case astree::unary_op_type: rhs = execute(boost::get<unary_op>(ast).rhs); switch (boost::get<unary_op>(ast).op) { case code_negate: return -rhs; case code_logical_not: return !rhs; case code_bitwise_not: return ~rhs; case code_prefix_increment: return ++vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]; case code_prefix_decrement: return --vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]; case code_postfix_increment: return vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]++; case code_postfix_decrement: return vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]--; } break; case astree::binary_op_type: lhs = execute(boost::get<binary_op>(ast).lhs); rhs = execute(boost::get<binary_op>(ast).rhs); switch (boost::get<binary_op>(ast).op) { case code_plus: return lhs + rhs; case code_minus: return lhs - rhs; case code_multiplies: return lhs * rhs; case code_divides: return lhs / rhs; case code_modulus: return lhs % rhs; case code_bitshift_left: return lhs << rhs; case code_bitshift_right: return lhs >> rhs; case code_less: return lhs < rhs; case code_less_equal: return lhs <= rhs; case code_greater: return lhs > rhs; case code_greater_equal: return lhs >= rhs; case code_equal_to: return lhs == rhs; case code_not_equal_to: return lhs != rhs; case code_logical_or: return lhs || rhs; case code_logical_and: return lhs && rhs; case code_bitwise_or: return lhs | rhs; case code_bitwise_xor: return lhs ^ rhs; case code_bitwise_and: return lhs & rhs; case code_assignment_direct: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] = rhs); case code_assignment_summation: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] += rhs); case code_assignment_difference: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] -= rhs); case code_assignment_product: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] *= rhs); case code_assignment_quotient: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] /= rhs); case code_assignment_remainder: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] %= rhs); case code_assignment_bitshift_left: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] <<= rhs); case code_assignment_bitshift_right: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] >>= rhs); case code_assignment_bitwise_and: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] &= rhs); case code_assignment_bitwise_xor: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] ^= rhs); case code_assignment_bitwise_or: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] |= rhs); case code_comma: return lhs, rhs; } break; case astree::ternary_op_type: c = execute(boost::get<ternary_op>(ast).c); a = execute(boost::get<ternary_op>(ast).a); b = execute(boost::get<ternary_op>(ast).b); switch (boost::get<ternary_op>(ast).op) { case code_ternary_conditional: return c ? a : b; } break; } return T(0); } }; } // namespace client int main(int argc, char *argv[]) { int rv = 0; typedef std::string::const_iterator iterator_type; typedef int value_type; client::calculator<iterator_type> calc; std::map<std::string, value_type> vars; std::string str; client::astree result; value_type a; while (std::getline(std::cin, str)) { iterator_type it = str.begin(), end = str.end(); bool r = phrase_parse(it, end, calc, boost::spirit::ascii::space, result); client::calculator_astree_machine<value_type> vmachine(vars); a = vmachine.execute(result); if (r && it == end) { std::cout << "succeeded:\t" << std::endl; std::cout << a << std::endl; } else { std::cout << "failed:\t" << std::string(it, end) << std::endl; rv = !0; } } return rv; }
同様に、もし unsigned int
型の演算を行いたければ、main
関数の冒頭を typedef unsigned int value_type;
に書き換えれば良い。
ちなみに、この実装では代入時に未使用の変数を新たに使用することができ、変数の参照時に未使用の変数を使用すると零が代入されているものとする。
diff -u iexpr+variant.cc icalc+variant.cc
上述の二つのプログラムリストの掲示だけでは、どのように変数のサポートと代入演算子を導入したかが分かり辛いので、これらの Unified diff 形式をみてみよう。
--- iexpr+variant.cc +++ icalc+variant.cc @@ -3,6 +3,7 @@ #include <string> #include <boost/variant.hpp> #include <vector> +#include <map> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix.hpp> @@ -18,6 +19,7 @@ boost::recursive_wrapper<unary_op>, boost::recursive_wrapper<binary_op>, boost::recursive_wrapper<ternary_op>, + std::string, int > type; typedef type::types types; @@ -26,6 +28,7 @@ unary_op_type, binary_op_type, ternary_op_type, + string_type, value_type, }; @@ -42,6 +45,25 @@ astree &ternary_conditional(astree const &a, astree const &b); + astree &assignment_direct(astree const &rhs); + astree &assignment_summation(astree const &rhs); + astree &assignment_difference(astree const &rhs); + astree &assignment_product(astree const &rhs); + astree &assignment_quotient(astree const &rhs); + astree &assignment_remainder(astree const &rhs); + astree &assignment_bitshift_left(astree const &rhs); + astree &assignment_bitshift_right(astree const &rhs); + astree &assignment_bitwise_and(astree const &rhs); + astree &assignment_bitwise_xor(astree const &rhs); + astree &assignment_bitwise_or(astree const &rhs); + + astree &prefix_increment(); + astree &prefix_decrement(); + astree &postfix_increment(); + astree &postfix_decrement(); + + astree &binary_comma(astree const &rhs); + astree &binary_logical_or(astree const &rhs); astree &binary_logical_and(astree const &rhs); @@ -102,7 +124,24 @@ code_bitwise_or, code_bitwise_xor, code_bitwise_and, + code_assignment_direct, + code_assignment_summation, + code_assignment_difference, + code_assignment_product, + code_assignment_quotient, + code_assignment_remainder, + code_assignment_bitshift_left, + code_assignment_bitshift_right, + code_assignment_bitwise_and, + code_assignment_bitwise_xor, + code_assignment_bitwise_or, + code_prefix_increment, + code_prefix_decrement, + code_postfix_increment, + code_postfix_decrement, + code_comma, code_ternary_conditional, + code_var, code_value, }; @@ -136,6 +175,57 @@ { expr = ternary_op(code_ternary_conditional, expr, a, b); return *this; } + inline + astree &astree::assignment_direct(astree const &rhs) + { expr = binary_op(code_assignment_direct, expr, rhs); return *this; } + inline + astree &astree::assignment_summation(astree const &rhs) + { expr = binary_op(code_assignment_summation, expr, rhs); return *this; } + inline + astree &astree::assignment_difference(astree const &rhs) + { expr = binary_op(code_assignment_difference, expr, rhs); return *this; } + inline + astree &astree::assignment_product(astree const &rhs) + { expr = binary_op(code_assignment_product, expr, rhs); return *this; } + inline + astree &astree::assignment_quotient(astree const &rhs) + { expr = binary_op(code_assignment_quotient, expr, rhs); return *this; } + inline + astree &astree::assignment_remainder(astree const &rhs) + { expr = binary_op(code_assignment_remainder, expr, rhs); return *this; } + inline + astree &astree::assignment_bitshift_left(astree const &rhs) + { expr = binary_op(code_assignment_bitshift_left, expr, rhs); return *this; } + inline + astree &astree::assignment_bitshift_right(astree const &rhs) + { expr = binary_op(code_assignment_bitshift_right, expr, rhs); return *this; } + inline + astree &astree::assignment_bitwise_and(astree const &rhs) + { expr = binary_op(code_assignment_bitwise_and, expr, rhs); return *this; } + inline + astree &astree::assignment_bitwise_xor(astree const &rhs) + { expr = binary_op(code_assignment_bitwise_xor, expr, rhs); return *this; } + inline + astree &astree::assignment_bitwise_or(astree const &rhs) + { expr = binary_op(code_assignment_bitwise_or, expr, rhs); return *this; } + + inline + astree &astree::prefix_increment() + { expr = unary_op(code_prefix_increment, expr); return *this; } + inline + astree &astree::prefix_decrement() + { expr = unary_op(code_prefix_decrement, expr); return *this; } + inline + astree &astree::postfix_increment() + { expr = unary_op(code_postfix_increment, expr); return *this; } + inline + astree &astree::postfix_decrement() + { expr = unary_op(code_postfix_decrement, expr); return *this; } + + inline + astree &astree::binary_comma(astree const &rhs) + { expr = binary_op(code_comma, expr, rhs); return *this; } + inline astree &astree::binary_logical_or(astree const &rhs) { expr = binary_op(code_logical_or, expr, rhs); return *this; } inline @@ -211,7 +301,7 @@ template <typename Iterator> struct calculator : qi::grammar<Iterator, astree(), ascii::space_type> { - qi::rule<Iterator, astree(), ascii::space_type> expr, t[9], term, fctr; + qi::rule<Iterator, astree(), ascii::space_type> vars, e[7], expr, t[9], term, fctr; calculator() : calculator::base_type(expr) { using qi::_val; @@ -220,9 +310,27 @@ using qi::hex; using qi::oct; using qi::uint_; - - expr = t[0][_val = _1] >> *('?' >> expr >> - ':' >> expr)[_val = bind(&astree::ternary_conditional, _val, _1, _2)]; + using qi::alpha; + using qi::alnum; + using qi::lexeme; + using qi::as_string; + + vars = as_string[lexeme[(alpha >> *(alnum | '_'))]]; + expr = e[0][_val = _1] >> *(',' >> e[0][_val = bind(&astree::binary_comma, _val, _1)]); + e[0] = e[1] | e[2] | e[3] | e[4] | e[5] | e[6]; + e[1] = vars[_val = _1] >> ('=' >> e[0][_val = bind(&astree::assignment_direct, _val, _1)]); + e[2] = vars[_val = _1] >> ("+=" >> e[0][_val = bind(&astree::assignment_summation, _val, _1)] | + "-=" >> e[0][_val = bind(&astree::assignment_difference, _val, _1)]); + e[3] = vars[_val = _1] >> ("*=" >> e[0][_val = bind(&astree::assignment_product, _val, _1)] | + "/=" >> e[0][_val = bind(&astree::assignment_quotient, _val, _1)] | + "%=" >> e[0][_val = bind(&astree::assignment_remainder, _val, _1)]); + e[4] = vars[_val = _1] >> ("<<=" >> e[0][_val = bind(&astree::assignment_bitshift_left, _val, _1)] | + ">>=" >> e[0][_val = bind(&astree::assignment_bitshift_right, _val, _1)]); + e[5] = vars[_val = _1] >> ("&=" >> e[0][_val = bind(&astree::assignment_bitwise_and, _val, _1)] | + "^=" >> e[0][_val = bind(&astree::assignment_bitwise_xor, _val, _1)] | + "|=" >> e[0][_val = bind(&astree::assignment_bitwise_or, _val, _1)]); + e[6] = t[0][_val = _1] >> *('?' >> e[0] >> + ':' >> e[0])[_val = bind(&astree::ternary_conditional, _val, _1, _2)]; t[0] = t[1][_val = _1] >> *("||" >> t[1][_val = bind(&astree::binary_logical_or, _val, _1)]); t[1] = t[2][_val = _1] >> *("&&" >> t[2][_val = bind(&astree::binary_logical_and, _val, _1)]); t[2] = t[3][_val = _1] >> *('|' >> t[3][_val = bind(&astree::binary_bitwise_or, _val, _1)]); @@ -244,6 +352,11 @@ fctr = "0x" >> hex[_val = _1] | '0' >> oct[_val = _1] | uint_[_val = _1] | + "++" >> vars[_val = bind(&astree::prefix_increment, _1)] | + "--" >> vars[_val = bind(&astree::prefix_decrement, _1)] | + vars[_val = bind(&astree::postfix_increment, _1)] >> "++" | + vars[_val = bind(&astree::postfix_decrement, _1)] >> "--" | + vars[_val = _1] | '(' >> expr[_val = _1] >> ')' | '-' >> fctr[_val = bind(&astree::unary_negate, _1)] | '+' >> fctr[_val = _1] | @@ -254,11 +367,18 @@ template <typename T> struct calculator_astree_machine { - calculator_astree_machine() {} + std::map<std::string, T> &vars; + calculator_astree_machine(std::map<std::string, T> &vars) : vars(vars) {} T execute(const astree &ast) { if (ast.which() == astree::value_type || + ast.which() == astree::string_type || false) { + if (ast.which() == astree::string_type) { + if (vars.find(boost::get<std::string>(ast)) == vars.end()) + vars[boost::get<std::string>(ast)] = 0; + return vars[boost::get<std::string>(ast)]; + } return (T)boost::get<int>(ast); // ! } T lhs, rhs, c, a, b; @@ -269,6 +389,10 @@ case code_negate: return -rhs; case code_logical_not: return !rhs; case code_bitwise_not: return ~rhs; + case code_prefix_increment: return ++vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]; + case code_prefix_decrement: return --vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]; + case code_postfix_increment: return vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]++; + case code_postfix_decrement: return vars[boost::get<std::string>(boost::get<unary_op>(ast).rhs)]--; } break; case astree::binary_op_type: @@ -293,6 +417,18 @@ case code_bitwise_or: return lhs | rhs; case code_bitwise_xor: return lhs ^ rhs; case code_bitwise_and: return lhs & rhs; + case code_assignment_direct: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] = rhs); + case code_assignment_summation: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] += rhs); + case code_assignment_difference: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] -= rhs); + case code_assignment_product: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] *= rhs); + case code_assignment_quotient: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] /= rhs); + case code_assignment_remainder: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] %= rhs); + case code_assignment_bitshift_left: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] <<= rhs); + case code_assignment_bitshift_right: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] >>= rhs); + case code_assignment_bitwise_and: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] &= rhs); + case code_assignment_bitwise_xor: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] ^= rhs); + case code_assignment_bitwise_or: return (vars[boost::get<std::string>(boost::get<binary_op>(ast).lhs)] |= rhs); + case code_comma: return lhs, rhs; } break; case astree::ternary_op_type: @@ -316,13 +452,14 @@ typedef std::string::const_iterator iterator_type; typedef int value_type; client::calculator<iterator_type> calc; + std::map<std::string, value_type> vars; std::string str; client::astree result; value_type a; while (std::getline(std::cin, str)) { iterator_type it = str.begin(), end = str.end(); bool r = phrase_parse(it, end, calc, boost::spirit::ascii::space, result); - client::calculator_astree_machine<value_type> vmachine; + client::calculator_astree_machine<value_type> vmachine(vars); a = vmachine.execute(result); if (r && it == end) { std::cout << "succeeded:\t" << std::endl;
変数のサポートのために、std::map<std::string, value_type> vars
が導入され、クラス astree
の boost::variant
型のメンバ変数 expr
に std::string
が追加されていることがわかるだろう。