Comment ce modèle de PCRE détecter palindromes?

Question

  

_{Cette question est une démonstration pédagogique de l'utilisation de préanalyse, référence imbriquée, et les conditions dans un modèle de PCRE pour répondre à toutes les palindromes, y compris ceux qui ne peuvent pas être abondés par le modèle récursive dans la page de manuel de PCRE.}

Examinez ce modèle de PCRE en PHP Snippet:

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


/';

Ce modèle semble détecter palindromes, comme on le voit dans ce cas de test ( Voir aussi sur 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);  
}

Alors, comment fonctionne ce modèle?

---

Remarques

Ce modèle utilise un de référence imbriquée, qui est une technique similaire à celle utilisée dans How ce ne Java regex détecter palindromes? , mais contrairement à ce modèle Java , il n'y a pas lookbehind (mais il utilise une conditionnelle ).

En outre, notez que le PCRE page man présente un motif récurrent pour correspondre à certains palindromes:

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

La page de manuel avertit que ce modèle récursif ne peut pas détecter tous les palindromes (voir: Pourquoi cette regex récursive ne correspond quand un personnage répète 2 ⁿ - 1 fois et aussi ideone.com ), mais le motif de référence imbriquée / positif présenté dans préanalyse cette boîte question.

Answer 1

L'essai Let de comprendre la regex en le construisant. Tout d'abord, un palindrome doit commencer et finir avec la même séquence de caractères dans le sens opposé:

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

nous voulons réécrire ce de telle sorte que la ... n'est suivie d'une longueur finie de motifs, de sorte qu'il pourrait être possible pour nous de le convertir en un *. Ceci est possible avec un test avant:

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

mais il y a encore des parties hors du commun. Et si nous pouvons « enregistrer » les groupes capturés précédemment? S'il est possible que nous pourrions réécrire comme:

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

qui pourrait être convertie en

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

Presque bon, sauf que \2 (la capture enregistrée) n'est pas vide au départ. Il échouerait à tout match. Nous en avons besoin pour correspondre à vide si la capture enregistrée n'existe pas. Ceci est la façon dont la chair de poule d'expression conditionnelle dans.

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

donc notre expression devient

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

Maintenant, il correspond à la première moitié de la palindrome. Que diriez-vous de la 2ème mi-temps Eh bien, après la 1ère mi-temps est adaptée, la \2 de capture enregistré contiendra le 2ème semestre. Donc, nous allons mettre juste à la fin.

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

Nous voulons prendre soin de palindrome de longueur impaire ainsi. Il y aurait un caractère libre entre le 1er et le 2ème semestre.

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

Cela fonctionne bien sauf dans un cas - quand il n'y a que 1 caractère. Ceci est à nouveau en raison de matchs \2 rien. Donc,

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