Le PCRE peut-il correspondre à des grammaires contextuelles comme {a^n b^n c^n; ?

Correspondance des grammaires contextuelles avec PCRE : A^n B^n C^n (par exemple, "aaabbbccc")

Bien que régulier les expressions sont traditionnellement associées à l'analyse des grammaires régulières, les implémentations modernes comme PCRE offrent des fonctionnalités étendues. Cela soulève la question : pouvons-nous utiliser PCRE pour analyser des grammaires plus complexes et sensibles au contexte ?

Plus précisément, explorons le défi de faire correspondre des chaînes suivant la grammaire contextuelle {a^n b^n c^n ; n> 0} (par exemple, "aaabbbccc").

Solution Regex :

Inspirés par la tentative initiale de NullUserException, nous avons conçu la regex suivante :

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

Explication :

• La section extérieure ~^...$~ garantit que la chaîne commence et se termine avec le motif souhaité.
• À l'intérieur des parenthèses , ~?(a(?-1)?b)c~ est une assertion prospective positive qui vérifie un nombre égal de as et de bs.
• ~a ~ correspond à n'importe quel nombre de as.
• ~b(?-1)?c~ correspond à un nombre égal de bs suivi de cs.
• Le (?-) dans (?-1) nous permet de faire correspondre des séquences arbitraires de as et bs qui satisfaire l'assertion d'anticipation.

Cas de test :

Nous avons testé l'expression régulière par rapport à diverses entrées, notamment :

• "aabbcc " - Correspond avec succès
• "aaabbbccc" - Correspond avec succès
• "aaabbbcc" - Ne correspond pas (correct)
• "aaaccc" - Ne correspond pas (correct)
• "aabcc" - Ne correspond pas (correct)
• "abbcc" - Ne correspond pas (correct)

Conclusion :

Cette expression régulière démontre la puissance remarquable des expressions régulières modernes, s'étendant au-delà des grammaires régulières pour correspondre même aux grammaires contextuelles comme {a^n b^n c^n}. Cette capacité à analyser des modèles plus complexes ouvre de nouvelles possibilités pour les applications regex.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!