boost::spirit::qi を触ってみる
C++における文法解析ライブラリとしてboost::spiritというものがある。BNF記法に非常に近い見た目の(しかもちゃんと動く) c++のコードとして文法を書き下せるという、c++の限界に挑戦している感のあるライブラリである。マニュアルを読む(ほぼqiのところしか読んでないけど)のに大分時間をかけてしまったので備忘録を兼ねて記事にしてみる。
boost::spiritは大きく3つのモジュールに分かれていて、定義した文法に沿って文字列をデータに変換するqi、逆にデータから文字列をつくるkarma、また字句解析に特化したlexからなっている。今回はその中のqiを触ってみる。
BNF記法とspirit
BNF記法(あるいはEBNF記法)というのは、
group ::= '(' expression ')'
factor ::= integer | group
term ::= factor (('*' factor) | ('/' factor))*
expression ::= term (('+' term) | ('-' term))*というやつ*1。
boost::spiritを使うとこれをC++コードとして(!!)
group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term));
のように書ける。*が前に来てたりとかくっつけるのに >> を使ってたりするくらいで、ほぼそのまま。
もともといくつかの定義が組み込まれていて、例えば int_ はintを、double_ は double を受ける事ができる。
std::string input = "123, 456.789"; std::pair<int, double> p; qi::parse(input.begin(), input.end(), '(' >> qi::int_ >> ", " >> qi::double_ >> ')', // <- ここが定義 p);
とすると p.first に 123、 p.second に 456.789 が格納されるという具合。
単純な論理式: 文法の定義と rule の定義
今回は練習として、 (T v F) とか (F v (F v T)) みたいな論理式を与えると結果を T か F で返してくるものを作ってみた。
文法の定義は
constant ::= 'T' | 'F'
formula ::= constant | '(' formula 'v' formula ')' |'(' formula '^' formula ')'
としておく。括弧の付け方に曖昧さのない定義*2。
この定義の一行に相当するのをboost::spiritではruleといい、ruleをまとめたものをgrammarという。
上の定義の1行目は spirit では
constant = lit('T') | lit('F');
セマンティックアクションで値や処理を指定
読み込んだらboolとして値を得たい、というときにはセマンティックアクションというものを使う。[]演算子がオーバーロードされていて、この中に処理を書く。今の定義にセマンティックアクションを加えると次のようになる:
constant = lit('T')[_val = true] | lit('F')[_val = false];
ちょっと黒魔術めいてきたけれども、_valというのがパース結果のための変数にあたる。これはboost::lambdaカスタム仕様みたいなライブラリであるphoenixの一員。他にも例えばパーサが別の子パーサの組み合わせからなっている時に子パーサの結果を _1 とか _2 とかで受けるとかできる。phoenixの式でなくて関数ポインタとか関数オブジェクト、boost::lambdaの式なんかを与える事もできる。値を指定するのに限らず外の変数を書き換えたりとか色々可能。
rule/grammar の attribute
パース結果の型はどう扱われているのか気になるかもしれない。boost::qiではこの型をsynthesized attributeといっている。attributeというのは、qiのマニュアルを読む限りでは似たような型をまとめたものと思っていいと思う(例えばvector
qi::rule<Iterator, int(double)>
テンプレート引数の2番目がそれで、関数と同じような形式の宣言になっているのがわかると思う*4。今の constant は bool() という形の宣言をする事になる。
あと宣言としては、パース時に空白を適宜スキップしたいときはもう一つ引数が加わって
qi::rule<Iterator, int(double), qi::space_type>
*5
という形になる。grammarでも同じ。
2行目。
formula = (constant [_val = _1] |
('(' >> formula >> 'v' >> formula >> ')')[_val = _1 || _2] |
('(' >> formula >> '^' >> formula >> ')')[_val = _1 && _2]);
早速 _1、_2 を使っている。こうやってそれぞれ1つ目と2つ目のパーサの結果を受けて計算するという事ができる*6。
grammarの定義
この2つをまとめるのにgrammarというのを定義する事になる。手順としては、
- qi::grammar
- メンバ変数としてrule群を宣言
- コンストラクタでbase_typeを一番最初に来るruleで初期化する
- コンストラクタ内で各ruleを定義していく
という感じになる。
template<typename Iterator> struct bool_grammar : qi::grammar<Iterator, bool(), ascii::space_type>{ bool_grammar() : bool_grammar::base_type(formula){ // formulaから開始 using qi::lit; constant = (lit('T')[_val = true] | lit('F')[_val = false]); formula = (constant [_val = _1] | ('(' >> formula >> 'v' >> formula >> ')')[_val = _1 || _2] | ('(' >> formula >> '^' >> formula >> ')')[_val = _1 && _2]); } qi::rule<Iterator, bool(), ascii::space_type> constant, formula; };
使ってみる
こうして定義したgrammarを、phrase_parse (空白を読み飛ばす場合)なり parse (読み飛ばさない場合)なりに渡す事でパースを行う。
今回は空白を許容するためphrase_parseの方を使う。入力の範囲を表すイテレータ2つと パース用rule/grammar、読み飛ばすべき文字を表すrule/grammar を渡す。結局全体としては次のようになる:
#include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix.hpp> using namespace boost::spirit; using namespace boost; template<typename Iterator> struct bool_grammar : qi::grammar<Iterator, bool(), ascii::space_type>{ bool_grammar() : bool_grammar::base_type(formula){ // formulaから開始 using qi::lit; constant = (lit('T')[_val = true] | lit('F')[_val = false]); formula = (constant [_val = _1] | ('(' >> formula >> 'v' >> formula >> ')')[_val = _1 || _2] | ('(' >> formula >> '^' >> formula >> ')')[_val = _1 && _2]); } qi::rule<Iterator, bool(), ascii::space_type> constant, formula; }; #include <iostream> #include <string> using namespace std; int main(){ string buf; bool result; bool_grammar<string::const_iterator> grammar; while(getline(cin, buf)){ string::const_iterator iter = buf.begin(), end = buf.end(); bool success = qi::phrase_parse(iter, end, grammar, ascii::space, result); if(success && iter == end){ // パース成功かつ残り物がない cout << " => " << (result ? 'T' : 'F') << endl; }else{ cout << " => parse failed" << endl; } } return 0; }
コンパイルして実行すると入力待ちになり、論理式を入力すると都度パースして計算結果を表示する。ctrl+dで終了。
$ g++ -I/usr/local/include bool.cc -o bool $ ./bool T => T F => F abc => parse failed F v F => parse failed (F v F) => F (T ^ F) => F (T v F) => T (F v (F v T)) => T
定義してない単語を入れたり括弧の付け方が間違っているとちゃんとはじかれる。
強力さ、弱み
このように40行足らずで入力をパースしてブール演算をするプログラムが書ける。公式のチュートリアルを見るとxmlパーサなどもデータ構造などを含めてなかなかきれいに書けるのがわかって面白い。
上のコードだと読み飛ばしにspirit::asciiを使っているが、これはutf-8を想定していない(クラッシュする)ので、そういうのを読ませたい時は ascii::*7 となっているところを全部 standard_wide:: にするとよいようだ*8 *9。
というわけでとても面白いライブラリだけど、欠点として非常にコンパイル時間がかかること(この小さな例でもmac book pro retina 2012モデルで11秒弱かかる)、エラーメッセージが膨大になることがある。この辺との付き合い方については http://sssslide.com/www.slideshare.net/yak1ex/impractical-introduction-ofboostspiritqi-pdf の"蛇足"を見るとよいと思う。
link
let's boostの記事 http://www.kmonos.net/alang/boost/classes/spirit.html
マニュアル(英語) http://www.boost.org/doc/libs/1_55_0/libs/spirit/doc/html/index.html
*1:こういうように書けるものを文脈自由言語という。正規言語がオートマトンで受理出来るものなのに対して、正規言語はオートマトンにスタックを1つ加えたもので受理出来るものをいう
*2:曖昧さのある文法の時は、|がショートサーキット的に働くのに注意。つまりa|bでaにもbにも当てはまる場合bは試みられない。またしばらく後で失敗した時のバックトラック対象にもならないようだ。
*3:オーバーロードのおかげで左右かたっぽがruleやgrammarだったりするとlitは省略出来る。全部省略は出来ないあたりがc++の型推論の限界なのかもしれないが
*4:1番目は色々な入力をとれるようにテンプレートにしてある
*5:この宣言がない時はqi::parse、あるときは qi::phrase_parse を使う事になる ref: http://slashdot.jp/journal/524079/Boost-Spirit-Qi-の-rule-と-Skipper-の有無について http://d.hatena.ne.jp/sorayukinoyume/20121113/1352810975
*6:'('みたいなのも厳密にはパーサなのだが、synthesized attributeがUnusedというものになっているのでその結果はいなかったことになる
*7:正確には boost::spirit::ascii::
*8:http://sourceforge.net/mailarchive/message.php?msg_id=24449761 、 http://www.boost.org/doc/libs/1_55_0/libs/spirit/doc/html/spirit/qi/reference/char/char_class.html
*9:クラッシュしさえしなければいいのではなくパーサそのものもutf-8を想定したい場合はやったことないけど http://stackoverflow.com/questions/13679669/how-to-use-boostspirit-to-parse-utf-8 あたりを参考にすればいいのかも
