php - sola - ¿Cómo este patrón PCRE detecta los palíndromos?

poemas palindromos

Question

_{Esta pregunta es una demostración educativa del uso de lookahead, referencia anidada y condicionales en un patrón de PCRE para que coincida con TODOS los palíndromos, incluidos los que no se pueden hacer coincidir con el patrón recursivo dado en la página de manual de PCRE.}

Examine este patrón de PCRE en el fragmento de PHP:

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

Este patrón parece detectar palíndromos, como se ve en los casos de prueba ( vea 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 usa una referencia anidada , que es una técnica similar que se usa en ¿Cómo esta expresión regular de Java detecta los palíndromos? , pero a diferencia de ese patrón de Java, no hay ningún aspecto por detrás (pero sí usa un conditional ).

Además, tenga en cuenta que la página de manual de PCRE presenta un patrón recursivo 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 recursivo NO puede detectar todos los palíndromos (consulte: ¿Por qué este regex recursivo solo coincidirá cuando un personaje se repita 2 ⁿ - 1 veces? Y también en ideone.com ), pero se presenta el patrón de referencia / aspecto positivo anidado en esta pregunta puede

Answer 1

Intentemos entender la expresión regular construyéndola. En primer lugar, un palíndromo debe comenzar y terminar con la misma secuencia de caracteres en la dirección opuesta:

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

queremos volver a escribir esto de modo que ... solo sea seguido por una longitud finita de patrones, para que podamos convertirlo en un * . Esto es posible con un lookahead:

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

Pero todavía hay partes poco comunes. ¿Qué pasa si podemos "grabar" los grupos capturados anteriormente? Si es posible podríamos reescribirlo como:

^(.)(?=.*(?<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
...

que podria ser convertido en

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

Casi bueno, excepto que /2 (la captura grabada) no está vacía inicialmente. Simplemente no podrá coincidir con nada. Necesitamos que coincida con vacío si la captura grabada no existe. Así es como se arrastra la expresión condicional.

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

así nuestra expresión se convierte en

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

Ahora coincide con la primera mitad del palíndromo. ¿Qué tal la segunda mitad? Bueno, después de que la primera mitad coincida, la captura grabada /2 contendrá la segunda mitad. Así que vamos a ponerlo al final.

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

También queremos cuidar el palíndromo de longitud irregular. Habría un personaje libre entre la 1ª y 2ª mitad.

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

Esto funciona bien, excepto en un caso, cuando solo hay 1 carácter. Esto se debe de nuevo a que /2 no coincide con nada. Asi que

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