std.regexについて少し書いた #dlang

std.regex

今のD言語の正規表現エンジンはDmitryOlshansky 氏が書いたThompson NFAベースのものです。今年D Blogに掲載された記事では高速化の実装詳細、bit parallel法による固定文字列探索手法であるShiftOrアルゴリズムについて氏が説明しています。

今回はもう少し大枠で見ていきましょう。

D言語の正規表現エンジンは名前付きキャプチャやRangeインターフェースを扱うことができるようになっています。構文についてはこちらを参考にしてください。基本的にはECMA-262 の知識があれば問題なく使えるように設計されています。

import std.regex;
import std.stdio;

void namedCapture()
{
    auto re = regex(`(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})`);
    // writeln("バイトコード表現",  re.ir);

    auto nc = re.namedCaptures;
    writeln("名前付きキャプチャ", nc);

    auto m = matchFirst("2014-06-02", re);
    writeln("year: ", m["year"]);
    writeln("month: ", m["month"]);
    writeln("day: ", m["day"]);
}

void rangeCapture()
{
    auto re = regex(`(\d{4})-(\d{2})-(\d{2})`);
    static TO_SEARCH = "On 2010-03-14, foo happened. On 2014-10-14, bar happened.";

    foreach (caps; matchAll(TO_SEARCH, re))
    {
        writefln("year: %s, month: %s, day: %s", caps[1], caps[2], caps[3]);
    }
}

void main()
{
    namedCapture();
    rangeCapture();
}

regex 関数で正規表現オブジェクトの作成を行っています。正規表現オブジェクトの実体はバイトコードで、uint型の変数にIR表現とデータを格納したバイト列が並んでいます。

matchAll で正規表現マッチングを行います。入力文字列を先頭からみていって正規表現オブジェクトとつきあわせて内部で状態遷移を行っていっています。Thompson NFAはバックトラックがないので入力文字列は一度しかみることはありません。

特徴

ctRegex! コンパイル時正規表現オブジェクト生成

D言語の正規表現最大の特徴はなんといってもコンパイル時正規表現オブジェクト生成でしょう。ループの中で同一の正規表現オブジェクトを使うときでもそのまま使うことができます。

雑なコード

void innerLoopFunction()
{
    auto r = ctRegex!`...`;  // コンパイル時に正規表現がコンパイルされる!!
}
...
    foreach (i; 0 .. 10e7)
        innerLoopFunction();
...

matchに比べると軽い処理ですが、それでも正規表現オブジェクト生成はそれなりに重い処理となります。ループ内で毎回生成するとあほみたいにパフォーマンスが悪くなります。グローバル変数にするとか関数の引数に渡すとか回避策はありますが、コンパイル時生成のほうが素直に、そして実行時コスト0で書くことができます。

さいごに

特徴って１個しか書いてない。。

あと私は正規表現の専門家でもなんでもないので間違った知識でものを語っているかもしれません。その際はコメントもしくは編集リクエストなどで指摘よろしくお願いします。