Comment pouvons-nous faire correspondre un ^ nb ^ n avec Java regex?

_{Ceci est la deuxième partie d'une série d'articles pédagogiques sur les expressions régulières. Il montre comment les anticipations et les références imbriquées peuvent être utilisées pour correspondre au langage non régulier a ⁿ b ⁿ . Les références imbriquées sont d'abord introduites dans: Comment cette regex trouve-t-elle des nombres triangulaires?}

L'une des langues non régulières archétypales est:

L = { aⁿ bⁿ: n > 0 }

C'est la langue de toutes les chaînes non vides composées d'un certain nombre de a's suivi d'un nombre égal de b' s. Des exemples de chaînes dans cette langue sont ab, aabb, aaabbb.

Ce langage peut être montré comme non régulier par le lemme de pompage . Il s'agit en fait d'un langage archétypal sans contexte , qui peut être généré par la grammaire sans contexte S → aSb | ab .

Néanmoins, les implémentations de regex modernes reconnaissent clairement plus que de simples langages ordinaires. Autrement dit, ils ne sont pas «réguliers» selon la définition de la théorie formelle du langage. PCRE et Perl prennent en charge les expressions régulières récursives et .NET prend en charge la définition des groupes d'équilibrage. Encore moins de fonctionnalités «fantaisistes», par exemple la correspondance des références arrière, signifie que l'expression régulière n'est pas régulière.

Mais quelle est la puissance de ces fonctionnalités «de base»? Peut-on reconnaître Lavec Java regex, par exemple? Peut - on combiner peut - être lookarounds et références imbriquées et ont un modèle qui fonctionne avec par exemple String.matchespour correspondre à des chaînes comme ab, aabb, aaabbb, etc?

Références

• perlfaq6: Puis-je utiliser des expressions régulières Perl pour faire correspondre du texte équilibré?
• MSDN - Éléments de langage d'expression régulière - Définitions de groupe d'équilibrage
• pcre.org - Page de manuel PCRE
• regular-expressions.info - Lookarounds et regroupements et backreferences
• java.util.regex.Pattern

Questions liées

• La recherche affecte-t-elle les langues auxquelles les expressions régulières peuvent correspondre?
• Groupes d'équilibrage .NET Regex vs modèles récursifs PCRE

La réponse est, il va sans dire, OUI! Vous pouvez très certainement écrire un modèle d'expression régulière Java pour correspondre à un ⁿ b ⁿ . Il utilise une anticipation positive pour l'assertion et une référence imbriquée pour le "comptage".

Plutôt que de donner immédiatement le modèle, cette réponse guidera les lecteurs tout au long du processus de dérivation. Divers indices sont donnés au fur et à mesure que la solution est construite lentement. Dans cet aspect, j'espère que cette réponse contiendra beaucoup plus qu'un simple autre modèle de regex soigné. Espérons que les lecteurs apprendront également à «penser en regex», et comment assembler harmonieusement diverses constructions, afin de pouvoir en tirer plus de modèles à l'avenir.

Le langage utilisé pour développer la solution sera PHP pour sa concision. Le test final une fois le modèle finalisé sera effectué en Java.

Étape 1: Rechercher une assertion

Commençons par un problème plus simple: nous voulons faire correspondre a+au début d'une chaîne, mais seulement si elle est immédiatement suivie de b+. Nous pouvons utiliser ^pour ancrer notre correspondance, et comme nous ne voulons faire correspondre que le a+sans le b+, nous pouvons utiliser l' assertion lookahead(?=…) .

Voici notre modèle avec un harnais de test simple:

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}
 
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
 
$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

Le résultat est ( comme vu sur ideone.com ):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

C'est exactement la sortie que nous voulons: nous correspondons a+, seulement si c'est au début de la chaîne, et seulement si elle est immédiatement suivie de b+.

Leçon : Vous pouvez utiliser des modèles dans les lookarounds pour faire des assertions.

Étape 2: Capture dans une anticipation (et en mode espacement libre)

Maintenant, disons que même si nous ne voulons pas que le b+fasse partie du match, nous voulons quand même le capturer dans le groupe 1. De plus, comme nous prévoyons avoir un modèle plus compliqué, utilisons un xmodificateur pour l'espacement libre afin que nous peut rendre notre regex plus lisible.

En nous basant sur notre précédent extrait de code PHP, nous avons maintenant le modèle suivant:

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead
 
testAll($r2, $tests);

La sortie est maintenant ( comme vu sur ideone.com ):

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

Notez que par exemple aaa|best le résultat de join-ing ce que chaque groupe a capturé '|'. Dans ce cas, le groupe 0 (c'est-à-dire ce que le modèle correspondait) capturé aaaet le groupe 1 capturé b.

Leçon : vous pouvez capturer l'intérieur d'un lookaround. Vous pouvez utiliser l'espacement libre pour améliorer la lisibilité.

Étape 3: Refactorisation de l'anticipation dans la "boucle"

Avant de pouvoir introduire notre mécanisme de comptage, nous devons apporter une modification à notre modèle. Actuellement, l'anticipation est en dehors de la +"boucle" de répétition. C'est très bien pour l'instant parce que nous voulions juste affirmer qu'il y a un b+suivant notre a+, mais ce que nous voulons vraiment faire finalement, c'est affirmer que pour chacun aque nous apparions à l'intérieur de la "boucle", il y a un correspondant bqui va avec.

Ne nous inquiétons pas du mécanisme de comptage pour le moment et faisons simplement la refactorisation comme suit:

• Premier refactor a+à (?: a )+(notez qu'il (?:…)s'agit d'un groupe non capturant)
• Ensuite, déplacez le regard dans ce groupe non capturant
  • Notez que nous devons maintenant "sauter" a*avant de pouvoir "voir" le b+, donc modifiez le modèle en conséquence

Nous avons donc maintenant les éléments suivants:

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

Le résultat est le même qu'avant ( comme vu sur ideone.com ), il n'y a donc aucun changement à cet égard. L'important est que maintenant nous faisons l'assertion à chaque itération de la +"boucle". Avec notre modèle actuel, ce n'est pas nécessaire, mais ensuite nous ferons "compter" le groupe 1 pour nous en utilisant l'auto-référence.

Leçon : Vous pouvez capturer à l'intérieur d'un groupe sans capture. Les Lookarounds peuvent être répétés.

Étape 4: C'est l'étape où nous commençons à compter

Voici ce que nous allons faire: nous réécrirons le groupe 1 de telle sorte que:

• À la fin de la première itération du +, lorsque le premier aest mis en correspondance, il doit capturerb
• À la fin de la deuxième itération, lorsqu'une autre aest mise en correspondance, elle doit capturerbb
• À la fin de la troisième itération, il devrait capturer bbb
• ...
• À la fin de la n- ième itération, le groupe 1 devrait capturer b ⁿ
• S'il n'y en a pas assez bpour capturer dans le groupe 1, l'assertion échoue tout simplement

Donc, le groupe 1, qui est maintenant (b+), devra être réécrit en quelque chose comme (\1 b). Autrement dit, nous essayons d '"ajouter" un bà quel groupe 1 capturé dans l'itération précédente.

Il y a un léger problème ici en ce que ce modèle n'a pas le "cas de base", c'est-à-dire le cas où il peut correspondre sans l'auto-référence. Un cas de base est requis car le groupe 1 démarre "non initialisé"; il n'a encore rien capturé (pas même une chaîne vide), donc une tentative d'auto-référence échouera toujours.

Il y a plusieurs façons de contourner cela, mais pour l'instant, rendons simplement la correspondance d'auto-référence facultative , c'est-à-dire \1?. Cela peut fonctionner parfaitement ou non, mais voyons simplement ce que cela fait, et s'il y a un problème, nous traverserons ce pont lorsque nous y arriverons. Nous ajouterons également d'autres cas de test pendant que nous y sommes.

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
 
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

La sortie est maintenant ( comme vu sur ideone.com ):

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

A-ha! On dirait que nous sommes vraiment proches de la solution maintenant! Nous avons réussi à faire «compter» le groupe 1 en utilisant l'auto-référence! Mais attendez ... quelque chose ne va pas avec le deuxième et le dernier cas de test !! Il n'y a pas assez de bs, et d'une manière ou d'une autre, ça compte mal! Nous examinerons pourquoi cela s'est produit à l'étape suivante.

Leçon : Une façon d '«initialiser» un groupe d'auto-référencement est de rendre la correspondance d'auto-référence facultative.

Étape 4½: Comprendre ce qui n'a pas fonctionné

Le problème est que puisque nous avons rendu la correspondance d'auto-référence facultative, le "compteur" peut "réinitialiser" à 0 quand il n'y en a pas assez b. Examinons de près ce qui se passe à chaque itération de notre modèle avec aaaaabbbcomme entrée.

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

A-ha! Lors de notre quatrième itération, nous pourrions toujours correspondre \1, mais nous ne pouvions pas égaler \1b! Puisque nous permettons à la correspondance d'auto-référence d'être facultative avec \1?, le moteur revient en arrière et a pris l'option "non merci", qui nous permet ensuite de faire correspondre et de capturer juste b!

Notez cependant que, sauf lors de la toute première itération, vous pouvez toujours faire correspondre uniquement l'auto-référence \1. C'est évident, bien sûr, car c'est ce que nous venons de capturer lors de notre itération précédente, et dans notre configuration, nous pouvons toujours le faire correspondre à nouveau (par exemple, si nous avons capturé la bbbdernière fois, nous sommes sûrs qu'il y en aura toujours bbb, mais il se peut ou peut-être pas bbbbcette fois).

Leçon : méfiez-vous des retours en arrière. Le moteur regex fera autant de retour arrière que vous le permettez jusqu'à ce que le modèle donné corresponde. Cela peut avoir un impact sur les performances (c.-à-d. Un retour en arrière catastrophique ) et / ou l'exactitude.

Étape 5: La possession de soi à la rescousse!

Le "correctif" devrait maintenant être évident: combiner la répétition facultative avec un quantificateur possessif . C'est-à-dire, au lieu d' ?utiliser simplement à la ?+place (rappelez-vous qu'une répétition qui est quantifiée comme possessive ne revient pas en arrière, même si une telle "coopération" peut aboutir à une correspondance avec le modèle global).

En termes très informels, voici ce que ?+, ?et ??dit:

?+

• (facultatif) "Il ne doit pas être là",
  • (possessif) "mais s'il est là, il faut le prendre et ne pas lâcher prise!"

?

• (facultatif) "Il ne doit pas être là",
  • (gourmand) "mais si c'est le cas, vous pouvez le prendre pour l'instant,"
    • (retour en arrière) "mais on vous demandera peut-être de lâcher prise plus tard!"

??

• (facultatif) "Il ne doit pas être là",
  • (réticent) "et même si c'est le cas, vous n'êtes pas obligé de le prendre tout de suite,"
    • (retour en arrière) "mais on vous demandera peut-être de le reprendre plus tard!"

Dans notre configuration, \1ne sera pas là la toute première fois, mais il sera toujours là à tout moment après cela, et nous voulons toujours le faire correspondre alors. Ainsi, \1?+accomplirait exactement ce que nous voulons.

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Maintenant, la sortie est ( comme vu sur ideone.com ):

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

Voilà !!! Problème résolu!!! Nous comptons maintenant correctement, exactement comme nous le voulons!

Leçon : Apprenez la différence entre la répétition avide, réticente et possessive. Facultatif-possessif peut être une puissante combinaison.

Étape 6: Touches finales

Donc, ce que nous avons en ce moment est un modèle qui correspond à aplusieurs reprises, et pour tout ce aqui a été mis en correspondance, il y a un correspondant bcapturé dans le groupe 1. Le se +termine quand il n'y en a plus a, ou si l'assertion a échoué parce qu'il n'y a pas de correspondant bpour un a.

Pour terminer le travail, nous devons simplement ajouter à notre modèle \1 $. Il s'agit maintenant d'une référence arrière à la correspondance du groupe 1, suivie de la fin de l'ancre de ligne. L'ancre garantit qu'il n'y a pas d'extra bdans la chaîne; en d'autres termes, qu'en fait nous avons un ⁿ b ⁿ .

Voici le modèle finalisé, avec des cas de test supplémentaires, dont un de 10000 caractères:

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);
 
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Il trouve 4 matches: ab, aabb, aaabbb, et a ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Cela ne prend que 0,06 seconde pour fonctionner sur ideone.com .

Étape 7: Le test Java

Donc, le modèle fonctionne en PHP, mais le but ultime est d'écrire un modèle qui fonctionne en Java.

public static void main(String[] args) {
 
        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }
 
}
 
static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

Le modèle fonctionne comme prévu ( comme vu sur ideone.com ).

Et maintenant nous arrivons à la conclusion ...

Il faut dire que le a*dans la recherche anticipée, et en fait la " +boucle principale ", permettent tous deux un retour en arrière. Les lecteurs sont encouragés à confirmer pourquoi ce n'est pas un problème en termes d'exactitude, et pourquoi en même temps rendre les deux possessifs fonctionnerait également (bien que peut-être mélanger des quantificateurs possessifs obligatoires et non obligatoires dans le même schéma puisse conduire à des perceptions erronées).

Il faut aussi dire que s'il est bien qu'il y ait un modèle d'expression régulière qui correspondra à un ⁿ b ⁿ , ce n'est pas toujours la «meilleure» solution en pratique. Une bien meilleure solution consiste simplement à faire correspondre ^(a+)(b+)$, puis à comparer la longueur des chaînes capturées par les groupes 1 et 2 dans le langage de programmation hôte.

En PHP, cela peut ressembler à quelque chose comme ceci ( comme on le voit sur ideone.com ):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

Le but de cet article n'est PAS de convaincre les lecteurs que les regex peuvent faire presque tout; il ne peut clairement pas, et même pour les choses qu'il peut faire, au moins une délégation partielle au langage d'hébergement devrait être envisagée si cela conduit à une solution plus simple.

Comme mentionné en haut, bien que cet article soit nécessairement étiqueté [regex]pour stackoverflow, il s'agit peut-être de plus que cela. Bien qu'il y ait certainement de la valeur à apprendre sur les assertions, les références imbriquées, le quantificateur possessif, etc., la plus grande leçon ici est peut-être le processus créatif par lequel on peut essayer de résoudre des problèmes, la détermination et le travail acharné que cela nécessite souvent lorsque vous êtes soumis à diverses contraintes, la composition systématique de différentes pièces pour construire une solution de travail, etc.

Matériel bonus! Motif récursif PCRE!

Puisque nous avons mis en place PHP, il faut dire que PCRE prend en charge les schémas récursifs et les sous-programmes. Ainsi, le modèle suivant fonctionne pour preg_match( comme vu sur ideone.com ):

$rRecursive = '/ ^ (a (?1)? b) $ /x';

Actuellement, l'expression régulière de Java ne prend pas en charge le modèle récursif.

Encore plus de matériel bonus! Correspondance a ⁿ b ⁿ c ⁿ !!

Nous avons donc vu comment faire correspondre un ⁿ b ⁿ qui n'est pas régulier, mais toujours sans contexte, mais pouvons-nous aussi faire correspondre un ⁿ b ⁿ c ⁿ , qui n'est même pas sans contexte?

La réponse est, bien sûr, OUI! Les lecteurs sont encouragés à essayer de résoudre ce problème par eux-mêmes, mais la solution est fournie ci-dessous (avec une implémentation en Java sur ideone.com ).

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $

Étant donné qu'aucune mention n'a été faite de PCRE prenant en charge les modèles récursifs, je voudrais simplement souligner l'exemple le plus simple et le plus efficace de PCRE qui décrit le langage en question:

/^(a(?1)?b)$/

Comme mentionné dans la question - avec le groupe d'équilibrage .NET, les modèles du type a ⁿ b ⁿ c ⁿ d ⁿ … z ⁿ peuvent être facilement mis en correspondance comme

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))
$

Par exemple: http://www.ideone.com/usuOE

Éditer:

Il existe également un modèle PCRE pour le langage généralisé avec un modèle récursif, mais une anticipation est nécessaire. Je ne pense pas que ce soit une traduction directe de ce qui précède.

^
  (?=(a(?-1)?b))  a+
  (?=(b(?-1)?c))  b+
  ...
  (?=(x(?-1)?y))  x+
     (y(?-1)?z)
$

Par exemple: http://www.ideone.com/9gUwF