blog.livewing.net

C++で構文解析 Boost.Spirit.Qi #2

今回から、詳しい文法の定義方法を紹介します。

EBNF記法

コンピュータ言語の定義に使われるBNF(Backus-Naur form)を拡張したEBNF(Extended BNF)に近い書き方で文法を定義できるのがQiの特徴です。

例えば、EBNFで自然数(先頭が'0'でない1以上の数字列)を定義すると、

digit excluding zero ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
digit                ::= "0" | digit excluding zero
natural number       ::= digit excluding zero, digit*

といった感じになります(詳しくはググってください)。Qiではほぼこのまま(演算子が違ったりはするけど)文法を定義できます。おかげでC++書いている心地がしません。

>> 演算子

>>演算子を使用すると、「記号の連続」を表すことが出来ます。

qi::lit("<") >> qi::int_ >> qi::lit(">")

ここでのqi::lit("<")は、「<をパースするけれどパース結果を出さない」といった役割を持つパーサプリミティブです。数値を特定の記号で囲う、とかするときによく使います。

具体的な使用例は以下の通りです。

std::string str(" < 12345 > ");
auto itr = str.begin(), end = str.end();
int result;
bool success = qi::phrase_parse(itr, end, qi::lit("<") >> qi::int_ >> qi::lit(">"), qi::space, result);
if (success && itr == end) {
    std::cout << result << std::endl;
}

このコードの実行結果は以下の通りとなります。

12345

他にはこういった定義もよく使うような気がします。

qi::lit("value") >> qi::lit(":") >> qi::double_

ここでわざわざ"value"と":"に分けている理由は、qi::phrase_parse()関数を使用して空白を読み飛ばすようにすることで、"value"と":"の間に空白などが入っていてもパースできるようにするためです。

2つの値をパースする

例えば、>>演算子を使用して

qi::int_ >> qi::lit(",") >> qi::double_

とした場合、カンマ区切りのint型の値とdouble型の値2つ受け取るということになります。この時「パースした値の格納先(qi::parse()関数の最後の引数に指定する)の型」が変化します。まあint型の変数1個じゃ受け取れきれないので当然ですね。

>>演算子を使用してT型とU型の2つの値を受け取るとき、結果の型は

std::tuple<T, U> result;

に変化します。std::tupleは複数の値の組を表すクラスです(C++11より。詳しくはググってね)。

つまり、コード全体は

std::string str("12345, 67.89");
auto itr = str.begin(), end = str.end();
std::tuple<int, double> result;
bool success = qi::phrase_parse(itr, end, qi::int_ >> qi::lit(",") >> qi::double_, qi::space, result);
if (success && itr == end) {
    std::cout << std::get<0>(result) << std::endl; // std::get()でタプル内の要素を取得
    std::cout << std::get<1>(result) << std::endl;
}

になる…かと思いきやここで1つトラップがあります。std::tupleの値を結果として受ける場合は

#include <boost/fusion/include/std_tuple.hpp>

を書いておく必要があります。どうやらBoost.Fusionというライブラリを使う必要があるらしいですがQiを使うだけならそんなに詳しく知る必要は(多分)無いです。これをincludeする必要があることに気づくまで3時間くらいかかった気がする…

このコードの実行結果は以下の通りとなります。

12345
67.89

「演算子の使用による型の変化」は、後述する「パーサの属性 (Attribute)」で詳しく説明します。

* 演算子

*演算子を使用すると、「記号の0回以上の繰り返し」を表すことが出来ます。正規表現の*と同じです。

*qi::int_

*演算子を適用すると、結果の型はstd::vectorになります。

具体的な使用例は以下の通りです。

std::string str("12 34 56 78 90");
auto itr = str.begin(), end = str.end();
std::vector<int> result;
bool success = qi::phrase_parse(itr, end, *qi::int_, qi::space, result);
if (success && itr == end) {
    for (auto a : result)
        std::cout << a << std::endl;
}

このコードの実行結果は以下の通りとなります。

12
34
56
78
90

+ 演算子

+演算子を使用すると、「記号の1回以上の繰り返し」を表すことが出来ます。正規表現の+と同じです。

*演算子とほぼ同じなので詳細は省略。

% 演算子

%演算子を使用すると、「ある記号で区切られたリスト」を表すことが出来ます。

qi::int_ % qi::lit(",")

この例だと、カンマ区切りのintの値1個以上をパース出来ます。

%演算子を適用すると、結果の型はstd::vectorになります。

具体的な使用例は以下の通りです。

std::string str("12, 34, 56, 78, 90");
auto itr = str.begin(), end = str.end();
std::vector<int> result;
bool success = qi::phrase_parse(itr, end, qi::int_ % qi::lit(","), qi::space, result);
if (success && itr == end) {
    for (auto a : result)
        std::cout << a << std::endl;
}

このコードの実行結果は以下の通りとなります。

12
34
56
78
90

パーサの属性 (Attribute)

「属性」とかいう難しそうな言葉に惑わされてはいけません。要は「その文法定義でパースした結果生み出す値の型」のことです。

パーサプリミティブでは、例えばqi::int_の属性はint、qi::lit("hoge")の属性はUnused(使用されない)となります。

各種演算子を適用すると、属性も変化します。今回使用した演算子の属性の変化をまとめました。以下の表中のAとBは任意の属性を表します。「->」の右側が変化後の属性です。

演算子属性
a >> ba: A, b: B -> tuple<A, B>
a: A, b: Unused -> A
a: Unused, b: B -> B
a: Unused, b: Unused -> Unused

a: A, b: A -> vector<A>
a: vector<A>, b: A -> vector<A>
a: A, b: vector<A> -> vector<A>
a: vector<A>, b: vector<A> -> vector<A>
*aa: A -> vector<A>
a: Unused -> Unused
+aa: A -> vector<A>
a: Unused -> Unused
a % ba: A, b: B -> vector<A>
a: Unused, b: B -> Unused

上記の表より、%演算子は以下のものと同義になります。

qi::int_ % qi::lit(",")                 // % 演算子は…
qi::int_ >> *(qi::lit(",") >> qi::int_) // このようにも表現できる

まず、qi::lit(",")がUnused、qi::int_がintなので、qi::lit(",") >> qi::int_の属性はintになります。それ全体に*演算子を適用しているので、*(qi::lit(",") >> qi::int_)の属性はvector<int>になります。さらに、属性intのパーサが>>演算子によって連続しているので、qi::int_ >> *(qi::lit(",") >> qi::int_)の属性はvector<int>になります。

次回

まだまだQiはたくさんの機能があります。がんばる。