Tutorials からはじめる Boost.Spirit.Qi

この記事は Aizu Advent Calendar 2013 7日目 の記事を想定して作成されています。

Let's Boost.Spirit!

Boost.Spirit とは構文解析用のライブラリで、Spirit.Lex, Spirit.Qi, Spirit. Karma の３種類があります。
それぞれ字句解析器、字句＋構文解析器、パーサジェネレータ（Qiの逆）を担います。
今回は、その中でも最も利用されやすい Spirit.Qi について取り上げてみます。

このライブラリを使ったコードを自分で一から書こうとするとき、ある程度理解が及んでいないとコンパイルエラーの嵐となって大変です。
しっかり理解するためには人のコードを丁寧に読むしかないのでは。そう思って、今回 Spirit.Qi の公式ドキュメント Tutorials の一部のサンプルコードを詳しく読んでみようという記事を書きました。

私が自分で使って遊んでみたコードを書いてみてもよかったのですが、記事にまとめ上げる時間を作れなかったです。これはひどい。

そんな感じで今回 Spirit.Qi の Tutorials の

1. Mini XML - ASTs!

のサンプルコードの内容を一行ずつ詳しく見つつ、また並行して Spirit.Qi の基本文法に慣れていこうという記事にしました。

当記事は
「Spirit.Qi を使いたいけど公式ドキュメントの Tutorials もよく読めてないしわからない」
という人を対象としています。
私自身勉強中の身ですので、間違いが有りましたらご指摘を頂ければ幸いです、そしてそのときはごめんなさい。
（ところで人のサンプルコードを説明って問題あるんですかね）

Spirit.Qi is 何

Spirit.Qi はユーザの定義する構文の解析と、その結果を任意のデータ構造に格納する事をしています。yacc/bisonなどと大きく異なる部分は、C++の演算子のオーバーロードしてEBNFのような記述をC++のコードとして直接書き込めるようにしていることです。

そういう訳で、Spirit.Qi を使っているコードの構文の定義部分は比較的容易に読むことができます。

Spirit.Qi の構文定義の記法

EBNF と似たような記述は可能ですが、C++にない演算子は使えないので少し違いを注意をする必要があります。
それを踏まえた上で以下に列挙する基本的な記法を学びましょう。

1. aとbが連続するとき、「a b」という表記の代わりに「a >> b」を用いる
2. aとbが連続するとき、それが連続しない場合解析失敗とするときは「a > b」と書く（バックトラックしない）
3. aが0回以上連続するとき「*a」と書く
4. aが1回以上連続するとき「+a」と書く
5. 区切り文字を指定して連続してaを解析するとき、「a % b」と書く
6. 「a | b | c | ...」と書くと、a, b, c, ... と先頭からみて初めてマッチしたものを採用する
7. 「a - b」 と書くと、b の条件にマッチしない a にマッチする
8. 「!a」と書くと、その場には a が置かれてはいけない

以上のことが最低限確認されていると良いです。
もっと多くを知りたい場合は公式ドキュメントを見てみてください。

Tutorials: Mini XML - ASTs!

本題です。
このサンプルコードでは簡単なXMLの構文解析をしようとしています。XMLはタグで囲まれた部分がネストしていくので再帰的下向き構文解析をして、結果を木構造に埋めていきます。

Our mini XML tree representation

先頭の名前空間 client を見ると

1. boost::spirit::qi
2. boost::phoenix
3. boost::fusion

の3つが使われていることが分かります。それぞれ

1. 構文解析
2. Spiritにおける無名関数（ラムダ式）の扱い
3. タプル(Fusion Sequence)の扱い

をします。タプルとは無名の構造体のことです。無名関数とは、処理する場所に直接記述できる無名の関数です。

続きを見ていくと、boost::variant というものがあります。共用体のような振る舞いをします。
boost.variantの値の読み込みにはgetよりもapply_visitorを使いましょう。ライブラリ側でVisitor*1に型ごとの処理が振り分けられ、コンパイル時に型チェックが出来ます。

boost::variant<...> は大抵長くなるのでtypedefしておくのが普通です。
boost::recursive_wrapper<...> によって再帰的なデータ構造を動的に確保しています。（実態は連結する構造体のポインタを持った上で便利にラッピングしているようです）

抽象構文木の例を記します。

mini_xml
 |
 |     children
 |___ 「 name
 |     L mini_xml(variant)
 |          |
 |          |    children
 |          |___「 name
 |               L std::string
 |___ 「 name 
       L std::string

これは以下のサンプルコードと比較できると思います。

    typedef
        boost::variant<
            boost::recursive_wrapper<mini_xml>
          , std::string
        >
    mini_xml_node;

    struct mini_xml
    {
        std::string name;                           // tag name
        std::vector<mini_xml_node> children;        // children
    };

次にくるのは、boost::fusion の adapt_struct です。
boost::fusion は「タプルを扱う」と述べましたが、これはタプルに関する様々なアルゴリズムの適用をすることが出来ます。
しかしユーザ定義型の構造体はタプルではないので、これをタプルにアダプトしなければなりません。これを可能にするのが BOOST_FUSION_ADAPT_STRUCT() というマクロです。
（＜追記 12/11＞「タプルにアダプト」といいましたが、ここでのタプルとは Fusion Sequence のことで Random Access Sequence です。Random Access Sequence とは Random Access Iterator を用いた双方向性のシーケンスです。BOOST_FUSION_ADAPT_STRUCT() によって、元の構造体名が Random Access Sequence であるように扱えます）

BOOST_FUSION_ADAPT_STRUCT() はグローバルに記述される必要があります。よって、以下のアダプトする mini_xml も名前空間 client から完全に指定されなければなりません。

BOOST_FUSION_ADAPT_STRUCT(
    client::mini_xml,
    (std::string, name)
    (std::vector<client::mini_xml_node>, children)
)

以上で XML を取り入れるデータ構造の記述が終わりました。

Print out the mini xml tree

文法定義の前に、解析された XML の表示する部分がきます。

struct mini_xml_node_printer は boost::static_visitor<> を継承します。ここに boost::variant の 型ごとの処理内容が記述されます。
関数オブジェクトの定義の返り値の型がvoidなので static_visitor<> の <> 内も対応してvoidもしくは空白にします。

ここで定義された関数オブジェクトを用いてVisitorパターンを適用します。
void mini_xml_printer 内で

BOOST_FOREACH(mini_xml_node const& node, xml.children)
{
    boost::apply_visitor(mini_xml_node_printer(indent), node);
}

と記述されているのが分かると思います。variant である mini_xml_node の示す型によって異なった処理を呼び出しています。

Our mini XML grammar definition (xml1)

XMLの文法定義をする部分です。ここはファイル mini_xml1.cpp と mini_xml2.cpp とで記述が異なっています。まずは xml1 から見ていきましょう。

はじめに、文法の定義は以下のように*2書くことができます。

template <typename Iterator>
struct my_grammar : grammar<Iterator, A1, A2, A3>
{
    my_grammar() : my_grammar::base_type(start, name)
    {
        // Rule definitions
        start = /* ... */;
    }

    rule<Iterator, A1, A2, A3> start;
    // more rule declarations...
};

中央に Rule definitions と書かれていますが、ルールとはなんでしょうか。例えば以下のような適当なEBNFが与えられたとき

digit_ex_zero = 1 | 2 | ... | 9 ;
digit         = 0 | digit_ex_zero ;

上のそれぞれがルールになります。

qi::grammarは１つ以上のルールのカプセル化をします。再帰的下向き構文解析の文法の定義のためにはqi::grammarを使う必要があります。
その際 rule<...> start; のように構造体のメンバ変数の宣言の形で使うルールを宣言していく必要があります。

また上のコードに Iterator というテンプレートクラスがあります。文法の定義によってはバックトラックしうるので、Iterator には双方向イテレータに代わるもの（例えばstd::stringのイテレータ）が与えられます。
解析結果を格納するデータ構造や、スキップパーサ（読み飛ばし）の指定などがA1, A2, A3にオプション要素であります。base_typeには、解析のはじめとなるルールを指定しておきましょう。nameの指定はオプションで今回は使いません。

ここでサンプルコード照らし合わせてみましょう。
はじめに文法定義クラス mini_xml_grammar が qi::grammar を継承しています。
解析結果は mini_xml に返します。ascii::space_typeでスキップパーサを指定しています。

ルールの定義の部分は以下です。

text = lexeme[+(char_ - '<')        [_val += _1]];
node = (xml | text)                 [_val = _1];

start_tag =
          '<'
      >>  !lit('/')
      >>  lexeme[+(char_ - '>')       [_val += _1]]
      >>  '>'
;

end_tag =
          "</"
      >>  string(_r1)
      >>  '>'
;

xml =
          start_tag                   [at_c<0>(_val) = _1]
      >>  *node                       [push_back(at_c<1>(_val), _1)]
      >>  end_tag(at_c<0>(_val))
;

lexeme 内ではスキップパーサを無視して文字列を読み取ります。
+(char_ - '>') というルール記述の後にある [ ] で囲まれたものの中にセマンティックアクション（意味アクション、解析時アクション）を記述します。

セマンティックアクションとは文法のパースが成功したときどうするか、というものです。これのおかげで単なる文法の記述から内容をデータ構造へ格納する橋渡しができます。内に関数ポインタや関数オブジェクトを指定して、その先でセマンティックアクションを記述することも可能ですが、Phoenixの無名関数を用いて直接ラムダ式を記述するのが楽です。

名前空間 qi::labels の中にプレースホルダ _val, _1, _r1 が存在する*3のでそれを使って記述をしています。
ルールtextの文法定義の記述とセマンティックアクションの記述において、等号の LHS と RHS は対応しています。_val には rule text の attribute である std::string が対応し、解析した内容は _1 に対応していて、セマンティックアクションでデータ構造に代入する処理が記されています。
_1 の数字は解析データの番号ですが、これはその数によって _2, _3 と増えていきます。

ルール xml の定義の セマンティックアクション中の LHS at_c<0>(_val) は、返す mini_xml の0番要素（BOOST_ADAPT_STRUCT()を参照するとこれはstd::string name）を示しています。次の行の push_back(at_c<1>(_val), _1) は、mini_xml の1番要素、つまりstd::vector children に _1(0回以上のnodeの繰り返し) を push_back していくことを表します。

最後の宣言部、qi::rule<...> ...; の<>内について、2つ目の要素はそのルールが呼ばれるときの「"返り値"の型("引数"の型)」の指定、3つ目はスキップパーサの指定です。

Our mini XML grammar definition (xml2)

こちらは xml1 と異なり、ルールの記述に = でなく %= を用いてセマンティックアクションの記述の多くが省略しています。他は同じです。

Main program

bool r = phrase_parse(iter, end, xml, space, ast);

if (r && iter == end)
{
    std::cout << "-------------------------\n";
    std::cout << "Parsing succeeded\n";
    std::cout << "-------------------------\n";
    client::mini_xml_printer printer;
    printer(ast);
    return 0;
}

ここだけ少し説明します。phrase_parse() では storage.begin() と指定しないようにしましょう。渡されたイテレータを用いて解析を進めるからです。phrase_parse() の返り値は、「解析が成功したかどうか」です。その情報に加えて、解析の先頭から始まったイテレータが最後まで到達しているかをチェックする必要もあります。

終わりに

Spirit.Qi の Tutorials であっても、細かくフルコードを見ていくと結構大変な気がします。（私が大変でした）
しかし細かく読んで曖昧な部分をなくしていくことで初めてこのライブラリが使えるようになっていくのではとも思います。

当記事がBoost.Spiritを使う足がかりとなれば幸いです。
多分このライブラリを使えるようにするためには、英語の公式ドキュメントを一通りしっかり読んだ方がよさそうです。

あと、２度目ですが間違った記述があれば教えて欲しいです。自分自身が勉強しながら書いた記事なので。。。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

さてさて、今年のAizu Advent Calendarも始まってちょうど１週間が経ちました。しかしまだまだAdventは続きます！

次の Aizu Advent Calendar 2013 8日目 担当は たくち さんになります！

*1:GoFのVisitorパターン、参考サイト: http://www.geocities.jp/ky_webid/design_pattern/022.html

*2:引用元 Nonterminals (Spirit.Qiの非終端記号): http://www.boost.org/doc/libs/1_55_0/libs/spirit/doc/html/spirit/qi/quick_reference/non_terminals.html

*3:qiの中にも_valや_1などのプレースホルダが定義されているようですが、違いはわかりません