Pourquoi cette regex récursive ne correspond quand un personnage se répète 2 ^ n - 1 fois?

Question

Après avoir lu polygenelubricants 'de les séries d'articles sur les techniques d'expressions régulières avancées (notamment How ce ne Java regex détecter palindromes? ), je décide de tenter de créer ma propre PCRE regex pour analyser un palindrome, en utilisant la récursivité (en PHP).

Qu'est-ce que je suis venu avec était:

^(([a-z])(?1)\2|[a-z]?)$

Ma compréhension de cette expression est qu'il doit soit correspondre à zéro ou un caractère (chaque chaîne de moins de 2 caractères est implicitement un palindrome, ainsi que pour tenir compte des palindromes avec des longueurs impaires dans la récursion), ou deux des même caractère séparé par une récursion du motif.

Malheureusement, il ne semble pas fonctionner de cette façon, comme vous pouvez le voir à www.ideone.com/ a9T3F . Au lieu de cela, seules les chaînes de 2 ⁿ - 1 (.-À-dire une chaîne vide, a, aaa, aaaaaaa, a ¹⁵ ) caractères répétés correspondent à la expression régulière.

Bizarrement, si je modifie mon modèle afin que la récursion est en option (ie. ^(([a-z])(?1)?\2|[a-z]?)$, voir www.ideone. com / D6lJR , elle correspond uniquement les chaînes avec un caractère répété 2 ⁿ fois (ie. chaîne vide, a, aa, aaaa, aaaaaaaa, a ¹⁶ ).

Pourquoi mon regex ne fonctionne pas la façon dont je pense à?

Note pour les gens qui sont des démangeaisons à suggérer de ne pas utiliser regex: Le point de cette question est d'apprendre à utiliser des expressions régulières récursives correctement. Je sais que ce n'est pas un moyen efficace de déterminer si une chaîne est un palindrome, et je ne voudrais pas utiliser une expression régulière récursive si pour une raison quelconque, je devais déterminer palindromes dans le code de production; Je suis simplement intéressé à en apprendre davantage sur les aspects avancés de regex.

Answer 1

Le phénomène vous observez est dû au fait que PCRE récursion est atomique subpattern, contrairement à Perl. La page de manuel couvre effectivement ce problème en détail:

  

Dans PCRE (comme Python, mais contrairement à Perl), un appel récursif est subpattern    toujours traité comme un groupe atomique . C'est, une fois qu'il a adapté quelques-uns des   la chaîne de sujet, il est jamais re-saisie, même si elle contient non éprouvée   alternatives et il y a un échec de correspondance ultérieure .

     

Ceci peut être illustré par le schéma de ce qui suit, qui est censé correspondre à une chaîne palindromique qui contient un nombre impair de caractères (par exemple,   "a", "aba", "abcba", "abcdcba"):

    ^(.|(.)(?1)\2)$

     

L'idée est qu'il correspond soit à un seul caractère, ou deux identiques   caractères entourant un sous-palindrome. En Perl, ce modèle fonctionne;   PCRE n'a pas si le motif est plus de trois caractères .

     

Considérons la chaîne sujet "abcba":

     

Au niveau supérieur, le premier caractère est mis en correspondance, mais comme il est pas   la fin de la chaîne, la première défaillance de remplacement; la seconde variante   est pris et les coups de pied de récursion. L'appel récursif à 1 subpattern   matchs avec succès le caractère suivant ("b"). (Notez que le début   et à la fin des tests de ligne ne font pas partie de la récursion).

     

Retour au niveau supérieur, le caractère suivant ("c") est comparé à ce que   2 sous-motif adapté, qui a été "a". Cela échoue. Parce que la récursion   est considéré comme un groupe atomique, il y a maintenant pas de points backtracking,   et si l'ensemble échoue partie. (Perl est en mesure, à ce stade, de re-   entrer dans la récursivité et essayer la seconde alternative.) Toutefois, si la   modèle est écrit avec les solutions de rechange dans l'autre ordre, les choses sont   différent:

    ^((.)(?1)\2|.)$

     

Cette fois-ci, l'alternative récursion est d'abord essayé, et continue à   récursif jusqu'à ce qu'il court de caractères, à quel point la récursion   échoue. Mais cette fois-ci nous avons une autre alternative pour essayer à la   niveau supérieur. Telle est la grande différence: dans le cas précédent, le   restant alternative est à un niveau plus profond de récursivité, qui PCRE ne peut pas utiliser.

     

Pour modifier le modèle de façon qui correspond à toutes les chaînes palindromes, non seulement   ceux qui ont un nombre impair de caractères, il est tentant de changer la   motif à ceci:

    ^((.)(?1)\2|.?)$

     

Encore une fois, cela fonctionne en Perl, mais pas dans PCRE, et pour la même raison .   Quand un récursion plus profond a égalé un seul caractère, il ne peut pas être   entré à nouveau afin de faire correspondre une chaîne vide. La solution consiste à   séparer les deux cas, et d'écrire les cas bizarres et même des solutions de rechange   au niveau supérieur:

    ^(?:((.)(?1)\2|)|((.)(?3)\4|.))$

     

---

     

ATTENTION !!!

     

Les motifs palindrome-correspondants ci-dessus travail que si la chaîne sujet ne démarre pas avec un palindrome qui est plus courte que la   chaîne entière. Par exemple, bien que "abcba" est correctement adapté, si   le sujet est "ababa", PCRE trouve au début du "aba" palindrome,   échoue alors au plus haut niveau parce que la fin de la chaîne ne suit pas.   Encore une fois, il ne peut pas revenir en arrière dans le récursivité pour essayer d'autres alternatives,   si l'ensemble échoue partie.

Références supplémentaires

• regular-expressions.info/Atomic groupe
  • (?>…) dans une certaine saveur est le groupement atomique syntaxe
  • Lookarounds (?=…), (?!…), (?<=…), (?<!…), sont tous atomique
  • possessifs quantificateur (par exemple a*+) est également atomique
  • PCRE récursive subpattern et appelle sous-programme sont également atomique

---

Un examen plus approfondi du modèle

L'argument atomicité est correct, mais peut-être il est pas évident comment il explique pourquoi les motifs se comporte comme observé. Jetons un coup d'oeil de plus près et voir comment tout cela se:

Nous allons utiliser le premier motif:

^(([a-z])(?1)\2|[a-z]?)$

Je vais utiliser la notation suivante pour désigner la récursion:

• 1 signifie que le caractère a été capturé dans le groupe 2 dans le premier suppléant
• 2 signifie que le caractère a été compensée par le deuxième suppléant
  • Ou si le 2 ne dépasse pas un caractère, l'option zéro de répétition ? est exercé
• \ signifie que le caractère a été compensée par le backreference au groupe 2 dans la première alternative
• _ désigne le fond d'une branche récursive
  • Cette branche ne sera PAS réentrée même s'il y a d'autres alternatives!

Considérons maintenant "aaa" comme entrée:

      _
1 1 1 2 
a a a   # This is the first bottom of the recursion,
        # now we go back to the third 1 and try to match \.
        # This fails, so the third 1 becomes 2.
    _
1 1 2
a a a   # Now we go back to the second 1 and try to match \.
        # This fails, so the second 1 becomes 2.
  _
1 2
a a a   # The second level matched! now we go back to the first level...

_____
1 2 \
a a a   # Now the first 1 can match \, and entire pattern matches!!

---

Considérons maintenant "aaaaa":

          _
1 1 1 1 1 2
a a a a a  # Fifth 1 can't match \, so it becomes 2. 
        _
1 1 1 1 2
a a a a a  # Fourth 1 can't match \, so it becomes 2.
    _____
1 1 1 2 /
a a a a a  # Here's a crucial point. The third 1 successfully matched.
           # Now we're back to the second 1 and try to match \, but this fails.
           # However, since PCRE recursion is atomic, the third 1 will NOT be
           # reentered to try 2. Instead, we try 2 on the second 1.
_____
1 2 \
a a a a a  # Anchors don't match, so the first 1 becomes 2, and then also the
           # anchors don't match, so the pattern fails to match.

Notez qu'une fois un matches de niveau de récursivité sur la première alternative, la seconde alternative ne sera pas tenté à l'avenir (même si cela peut entraîner un peut correspondre), car PCRE récursion subpattern est atomique.

---

Considérons maintenant "aa":

    _
1 1 2 
a a
  _
1 2
a a  # The second level matched by taking the one repetition option on ?.
     # We now go back to the first level, and we can't match \.
     # Since PCRE recursion is atomic, we can't go back to the second level
     # to try the zero repetition option on ?.
_    
2
a a  # Anchors don't match, trying zero option on ? also doesn't help,
     # so the pattern fails to match!

Notez qu'une fois un matches de niveau de récursivité sur une répétition du ? sur la seconde alternative, l'option zéro de répétition ne sera pas tentée dans l'avenir (même si cela peut entraîner un peut correspondre), parce que PCRE récursion subpattern est atomique.

---

Considérons maintenant aaaaaaa

              _
1 1 1 1 1 1 1 2  
a a a a a a a 
            _
1 1 1 1 1 1 2  
a a a a a a a 
        _____
1 1 1 1 1 2 \  
a a a a a a a  # A crucial point: the fifth level matched and now the fourth
               # level can't match \, but it does NOT reenter the fifth level to
               # try 2. Instead, the fourth level tries 2.
    _____    
1 1 1 2 \  
a a a a a a a 
  _________    
1 1 1 2 \ \ 
a a a a a a a 
_____________    
1 1 1 2 \ \ \
a a a a a a a  # Entire pattern is a match! 

A noter que même si PCRE récursion sous-motif est atomique, il peut encore correspondre avec succès un palindrome constitué d'un caractère répétant 2 ⁿ -1 fois.

---

Maintenant, juste pour le plaisir, nous allons essayer "abcba":

          _
1 1 1 1 1 2
a b c b a
        _
1 1 1 1 2
a b c b a

1 1 1 2 
a b c b a   # Third level attempts \, but c does not match a!
            # So we go back to third 1 and try 2.
  _____
1 1 2 \ 
a b c b a 
_________
1 1 2 \ \
a b c b a   # Entire pattern is a match!

Ainsi, le modèle ne se contente pas correspondre "seulement quand un personnage répète 2 ⁿ -1 fois". Il peut en effet correspondre "abcba" ( vu sur ideone.com ). Il ne peut pas, cependant, "ababa" match, et ne peut pas correspondre "aaaaa" (voir l'avertissement sur la page de manuel!), Parce que récursion subpattern dans PCRE est atomique.

Vous pouvez appliquer ce même processus de traçage pour expliquer le comportement du motif sur une entrée.

Answer 2

Dans le cas où vous souhaitez une expression PCRE entièrement fonctionnel pour correspondre palindromes, vous pouvez utiliser les éléments suivants:

  

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