boost::spirit を使う

仕事柄、いろいろなパーザを作ることが多い。 今回は簡単な CSV パーザを作ることになった。 力まかせにガリガリと作ってもいいのだけれど、それではつまらない。 というわけで、Let’s boost でも 変態的 と賞讃されている boost::spirit を使ってみることにした。

たしかに見事な「変態」ぶりである。 なにしろ、BNF (Backus-Naur Form) で記述された文法を、 ほとんどそのまま C++ の式として書き下すことができるのだ。 たとえば、今回のお題である CSV は、BNF では次のように記述できるだろう (これは完全な CSV ではないかもしれない)。

  csv ::= value [ ',' value ]* EOL
  value ::= [空白]* '"' quoted_value '"' [空白]* | naked_value
  quoted_value ::= [ <'"' 以外の文字> | '""' ]*
  naked_value  ::= [ <',' および '"' および '\n' 以外の文字> ]*

これを spirit で書くと次のようになる。

  rule<> csv, val, quoted_val, naked_val;
  csv = val >> *(',' >> val) >> eol_p;
  val = *blank_p >> ch_p('\"') >> quoted_val >> ch_p('\"') >> *blank_p | naked_val;
  quoted_val = *(~ch_p('"') | str_p("\"\""));
  naked_val = *(~ch_p(',') & ~ch_p('\"') & ~ch_p('\n'));

つまり、

• 項の連結は、 >>
• 項の選択は、 |
• 項の任意個の繰り返しは、単項 *

のように、BNF の記法をそのまま C++ の演算子で表現しているのである。 で、この式を実行すると、最終的に CSV をパージングする構文解析器 csv が構築されるというわけだ。

parse()

実際にパージングを行うには、

  parse( str, csv );  // str は 0 で終端する C 文字列

  parse( first, last, csv );  // first, last は解析範囲を指定するイテレータ

というような関数を呼び出す。この parse() は、spirit が用意している ヘルパ関数である。

parse_info<>

関数 parser() は、parse_info<IteratorT> という構造体を戻値として返す。parse_info は次の4つのメンバを持っている。

stop	パージングの終了位置 (IteratorT; 次のパージングの開始位置となる)
hit	パージングに成功したら true を返す
full	入力文字列がすべて読み込まれたら true を返す
length	パージングによって読み込まれた入力文字数を返す

parse_info<> を使ったパージング ループは、およそ次のようになるだろう。

  IteratorT first, last;
  rule<> r;
  while ( first != last ) {
    // パージング実行
    parse_info<IteratorT> info = parse( first, last, r );
    
    // パージングに失敗したらループを終了
    if (!info.hit) break;

    // 次のパージング位置を設定
    first = info.stop;
  }

grammar<>

文法を定義するには、grammar<> という基底クラスから派生させたクラスを用いるのが便利である。 grammar<> は、派生させるクラスを引数とするクラステンプレートで、 そのスケルトンは次のようになる。 (The Grammar より引用)

  struct my_grammar : public grammar<my_grammar>
  {
    template <typename ScannerT>
    struct definition
      {
	rule<ScannerT>  r;
	definition(my_grammar const& self)  { r = /*..define here..*/; }
	rule<ScannerT> const& start() const { return r; }
      };
  };  

つまり、definition という内部クラステンプレートを持ち、 definitionはさらに、

• 起点となるルール
• ルールを構築するコンストラクタ definition()
• 起点となるルールを返す関数 start()

を持つ。definition<> はテンプレート引数としてスキャナの型を要求するが、 parse() 関数を呼ぶとイテレータ引数 first や last から自動的に構成してくれる。 とくに思い悩まずに済むので楽である。

実際、今回の作業で、grammar<> によるラッピングを行わずに直接にルールを作成して parse() 関数に渡そうとしたら、 どうも ScannerT の型が合わないらしく、コンパイルが通らなかった。

アクション

ルールの構成要素 (parser) は、 それが hit したときに実行すべきアクションを定義することができる。 アクションは、関数または関数オブジェクトであり、

  expression[ action ]

のような形で記述する。たとえば spirit は append というファンクタクラスを用意しており、

  vector<string> v;
  expression[ append(v) ];

とやると、expression にマッチした部分文字列が v に push_back される。

アクションは、次のように範囲を指定する2つのイテレータを引数とする。

  // 関数
  void action( IteratorT first, IteratorT last );

  // ファンクタ
  struct action {
    void operator()( IteratorT first, IteratorT last ) const;
  };

csv-parser.cpp

#include <iostream>
#include <iterator>
#include <vector>
#include <string>

// Spirit のコードをインクルード (必要なものだけ)
#include <boost/spirit/core.hpp>
#include <boost/spirit/iterator/file_iterator.hpp>

using namespace std;
using namespace boost::spirit;

// 値をベクタにコピーする Semantic Action
// 組み込みの append と同じような処理をしている(と思う)が、ここでは、
// ダブルクォートが重なっていたら、1つに落とすという処理が追加されている
struct push_val {
    vector<string>& values;
    push_val( vector<string>& vec ) : values(vec) { }

    template<class IteratorT>
    void operator()(IteratorT first, IteratorT last) const { // const が重要
#ifdef _MSC_VER
        // なぜか VC6 だとコンストラクタによる初期化がうまくいかない
        string s;
        s.resize(distance(first, last));
        for (size_t i = 0; first != last; ++i) {
            s[i] = *first++;
        }
#else
        string s( first, last );
#endif
        string::size_type pos = 0;
        while (1) {
            pos = s.find("\"\"", pos);
            if (pos == string::npos)
                break;
            ++pos;
            s.erase(pos, 1);
        }
        values.push_back(s);
    }
};

// csv パーザ
struct csv_parser : public grammar<csv_parser> {
    vector<string>& v;

    csv_parser( vector<string>& vec ) : v(vec) { }

    template<typename ScannerT>
    struct definition {
        rule<ScannerT> csv, val, quoted_val, naked_val;

        definition(const csv_parser& self)
        {
            csv = val >> *(',' >> val) >> (eol_p | end_p);

            val = *blank_p >>
                  ch_p('\"') >> quoted_val[push_val(self.v)] >> ch_p('\"') >>
                  *blank_p
                | naked_val[push_val(self.v)];

            quoted_val = *(~ch_p('"') | str_p("\"\""));

            naked_val = *(~ch_p(',') & ~ch_p('\"') & ~ch_p('\n'));
        }

        const rule<ScannerT>& start() const { return csv; }
    };
};

// パーザ呼び出し用のラッパ関数
template<typename IteratorT>
parse_info<IteratorT>
parse_csv(const IteratorT& first, const IteratorT& last, vector<string>& v)
{
    csv_parser csv(v);

    return parse(first, last, csv);
}

// ファイルからcsvデータを読み出して表示する例
int main( int argc, char** argv)
{
    if (argc != 2) return 1;

    // Spirit は forwardイテレータを要求するので、ifstream では力不足。
    // そのため spirit が用意している file_iterator を使う。
    typedef file_iterator<char> iterator_t;

    // ファイルを開いて、その先頭を指すイテレータを生成
    iterator_t begin(argv[1]);
    if (!begin) {
        cout << "Unable to open file: " << argv[1] << endl;
        return -1;
    }

    // 先頭を指すイテレータを複製
    iterator_t first = begin;
    // 終端を指すイテレータを生成
    iterator_t last = first.make_end();

    while ( first != last ) {
        vector<string> v;
        parse_info<iterator_t> info = parse_csv( first, last, v );

        if (!info.hit) {
            cout << "Error! Point: " << distance(begin, info.stop) << endl;
            break;
        }

        cout << "Parses OK:" << endl;
        for (vector<string>::size_type i = 0; i < v.size(); ++i)
            cout << i << ": " << v[i] << endl;

        cout << "-------------------------\n";

        // 次の解析位置を設定
        first = info.stop;
    }

    return 0;
}

初出: 2003年5月11日

C++ ラビリンスの目次へ