このチュートリアルの以前のトピックでは、正規表現の再帰と正規表現のサブルーチンの呼び出しについて説明しています。このトピックでは、「再帰」という単語は、正規表現全体の再帰、キャプチャグループの再帰、およびキャプチャグループへのサブルーチンの呼び出しを指します。

PerlとRubyは、再帰後の正規表現の残りの部分がマッチに失敗した場合、再帰にバックトラッキングします。正規表現の残りの部分がマッチするように、必要に応じて再帰のすべての順列を試行します。PCREは、再帰をアトミックとして扱います。PCREは再帰中に通常通りバックトラッキングしますが、再帰がマッチした後は、正規表現の残りの部分がマッチに失敗した場合でも、再帰の他の順列を試行しません。その結果、PerlとRubyはPCREでは見つからない正規表現のマッチを見つける可能性があり、またはPerlとRubyで異なる正規表現のマッチが見つかる可能性があります。

次の正規表現を考えてみましょう。aa$|a(?R)a|aPerlの場合、または同等のaa$|a\g'0'a|aRuby 2.0の場合。PCREはどちらの構文もサポートしています。Perl、Ruby、およびPCREが、この正規表現のマッチングプロセスをどのように実行するのかを見てみましょう。対象文字列がaaaの場合です。

最初の選択肢aa$は、アンカーが文字列の2番目と3番目のaの間にマッチできないため失敗します。文字列の先頭で2番目の選択肢を試行すると、aがマッチします。ここで正規表現エンジンは最初の再帰に入ります。a再帰内では、最初の選択肢は文字列の2番目と3番目の

aaにマッチします。正規表現エンジンは、成功した再帰を終了します。しかし、ここで続くaa(?R)または\g'0'は、正規表現エンジンが既に文字列の終わりに達しているため、マッチに失敗します。したがって、正規表現エンジンはバックトラッキングする必要があります。ここでPCREはPerlやRubyとは異なる動作をします。

PerlとRubyは、再帰内で正規表現が2番目の選択肢にマッチし、3つの選択肢があることを覚えています。PerlとRubyは再帰内にバックトラッキングします。再帰内の2番目の選択肢がバックトラッキングされ、これまでのマッチが文字列の最初のaaaに減少します。次に、3番目の選択肢が試行されます。aは文字列の2番目のaa(?R)または\g'0'aaにマッチします。正規表現エンジンは、同じ再帰から再び正常に終了します。今回は、正規表現のaaaa

が文字列の3番目のaにマッチします。aが全体のマッチとして見つかりました。a一方、PCREは、文字列の最後にaがマッチします。ここで正規表現エンジンは最初の再帰に入ります。aaa

にマッチしたことを除いて、再帰について何も覚えていません。PCREは再帰上でバックトラッキングし、これまでのマッチを文字列の最初のaに減少させます。しかし、これにより、正規表現の2番目の選択肢には、試行できる他の順列がなくなります。したがって、2番目の選択肢の先頭のaもバックトラッキングされ、これまでのマッチは何もなくなります。PCREは文字列の先頭で3番目の選択肢を使用してマッチの試行を続け、文字列の先頭の

aを見つけます。PCREでは、これが全体のマッチです。アトミックグループを追加することで、PerlとRubyの再帰をアトミックにすることができます。

aa$|a(?>(?R))a|a

Perlの場合、および

aa$|a(?>\g'0')a|a

Rubyの場合、PCREの元の正規表現と同じです。JGsoft V2では、再帰をアトミックにするかどうかを選択できます。アトミックな再帰はパフォーマンスが向上しますが、上記のように特定のマッチが除外されたり、異なるマッチが見つかったりする可能性があります。aa$|a(?P>0)a|a?はJGsoft V2ではアトミックです。この再帰の構文はアトミックグループと同様に山括弧を使用しているため、覚えやすいでしょう。番号付きまたは名前付きのキャプチャグループへのアトミックサブルーチンの呼び出しには、ゼロの代わりに数字または名前を使用できます。JGsoft V2では、それ以外の再帰の構文はアトミックではありません。Boostは二つの考え方を持っています。PCREと同様に、正規表現全体の再帰はBoostではアトミックです。しかし、BoostはPerlのように、サブルーチンの呼び出しとキャプチャグループの再帰にバックトラッキングします。したがって、正規表現全体をキャプチャグループでラップし、それを呼び出すことで、Boostで非アトミックな再帰を行うことができます。PCRE2は元々PCREのように動作し、すべての再帰とサブルーチンの呼び出しをアトミックとして扱っていました。PCRE2 10.30ではこれが変更され、Perlにより近づこうとしましたが、Boostのようなものになりました。PCRE2 10.30は、Perlのように、サブルーチンの呼び出しとキャプチャグループの再帰にバックトラッキングします。しかし、PCRE2はまだ正規表現全体の再帰にバックトラッキングすることはできません。以下の例では、「PCRE」は元のPCREのみを意味します。PCRE2 10.22以前はPCREの例に従ってください。PCRE2 10.30以降はPerlの例に従ってください。PerlとRubyにおける任意の長さの回文再帰とキャプチャグループに関するトピックでは、回文（文字数が奇数のもの）にマッチする正規表現について説明しています。解決策は些細なように見えます。

\b(?'word'(?'letter'[a-z])(?&word)\k'letter'|[a-z]?)\bはPerlでうまく機能します。量子化子は、回文の中央の文字にマッチする[a-z]をオプションにします。Rubyでは、\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\b, \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bを使用できます。これは、バックリファレンスの再帰レベルを指定するソリューションに同じ量子化子を追加します。PCREでは、Perlのソリューションは奇数長の回文にはまだマッチしますが、偶数長の回文にはマッチしません。[a-z]これらの正規表現がどのようにマッチするか、またはマッチに失敗するのかを見てみましょう。[a-z]deed

PCREは、元の正規表現と同様に、PerlとRubyと同じように開始します。「letter」グループは?d[a-z]にマッチします。3回の連続した再帰で、グループは\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\be[a-z]、および\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\be

をキャプチャします。4回目の再帰は失敗します。マッチする文字がなくなっているためです。3回目の再帰に戻ると、最初の選択肢がバックトラッキングされ、2番目の選択肢は文字列の最後の\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bd[a-z]にマッチします。エンジンは、成功したマッチで3回目の再帰を終了します。2回目の再帰に戻ると、バックリファレンスは失敗します。文字列に残りの文字がなくなっているためです。\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bここで動作が異なります。PerlとRubyは3回目の再帰内にバックトラッキングし、2番目の選択肢をオプションにする量子化子をバックトラッキングします。3回目の再帰では、2番目の選択肢は文字列の最後にマッチした[a-z]d

を放棄します。エンジンは、今回は長さ0の成功したマッチで3回目の再帰を再び終了します。2回目の再帰に戻ると、バックリファレンスは依然として失敗します。グループは2回目の再帰用に\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\be

をキャプチャします。4回目の再帰は失敗します。マッチする文字がなくなっているためです。3回目の再帰に戻ると、最初の選択肢がバックトラッキングされ、2番目の選択肢は文字列の最後の\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bd[a-z]e\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bを格納しましたが、文字列の次の文字は[a-z]d\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bです。したがって、最初の選択肢がバックトラッキングされ、2番目の選択肢は文字列の2番目の[a-z]d

にマッチします。2回目の再帰は成功して終了します。

1回目の再帰では、バックリファレンスは再び失敗します。グループは1回目の再帰用に

\b(?'word'
  (?'oddword' (?'oddletter' [a-z])(?P>oddword)  \k'oddletter' |[a-z])
| (?'evenword'(?'evenletter'[a-z])(?P>evenword)?\k'evenletter')
)\b

基本的に、これは元の正規表現の2つのコピーをオルタネーション（選択）で組み合わせたものです。最初の選択肢では、「word」と「letter」のグループ名が「oddword」と「oddletter」に変更されています。2番目の選択肢では、「word」と「letter」のグループ名が「evenword」と「evenletter」に変更されています。(?P>evenword)の呼び出しは、オルタネーション|[a-z]の代わりに、疑問符を使用してオプション化されています。「word」という新しいグループは、「oddword」と「evenword」の2つのグループを組み合わせることで、単語境界が正規表現全体に適用されるようにしています。

この正規表現の最初の選択肢「oddword」は、「radar」のような奇数長の回文に一致します。radarこれは、「再帰とキャプチャグループ」に関するトピックで説明した正規表現とまったく同じ方法です。新しい正規表現の2番目の選択肢は、決して試行されません。

文字列が「kayak」のような偶数長の回文の場合、新しい正規表現は最初に最初の選択肢のすべての順列を試みます。「evenword」という2番目の選択肢は、最初の選択肢が一致を見つけるのに失敗した後にのみ試行されます。はPerlでうまく機能します。量子化子kayak

2番目の選択肢は、元の正規表現と同じ方法で始まります。「evenletter」グループは[a-z]をオプションにします。Rubyでは、\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\b, \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bを使用できます。これは、バックリファレンスの再帰レベルを指定するソリューションに同じ量子化子を追加します。PCREでは、Perlのソリューションは奇数長の回文にはまだマッチしますが、偶数長の回文にはマッチしません。[a-z]に一致します。4回目の再帰は、一致させる文字が残っていないため失敗します。3回目の再帰に戻ると、正規表現エンジンは再帰呼び出し(?P>evenword)?がオプションであることに気付きます。その後ろ参照\k'evenletter'に進みます。文字列に文字が残っていないため、後ろ参照は失敗します。再帰にはさらに試行する選択肢がないため、バックトラックされます。「evenletter」グループは最新のマッチを放棄し、PCREは失敗した3回目の再帰から終了します。

2回目の再帰では、その再帰中にキャプチャグループが\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bに一致したため、文字列の次の文字が[a-z]であるため、後ろ参照は失敗します。グループは別のマッチを放棄し、PCREは失敗した2回目の再帰から終了します。

1回目の再帰に戻ると、後ろ参照は成功します。その再帰中にグループは文字列の先頭の\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z]?)\bに一致し、後ろ参照は2番目の文字に一致します。PCREは成功した1回目の再帰から終了します。

全体的なマッチングの試行に戻ると、後ろ参照は再び成功します。グループは文字列の先頭で[a-z]に一致し、後ろ参照は最後の[a-z]に一致します。「evenword」と「word」のグループから抜けると、単語境界は文字列の最後に一致します。はPerlでうまく機能します。量子化子が全体的なマッチとなります。