Impractical Introduction of Boost Spirit Qi [PDF]

非実用的 Boost Spirit Qi 入門

2011/5/14 Boost 勉強会名古屋
@yak_ex / 新康孝

自己紹介
• 氏名：新康孝 (あたらしやすたか)
• Twitter ID: yak_ex
• Web: http://yak3.myhome.cx:8080/junks

• C++ / Perl が主戦場
• 現在、仕事でコードに触れていないので
競技プログラミング（TopCoder、Codeforces）で
潤い補充
• 闇の軍団に憧れるただの C++ 好き
– 初めて Spirit 使った経験を元に発表

Spirit との馴れ初め
• PDF 用 Susie プラグインがライセンスの
関係でずっと公開停止になってる
→ライセンスの問題がない PDF Susie プラグインを
作ろう！
→最低限、画像だけ抜いて来られればいいや
→PDF フォーマットは割とテキストベース
→構文解析が必要

• せっかくだから俺はこの Spirit を選ぶぜ！
→ Spirit を初めて使用した経験を元に発表
※プラグインは axpdf--.spi β版として公開中

Boost Spirit とは？
• Boost 公式サイトの記述：
– LL parser framework represents parsers
directly as EBNF grammars in inlined C++
– 構文解析器を、C++ 内で直接 EBNF 文法を書く
事で作れるフレームワーク

• はぁ？

• 世間での評判
– 変態なことで有名なBoost::Spiritを…
http://zo3kirin3.net/?p=82

– 変態的と名高い(?) Boost.Spirit で解析。
http://ja.doukaku.org/comment/6518/

– …同じく変態（褒め言葉）と名高いboost::spirit を
使って実装することにした。
http://d.hatena.ne.jp/Hossy/20080407

結論： Boost Spirit ＝変態

へんたい

これが Spirit の力だ！
• // #include と using namespace 省略
int main(void){ 型と出力変数定義
typedef std::map<std::string, std::string> Config;
Config config;
入力定義
std::string input("Boost.Spirit = extraordinary ¥n C++er = ...");
phrase_parse(input.begin(), input.end(),
*(lexeme[*(graph - char_('='))] >> lit('=') >> lexeme[*graph]),
space, config);
BOOST_FOREACH(Config::value_type &kv, config) {
std::cout << kv.first << '=' << kv.second << std::endl; 出力
}
}
• 出力
Boost.Spirit=extraordinary <key>=<value>が std::map に突っ込まれる
C++er=...

高度に発達したC++は
魔法と区別がつかない
アーサー・C++・クラーク

• Boost ライブラリの中でも最高峰の一つ（超私見）
– Optional, Variant, Fusion, Proto, Phoenix, MPL 等、
他の Boost ライブラリをふんだんに使用
– C++ でできることのベンチマーク的位置づけ
• どんなものか知っとくだけでも意味はあるかと
• Qi, Karma, Lex で構成
– Qi: 構文解析（文字列→データ構造） ←今回のテーマ
– Karma：出力（データ構造→文字列）
– Lex：字句解析（文字列→トークン列）

Spirit Qi 入門

Tutorial
嫁

アジェンダ
• 概要紹介
– 限定された使い方のみ
• 拡張性
– Directive を自作してみる
– Customization point
• 蛇足

• Boost 公式サイト：
– LL parser framework represents parsers
directly as EBNF grammars in inlined C++
– 構文解析器を、C++ 内で直接 EBNF 文法を書く
事で作れるフレームワーク

構文解析と EBNF
• 構文解析（文字列→データ構造）
– あるルールに則った文字列を解析
例：式
1 0 + 2 0 * ( 3 0 - 4 0 )

+
*
-
10 20 30 40

構文解析と EBNF
• EBNF = Extended Backus Normal Form
– 「あるルール」＝文法の表記方法
• 選択 |
• 0回以上の繰り返し *、1回以上の繰り返し +
– 例：式
• <Expression> ::= <Term> ((„+‟ | „-‟ ) <Term>)*
• <Term> ::= <Factor> ((„*‟ | „/‟ ) <Factor>)*
• <Factor> ::= <Integer> | „(„ <Expression> „)‟

Boost Spirit の rule
• EBNF による式の表現
– <Expression> ::= <Term> ((„+‟ | „-‟ ) <Term>)*
– <Term> ::= <Factor> ((„*‟ | „/‟ ) <Factor>)*
– <Factor> ::= <Integer> | „(„ <Expression> „)‟

• Spirit での式の表現 C++ の式として有効
– expr = term >> *(char_(“+-”) >> term);
– term = factor >> *(char_(“*/”) >> factor);
– factor = int_ | lit(„(„) >> expr >> lit(„)‟);

• 構成要素
– Parser（基本要素）
– Directive（修飾）
– Operator（結合）

• Parser（基本要素）
char_ 任意の1文字を読む
char_(„a‟, „b‟) a～bの範囲の1文字を読む
char_(“abc”) abc いずれか1文字を読む
int_ 整数値を読む
lit(„a‟) a 1文字を読む
lit(“abc”) 文字列 abc を読む
graph isgraph() が true な1文字を読む
etc.

• Directive (修飾：Parser の挙動を変える)
lexeme[p] p 先頭で空白をスキップ、p 内部
では空白をスキップしない
no_case[p] p 内部で大文字、小文字を区別
しない
repeat(N)[p] p の N 回の繰り返し
repeat(N,M)[p] p の N～M 回の繰り返し
repeat(N,inf)[p] p の N 回以上の繰り返し

etc.

• Operator (結合)
a >> b 連接（普通に繋げる）
a|b 選択（a あるいは b）
*a p の 0 回以上の繰り返し
+a p の 1 回以上の繰り返し
-a p が 0 or 1 回
a-b b でない a
a%b b で区切られた a の繰り返し
etc.

へんたい

これが Spirit の力だ！
int main(void){
Config config;
std::string input("Boost.Spirit = extraordinary ¥n C++er = ...");
*(lexeme[*(graph - char_('='))] >> lit('=') >> lexeme[*graph]),
space, config);
std::cout << kv.first << '=' << kv.second << std::endl;
}
}
• 出力
Boost.Spirit=extraordinary <key>=<value>が std::map に突っ込まれる
C++er=...

• *( 0回以上の繰り返し
lexeme[ 内部スキップなし
*( 0回以上の繰り返し
graph - char_('=') = 以外の表示文字
)]
>> lit('=') =
>> lexeme[ 内部スキップなし
*graph 表示文字の 0 回以上の
]) 繰り返し

<key>=<value>の繰り返し

で、出力は？
• Parser には「属性」があってその属性型の値を返す
– int_ → int / char_ → char
• 修飾、結合されたものは？
→Fusion シーケンス or STL コンテナが属性になる
– char_ >> int_ >> double_
→ tuple<char, int, double>
– *int_ → vector<int>
– int_ >> int_ は？ → どっちでもOK

※詳細は「Quick Reference」の「Compound Attribute Rules」を参照

※tuple, vector は代表で Fusion シーケンス / コンテナなら何でも良い

で、出力は？
• pair はアダプタによって Fusion シーケンスと見なせる
(ヘッダの #include が必要)
• 構造体も Fusion シーケンスと見なせる
– BOOST_FUSION_ADAPT_STRUCT
– BOOST_FUSION_DEFINE_STRUCT で
構造体定義とADAPT を一気にできる

BOOST_FUSION_DEFINE_STRUCT(
(yak)(pdf), 構造体 yak::pdf::indirect_ref が
indirect_ref, tuple<int, int> 相当になる
(int, number)
(int, generation)
)
※Fusion は前回勉強会の cpp_akira さんの発表も参照

出力先
Ruleの属性
*(lexeme[*(graph - char_('='))] >> lit('=') >> lexeme[*graph])
• lexeme は skip の仕方が変わるだけで属性は変化しないので消す
*(*(graph - char_('=')) >> lit('=') >> *graph)
→ lit は無属性(unused_type)、graph, char_ はchar、pa – pb は pa の属性
*(*char >> *char)
→ vector<tuple<vector<char>, vector<char> > > or
vector<vector<char> >

代入先 ※vector<char> と
• std::map<std::string, std::string> string は互換
→ std::pair<std::string, std::string> のコンテナ →これらも互換
→ std::string, std::string の Fusion シーケンスのコンテナ

まだ Spirit の
Spirit.Qi 入門
変態フェイズは
終了してないぜ！！

拡張性
• Spirit （の変態性）を支える重要な要素
– 後から拡張できるような仕掛けがしてある
• Proto を使っているので自前のコンポーネント（Parser
等）を作成できる
→Directive の自作
• 処理にフックが用意してある
→Customization point

Boost Spirit の rule （再掲）
• Directive (修飾：Parser の挙動を変える)
lexeme[p] p 先頭で空白をスキップ、p 内部
では空白をスキップしない
no_case[p] p 内部で大文字、小文字を区別
しない
repeat(N)[p] p の N 回の繰り返し
repeat(N,M)[p] p の N～M 回の繰り返し
repeat(N,inf)[p] p の N 回以上の繰り返し

etc.

Directive の自作
• Parser の自作は boost-spirit.com に記事有り
http://bit.ly/ikdvQt
• 作る物： delimited(delimiter)[parser]
– 例： delimited(std::string(“endstream”))[char_]
endstream という文字列にぶつかるまで char を読
み出す
– せっかくなので char 非限定で作成
• std::vector<int> delim(2, -1);
delimited(delim)[int_]
で -1 -1 にぶつかるまで int を読み出す

Directive の自作
• 自作コンポーネントの要素
– 終端記号の宣言
– Parser 本体の定義
• 属性の型
• 実際の解析処理
– Parser generator の定義(rule → Parser の変換)
– 有効化
• コンポーネント自身
• Semantic action ※今回 semantic action には全く
触れませんので Tutorial 参照

Directive の自作
• 終端記号の宣言

namespace mine {
BOOST_SPIRIT_TERMINAL_EX(delimited)
}

Directive の自作 delimited(delimiter)[parser]
• Parser 本体 ※Directive 内部の
namespace mine { Parser の型

// 内部 parser が 1 つの parser 型を定義 (CRTP を利用)
template<typename Subject, typename Delimiter>
struct delimited_parser
: boost::spirit::qi::unary_parser<delimited_parser<Subject, Delimiter> > {
// メンバテンプレートクラス attribute を定義（type が属性の型）
template<typename Context, typename Iterator>
struct attribute {
typedef typename boost::spirit::traits::build_std_vector<
typename boost::spirit::traits::attribute_of<Subject, Context, Iterator>::type
>::type type;
};
// コンストラクタ（parser generator から呼ばれる）
delimited_parser(Subject const &subject, Delimiter const &delimiter)
: subject(subject), delimiter(delimiter) {}

Directive の自作
• Parser 本体
namespace mine { ※属性

// 実際の解析ルーチン
template<typename Iterator, typename Context, typename Skipper, typename Attribute>
bool parse(Iterator &first, Iterator const &last,
Context &context, Skipper const &skipper, Attribute &attribute) const {
// 詳細略 subject.parse() を使ってKMP法的に処理。
// 汎用的にやるならコンテナ操作には traits を使う。
// traits::container_value<Attribute>::type
// traits::container_iterator<const Delimiter>::type
// traits::begin(delimiter);
}
template <typename Context>
boost::spirit::info what(Context& context) const {
return boost::spirit::info(“delimited”, subject.what(context));
}
Subject subject; // Directive 内部のパーサー保持用
Delimiter delimiter; // デリミタ保持用
};

Directive の自作 delimited(delimiter)[parser]
• Parser generator の定義(rule → Parser の変換)
Directive の引数の型：
namespace boost { namespace spirit { namespace qi { Delimiter 1つ
template <typename Delimiter, typename Subject, typename Modifiers>
struct make_directive<
terminal_ex<mine::tag::delimited,
fusion::vector1<Delimiter> >, Subject, Modifiers> {
// Parser の型
typedef mine::delimited_parser<Subject, Delimiter> result_type;
// Parser を返す operator()
template <typename Terminal>
result_type operator()
(Terminal const& term, Subject const& subject, unused_type) const {
return result_type(subject, fusion::at_c<0>(term.args));
}
}; Parser の
引数の 0 番目要素コンストラクタ呼び出し
}}}

Directive の自作
• 有効化(Proto に認識させる）
namespace boost { namespace spirit {
// 通常用
template<typename Delimiter>
struct use_directive<qi::domain,
terminal_ex<mine::tag::delimited,
fusion::vector1<Delimiter> > > : mpl::true_ {};
// Phoenix (Lambda みたいなもの)用
template<>
struct use_lazy_directive<qi::domain,
mine::tag::delimited, 1 // arity
> : mpl::true_ {};

Directive の自作
int main(void){
Config config; ※入力を微妙に変更
std::string input("Boost.Spirit= extraordinary ¥n C++er= ...");
*(lexeme[delimited(std::string(“=“))[graph]] >> lexeme[*graph]),
space, config);
std::cout << kv.first << '=' << kv.second << std::endl;
}
}
• 出力
Boost.Spirit=extraordinary
C++er=...

代替手段
• 引数(Inherit attribute)付きルールを定義
属性引数の型
rule<Iterator, std::string(std::string)> delimited;
delimited = *(graph_ - _r1) >> omit[_r1];
引数値を捨てる引数
• 使い方
*(lexeme[delimited(“=“)] >> lexeme[*graph]),
space, config);

非実用的
入門
※最悪計算量的にはO(nm) v.s. O(n+m)

Customization point
• いちいち Parser とか Directive とか
作ってらんないけど挙動をカスタマイズしたい

→それ、Spirit ならできるよ！

→traits を特殊化することで挙動を変更

Customization point
• boost::spirit::traits 以下に用意されている。
SFINAE 用の Enabler は省略

– is_container<Container> >> 系用
• 関連： container_value<Container> etc.
– handles_container<Component, Attr> >> 系用
– transform_attribute<Exposed, Transformed, Domain> rule 系用
– assign_to_attribute_from_iterators<Attr, Iterator> 汎用
– assign_to_attribute_from_value<Attr, T> 汎用
– assign_to_container_from_value<Attr, T> 汎用
– push_back_container<Container, Attr> 繰返系用
– clear_value<Attr> 繰返系用
– etc.

– create_parser<T> auto_用
cf. http://slashdot.jp/~Yak!/journal/525693

Customization point の関係
例） Foo >> *Bar の結果の戻し先として型 Qux の変数 qux が渡された場合
※ Foo >> *Bar の属性が Qux 型であるとは限らない！
※ 大枠だけ図示、::type や ::call も省略
true true
is_container<Qux> handles_container<Foo> qux ← Foo 読み出し
false
container_value<Qux>::type foo_temp;

foo_temp ← Foo 読み出し
push_back_container<Qux,Foo_temp>(qux, foo_temp);

handles_container<*Bar> ※ * ならデフォルト true
true false なら↑と同様の処理

qux ← *Bar 読み出し clear_value<Bar>
push_back_container<Qux,Bar_attr>
を内部で利用

Customization point の関係
例） Foo >> *Bar の結果の戻し先として型 Qux の変数 qux が渡された場合
※ Foo >> *Bar の属性が Qux 型であるとは限らない！
※ 大枠だけ図示、::type や ::call も省略
false true
is_container<Qux> is_container<QA> 前ページと同様の処理
Qux は 2 要素の false
Fusion シーケンス
tuple<QA, QB>とする Foo は何？
他 rule や attr_cast

Foo_attr foo_temp; transform_attribute<QA, Foo_attr>::type foo_temp =
transform_attribute<QA, Foo_attr>::pre(qa);
foo_temp ← Foo 読み出し
assign_to(foo_temp, qa); foo_temp ← Foo 読み出し
※内部で assign_to_* 族 transform_attribute<QA, Foo_attr>::post(qa, foo_temp);
を使用 ※デフォルトは内部で assign_to を使用

QB と *Bar の属性について上と同様の処理

Spirit Qi とうまく付き合うために
• コンパイル時間が Boost!!!
→コーヒーでも飲んで優雅に待つといいよ！
※axpdf--.spi だとフルビルドに約 10 分

→Spirit 関連部分を分離して文法が変わらない
限り再コンパイル不要にする
– Parser はあくまで parser に徹して
構文解析結果に対する処理は別に分けるとか

• エラーメッセージ量が Boost!!!
→例： 3.3MB

見えてる範囲

20%縮小表示

画像補正しないと
薄くて文字が
分からないレベル

→例： 3.3MB
• テンプレートのインスタンス化情報がほとんど
– まずは error で検索

error で検索

ココ

20%縮小表示

→例： 3.3MB
• テンプレートのインスタンス化情報がほとんど
– まずは error で検索
– 後はどこが真因かインスタンス化情報を遡る…前に
– 一度エラー箇所を見てみるといいことがあるかも

• ケース1. static_assert
– エラーメッセージ

spirit7.cpp:30: instantiated from here
/usr/local/include/boost/spirit/home/qi/nonterminal/gra
mmar.hpp:75: error: no matching function for call to
„assertion_failed(mpl_::failed************
(boost::spirit::qi::grammar<Iterator, T1, T2, T3,
T4>::grammar(const boost::spirit::qi::rule<Iterator_,
T1_, T2_, T3_, T4_>&, const std::string&) [何か一
杯]::incompatible_start_rule::************)(何か一杯))‟

• ケース2. コメント
– エラーメッセージ

spirit7.cpp:39: instantiated from here
/usr/local/include/boost/spirit/home/qi/nonterminal/rule.hpp:277:
error: no match for call to „何か一杯’

– /usr/local/include/boost/spirit/home/qi/nonterminal/rule.hpp

// If you are seeing a compilation error here stating that the
// forth parameter can't be converted to a required target type
// then you are probably trying to use a rule or a grammar with
// an incompatible skipper type.
if (f(first, last, context, skipper)) 277行目

• 先生！コンパイル通ったけど思った通りに
動きません！
→プログラムは思った通りに動かない。
書いたとおりに動く。

→debug(rule); を使うと構文解析の様子がトレース
できる
http://boost-spirit.com/home/articles/doc-
addendum/debugging/
– 属性に operator<< が必要

まとめ

•Spirit は変態
真面目に Spirit やりたい人は

• Tutorial を読みながら一通り実行する
• boost-spirit.com の記事を読む
• 随時 Quick Reference を参照する

ご静聴ありがとうございました

Impractical Introduction of Boost Spirit Qi [PDF]

Recommended

Recommended

More Related Content

Recently uploaded

Recently uploaded (9)

Featured

Featured (20)

Impractical Introduction of Boost Spirit Qi [PDF]