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}

Alors que les expressions régulières ont toujours été associées aux expressions régulières grammaires, les implémentations modernes comme PCRE présentent des capacités avancées qui s'étendent au-delà de ce cadre théorique. L'une de ces capacités est l'expression de grammaires contextuelles.

Dans cette veine, la question se pose : PCRE peut-il analyser {a^n b^n c^n}, une grammaire qui ne peut pas être décrite par des expressions régulières ? La réponse, comme l'ont démontré plusieurs utilisateurs, est un « oui » étonnant.

Une solution particulièrement convaincante présentée par l'utilisateur implique l'utilisation d'une assertion prospective positive :

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

Explication :

Sans l'assertion d'anticipation, l'expression régulière vérifie un nombre arbitraire de as, suivi d'un nombre égal de bs et cs. Cependant, cela ne garantit pas que le nombre de as est égal au nombre de bs, comme l'exige la grammaire.

L'assertion d'anticipation, en particulier (?=(a(?-1)?b)c), répond à ce problème. Il fait correspondre les séquences de as, suivies de bs, en s'assurant à chaque fois que le nombre de as correspond au nombre de bs. L'inclusion de c garantit que la correspondance consomme tous les bs.

Conclusion :

Cet exemple montre la puissance remarquable des implémentations d'expressions régulières modernes. La capacité de PCRE à analyser des grammaires non-contextuelles met en évidence sa polyvalence et sa capacité à exprimer des modèles complexes. Cela remet en question la croyance de longue date selon laquelle les regex sont uniquement capables de capturer des langues normales.

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!