一致の動作
.NET Framework の正規表現エンジンはバックトラッキング正規表現検索エンジンであり、Perl、Python、Emacs、および Tcl で使用されているのと同じ従来型の非決定性有限オートマトン (NFA: Nondeterministic Finite Automaton) エンジンを採用しています。このエンジンは、awk、egrep、または lex に見られるような、高速であるが制限が多い、純粋な正規表現決定性有限オートマトン (DFA: Deterministic Finite Automaton) エンジンとは異なります。また、標準化されているが低速な POSIX NFA とも異なります。
3 種類の正規表現エンジン
このセクションでは、3 種類のエンジンの長所と短所を簡単に示し、.NET Framework が従来型 NFA エンジンを実装している理由について説明します。
DFA エンジンは、バックトラッキングを必要としない (つまり、同じ文字を 2 回テストすることがない) ため、線形時間で検索を実行します。このエンジンでは、想定され得る最長の文字列を確実に検索できます。しかし、DFA エンジンには限定された状態しか含まれないため、前方参照を使用してパターンを検索することはできません。また、明示的な展開形式が作成されないため、部分表現をキャプチャできません。
従来型 NFA エンジンは、最長一致バックトラッキング アルゴリズムを使用しています。このアルゴリズムでは、ある正規表現から展開できるすべての形式を特定の順序でテストし、最初に一致した文字列を採用します。NFA では、見つかった文字列用にその正規表現固有の展開形式が作成されるため、部分表現に一致する文字列、および一致する前方参照をキャプチャできます。しかし、NFA ではバックトラックが行われるため、1 つの状態に到達する経路が複数ある場合には、まったく同じ状態に何度も到達することがあり得ます。その結果、最悪の場合には指数関数的に実行速度が遅くなることがあります。NFA では、最初に見つかった文字列が採用されるため、その他の (おそらくはより長い) 一致文字列が見つからないままになる場合もあります。
POSIX NFA エンジンは従来型 NFA エンジンと似ていますが、一致する最長の文字列が見つかるまでバックトラックが継続される点が異なります。その結果、POSIX NFA エンジンは従来型 NFA よりも遅くなります。また、POSIX NFA エンジンを使用する場合は、バックトラッキング検索の順序を変更して、短い一致文字列を長い一致文字列よりも優先させることはできません。
従来型 NFA エンジンは、DFA エンジンや POSIX NFA エンジンよりも多様性があるため、プログラマに人気があります。NFA エンジンは、最悪の場合には実行速度が遅くなることもありますが、あいまいさを少なくし、バックトラッキングを制限するパターンを使用することで、一致する文字列を線形時間または多項式時間で見つけるように調整できます。
.NET Framework エンジンの機能
従来型の NFA エンジンの長所を考慮して、.NET Framework 正規表現エンジンにはプログラマがバックトラッキング エンジンを調整できるようにするため、構成体セットが組み込まれています。それらの構成体を使用すると、高速検索を実行したり、他の展開形式よりも特定の展開形式を優先させたりできます。
他にも次の機能があります。
最短一致の量指定子 (??、*?、+?、{n,m}?)。これらの量指定子は、バックトラッキング エンジンに対し、繰り返しの回数が最も少ない文字列を最初に検索するように指示します。逆に、通常の最長一致の量指定子は、繰り返し回数の最も多い文字列を最初に検索しようとします。
肯定先読み。この機能により、バックトラッキング エンジンは部分表現と一致する文字列を見つけた後で、テキスト内の同じ位置に戻ることができます。同じ位置から複数のパターンを確認しながらテキスト全体を検索する場合に便利です。
否定先読み。この機能により、部分表現に一致する文字列が見つからなかった場合だけ、表現に一致できるようになります。ある文字列を除外する表現の方が、含める表現よりも単純になることが多いため、この機能は検索を簡略化する場合に特に力を発揮します。たとえば、" non" で始まらない単語を表す表現を記述するのは簡単ではありません。
条件付き評価。この機能により、エンジンは直前の部分表現検索の結果に従って、複数の代替パターンを使用した検索を実行できます。そのため、より強力な前方参照が可能になります。たとえば、部分表現で左かっこをキャプチャした後に、右かっこを検索できます。
非バックトラッキング部分表現。最長一致部分表現とも呼ばれます。この機能により、バックトラッキング エンジンは、部分表現と最初に一致した文字列だけを確実に検索できるようになります。この場合、表現は、部分表現を含む表現とは関係ないように処理されます。この構成体を使用しない場合は、より大きな正規表現によるバックトラッキング検索時に、部分表現の動作が変化する可能性があります。
右から左への一致。この機能は、左から右ではなく右から左に向かって検索する場合や、パターンの左側ではなく右側で検索を開始した方が効果的な場合に便利です。
肯定/否定後読み。先読みと似ています。この正規表現エンジンを使用すると完全な右から左への一致を実行できるため、制限のない後読みが可能になります。