静的な正規表現

静的な正規表現とは？

みなさんは静的な正規表現をご存知だろうか。
私は初めて静的な正規表現という単語を聞いたときなんだそれと感じたのを覚えている。

しかしちょっと思考を巡らせると、簡単に言えば、
コンパイル時に構文チェックしてくれるような正規表現じゃないかという考えへ容易にたどり着くだろう。

Boost.Xpressiveは動的な正規表現とともに、そのような静的な正規表現を提供してくれるライブラリだ。
今回はそんなBoost.Xpressiveの一端を見てみようと思う。

静的な正規表現の利点

Boost.Xpressiveにおける静的な正規表現では以下のような利点がある。

• 正規表現の文法ミスがコンパイル時にわかる。
• 静的束縛によるインライン化、最適化が起こりやすい。
• 他のコード、データ、正規表現を自然に参照できる。
• 検索対象が文字列に限定されない。

以下ではそれぞれについて見ていくことにする。

正規表現の文法ミスがコンパイル時にわかる。

まずはじめに、Boost.Xpressiveが提供する動的な正規表現で文法を間違えた正規表現をコンパイルしてみる。
std::regexやboost::regexでも同じような結果が出るとは思いますが、今回はBoost.Xpressiveの紹介なので割愛します。

とりあえず、
(\d)のような正規表現を書きたいとして、間違えて(\dとしてしまった場合どうなるのか
試してみます。

動的な正規表現

#include <boost/xpressive/xpressive_dynamic.hpp>
using namespace boost::xpressive;

int main()
{
    sregex re = sregex::compile("(\d");
    return 0;
}

実行結果

libc++abi.dylib: terminating with uncaught exception of type boost::exception_detail::clone_impl<boost::xpressive::regex_error>: mismatched parenthesis

コンパイル時にはエラーが検出されませんでしたが、実行時エラーは発生しました。
本来ならば例外をきちんと捉えるべきですが、サンプルコードなので割愛しました。

次に、静的な正規表現を試してみます。
静的Xpressiveでは(\d)は(s1=_d)のように記述することになります。
数字にマッチするメタ文字\dが_dに対応します。s1は後方参照用の特殊なトークンで、後方参照しないならs1はいりません。
つまり、(?:\d)としたいならば、(_d)と記述することになります。

静的な正規表現

#include <boost/xpressive/xpressive_static.hpp>
using namespace boost::xpressive;

int main()
{
    sregex re = (s1=_d;
    return 0;
}

コンパイル結果

src/error_check.cc:6:23: error: expected ')'
    sregex re = (s1=_d;
                      ^
src/error_check.cc:6:17: note: to match this '('
    sregex re = (s1=_d;
                ^
1 error generated.

コンパイル時にきちんとチェックしてくれました！
まあ文字列ではなく、式テンプレートとして評価しているので当然っちゃ当然なのですが感動です・・

静的束縛によるインライン化、最適化が起こりやすい。

BoostのUser's Guideには以下のように記述されていました。(ちょっと変えていますがだいたい同じです。)

Static regexes are statically bound for better inlining and optimization. Static regexes require no state tables, virtual functions, byte-code or calls through function pointers that cannot be resolved at compile time.

どうも静的な正規表現はインライン化や最適化を促進するように静的束縛し、状態表や仮想関数、バイトコードや関数ポインタ呼び出しといったコンパイル時に解決できないものを必要としないそうです。

ちなみに、statically bound（静的束縛）って聞いたことある方多いのでしょうか。
あるオブジェクト指向の入門書をみると、

動的束縛: ある操作のたびに、操作のターゲットの型に基づいて正しいバージョンの操作がきちんと選択されることの保証。

とありました。継承やらポリモーフィズムに関係するようです。
ならおおまかに言えば、静的束縛はコンパイル時もしくはリンク時には操作が選択されているということでしょうか。

これもBoostのUser's Guideに書いてあった内容の受け売りなのですが、
静的な正規表現のほうが動的な正規表現よりも平均して10~15%ほど高速らしいです。
Boostのサイトにベンチマークありました。

他のコード、データ、正規表現を自然に参照できる。

サンプルその1

詳説 正規表現からサンプルもってきました。
簡単のため若干改変を加えていますがご了承ください。

カスタマイズが必要なところにマーカがつけてある手紙のテンプレートを使って、ダイレクトメールを製造するシステムがあるとする。
たとえば、次のような感じだ。

Dear =FIRST=
You have been chosen to win a brand new =TRINKET=! Free
Could you use another =TRINKET= in the =FAMILY= household?
Yes =SUCKER=, I bet you could! Just respond by ..."

この手紙を特定の宛先のために処理するためには、次のコードでフォームを埋める。

\$given = "Tom";
\$family = "Cruise";
\$letter =~ s/=FIRST=/\$given/g;
\$letter =~ s/=FAMILY=/\$family/g;
\$letter =~ s/=SUCKER=/\$given \$family/g;
\$letter =~ s/=TRINKER=/fabulous 100% genuine faux diamond;

上と同じようなことをxpressiveでもやりたいのでやってみる。

FormLetter

#include <iostream>
#include <map>
#include <boost/xpressive/xpressive.hpp>
#include <boost/xpressive/regex_actions.hpp>
using namespace boost::xpressive;

int main()
{
    std::string input = 
        "Dear =FIRST=,\n"
        "You have been chosen to win a brand new =TRINKET=! Free!\n"
        "Could you use another =TRINKET= in the =FAMILY= household?\n"
        "Yes =SUCKER=, I bet you could! Just respond by ...";

    std::map<std::string, std::string> env;
    env["FIRST"] = "Tom";
    env["FAMILY"] = "Cruise";
    env["SUCKER"] = env["FIRST"] + ' ' + env["FAMILY"];
    env["TRINKET"] = "fabulous 100\% genuine faux diamond";

    // "=ABC="のような文字列を探してenv["ABC"]で置換する。
    sregex envar = '=' >> (s1 = +upper) >> '=';
    std::string output = regex_replace(input, envar, ref(env)[s1]);

    std::cout << output << std::endl;

    return 0;
}

コメントにもあるように上のプログラムは置換対象の文字列から"=ABC="のような文字列を探し出し、env["ABC"]で置換するようなプログラムである。
ちなみに+upperは[:upper:]+を意図しています。

ここではref(env)[s1]という書式化式(formatter expression)を使用している。
ref(env)[s1]は最初の部分マッチs1をenvのキーとするということを意味している。
また、ここでのxpressive::ref()はenvへの参照を遅延してs1の置換対象が分かるまでoperator[]の評価を遅らせるために使っている。

User’s Guideによると書式化式は文字列を生成するラムダ式だそうだ。
実際、書式化式を使用している部分はC++11から入ったラムダ式を用いて以下のようにも書ける。

lambda

std::string output = regex_replace(input, envar, [&env](const smatch& what){ return env[what[1].str()]; });

ちなみに出力結果は想像通りでニヤリ。

出力結果

Dear Tom,
You have been chosen to win a brand new fabulous 100% genuine faux diamond! Free!
Could you use another fabulous 100% genuine faux diamond in the Cruise household?
Yes Tom Cruise, I bet you could! Just respond by ...

サンプルその2

いまどき珍しくはないだろうが正規表現を自己参照的にすることができる。
これにより再帰正規表現や文脈自由文法を構築することが可能になる。

以下では簡単な入れ子の括弧問題を見てみる。

入れ子の括弧

#include <iostream>
#include <vector>
#include <boost/xpressive/xpressive.hpp>
using namespace std;
using namespace boost::xpressive;

int main()
{
    sregex parentheses;
    parentheses = '(' >> *by_ref(parentheses) >> ')';

    vector<string> inputs = {"()", "(()", "((()())())"};
    for (const auto& input : inputs) {
        cout << input;

        smatch what;
        if (regex_match(input, what, parentheses)) {
            cout << " YES" << endl;
        }
        else {
            cout << " NO" << endl;
        }
    }

    return 0;
}

出力結果

() YES
(() NO
((()())()) YES

by_ref()により正規表現は別の正規表現を参照できるようになる。
今回、by_refの引数に指定されているのは自分自身なので、自己参照が起こり、再帰的表現ができるようになった。

次は文法の構築プログラムを見る。
BNFっぽく以下のように定義された文法をXpressiveでも構築したいとする。
expr = term (('+' | '-') term)*
term = factor (('*' | '/') factor)*
factor = digit+ | '(' expr ')'

数式にマッチするプログラム

#include <iostream>
#include <boost/xpressive/xpressive.hpp>
using namespace std;
using namespace boost::xpressive;

int main()
{
    sregex factor, term, expr;

    factor = +_d | '(' >> by_ref(expr) >> ')';
    term   = factor >> *((as_xpr('*') | '/') >> factor);
    expr   = term   >> *((as_xpr('+') | '-') >> term);

    string input = "foo 12+34*(56-(7+8)/9) bar";
    smatch what;
    if (regex_search(input, what, expr)) {
        cout << what[0] << endl;
    }

    return 0;
}

出力結果

12+34*(56-(7+8)/9)

おおよそわかりやすく記述できたのではないでしょうか。
'+'|'-'を表している部分がプログラム上だとas_xpr('+')|'-'となってしまっているが、これは演算子のオーバーロードを解決するため、as_xpr()を呼び出すことで正規表現で使えるようにしている。

検索対象が文字列に限定されない。

例えば、文字列ではなく数列に対しても正規表現の対象とすることができます。

数列$1^1, 2^2, 3^3, ...,9^9$から1,000以上100,000,000以下の数字を列挙せよ

ぱっと今考えた問題ですがxpressiveで解いてみます。
User's Guideによるとnull_regex_traits<>をimbueに渡すことで非文字データに対し正規表現をかますことができるようです。

正規表現の対象を数列にする。

#include <iostream>
#include <cmath>
#include <limits>
#include <algorithm>
#include <vector>
#include <boost/xpressive/xpressive.hpp>
#include <boost/xpressive/traits/null_regex_traits.hpp>
using namespace std;
using namespace boost::xpressive;

using iregex = basic_regex<vector<int>::const_iterator>;
using imatch = match_results<vector<int>::const_iterator>;

int main()
{
    vector<int> seq(9);
    int i = 0;
    generate(seq.begin(), seq.end(),[&i](){ ++i; return pow(i, i); });

    null_regex_traits<int> nul;
    iregex re = imbue(nul)(+(s1=range(1000, 100000000)));

    imatch what;
    if (regex_search(seq, what, re)){
        for (auto it = what[0].first; it != what[0].second; ++it){
            cout << *it << " ";
        }
        cout << endl;
    }

    return 0;
}

出力結果

3125 46656 823543 16777216

$1^1, 2^2, 3^3, ...,9^9 =1, 4, 9, 256, 3125, 46656, 823543, 16777216, 387420489$
なので合っているようです。

もはや無茶苦茶な感じがしますね。。パラダイムの転換レベルのことが起きているといっていいでしょう。

参考

boostのサイト
xpressiveのUser's Guide
↑の日本語訳
boost xpressive で数列に対する文法を作る

最後に

この記事を書こうと思ったのは、
PHP:正規表現が正しいかどうかチェックしたかったが、思った以上に大変だった
という記事を見かけたのがことの発端だった。

自分はPHPにはいまのところそこまで明るくないし動的型付けの言語をガッツリと業務で扱ったことがあるわけでもないが、Pythonを仕事でいくらか使用していた。
ただ、静的型付けの言語であろうと、正規表現の構文チェックは動的に行われるのが一般的だと思う。

私は昔、仕事で静的型付けの言語を使用していたが、静的型付けの言語なら正規表現の構文エラーをチェックぐらいはしてほしいと思ったのである。。

実際、そのときのプロジェクトはC++でboostが使用できる環境だったが、見た目の観点からboost::xpressiveではなくstd::regexを使用したのを覚えている。

ただ、あのとき別にXpressiveのほうでも良かったかもなと思い供養として記事に贈ることにする。

また、ここで紹介したのはBoost.Xpressiveの機能の一部にすぎず、実際にはもっとたくさんの有用な機能があるので気になったら調べてみてください。

ゆるふわな感じに記事を書こうと思ったのに意外と結構な時間がかかってしまった。
boostやら正規表現やらと、結構気を使う分野だし仕方ないが、
そもそも両方使うのはマニアック感が否めない＾＾ｂ