再帰的パターン

どうすればカッコに括られた文字列とマッチできるか、という問題を 考えて見ましょう。このとき、カッコは何回でもネストできるとします。 再帰が使えないとすると、パターンを用いて、せいぜい、ある一定の深さの ネストまでしかマッチできないでしょう。任意の深さのネストを 処理することは不可能です。Perl 5.6 では、正規表現において再帰を行う 実験的な機能が導入されています。 PCRE では、再帰という特殊なケースに対して専用のシーケンス (?R) が導入されました。上記のカッコ問題を解決する PCRE のコードは 以下のようになります（PCRE_EXTENDED オプションが設定され空白文字が無視されると仮定）。

      \( ( (?>[^()]+) | (?R) )* \)
      

まず、このパターンは開きカッコにマッチします。続いて、 カッコ以外の文字が並んでいるか、または、再帰的にパターン自体に マッチする（すなわち正しくカッコで括られている）かする部分文字列に 何回でもマッチします。最後に閉じカッコにマッチします。

このパターン例には、ネストした無制限の繰り返しが含まれているため、 マッチが成功し得ない文字列に対してこのパターンが適用される場合も考えて、 カッコ以外の文字列にマッチングさせる部分に再試行無しのサブパターンを 使うことが重要です。例えば、このパターンを

      (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa()
      

という文字列に適用すると、「マッチしない」という判定が速やかに 行われます。しかし、再試行無しのサブパターンを使わないと、 対象文字列を分割し得る + と * の繰り返し数の種類が非常に多く、 そのすべてが確認された後にマッチの失敗が報告されるため、 マッチングに非常に時間がかかります。

キャプチャ用サブパターンにセットされる値は、そのサブパターンに 値がセットされ得る最も外側で最も後の再帰レベルからのものになります。 上記のパターンを

      (ab(cd)ef)
      

にマッチングさせると、キャプチャされる値は "ef" であり、 最上位レベルの最後の値です

      \( ( ( (?>[^()]+) | (?R) )* ) \)
      

次のようにカッコを追加すると、キャプチャされる文字列は、"ab(cd)ef" となり、最上位レベルのカッコの中身となります。一つのパターン中に 15 以上のキャプチャ用サブパターンを用いると、PCRE は 再帰を行っている間のデータ保存用に追加の記憶領域を確保する必要が あります。記憶領域が確保できない場合、メモリ不足エラーを再帰の内側から 出力する手段がないため、最初の 15 個のキャプチャ用サブパターンに ついてのみデータが保存されます。

(?1), (?2) といった記法が 再帰的サブパターンとして使用可能です。 (?P>name) あるいは (?&name) といった名前付きのサブパターンも使用可能です。

この再帰的サブパターンの記法は（数字によるものも名前によるものの双方とも） 参照するカッコの外で使用でき、プログラム言語のサブルーチンの様に処理されます。 前に示した例で、パターン (sens|respons)e and \1ibility は "sense and sensibility" および "response and responsibility" にはマッチしますが "sense and responsibility" にはマッチしませんでした。 一方、パターン (sens|respons)e and (?1)ibility は、 上記 2 つに加え "sense and responsibility" にもマッチします。 ただし、参照先のサブパターンの後に記述する必要があります。

対象文字列の最大の長さは、integer 型の最大の値となります。 しかし、PCRE は再帰を使用してサブパターンの処理や繰り返し処理を行います。 つまり、そのパターンで処理する対象文字列の長さによって、 使用可能なスタック空間の大きさが制限されるということです。