Faire correspondre a^n b^n c^n (par exemple "aaabbbccc") en utilisant des expressions régulières (PCRE)

Question

Il est bien connu que les implémentations modernes d'expressions régulières (notamment PCRE) ont peu de choses en commun avec la notion originale d'expression régulière. grammaires régulières . Par exemple, vous pouvez analyser l'exemple classique d'une grammaire sans contexte {a n b n ; n>0} (par ex. aaabbb ) en utilisant cette regex ( Démonstration ) :

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

Ma question est la suivante : jusqu'où pouvez-vous aller ? Est-il également possible d'analyser le grammaire contextuelle {a n b n c n ;n>0} (par ex. aaabbbccc ) en utilisant PCRE ?

Answer 1

Inspiré par la réponse de NullUserExceptions (qu'il a déjà supprimée car elle a échoué pour un cas), je pense avoir trouvé une solution moi-même :

$regex = '~^
    (?=(a(?-1)?b)c)
     a+(b(?-1)?c)
$~x';

var_dump(preg_match($regex, 'aabbcc'));    // 1
var_dump(preg_match($regex, 'aaabbbccc')); // 1
var_dump(preg_match($regex, 'aaabbbcc'));  // 0
var_dump(preg_match($regex, 'aaaccc'));    // 0
var_dump(preg_match($regex, 'aabcc'));     // 0
var_dump(preg_match($regex, 'abbcc'));     // 0

Essayez vous-même : http://codepad.viper-7.com/1erq9v

---

Explication

Si vous considérez la regex sans l'assertion positive de lookahead (l'assertion (?=...) ), on obtient ceci :

~^a+(b(?-1)?c)$~

Cela ne fait rien de plus que de vérifier qu'il y a un nombre arbitraire de a suivis d'un nombre égal de b et c s.

Cela ne satisfait pas encore notre grammaire, parce que le nombre de a doivent également être les mêmes. Nous pouvons nous en assurer en vérifiant que le nombre de a est égal au nombre de b s. Et c'est ce que fait l'expression dans l'assertion lookahead : (a(?-1)?b)c . Le site c est nécessaire pour que nous ne fassions pas correspondre seulement une partie de l'image de l'utilisateur. b s.

---

Conclusion

Je pense que cela montre de manière impressionnante que les expressions rationnelles modernes sont non seulement capables d'analyser des grammaires non régulières, mais peuvent même analyser des grammaires sans contexte. J'espère que cela mettra un terme à l'éternelle rengaine du "vous ne pouvez pas faire X avec regex parce que X n'est pas régulier".

Answer 2

Ma question est : jusqu'où pouvez-vous aller ?

Dans l'intérêt de ne pas créer un code qui soit une masse de ponctuation illisible, je vais risquer les votes négatifs et répondre à une question différente, bien que très liée : à quelle distance devrait Tu y vas ?

Les analyseurs d'expressions régulières sont une brillant Il s'agit d'un outil à posséder dans votre boîte à outils, mais il ne s'agit pas de la panacée en matière de programmation. La capacité d'écrire des analyseurs syntaxiques de manière lisible est un élément essentiel de la programmation. également une chose brillante à avoir dans sa boîte à outils.

Les expressions régulières doivent être utilisées jusqu'au moment où elles commencent à rendre votre code difficile à comprendre. Au-delà, leur valeur est au mieux douteuse, au pire dommageable. Dans ce cas précis, plutôt que d'utiliser quelque chose comme l'affreux :

~^(?=(a(?-1)?b)c)a+(b(?-1)?c)$~x

(avec les excuses de NikiC), que la grande majorité des personnes qui essaient de le maintenir vont devoir soit remplacer totalement, soit dépenser des euros. substantiel Après avoir lu et compris le texte, vous pourriez envisager une solution de type "analyseur approprié" (pseudo-code) non RE :

# Match "aa...abb...bcc...c" where:
# - same character count for each letter; and
# - character count is one or more.

def matchABC (string str):
    # Init string index and character counts.
    index = 0
    dim count['a'..'c'] = 0

    # Process each character in turn.
    for ch in 'a'..'c':
        # Count each character in the subsequence.
        while index < len(str) and str[index] == ch:
            count[ch]++
            index++

    # Failure conditions.
    if index != len(str):        return false # did not finish string.
    if count['a'] < 1:           return false # too few a characters.
    if count['a'] != count['b']: return false # inequality a and b count.
    if count['a'] != count['c']: return false # inequality a and c count.

    # Otherwise, it was okay.
    return true

Cela sera beaucoup plus facile à entretenir à l'avenir. J'aime toujours suggérer aux gens qu'ils devraient supposer que ceux qui viennent après eux (qui ont à maintenir le code qu'ils écrivent) sont des psychopathes qui savent où vous vivez - dans mon cas, c'est peut-être à moitié vrai, je n'ai aucune idée de l'endroit où vous vivez :-)

A moins que vous n'ayez un réel Si vous n'avez pas besoin d'expressions régulières de ce type (et il y a parfois de bonnes raisons, telles que les performances dans les langages interprétés), vous devriez optimiser pour lisibilité d'abord.

Answer 3

Voici une solution alternative utilisant groupes d'équilibrage avec .NET regex :

^(?'a'a)+(?'b-a'b)+(?(a)(?!))(?'c-b'c)+(?(b)(?!))$

Pas PCRE, mais peut être d'intérêt.

Exemple à : http://ideone.com/szhuE

Modifier : Ajout du contrôle d'équilibrage manquant pour le groupe a, et d'un exemple en ligne.

Answer 4

Truc de la Qtax

Une solution qui n'a pas été mentionnée :

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

Voir ce qui correspond et ce qui échoue dans la démo de la regex .

Cela utilise des groupes d'auto-référencement (une idée utilisée par @Qtax sur sa regex verticale ).