PHP 정규식(PCRE)의 모든 것 - 재귀 패턴(Recursive patterns)

Recursive patterns (재귀 패턴)

무한대의 중첩 괄호를 허용하면서 괄호 안의 문자열을 일치시키는 문제를 고려해 보자. 재귀를 사용하지 않고 수행 할 수 있는 최상의 방법은 중첩의 고정된 깊이까지 일치하는 패턴을 사용하는 것이다. 임의의 중첩 깊이는 처리 할 수 없다. Perl 5.6은 정규식을 반복 할 수 있는 실험적 기능을 제공한다. 특수 항목 (?R)은 재귀의 특정 경우에 대해 제공된다.

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

이 PCRE 패턴은 괄호 문제를 해결한다(공백을 무시하도록 PCRE_EXTENDED 옵션이 설정되어 있다고 가정한다).

먼저 여는 괄호와 일치한다. 그런 다음 괄호가 아닌 시퀀스 또는 패턴 자체의 재귀 일치 (예 : 올바르게 괄호로 묶은 부분 문자열)가 될 수 있는 임의의 수의 하위 문자열을 찾는다. 마지막으로 닫는 괄호가 있다.

이 특정 예제 패턴에는 중첩된 무제한 반복이 포함되어 있으므로 일치하지 않는 문자열에 패턴을 적용 할 때 괄호가 아닌 문자열을 일치 시키는데 한 번만 사용하는 서브 패턴을 사용하는 것이 중요하다. 예를 들어 "(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa()"에 적용하면 신속하게 "일치하지 않음"을 나타낸다. 그러나 once-only 서브 패턴이 사용되지 않으면 매우 오랜 시간 동안 검사가 실행된다. + 및 *의 반복은 모든 경우의 수에 대해 실패할 때까지 테스트해야 하기 때문이다.

캡춰 서브 패턴에 설정되는 값은 서브 패턴 값이 설정되어 있는 재귀의 최외각 레벨의 값이다. 위의 패턴이 (ab(cd)ef)와 일치하면 캡처 괄호의 값은 최상위 수준에서 마지막으로 취해진 값인 "ef"이다. 추가 괄호가 추가되면 \( ( ( (?>[^()]+) | (?R) )* ) \) 다음에 캡처하는 문자열은 "ab(cd)ef" 수준 괄호 패턴에 15개 이상의 캡처 괄호가 있는 경우 PCRE는 재귀 중에 데이터를 저장하기 위해 추가 메모리를 확보해야 한다. 재귀는 pcre_malloc을 사용하여 수행 한 후 나중에 pcre_free를 통해 해제 한다. 메모리를 확보 할 수 없으면 재귀 내에서 메모리 부족 오류를 제공 할 방법이 없기 때문에 처음 15개의 캡처링 괄호에 대한 데이터만 저장한다.

(?1), (?2) 등은 재귀 서브 패턴에도 사용될 수있다. 또한 이름이 지정된 서브 패턴 (?P>name) 또는 (?P&name)을 사용할 수도 있다.

재귀적 서브 패턴 참조 (숫자 또는 이름 기준)의 구문이 참조되는 괄호 밖에서 사용되면 프로그래밍 언어의 서브 루틴처럼 작동한다. 앞의 예는 패턴 (sens|respons)e and \1ibility가 "sense and sensibility", "response and responsibility"와 일치하지만 "sense and responsibility"와는 일치하지 않는다고 지적했다. 대신에 패턴 (sens|respons)e and (?1)ibility가 사용되면 다른 두 문자열과 마찬가지로 "sense and responsibility"와 일치한다. 그러나 이러한 참조는 참조하는 서브 패턴을 따라야 한다.

문자열의 최대 길이는 정수 변수가 가질 수 있는 최대 양수이다. 그러나 PCRE는 재귀를 사용하여 서브 패턴과 무한 반복을 처리한다. 이는 사용 가능한 스택 공간이 특정 패턴으로 처리 할 수 있는 제목 문자열의 크기를 제한 할 수 있음을 의미한다.

아래의 예시는 주어진 문장이 회문(palindrome)인지를 판별하는 정규식 예시이다.

<?php
$strs = ["saippuakauppias", "A man, a plan, a canal: Panama!"];
foreach ($strs as $str) {
    if (preg_match('/^(\W* (?: (\w) (?1) \g{-1} | \w? ) \W*)$/ix', $str)) {
        printf("'%s' is a palindrome\n", $str);
    } else {
        printf("'%s' is not a palindrome\n", $str);
    }
}
// 'saippuakauppias' is a palindrome
// 'A man, a plan, a canal: Panama!' is a palindrome

다음의 예시는 중첩된 balanced text(좌우에 대칭되는 표식에 의해 둘러싸여 있는 text)를 추출하는 정규식에 대한 예시이다.

Can I use Perl regular expressions to match balanced text?

<?php
$str = <<<STR
I have some <brackets in <nested brackets> > and <another group <nested once <nested twice> > >
and that's it.
<div>sfsd</div>
STR;

$regex = '/
        (                   (?# 캡처 버퍼 1의 시작)
        <                   (?# 여는 부등호에 일치)
            (?:
                [^<>]++     (?# 부등호를 제외한 문자들이 반복, 백트래킹하지 않음)
                  |
                (?1)        (?# < 또는 > 발견, 캡처 버퍼 1을 재귀적으로 부름)
            )*
        >                   (?# 닫는 부등호에 일치)
        )                   (?# 캡처 버퍼 1의 끝)
        /ix';
preg_match_all($regex, $str, $matches);
print_r($matches);

//Array
//(
//  [0] => Array
//      (
//          [0] => <brackets in <nested brackets> >
//            [1] => <another group <nested once <nested twice> > >
//            [2] => <div>
//          [3] => </div>
//      )
//    [1] => Array
//      (
//          [0] => <brackets in <nested brackets> >
//            [1] => <another group <nested once <nested twice> > >
//            [2] => <div>
//          [3] => </div>
//      )
//)