boost::spirit::qiを使って構文解析する

JavaScript onlyブログじゃなくなってきてるな、と思う今日この頃です。

今回はC++のライブラリBoostを使って構文解析をする方法についてです。

boost::spirit::qi

今回はBoostの中のboost::spirit::qiを使います。このライブラリはC++のオーバーロードを悪用活用して、ほとんどBNF記法のようにプログラムを書けるようにしてしまいました。

term = factor  (('+' | '-')  factor)*
factor = expr  (('*' | '/')  expr)*
expr = double | '(' term ')'

このBNF記法で書かれた文法が次のように変換されます。

term = factor >> *((lit('+') | lit('-')) >> factor);
factor = expr >> *((lit('*') | lit('/')) >> expr);
expr = double_ | lit('(') >> term >> lit(')');

ほとんどBNFそのままという恐ろしさ・・・

原始的なパーサー

文法を書いていく前に、まずは原始的なパーサーを使ってみます。

#include <iostream>
#include <string>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
using namespace std;
using namespace boost::spirit;
using namespace boost;

int main(){
    string buf;
    double result;
    while (getline(cin, buf)) {
        // 1行読み込んでパースする
        string::const_iterator iter = buf.begin(), end = buf.end();
        bool success = qi::phrase_parse(iter, end, qi::double_, ascii::space, result); // パース
        if (success && iter == end) {
            cout << "[success] " << result << endl;
        } else {
            cout << "[failed] invalid syntax" << endl;
        }
    }
    return 0;
}

入力を受け取ってそれがdouble型ならパース成功、それ以外は失敗というプログラムです。 qi::double_というのが今回のパーサーです。spirit::qi にはすでに基本的なパーサーが揃えられています。

boost::spirit::ascii:alpha
boost::spirit::ascii:char_
boost::spirit::ascii:digit
boost::spirit::hex

どれが何をパースするかはだいたい予想がつきますよね？

パーサーを組み合わせる

先程の原始的なパーサーを組み合わせて少し複雑な構文を解析してみます。パーサーを組み合わせる方法は次のようなものがあります。

parser1 | parser2 「parser1またはparser2」
parser1 >> parser2 「parser1に続いてparser2」
*parser 「parserが0個以上連続している」
-parser 「parserが0個あるいは1個」

例えば次のパーサーは「スペース1つを挟んでアルファベットの単語が２つ」という構文を受理します。

ascii::alpha >> lit(' ') >> ascii::alpha

litについては後述します。

パースした結果を変える

通常、受理するかどうかの判定のためだけに構文解析をすることは稀です。普通、解析木なり、評価結果なり、なんらかの結果がほしいはずです。そこでqiではactionを使います。actionは次のように記述します。

parser[&action]; // actionという引数を1つ受け取る関数
parser[cout << _1 << endl]; // Boost.Lambdaを使う
parser[_val = _1 + 3]; // 後述

_1 というのはパーサーがデフォルトで返す結果を表します。たとえばqi::double_ならdouble型の数値が入ります。パーサーが返す値を変更したい場合は、_valというプレースホルダーに対して代入を行います(実は若干違うようなのですが、よくわかっていません)。

数式を評価する

パーサーを作るとなったら、やっぱり数式は解析しますよね？

#include <iostream>
#include <string>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
using namespace std;
using namespace boost::spirit;
using namespace boost;

template <typename Iterator> struct my_grammar : qi::grammar<Iterator, double(), ascii::space_type> {
    my_grammar() : my_grammar::base_type(term) {
        using qi::lit;
        term = factor[_val = _1] >> *((lit('+') >> factor)[_val += _1] | (lit('-') >> factor)[_val -= _1]);
        factor = expr[_val = _1] >> *((lit('*') >> expr)[_val *= _1] | (lit('/') >> expr)[_val /= _1]);
        expr = (double_ | lit('(') >> term >> lit(')'))[_val = _1];
    }
    qi::rule<Iterator, double(), ascii::space_type> term, factor, expr;
};

int main(){
    string buf;
    double result;
    my_grammar<string::const_iterator> grammar;
    while (getline(cin, buf)) {
        string::const_iterator iter = buf.begin(), end = buf.end();
        bool success = phrase_parse(iter, end, grammar, ascii::space, result);
        if (success && iter == end) {
            cout << result << endl;
        } else {
            cout << "invalid syntax" << endl;
        }
    }
    return 0;
}

main()の中はほぼそのままです。パーサーを組み合わせてgrammarを作っている点だけ異なります。

独自の文法を解析する

僕自身あまりどうして動いているのか理解できていないので、先程の数式の文法を例に取り、注意点のみ書きます。

qi::rule

qi::rule<Iterator, double(), ascii::space_type>のdoubleの部分には、評価結果の型を指定します。今回は数式を評価するので、double型の結果としました。qi::grammar<Iterator, double(), ascii::space_type>も同様です。

評価結果として文字列がほしいならstring()、整数型ならint()という感じです。

my_grammar::base_type

base_type(term)のtermの部分が、文法の導入地点です。文法は渡された文字列をtermから解析しようとします。

lit

litは文字を表します。しかし、_1に現れません。ドキュメントを熟読してない(というか用語が多すぎて面倒くさくなった)ので細かいことはわかりませんが、

(string("hoge") >> qi::double_ >> string("fuga"))[cout << _1 << endl]

のようにするとエラーが起きます。_1にどれを入れたらいいのかわからないため起きるようです。しかし、パーサーを繋いだから_1が決まらないのかというとそうではありません。

(string("hoge") | string("fuga"))[cout << _1 << endl]

この例では普通に動きます。_1は現在までのパース結果が入るみたいです。

#include <iostream>
#include <string>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
using namespace std;
using namespace boost::spirit;
using namespace boost;

template <typename Iterator> struct my_grammar : qi::grammar<Iterator, double(), ascii::space_type> {
    my_grammar() : my_grammar::base_type(term) {
        using qi::lit;
        term = factor[_val = _1] >> *((lit('+') >> factor)[_val += _1] | (lit('-') >> factor)[_val -= _1]);
        factor = expr[_val = _1] >> *((lit('*') >> expr)[_val *= _1] | (lit('/') >> expr)[_val /= _1]);
        expr = (double_ | lit('(') >> term >> lit(')'))[_val = _1];
    }
    qi::rule<Iterator, double(), ascii::space_type> term, factor, expr;
};

int main(){
    string buf;
    double result;
    my_grammar<string::const_iterator> grammar;
    while (getline(cin, buf)) {
        string::const_iterator iter = buf.begin(), end = buf.end();
        bool success = phrase_parse(iter, end, grammar, ascii::space, result);
        if (success && iter == end) {
            cout << result << endl;
        } else {
            cout << "invalid syntax" << endl;
        }
    }
    return 0;
}

// ヘッダ等略

int main(){
    string buf;
    string result;
    my_grammar<string::const_iterator> grammar;
    while (getline(cin, buf)) {
        string::const_iterator iter = buf.begin(), end = buf.end();
        bool success = phrase_parse(iter, end, ascii::string("hoge")[cout << _1 << endl], ascii::space, result);
        if (success && iter == end) {
            cout << result << endl;
        } else {
            cout << "invalid syntax" << endl;
        }
    }
    return 0;
}

これで何回かパースしてみるとどんどんresultにも_1にもhogeが追加されていきます。while内でresult = "";としてやると直ります。おそらく1行ごとにパースするけど、結果は全体でまとめたいときに活躍するのだと思います。