Regex

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。言語はライブラリが命。ということでライブラリの使い方編。

今回は Regex、つまり正規表現です。

参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
  - 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
  - Pull Request 等お待ちしております。

正規表現も普通に入ってて欲しいライブラリのひとつ。プログラム基礎・データ型で一度説明している内容と重複するものが多いが、独立させて記載しておきます。

正規表現について

ここでは正規表現の細かい内容には触れないが、簡単に言えばパターンマッチのこと。パターンの書き方を覚えればテキスト処理はほぼ何でもできる。Kinx では Oniguruma を使わせて頂きました。

オートマトン

DFA、NFA、従来型 NFA、POSIX NFA について（エンジンな話）

正規表現の実装の中身は有限オートマトンと言って、状態遷移マシンとなっている。有限オートマトンには DFA（決定性）か NFA（非決定性）の 2 種類があり、grep なんかは DFA で動く。DFA の方が速い。が、後方参照とかあんまり凝ったことはできない。

DFA を作るにも、一旦 NFA を作ってから DFA に変換するので、凝った作りの正規表現エンジンはだいたい NFA を作ったら NFA のまま実行させる。NFA エンジンでは、マッチしなかった場合、マッチしてたところまで戻って再探索する（これをバックトラッキングという）。NFA にも従来型 NFA と POSIX NFA というのがあり、POSIX NFA の場合はマッチしたものの中で最長のものを返す。従来型 NFA マッチでは、最初に見つかったものを返す。なので POSIX NFA の場合、1 つ見つかっただけでは探索を止めない、という違いがある。

オートマトンは数学的でやってて 面白い ので、正規表現ライブラリを自分で作ってみるのもおススメ。最終的には言語インタプリタみたいな感じになったりする（文法解釈して実行、つまり小さな言語処理系とも考えられますからね）。NFA には ε 遷移という入力なしに遷移する状態があるので「非決定性」と呼ばれる。ε 遷移の際に複数の状態を取り得るので分岐が入り、マッチしなかった際に巻き戻ってバックトラッキングが発動するイメージ。

ということで、本題。

Oniguruma は恐らく従来型 NFA エンジン。「おそらく」というのはパターンの書き方によっていくつか最適化されているような感じだったので。

Regex

やっと Regex。

サポート正規表現

Oniguruma の正規表現はすべてサポート。以下を参照のこと。

https://github.com/kkos/oniguruma/blob/master/doc/RE.ja

正規表現リテラル

正規表現リテラルは以下のようにスラッシュ（/）で囲われた文字列オブジェクトで、この中では / 以外、例えば改行コードなどにエスケープを行う必要はない。

/ab+[\t\n]/

これは以下と同じ意味。下の書き方の場合、改行などもエスケープしなくてはならない。Raw 文字列の書き方であればエスケープはしなくてよい。

new Regex("ab+[\\t\\n]");  // same as /ab+[\t\n]/
new Regex(%|ab+[\t\n]|);   // same as /ab+[\t\n]/

正規表現オブジェクトとして、/ の記号を変更したい場合は、%m プレフィックスを付けて任意の記号を利用可能。使用した記号以外はエスケープする必要がない。このとき、Raw 文字列とは違って本当に正規表現文字列で使っていない文字は全て使えるので、次のような書き方もできる（できたほうが良いのかは別）。

%m1ab+[\t\n]1  // same as /ab+[\t\n]/

もちろん、カッコを使う場合は対応する閉じカッコで対応させるように記述する。

%m<ab+[\t\n]>  // same as /ab+[\t\n]/
%m(ab+[\t\n])  // same as /ab+[\t\n]/

`=~` 演算子

左辺値、右辺値のいずれかに正規表現オブジェクトを取り、反対側で指定された文字列に対してマッチングを行う。復帰値は、マッチしなかった場合は false、マッチした場合はキャプチャ・オブジェクトへの配列が返される。キャプチャ・オブジェクトおよびその配列は以下の構造をしている。最初の要素はマッチした文字列全体を表す。

[
    {
        string: "マッチした文字列（マッチ全体）",
        begin: n0,  // マッチした文字列の開始位置（0～）
        end:   m0,  // マッチした文字列の終了位置（1～）
    },
    {
        string: "マッチした文字列（キャプチャ1）",
        begin: n1,  // マッチした文字列の開始位置（0～）
        end:   m1,  // マッチした文字列の終了位置（1～）
    },
    ...
]

begin と end はマッチした文字列の元文字列内での位置であり、[n, m) を意味する。=~ 演算子でループする例は以下の通り。

var a = "111/aaa/bbb/ccc/ddd";
while (group = (a =~ /\w+\//)) {
    for (var i = 0, len = group.length(); i < len; ++i) {
        System.println("found[%2d,%2d) = %s"
            % group[i].begin
            % group[i].end
            % group[i].string);
    }
}

結果。

found[ 0, 4) = 111/
found[ 4, 8) = aaa/
found[ 8,12) = bbb/
found[12,16) = ccc/

`!~` 演算子

マッチしない ことを判定する。復帰値は true/false。

var s = "XYZXYZ";
if (s !~ /ABC/) {
    System.println("ABC is not included.");
}

結果。

ABC is not included.

文字列メソッドへの適用

正規表現オブジェクトは、文字列に対する以下のメソッドの条件として使用できる。

replace

replace ... 変換元の文字列を正規表現で指定することが可能。

var s = "xabbbbbcabbc".replace(/ab+/, ",");
System.println(s);

結果。

x,c,c

split

split ... 区切り文字列を正規表現で指定することが可能。

var s = "xabbbbbcabbc".split(/ab+/);
s.each(&(e) => System.println(e));

結果。

x
c
c

正規表現リテラルに対する注意

正規表現リテラルを while 等の条件式に入れることができるが注意点がある。

例えば以下のように記述した場合、str の文字列に対してマッチしなくなるまでループを回すことができる（group にはキャプチャ一覧が入る）が、最後のマッチまで実行せずに途中で break 等でループを抜けると正規表現リテラルの対象文字列が次回のループで正しくリセットされない、という状況が発生する。

while (group = (str =~ /ab+/)) {
    /* block */
}

正規表現リテラルがリセットされるタイミングは以下の 2 パターン。

初回（前回のマッチが失敗して再度式が評価された場合を含む）。
str の内容が変化した場合。

将来改善を検討するかもしれないが、現在は上記の制約があることに注意。最後までループが回った場合（見つからない状態までループした場合）は問題ない。

おわりに

正規表現はテキスト処理に必須。正規表現くらいサポートしておかないと誰も使ってくれませんね。昔、自分で正規表現ライブラリを作ったりもしたことはありました（Boost よろしくヘッダだけで組み込める C++ 版 NFA エンジンなど）が、Oniguruma は非常に高機能だし、これを置き換えるほどのエンジンを作る、かつ品質を確保するのは至難の業なので、これを使うのがベストな選択でしょう。

ではまた次回。

Kinx ライブラリ - Regex（正規表現）

Regex

はじめに

正規表現について

オートマトン

Regex

サポート正規表現

正規表現リテラル

=~ 演算子

!~ 演算子

文字列メソッドへの適用

replace

split

正規表現リテラルに対する注意

おわりに

`=~` 演算子

`!~` 演算子