David Madore's WebLog: Méditations sur les regexps « étendues »

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #2125 [older|newer] / Entrée #2125 [précédente|suivante]:

(mercredi)

Méditations sur les regexps « étendues »

Je participe en ce moment à Télécom à un cours sur la théorie des langages : ce qui signifie notamment, pour ce qui est de la partie sur les langages rationnels, définir ce que c'est qu'une expression régulière, définir différentes sortes d'automates finis, et montrer le théorème de Kleene selon lequel la classe de langages reconnus par des automates finis et celle définie par les expressions régulières coïncident (et montrer comment, en pratique, on arrive à synthétiser l'automate fini reconnaissant une expression régulière donnée). Théoriquement, il n'y a aucun doute que cette classe des langages rationnels est à la fois très naturelle et très importante. Déjà à ce niveau-là les choses ne sont pas aussi évidentes qu'on pourrait le penser, voir par exemple la grosse expression régulière que j'avais produite qui définit les multiples de 7 écrits en base 10.

Mais en général, quand j'enseigne un sujet, j'aime bien en apprendre un peu plus que ce que j'enseigne. Et en l'occurrence, s'agissant des expressions régulières, essentiellement tous les moteurs d'expressions régulières qui existent ont des extensions par rapport aux expressions régulières mathématiques, de sorte qu'ils reconnaissent plus que la classe standard des langages rationnels. J'aimerais bien savoir s'il existe une étude théorique de ces extensions, et je m'agace un peu de ne rien trouver de satisfaisant.

L'extension la plus courante, ce sont les références arrière (backreferences) : par exemple, on peut écrire (a*)b\1b\1 reconnaît le langage formé de trois suites de ‘a’ de même longueur séparées à chaque fois par un seul ‘b’ (i.e., les anbanban), or ce langage n'est même pas définissable par une grammaire sans contexte comme on le montre facilement avec un lemme de pompage standard. A contrario, il semble intuitivement évident que le langage formé des anbn (c'est-à-dire un certain nombre de ‘a’ puis le même nombre de ‘b’), ou encore le langage des expressions bien-parenthésées, n'est pas définissable par une expression régulière-avec-références-arrière ; mais, je ne sais pas le montrer, parce que je n'ai aucun modèle théorique bien défini pour ces expressions (et aucun « lemme de pompage » qui irait avec).

À vrai dire, je ne suis pas sûr de savoir définir exactement la sémantique des références arrière dans tous les cas bizarres. Et pour commencer, les langages (ou moteurs de regexps) ne sont pas d'accord entre eux.

Par exemple, tout le monde est d'accord que (a?)b\1 est satisfaite exactement par b et aba. Mais qu'en est-il de (a)?b\1 : et spécifiquement, est-elle satisfaite par b ? La logique demande plutôt que non : comme il n'y a pas de ‘a’ avant le ‘b’, la possibilité suggérée par le ? n'a pas lieu, donc le groupage n'est pas fait et la référence arrière n'est pas définie (ce qui est différent de : définie à la chaîne vide, comme dans l'exemple précédente), si bien que le \1 refuse de matcher. C'est bien comme ça que se comporte Perl ainsi que GNU egrep ; en revanche, en JavaScript, /^(a)?b\1$/.test("b") renvoie true : apparemment c'est une idiosyncrasie du langage que les références arrière non définies puissent matcher la chaîne vide. Maintenant, qu'en est-il de ((a*)b)*c\2 ? elle est certainement satisfaite par abaabcaa (et dans JavaScript spécifiquement, par c, suivant la même logique que l'exemple précédent), mais devrait-elle matcher aussi aababcaa ? Là, tout le monde semble d'accord que non : il faut croire que des parenthèses placées dans une étoile de Kleene capturent la dernière des occurrences du groupe parenthésé (plutôt que, par exemple, n'importe lequel, de façon non-déterministe, ce qui m'aurait semblé plus logique — mais c'est sans doute plus complexe à implémenter).

Plus précisément, la logique est quelque chose comme ceci : les groupes de parenthèses sont numérotés d'après la position de la parenthèse ouvrante dans la regexp telle qu'elle est écrite, puis la chaîne vérifie la regexp lorsqu'il existe une manière de remplacer chaque référence arrière par la plus récente sous-chaîne capturée par une paire de parenthèses numérotées de la même manière qu'elle (étant entendu, en JavaScript spécifiquement, que si la capture n'est pas définie, la chaîne vide sera acceptée pour la référence arrière). Avec cette logique, ((a*)b)*c\2 est équivalent à (a*b)*(a*)bc\2 (sauf en JavaScript où il est équivalent à c|(a*b)*(a*)bc\2), ce qui explicite que c'est la dernière répétition du (a*) qui définit la valeur du \2. Remarquez qu'il est faux — contrairement à ce qu'on pourrait croire naïvement — que toutes les références arrière de même numéro désignent forcément la même sous-chaîne : ((a*)b\2c)*d\2 est satisfaite par abacaabaacdaa (tous les moteurs sont d'accord sur ce point) et le \2 a valu une fois a et deux fois aa.

Mais les moteurs ne sont pas d'accord sur les situations dans lesquelles une paire de parenthèse doit capturer une chaîne (et affecter la référence arrière correspondante). Pour illustrer ce fait subtil, on peut comparer l'expression régulière (X) ((a*)b)*c\2 (déjà évoquée, et dont je rappelle qu'elle n'est pas vérifiée par aababcaa) avec les deux suivantes : (YL) ((a*)b|(a*)b)*c\2 et (YR) ((a*)b|(a*)b)*c\3. Le comportement de GNU egrep est le suivant : (YL) et (YR) sont équivalentes, et sont toutes les deux vérifiées par aababcaa (contrairement à (X), donc) ; l'explication est la suivante : pour chaque groupe a*b, lorsque le moteur choisit de façon non-déterministe la branche gauche ou droite de l'alternative, il affecte \2 ou \3 selon la branche qu'il choisit, mais uniquement celui-ci, et au final il accepte une chaîne lorsqu'il y a moyen de choisir les branches de sorte que le \2 final coïncide avec une capture par le jeu de parenthèses correspondant — donc (YL) et (YR) reconnaissent toutes les chaînes dans lesquelles le nombre de ‘a’ suivant le ‘c’ est égal au nombre de ‘a’ précédant n'importe quel ‘b’. Perl, en revanche, n'est pas d'accord : pour lui, (YL) n'est pas vérifiée par aababcaa (pas plus que (X)) alors que (YR) l'est : la raison est que quand Perl choisit la branche droite, il désaffecte la capture (\2) éventuellement faite par la branche gauche précédente, pour retenir le fait que, cette fois, la branche gauche n'a pas été prise, mais quand il choisit la branche gauche, il ne touche pas à la capture faite par la branche droite précédente[correction]. Quant à JavaScript, il considère qu'aucune des regexps (X), (YL) ou (YR) n'est vérifiée par aababcaa : la raison est que JavaScript considère que chaque occurrences des parenthèses externes réaffecte toutes les captures (\2 et \3), y compris pour les branches qui ne sont pas prises.

Correction  : on m'a fait remarquer que mon explication initiale ne tient pas, parce qu'elle prédit que aabeabcaa ne devrait pas vérifier ((a*)b|e?(a*)b)*c\2, or c'est le cas (avec Perl comme avec egrep). La seule explication que je voie de la différence entre le fait que, selon Perl, aabeabcaa vérifie ((a*)b|e?(a*)b)*c\2 tandis que aababcaa ne la vérifie pas, est que son backtracking est incomplet : quand il change de branche, il conserve des scories des autres branches explorées (la capture \2 est affectée par l'exploration de la branche gauche de la disjonction et n'est pas restaurée à sa valeur antérieure par le backtracking sur la branche droite) ; la présence ou non du ‘e’ élimine un backtracking et les scories qui vont avec. Ce comportement viole un principe important du non-déterminisme, qui est que les branches qui ne matchent pas ne doivent pas avoir d'influence (donc, si on les implémente avec backtracking, le backtracking doit être complet). Il cause aussi la surprise suivante : ((a*)d|e?(a*)b)*c\2 est vérifié à la fois par aadabcaa et aadeabcaa, mais quand on remplace ‘d’ par ‘b’ dans la regexp et dans les chaînes, comme je viens de le dire, ce n'est plus vrai. Je suis tenté de résumer sous la forme : Perl est cinglé. • Ajout supplémentaire : voir aussi ici et (mais je reste sur le résumé Perl est cinglé).

Pour la même raison, Perl et JavaScript pensent que abbca ne satisfait pas ((a)?b)*c\2 alors que GNU egrep pense que si ; et GNU egrep et Perl pensent que abac vérifie ((a*)b|\2c)* mais pas abc alors que JavaScript pense exactement le contraire (et s'agissant de (\2c|(a*)b)*, Perl et JavaScript ne changent pas d'avis, mais GNU egrep signalent une erreur). Enfin, si on fait référence à un groupe de parenthèses dans lui-même, GNU egrep signale une erreur, JavaScript ne lui fait matcher que la chaîne vide (parce qu'il désaffecte immédiatement la référence arrière), et Perl lui donne la valeur précédente qu'avait ce même groupe (donc (a|b\1c)* est vérifié par abac en Perl). Ce qui un peu étrange, dans l'histoire, c'est surtout que PCREgrep semble avoir souvent le même comportement que GNU grep au lieu d'avoir celui de Perl.

Même dans le cadre des expressions avec références arrière, certains moteurs (Perl, Python, .NET) apportent plus de flexibilité en permettant de nommer explicitement les groupes de capture (y compris en donnant le même nom à deux groupes différents). Je ne pense pas vraiment que ceci permette de définir des langages qui ne seraient pas définissables sans cette fonctionnalité, mais ça ne me semble pas du tout évident, ni dans un sens ni dans l'autre.

Par ailleurs, certains moteurs d'expressions régulières, notamment de Perl, ajoutent une extension supplémentaire notable au pouvoir des expressions régulières : ce sont les motifs récursifs. La simple possibilité de rappeler un motif (comme dans (a*)b(?1), qui, contrairement à la référence arrière (a*)b\1, matche abaa et pas juste aabaa) n'apporte rien de nouveau en elle-même, mais elle devient très puissante si on l'utilise récursivement. Par exemple, (a(?1)b|) définit le langage formé des anbn dont j'ai signalé ci-dessus que je pense (même si je ne sais pas le prouver) qu'il n'est pas définissable avec simplement des références arrière : on peut ainsi écrire des « expressions régulières » pour les expressions bien-parenthésées et, sans doute, pour n'importe quel langage défini par une grammaire sans contexte (même si ce n'est pas totalement clair à cause des limitations sur la récursion). Le comportement est assez différent entre Perl et PCRE, parce que ce dernier ne sait pas faire de backtracking à l'intérieur du motif récursif, et Perl : alors que Perl voit bien que abbc vérifie (ab(?1)bc|b*), PCRE n'y arrive pas parce que le b* capture tous les ‘b’ et n'en laisse aucun pour bc.

Bref, ce serait bien d'étudier un petit peu tout ça sous l'angle mathématique, donner des définitions rigoureuses de ce que ces différents modèles d'expressions régulières permettent de faire, trouver ceux qui sont les plus naturels, et comparer la puissance des uns et des autres.

↑Entry #2125 [older|newer] / ↑Entrée #2125 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées