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
([correction].
Quant à JavaScript, il considère qu'aucune des regexps (X), (YL) ou
(YR) n'est vérifiée par \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édenteaababcaa
: 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 là
(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.