boost::spirit でpython(のサブセット)
前エントリーで書いたboost::spirit を使って、 pythonのサブセットを作った。
もう少し言うと、python風の数式をパースして構文木を返すものを作った。
boost::variantとboost::recursive_wrapperを使って、なるべく構文木を再帰的なデータ構造として素直に扱うのがboost::spiritを使うコツっぽい。
主に http://www.aihara.co.jp/~taiji/tp/?id=23 を参考にしたというか骨組みはそのまま。
pythonの文法はマニュアルに記載がある*1ので、それを単純にしたものを実装した。タプルとか代入とかはなくて、四則演算とブール演算のみ。あと左再帰というのにならないように少し修正が要る。
またpythonは 100 < x < 200 < y < 300みたいな記法ができるので、それをちょっと別立ての定義にしている。pythonのマニュアルによればこれは各部分のAND (つまり 100 < x && x < 200 && 200 < y && y < 300)として扱われるので評価の段ではそういう扱いをしている。
そもそもこのコードはデータのフィルタリング用のプログラムに組み込むのを目的に作っている。フィルタリング条件を変更するときにわざわざソースを書き換えて再コンパイルとやってるとややこしいことになるので、python風の設定ファイルを読み込んで関数オブジェクトを作れるようにしてやろうという魂胆*2。
今回はちょっと簡略化して
struct event_mock{ int event_number; double data[4]; };
というデータを取ってdouble値を返す関数オブジェクトを作るようになっている。作ると言ってもbindを使ってやや強引に。もっとちゃんとした方法もあるのかもしれないが*3、とりあえず動く事を優先した。
とりあえず以下のコードでは、 データの平均を表す AVR や 合計を表す TOTAL というシンボルを定義して、さらに適当に
event_mock e[3] = {{1, { 123, 0, 0, 456.789}}, {2, { 0, 100, 200, 300}}, {3, { 200, 400, 800, 1600}}};
というデータを用意しておいて、入力された式をそれぞれのデータに対し適用して結果を返すようになっている。
TOTAL => parse success e[0]: 579.789 e[1]: 600 e[2]: 3000 AVR => parse success e[0]: 144.947 e[1]: 150 e[2]: 750 TOTAL > 1000 => parse success e[0]: 0 e[1]: 0 e[2]: 1 130 < AVR <= 150 => parse success e[0]: 1 e[1]: 1 e[2]: 0 (1+2)*3 => parse success e[0]: 9 e[1]: 9 e[2]: 9 98 + 76 < 54 * 32 and 1 and not 0 => parse success e[0]: 1 e[1]: 1 e[2]: 1
という感じ。比較の結果はTrue/Falseがそれぞれ1と0で返ってくる。最後の方データに関係ないけど、こういう四則演算その他もできますということで。
演算子は + - * / and or not >= > <= < が使え、括弧でくくるのも可。あと内部的には全部doubleなので 2/3 とか書いても切り捨てが起こらない。
#include <iostream> #include <iomanip> #include <string> #include <vector> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix.hpp> #include <boost/variant.hpp> #include <boost/function.hpp> // 調べたいデータの型 struct event_mock{ int event_number; double data[4]; }; // データに対する関数 double event_avr(const event_mock& e){ double sum = 0; for(int i=0;i<4;++i){ sum+= e.data[i]; } return sum/4.0; } double total(const event_mock& e){ double result = 0; for(int i=0;i<4;++i) result += e.data[i]; return result; } double event_no(const event_mock& e){ return e.event_number; } // 関数の型名を付けておく。boost::functionは便利 typedef boost::function<double(const event_mock&)> event_fun; // 構文木の定義 namespace client{ struct nullary_op {}; struct unary_op; struct binary_op; struct anded_terms; // 構文木 struct astree{ typedef boost::variant< boost::recursive_wrapper<nullary_op>, boost::recursive_wrapper<unary_op>, boost::recursive_wrapper<binary_op>, boost::recursive_wrapper<anded_terms>, double, bool, event_fun > type; // enumを上と同じ順に定義しておくとswitchで使えて便利 enum types_code{ nullary_op_type, unary_op_type, binary_op_type, anded_terms_type, double_type, bool_type, event_fun_type, }; typedef type::types types; type expr; int which() const { return expr.which(); } astree() : expr(nullary_op()) {} astree(unary_op const &expr) : expr(expr) {} astree(binary_op const &expr) : expr(expr) {} astree(anded_terms const &expr) : expr(expr) {} astree(double expr) : expr(expr) {} astree(type const &expr) : expr(expr) {} }; } namespace client{ enum nullary_opcode{ }; enum unary_opcode{ kUnary_Neg = 1, kUnary_Not, }; enum binary_opcode{ kBinary_Add = 1, kBinary_Sub, kBinary_Mul, kBinary_Div, kBinary_Or, kBinary_And, }; enum anded_terms_opcode{ kAnded_GT = 1, kAnded_GE, kAnded_LT, kAnded_LE, }; } namespace client { struct unary_op{ unary_op() {} unary_op(unary_opcode op, astree const &rhs) : op(op), rhs(rhs) {} unary_opcode op; astree rhs; }; 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; }; // a < b < c みたいな式用。a を initial に、その後ろを // [(<, b), (<, c)] という形のvectorとして ops に保持しておく typedef std::pair<anded_terms_opcode, astree> opcode_tree_pair; struct anded_terms{ anded_terms() {} anded_terms(astree initial) : initial(initial) {} anded_terms(astree initial, std::vector<opcode_tree_pair> const &ops) : initial(initial), ops(ops) {} astree initial; std::vector<opcode_tree_pair> ops; }; } // 文法の定義 namespace client { namespace qi = boost::spirit::qi; namespace ascii = boost::spirit::ascii; template<typename Iterator> struct pymodoki_grammar : qi::grammar<Iterator, astree(), ascii::space_type> { qi::rule<Iterator, astree(), ascii::space_type> expr, t[6], atom; qi::rule<Iterator, astree(), ascii::space_type, qi::locals<astree, std::vector<opcode_tree_pair> > > comp_impl; qi::symbols<char, anded_terms_opcode> comparator_symbols; qi::symbols<char, event_fun> defined_symbols; pymodoki_grammar() : pymodoki_grammar::base_type(expr){ using qi::_val; using qi::_1; using qi::_2; using qi::_a; using qi::_b; using qi::double_; using qi::bool_; using qi::eps; using boost::phoenix::construct; using boost::phoenix::push_back; using boost::phoenix::bind; using boost::phoenix::val; expr = t[0][_val = _1] >> *("or" >> t[0][_val = construct<binary_op>(kBinary_Or, _val, _1)]); t[0] = t[1][_val = _1] >> *("and" >> t[1][_val = construct<binary_op>(kBinary_And, _val, _1)]); t[1] = t[2][_val = _1] | "not" >> t[2][_val = construct<unary_op>(kUnary_Not, _1)]; t[2] %= comp_impl | t[3]; comp_impl = (t[3][_a = _1] >> +(comparator_symbols >> t[3]) [push_back(_b, construct<opcode_tree_pair> (_1,_2))] >> eps[_val = construct<anded_terms>(_a, _b)]); t[3] = t[4][_val = _1] >> *("+" >> t[4][_val = construct<binary_op>(kBinary_Add, _val, _1)] | "-" >> t[4][_val = construct<binary_op>(kBinary_Sub, _val, _1)]); t[4] = t[5][_val = _1] >> *('*' >> t[5][_val = construct<binary_op>(kBinary_Mul, _val, _1)] | '/' >> t[5][_val = construct<binary_op>(kBinary_Div, _val, _1)]); t[5] = '+' >> atom[_val = _1] | '-' >> atom[_val = construct<unary_op>(kUnary_Neg, _1)] | atom[_val = _1]; atom %= '(' >> expr >> ')' | defined_symbols | double_ | bool_; comparator_symbols.add ("<=",kAnded_LE) (">=",kAnded_GE) ("<", kAnded_LT) (">", kAnded_GT); defined_symbols.add // 各データに対して定まる値 ("NO", &event_no) ("TOTAL", &total) ("AVR", &event_avr) // 手抜きでただの定数もこちらに含めてしまう ("mm" , val(1e-1)) ("cm" , val(1.0)) ("ns" , val(1.0)) ("us" , val(1e3)) ("ms" , val(1e6)) ("s" , val(1e9)); } }; // 与えられたイベントを元に構文木から結果を計算する template <typename T> struct astree_evaluator { T execute(const astree &ast, const event_mock &e){ T lhs, rhs; std::vector<std::pair<anded_terms_opcode, astree> > ops; switch(static_cast<astree::types_code>(ast.which())){ case astree::double_type: return boost::get<double>(ast.expr); case astree::bool_type: return boost::get<bool>(ast.expr); case astree::unary_op_type: rhs = execute(boost::get<unary_op>(ast.expr).rhs, e); switch(boost::get<unary_op>(ast.expr).op) { case kUnary_Not: return !rhs; case kUnary_Neg: return -rhs; } case astree::binary_op_type: rhs = execute(boost::get<binary_op>(ast.expr).rhs, e); lhs = execute(boost::get<binary_op>(ast.expr).lhs, e); switch(boost::get<binary_op>(ast.expr).op) { case kBinary_Add: return lhs + rhs; case kBinary_Sub: return lhs - rhs; case kBinary_Mul: return lhs * rhs; case kBinary_Div: return lhs / rhs; case kBinary_And: return lhs && rhs; case kBinary_Or : return lhs || rhs; } case astree::anded_terms_type: lhs = execute(boost::get<anded_terms>(ast.expr).initial, e); ops = boost::get<anded_terms>(ast.expr).ops; for(int i=0;i<ops.size();++i){ rhs = execute(ops[i].second, e); switch(ops[i].first){ case kAnded_LE: if(!(lhs <= rhs)){return false;}else{break;} case kAnded_LT: if(!(lhs < rhs)){return false;}else{break;} case kAnded_GE: if(!(lhs >= rhs)){return false;}else{break;} case kAnded_GT: if(!(lhs > rhs)){return false;}else{break;} } lhs = rhs; } return true; case astree::event_fun_type: // 引数の e はここでだけ使っている return (boost::get<event_fun>(ast.expr))(e); case astree::nullary_op_type: std::cerr << "not implemented" << std::endl; return 0; } } }; } int main(int argc, char **argv){ typedef std::string::const_iterator iterator_type; client::pymodoki_grammar<iterator_type> g; std::string str; client::astree result; event_mock e[3] = {{1, { 123, 0, 0, 456.789}}, {2, { 0, 100, 200, 300}}, {3, { 200, 400, 800, 1600}}}; while(std::getline(std::cin, str)){ iterator_type it = str.begin(), end = str.end(); bool r = phrase_parse(it, end, g, boost::spirit::ascii::space, result); client::astree_evaluator<double> evaluator; event_fun func = bind(&client::astree_evaluator<double>::execute, evaluator, result, boost::phoenix::arg_names::_1); if(r && it == end){ std::cout << " => parse success" << std::endl; std::cout << " e[0]: " << func(e[0]) << std::endl; std::cout << " e[1]: " << func(e[1]) << std::endl; std::cout << " e[2]: " << func(e[2]) << std::endl; }else{ std::cout << " => parse failed: " <<std::string(it, end) << std::endl; } } }
a %= bというのは a = b[_val = _1] の省略記法。
最後にexecuteメソッドをbindすることで関数オブジェクトとして扱ってしまう。
コンパイル時間はうちの環境で g++ 4.7 で 13秒くらい、clang-500.2.79 *4で 32秒くらい。
あとclangの方は -ftemplate-depth=512 とか指定しないと instantiation exceeded maximum depth of 128 と言われてコンパイルできなかった。
また間の空白に着いてはphrase_parseを使って手抜きで実装しているが、この場合 defined_symbol に 'no' という名前のシンボルが合ったりすると not の no の部分が食べられておかしな事になるので本当はそこもやったほうがいいが、今回はかぶらないようなシンボル名を取る事で逃げた。
