読者です 読者をやめる 読者になる 読者になる

ボレロ村上 - ENiyGmaA Code

中3女子です。

Boost.Spirit.Qi によるコードからみる雑多な解説

Spirit.Qi は Boost の構文解析ライブラリである。
演算子オーバーロードにより、EBNF 記法に近い書き方で、C++ のコードとして構文定義を書くことができる。


Spirit V2 からは、Boost.Fusion のタプル等と強力な連携がなされ、
解析結果をタプルやコンテナに格納する処理をより簡潔に明確に書けるようになった。


この記事では、Boost.Spirit.Qi を使ったコードから、その雑多な解説を試みてみようと思う。


VC9 + Boost 1.46.1 で動作を確認している。

コード


下記は、FTP プロトコルにおけるサーバ側のレスポンスを解析する構文解析クラス ftp_response のコードである。


なお、自分は boost::spirit::qi:: などの名前空間を常に全部書く方針で、元々のコードもそうだったのだが、
ここでは可読性のため単に qi:: に置換している。


そのため、このコードをそのままコンパイルするためには

namespace qi = boost::spirit::qi;

などと付けくわえる必要があることに留意されたし。

    • sprig/parser/ftp_response.hpp
#ifndef SPRIG_PARSER_FTP_RESPONSE_HPP
#define SPRIG_PARSER_FTP_RESPONSE_HPP

#include <boost/mpl/identity.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/fusion/include/value_at.hpp>

namespace sprig {
    namespace parser {
        namespace ftp_response_impl {
            //
            // locals_of
            //
            template<typename Tuple>
            struct locals_of
                : public boost::mpl::identity<
                    qi::locals<
                        typename boost::remove_reference<
                            typename boost::fusion::result_of::value_at_c<Tuple, 0>::type
                        >::type
                    >
                >
            {};
        }    // namespace ftp_response_impl
        //
        // ftp_response
        //
        template<
            typename Iterator,
            typename Tuple
        >
        class ftp_response
            : public qi::grammar<
                Iterator,
                Tuple (),
                typename ftp_response_impl::locals_of<Tuple>::type
            >
        {
        public:
            typedef Iterator iterator_type;
            typedef Tuple tuple_type;
            typedef typename boost::remove_reference<
                typename boost::fusion::result_of::value_at_c<tuple_type, 0>::type
            >::type status_code_type;
            typedef typename boost::remove_reference<
                typename boost::fusion::result_of::value_at_c<tuple_type, 2>::type
            >::type message_type;
        private:
            qi::rule<iterator_type, tuple_type (), typename ftp_response_impl::locals_of<Tuple>::type> response_;
            qi::rule<iterator_type, status_code_type ()> status_code_;
            qi::rule<iterator_type, message_type ()> message_;
        public:
            explicit ftp_response(bool including_crlf = true)
                : ftp_response::base_type(response_)
            {
                response_ %= status_code_[qi::_a = qi::_1]
                    >> -(
                        '-' >> (message_ % !(qi::lit(qi::_a) >> ' '))
                        >> qi::lit(qi::_a) >> &qi::lit(' ')
                        )
                    >> ' ' >> message_
                    ;
                status_code_ = qi::raw[
                    qi::digit >> qi::digit >> qi::digit
                    ];
                if (including_crlf) {
                    message_ = qi::raw[
                        *(qi::char_ - qi::lit("\r\n"))
                        >> qi::lit("\r\n")
                        ];
                } else {
                    message_ = qi::raw[
                        *(qi::char_ - qi::lit("\r\n"))
                        ]
                        >> qi::lit("\r\n")
                        ;
                }
            }
        };
    }    // namespace parser
}    // namespace sprig

#endif     // #ifndef SPRIG_PARSER_FTP_RESPONSE_HPP

FTP レスポンスについて


まずは前段として、FTP レスポンスの文法を明らかにしておく。


レスポンスの詳細な解説は、以下のページ等を参照のこと。

    • ネットワークプログラミングの基礎知識 >> FTP クライアントを作ってみよう (4)

http://x68000.q-e-d.net/~68user/net/ftp-4.html


また、FTP プロトコルそのものの仕様は以下にある。

    • RFC959

http://www.ietf.org/rfc/rfc959.txt


レスポンスは、例えば以下のような形式である。

227 Entering Passive Mode (10,0,0,1,156,92).
    1. 行頭には3桁のレスポンスコードがくる。
    2. 次いで(空白)がくる。
    3. 以降から行末までが詳細を示すメッセージである。
    4. 行の区切りは CRLF である。


至極単純である。
しかし、レスポンスは複数行にわたる場合がある。


その場合、例えば以下のようになる。

230-Welcome to FTP.
Located in Okayama, Japan.
230-code means "logged in."
230 User ftp logged in.
    1. 最初の行頭に3桁のレスポンスコードがくる。
    2. 次いで'-'(ハイフン)がくる。
    3. 同じレスポンスコード+(空白)が行頭に来る行までがメッセージになる。
    4. 最後の行にもメッセージがつく(場合がある)。


なお、例の3行目の行頭にも3桁のコードがあるが、これは後にが続かないため、単にメッセージの一部である。
FTP の仕様では、このような紛らわしい場合は行頭にスペースを入れて明確に区別するようサーバの実装に推奨しているが、
あくまで上記は「正しい」レスポンスである。

qi::grammar


Grammar(文法)は、ルール(PrimitiveParser やサブルール)の集合をカプセル化する。
Grammar は、それ自体ルールと同様に他のルールと合成することができる。


文法クラスを定義するには、通常 qi::grammar を継承する。
コードでは以下の部分である。

        template<
            typename Iterator,
            typename Tuple
        >
        class ftp_response
            : public qi::grammar<
                Iterator,
                Tuple (),
                typename ftp_response_impl::locals_of<Tuple>::type
            >
        {
            /* ... */
        };


ftp_response のテンプレート引数の Iterator は、文字列を走査するためのイテレータである。
同様に Tuple は、解析結果を格納するタプルである。


なお、Spirit.Qi では単にタプルと言った場合 boost::tuple でなく Boost.Fusion のシーケンスを指す。
(boost::tuple や std::pair 等をタプルとして使いたい場合は、Boost.Fusion がアダプトする仕組みを持っている)


通常、この程度の文法をオンデマンド的に書くのであれば、型を決め打ちして構わないかもしれないし、
実際ドキュメントのサンプルコードでも概ねそうしている。
ここでは、より汎用的にしてみるよう試みる。


さて、qi::grammar に渡すテンプレート引数を見てみる。
Spirit.Qi のドキュメントでは以下のように示されている。

template <typename Iterator, typename A1, typename A2, typename A3>
struct grammar;


Iterator は、上記と同じくイテレータである。
A1, A2, A3 は、Signature, Skipper or Locals と規定されている。
これら3つは、省略したり、好きな順序で書くことができる。


Signature は、ルールの結果の型(Attribute)や、ルールが引数をとる場合その型を宣言する。
Attribute はシグネチャの返値として書く。
ftp_response の場合、Tuple を結果とする引数をとらない文法とするので、シグネチャは Tuple () となる。
Attribute についてはまた後述する。


Skipper は空白文字等のスキップパーサを指定する。
ここでは使わないので説明は省略する。


Locals は、ルールが構文解析中に参照できるローカル変数を宣言する。
これには qi::locals を使う。


さて、Grammar というのは言ってみれば、(カプセル化された)ルールを返す関数のようなものである。
Grammar は通常、少なくとも一つのルールをメンバに持つ。
このルールとはつまり、構文解析の開始点となる開始ルールのことだ。
qi::grammar のテンプレート引数には、開始ルールのそれと同じものを指定する必要がある。


つまりここでは、開始ルールがローカル変数を使用するので、
qi::grammar の引数にも同じように qi::locals を指定しているのである。

qi::locals


qi::locals は、単にこのように宣言する。

qi::locals<L1, L2, L3 ..., LN>


ここで実装の詳細に使っている ftp_response_impl::locals_of は、
タプルの最初の型のローカル変数を返すメタ関数である。
定義は以下の部分である。

            template<typename Tuple>
            struct locals_of
                : public boost::mpl::identity<
                    qi::locals<
                        typename boost::remove_reference<
                            typename boost::fusion::result_of::value_at_c<Tuple, 0>::type
                        >::type
                    >
                >
            {};


fusion::result_of::value_at_c は、タプルの N 要素目の型を返す。
remove_reference は、参照のタプルが渡された場合への対応である。


例えば、以下のコードで locals_type は qi::locals に等しい。

typedef fusion::vector<unsigned, std::vector<std::string>, std::string> tuple_type;
typedef locals_of<tuple_type>::type locals_type;
BOOST_MPL_ASSERT((boost::is_same<locals_type, qi::locals<unsigned> >));


qi::locals によって宣言したローカル変数を参照するには、qi::_a プレースホルダを使う。
複数ある場合は、qi::_a, qi::_b, qi::_c... , qi::_j がそれぞれに対応する。

Attribute


まずは結果の型の要求を明確にしておく。
それは、概ね以下のようなものである。
なお、これはあくまで疑似コードであることに留意されたし。

tuple< (string | integer), optional< vector< string > >, string >
    1. tuple は、fusion::vector 等の Fusion のシーケンスである。
    2. string は文字列型である。
    3. integer は数値型である。
    4. optional は、boost::optional 等である。
    5. vector は、std::vector 等のコンテナである。


最初の要素 (string | integer) は、ステータスコードである。
これは3桁の10進数で表わされる。


2要素目の optional< vector< string > > は、もしメッセージが複数行にわたる場合の、
最後の行を除いたメッセージの文字列である。
これは行ごとに分割するものとする。


またこれは、単に vector< string > でもよい。
何故ならメッセージがない場合、空要素のコンテナは無効値と同じと考えられるからである。


3要素目の string は、(メッセージが複数行の場合は最後の行の)
ステータスコードと空白に続くメッセージの文字列である。


以下は、テンプレート引数に渡されたタプルから要素の型を取りだす部分である。

            typedef typename boost::remove_reference<
                typename boost::fusion::result_of::value_at_c<tuple_type, 0>::type
            >::type status_code_type;
            typedef typename boost::remove_reference<
                typename boost::fusion::result_of::value_at_c<tuple_type, 2>::type
            >::type message_type;


fusion::result_of::value_at_c と remove_reference については、前項の説明と同じである。


最初の要素がステータスコードを格納する型になる。
これは文字列型または数値型を期待する。


3要素目がメッセージの文字列(の1行分)を格納する型になる。

ルールの宣言


以下がルールの宣言部分である。

            qi::rule<iterator_type, tuple_type (), typename ftp_response_impl::locals_of<Tuple>::type> response_;
            qi::rule<iterator_type, status_code_type ()> status_code_;
            qi::rule<iterator_type, message_type ()> message_;


response_ は、これが開始ルールであり、これをトップレベルとして解析される。
テンプレート引数に渡すべきものは、基底クラスの qi::grammar と同様である。


status_code_ は、ステータスコード部分を解釈するサブルールである。
message_ は、メッセージの文字列(の1行分)部分を解釈するサブルールである。


基本的に、qi::rule のテンプレート引数に渡すべきは、qi::grammar についての説明と同じである。

コンストラクタ

            explicit ftp_response(bool including_crlf = true)
                : ftp_response::base_type(response_)


ここで base_type は、qi::grammar である。
基底クラスのコンストラクタには、開始ルールを渡す必要がある。
また、開始ルールの他にパーサ識別名を渡すこともできるが、ここでは省略する。


なお including_crlf は、解析結果にメッセージ行末の改行コード CRLF を含めるか否かのフラグとする。

ルールの構築


ここからが本題といえる。
実際に解析部分を書いていく。


以下が response_ のルール構築部分である。

                response_ %= status_code_[qi::_a = qi::_1]
                    >> -(
                        '-' >> (message_ % !(qi::lit(qi::_a) >> ' '))
                        >> qi::lit(qi::_a) >> &qi::lit(' ')
                        )
                    >> ' ' >> message_
                    ;


最初にステータスコードが解釈される。

status_code_[qi::_a = qi::_1]


後置の角括弧の内容は、セマンティックアクションである。
セマンティックアクションは、あるルールにマッチした時点で何らかの処理を呼ぶための機構である。

qi::_a = qi::_1

の部分は、Spirit.Phoenix によるラムダ式である。


qi::_a は前述したように、ルールに紐付けられたローカル変数を参照するプレースホルダである。
qi::_1 は、解析されたルールの Attribute を参照するプレースホルダである。


すなわちこれは、「status_code_ にマッチした結果をローカル変数に代入する」という動作になる。

>> -(
    '-' >> (message_ % !(qi::lit(qi::_a) >> ' '))
    >> qi::lit(qi::_a) >> &qi::lit(' ')
    )


これは、メッセージが複数行にわたる場合にマッチする部分である。


単項 -(マイナス)は optional operator である。
もしオペランドにマッチしない場合、ゼロ長マッチと同じになる。


'-' にマッチしない、つまりステータスコードにハイフンが続かない場合、この部分は単に無視される。

qi::lit(qi::_a)

は、「最初にマッチしたステータスコードと同じリテラル」になる。
qi::_a の参照するローカル変数には、最初のセマンティックアクションによって、
ステータスコードの値が格納されている。


qi::lit は便利なプリミティブパーサであって、文字列であれ数値であれ、
引数に渡したものにマッチするリテラルのパーサになる。
また、qi::lit の Attribute は unused、すなわち解析結果には格納されないものである。


! は not-predicate である。
オペランドにマッチした場合はエラーになり、でなければゼロ長マッチと同じになる。


% は list operator である。
オペランドで区切られた左オペランドのゼロ個以上のリストにマッチする。
Attribute は vector になる。


以上から、

'-' >> (message_ % !(qi::lit(qi::_a) >> ' '))

は、「ハイフンに続き、ステータスコード にマッチするまで、メッセージ文字列(一行分)のリストにマッチする」
というような意図になる。


list operator は通常、カンマ区切りのような文法に使うもので、リストにマッチしてから、
続いてステータスコード の部分をまた消化してやる必要がある。

>> qi::lit(qi::_a) >> &qi::lit(' ')


単項 & は、オペランドにマッチした場合、ゼロ長マッチと同じになる。
つまりこの場合、 があることを確認するが、イテレータの位置は の前のままという動作である。


これは、メッセージが単一行の場合と位置を合わせるためである。


ところでこの部分は、リストにマッチした時点で次にステータスコード が来ることが解っているので、

>> qi::omit[status_code_]

などと書いても同じことである。

>> ' ' >> message_


最後に と、最後の行のメッセージを読み取って終わりとなる。
この行だけは、タプルの3要素目に格納される。


なお %= は auto-rule definition であり、ここではルール定義がセマンティックアクションを含むため、
代入を %= で行う必要がある。

ステータスコード


status_code_ のルール構築部分は以下である。

                status_code_ = qi::raw[
                    qi::digit >> qi::digit >> qi::digit
                    ];


qi::digit は数字1文字にマッチする。
ステータスコードは3文字なのでその分を連結している。
Arrribute は Ch で、これは文字プリミティブの型である。


qi::raw ディレクティブは、Attribute が iterator_range である。
これは、マッチした部分の入力の範囲を示す。
内側のルールの Attribute は単に無視される。


qi::raw は、マッチの結果を「一つにまとめる」ために使うことができる。
ここでは、qi::raw を書かなかった場合、もし status_code_type が文字列型の場合はマッチするが、
status_code_type が数値型だった場合はマッチしない。

メッセージ


message_ のルール構築部分は、including_crlf の如何によって変わる。


もし行末の CRLF を含める場合は以下である。

                    message_ = qi::raw[
                        *(qi::char_ - qi::lit("\r\n"))
                        >> qi::lit("\r\n")
                        ];


qi::char_ は任意の文字プリミティブにマッチする。


二項 -(マイナス)は、difference operator である。
オペランドにマッチするものから、右辺オペランドにマッチするものを除いたものになる。


単項 * は、kleene operator である。
これは、オペランドのゼロ回以上の繰り返しにマッチする。
Attribute は vector である。


すなわち

*(qi::char_ - qi::lit("\r\n"))

は、CRLF を含まない任意の文字列にマッチする。


次に

qi::lit("\r\n")

で行末の CRLF を消化する。


ここで、qi::lit の Attribute は unused であり、そのままでは最後の CRLF は結果に含まれない。
qi::raw で囲むことによって、マッチした部分全体を結果に格納する。


行末の CRLF を含めない場合は以下である。

                    message_ = qi::raw[
                        *(qi::char_ - qi::lit("\r\n"))
                        ]
                        >> qi::lit("\r\n")
                        ;


最後の CRLF は qi::raw で囲まれていない。
こうした場合最後の CRLF は結果に格納されない。

テスト


実装についての説明はすべて終わったので、簡単なテストコードを書いてみよう。
入力ソースとして、最初のほうで示した、単一行の場合と複数行の場合のサンプルを使用する。

227 Entering Passive Mode (10,0,0,1,156,92).
230-Welcome to FTP.
Located in Okayama, Japan.
230-code means "logged in."
230 User ftp logged in.


以下がテストコードである。

#include <iostream>
#include <string>
#include <vector>
#include <boost/foreach.hpp>
#include <boost/range.hpp>
#include <boost/fusion/include/vector.hpp>
#include <sprig/parser/ftp_response.hpp>

template<typename Range, typename Parser>
void parse_test(Range const& input, Parser const& parser) {
    typedef typename Parser::start_type::attr_type result_type;

    result_type result;
    typename boost::range_const_iterator<Range>::type it = boost::begin(input);

    if (!boost::spirit::qi::parse(it, boost::end(input), parser, result)
        || it != boost::end(input)
        )
    {
        std::cout << "Parsing failed." << std::endl;
    } else {
        std::cout
            << "Parsing succeeded.\n"
            << "Status Code = " <<  boost::fusion::at_c<0>(result) << "\n"
            ;

        typedef typename boost::fusion::result_of::value_at_c<result_type, 1>::type messages_type;
        BOOST_FOREACH(boost::range_reference<messages_type>::type message, boost::fusion::at_c<1>(result)) {
            std::cout << "Message = " << message;
        }

        std::cout
            << "Message = " <<  boost::fusion::at_c<2>(result)
            << std::endl;
    }
}

int main() {
    std::string single_line(
        "227 Entering Passive Mode (10,0,0,1,156,92).\r\n"
        );
    std::string multi_line(
        "230-Welcome to FTP.\r\n"
        "230-code means \"logged in.\"\r\n"
        "Located in Okayama, Japan.\r\n"
        "230 User ftp logged in.\r\n"
        );

    typedef boost::fusion::vector<unsigned, std::vector<std::string>, std::string> result_type;
    typedef sprig::parser::ftp_response<std::string::const_iterator, result_type> parser_type;

    parse_test(single_line, parser_type());
    parse_test(multi_line, parser_type());

    return 0;
}


以下が実行結果である。
(VC9 + Boost 1.46.1)

Parsing succeeded.
Status Code = 227
Message = Entering Passive Mode (10,0,0,1,156,92).

Parsing succeeded.
Status Code = 230
Message = Welcome to FTP.
Message = 230-code means "logged in."
Message = Located in Okayama, Japan.
Message = User ftp logged in.


パースは成功した。


じつに冗長で雑多な解説となったが、この記事は以上である。

蛇足


僕が Boost.Spirit にはじめて出会ったのは、Spirit 1.6 の時点である。


そのころ Spirit は単に構文解析ライブラリであり、それは今 Spirit において classic と呼ばれる部分に遺されている。
Boost.Fusion も無ければ、Boost.Proto も無かった。


現在の Spirit V2 には、Spirit.Qi,Spirit.Karma,Spirit.Lex の3つのフレームワークと、Spirit.Phoenix がある。
このキュートな記法と一風変わったネーミングをもつライブラリは、Boost.Fusion との連携や、Boost.Proto による Expression Template 部分の一新等による進化によって、大幅に強化された。


Spirit とは、精神、魂、情熱、精霊、魂魄、幽鬼、亡き魂を意味する。
このネーミングが、ライブラリ作者である Hartmut Kaiser 氏の個人的体験と信念に由来することは周知の通りである。


僕はあるときふと、Spirit.Qi を『鬼』と解釈してみた。
英語で鬼はふつう"daemon"で、これは悪魔や悪霊のことであるが、東洋的な鬼は、
悪しき側面のみならず、むしろ祖霊や地霊、強さの象徴などとも結びつけられる。


とはいえ、鬼というやつは大抵見るにたえないみにくい貌をしている。
(見ろよ、この気色悪い演算子オーバーロードを)


おまけに図体はうすらでかいときた。
(いったいいくつのテンプレートを実体化すれば気がすむんだ?)


だから、力は強いくせに酷くのろまだ。
コンパイル時間はもはやティータイム代わりだ!)


人間はそんな彼を見るたび罵る。
(変態! 変態! 変態!!!)


それだのに内心は親切で心優しいだとさ。なんてお人よしだ。
(文法を書くだけで解析、おまけにタプルやコンテナに格納してくれる……)


なんと神通力があって、見通したことを教えてくれる。
(型レベルで文法の誤りを見つけてエラーにしてくれる!!)


もちろん、やっぱり彼は鬼なので、言葉が理解しにくいところもある。
(嵐のようなコンパイルエラーと判読困難なエラーメッセージ! ああ!!)


それでもやはり、そんな彼と、友達になってみたいと思ったのさ。
(Spirit.Qi かわいいよ Spirit.Qi)


ある意味において、Spirit は、「素晴らしく C++ らしい」ライブラリであるとさえ思っているのである。