¿Cómo detectar este patrón PCRE palíndromos?

Question

_{Esta pregunta es una demostración educativa de la utilización de búsqueda hacia delante, la referencia anidada y los condicionales en un patrón PCRE a coincidir con todos los palíndromos, incluyendo los que no pueden ser igualadas por el patrón recursiva dada en la página del manual PCRE.}

Examinar este patrón PCRE en PHP fragmento:

$palindrome = '/(?x)
^
  (?:
      (.) (?=
              .*
              (
                \1
                (?(2) \2 | )
              )
              $
          )
  )*
  .?
  \2?
$


/';

Este patrón parece detectar palíndromos, como se ve en estos casos de prueba ( ver también en ideone.com ) :

$tests = array(
  # palindromes
  '',
  'a',
  'aa',
  'aaa',
  'aba',
  'aaaa',
  'abba',
  'aaaaa',
  'abcba',
  'ababa',

  # non-palindromes
  'aab',
  'abab',
  'xyz',
);

foreach ($tests as $test) {
  echo sprintf("%s '%s'\n", preg_match($palindrome, $test), $test);  
}

Entonces, ¿cómo funciona este patrón?

---

Notas

Este patrón utiliza un referencia anidada , que es una técnica similar al utilizado en How tiene esto de Java expresiones regulares detectar palíndromos? , pero a diferencia de ese patrón de Java , no hay búsqueda hacia atrás (pero utiliza una condicional ).

Además, nota que el página PCRE hombre presenta un patrón recurrente para que coincida con algunos palíndromos:

# the recursive pattern to detect some palindromes from PCRE man page
^(?:((.)(?1)\2|)|((.)(?3)\4|.))$

La página del manual advierte que este patrón recurrente no puede detectar todos los palíndromos (ver: ¿Por qué esta expresión regular recursiva única coincidir cuando un personaje se repite 2 ⁿ - 1 veces y también en ideone.com ), pero el patrón de búsqueda hacia delante referencia anidada / positivo presentado en esta pregunta lata.

Answer 1

Let's try to understand the regex by constructing it. Firstly, a palindrome must start and end with the same sequence of character in the opposite direction:

^(.)(.)(.) ... \3\2\1$

we want to rewrite this such that the ... is only followed by a finite length of patterns, so that it could be possible for us to convert it into a *. This is possible with a lookahead:

^(.)(?=.*\1$)
 (.)(?=.*\2\1$)
 (.)(?=.*\3\2\1$) ...

but there are still uncommon parts. What if we can "record" the previously captured groups? If it is possible we could rewrite it as:

^(.)(?=.*(?<record>\1\k<record>)$)   # \1     = \1 + (empty)
 (.)(?=.*(?<record>\2\k<record>)$)   # \2\1   = \2 + \1
 (.)(?=.*(?<record>\3\k<record>)$)   # \3\2\1 = \3 + \2\1
 ...

which could be converted into

^(?: 
    (.)(?=.*(\1\2)$)
 )*

Almost good, except that \2 (the recorded capture) is not empty initially. It will just fail to match anything. We need it to match empty if the recorded capture doesn't exist. This is how the conditional expression creeps in.

(?(2)\2|)   # matches \2 if it exist, empty otherwise.

so our expression becomes

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*

Now it matches the first half of the palindrome. How about the 2nd half? Well, after the 1st half is matched, the recorded capture \2 will contain the 2nd half. So let's just put it in the end.

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*\2$

We want to take care of odd-length palindrome as well. There would be a free character between the 1st and 2nd half.

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2$

This works good except in one case — when there is only 1 character. This is again due to \2 matches nothing. So

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2?$
#      ^ since \2 must be at the end in the look-ahead anyway.