In che modo questo pattern PCRE rileva i palindromi?

Questa domanda è una dimostrazione educativa dell'uso di lookahead, riferimento annidato e condizionali in un model PCRE per corrispondere a tutti i palindromi, compresi quelli che non possono essere confrontati con il model ricorsivo indicato nella pagina man di PCRE.

Esamina questo pattern PCRE nello snippet di PHP:

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

Questo model sembra rilevare palindromi, come si è visto in questo caso ( vedi anche su ideone.com ):

 $tests = arrays( # 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); } 

Quindi, come funziona questo schema?


Gli appunti

Questo model usa un riferimento annidato , che è una tecnica simile usata in Come questa regex Java rileva i palindromi? , ma a differenza di quel pattern Java, non c'è alcun lookbehind (ma usa un condizionale ).

Inoltre, si noti che la pagina man di PCRE presenta uno schema ricorsivo per abbinare alcuni palindromi:

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

La pagina man avverte che questo pattern ricorsivo NON può rilevare tutti i palindromi (si veda: Perché questa espressione regiustiva ricorsiva corrisponde solo quando un personaggio ripete 2 n – 1 volte? E anche su ideone.com ), ma il model nidificato di riferimento / aspetto positivo presentato in questa domanda può.

Proviamo a capire la regex costruendola. Innanzitutto, un palindromo deve iniziare e terminare con la stessa sequenza di caratteri nella direzione opposta:

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

vogliamo riscrivere questo in modo tale che il ... sia seguito solo da una lunghezza finita di pattern, in modo che sia ansible per noi convertirlo in un * . Questo è ansible con un lookahead:

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

ma ci sono ancora parti non comuni. Cosa succede se possiamo "registrare" i gruppi precedentemente catturati? Se è ansible potremmo riscriverlo come:

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

che potrebbe essere convertito in

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

Quasi buono, tranne che \2 (l'acquisizione registrata) non è inizialmente vuoto. Non riuscirà a eguagliare nulla. Ne abbiamo bisogno per abbinare vuoto se l'acquisizione registrata non esiste. Ecco come si insinua l'espressione condizionale.

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

così la nostra espressione diventa

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

Ora corrisponde alla prima metà del palindromo. Che ne dici del 2 ° semestre? Bene, dopo che il primo tempo è stato abbinato, l'acquisizione registrata \2 conterrà la seconda metà. Quindi mettiamola alla fine.

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

Vogliamo prenderci cura anche del palindromo di lunghezza dispari. Ci sarebbe un personaggio libero tra il 1 ° e il 2 ° tempo.

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

Funziona bene tranne in un caso – quando c'è solo 1 carattere. Questo è di nuovo dovuto al fatto che \2 non corrisponde a nulla. Così

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