Le très bizarre QRegExp

| Jasmin Blanchette | traducteur : Thibaut Cuvelier | Qt Quarterly |

Les programmeurs en C++ peuvent utiliser des expressions régulières à la manière du Perl grâce à la classe QRegExp, complètement réécrite depuis Qt 3.0. Nous présentons ici quelques aspects pratiques de l'utilisation d'expressions régulières pour l'analyse, la validation et le filtrage. Nous jetterons aussi un œil à leur optimisation et à la rectification de quelques futilités.

Cet article est une traduction autorisée de Seriously Weird QRegExp, par Jasmin Blanchette.

Commentez

- Titre : Le très bizarre QRegExp

- Auteurs : Jasmin Blanchette, traducteur : Thibaut Cuvelier, Qt Quarterly

- Parution : 25 février 2009

- Mise à jour : 1 août 2011

- Licence : Copyright ® 2002 Jasmin Blanchette. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. L'article original

- II. Analyse

- II-A. Premier cas

- II-B. Deuxième cas

- II-C. Troisième cas

- III. Validation

- IV. Recherche et filtrage

- V. Optimisations

- V-A. Optimisations générales

- V-A-1. Utiliser (?: ... ), au lieu de ( ... ), autant que possible

- V-A-2. Utiliser ^ ou QRegExp::exactMatch(), dès que possible

- V-A-3. Factoriser les sous-expressions

- V-A-4. Éviter les références en arrière ( \\1 , \\2 ...), les répétitions ( ({1,500}) )

- V-A-5. Éviter le non-déterminisme

- V-B. Optimisations de search() et heuristiques

- V-B-1. Heuristique de bonne série

- V-B-2. Heuristique de mauvais caractère

- V-C. Statistiques

- VI. Futilités mathématiques

- VII. Bogues ?

- VIII. Références

- IX. Divers

I - L'article original

Qt Quarterly est une revue trimestrielle électronique proposée par Qt à destination des développeurs et utilisateurs de Qt. Vous pouvez trouver les versions originales.

Nokia, Qt, Qt Quarterly et leurs logos sont des marques déposées de Nokia Corporation en Finlande et/ou dans les autres pays. Les autres marques déposées sont détenues par leurs propriétaires respectifs.

Cet article est la traduction de l'article Seriously Weird QRegExp de Jasmin Blanchette paru dans la Qt Quarterly Issue 1.

Cet article est une traduction de l'un des tutoriels en anglais écrits par Nokia Corporation and/or its subsidiary(-ies), inclus dans la documentation de Qt. Les éventuels problèmes résultant d'une mauvaise traduction ne sont pas imputables à Nokia.

II - Analyse

Yacc's own input files are best parsed with a more powerful parser than Yacc.
John Aycock
(Les fichiers d'entrée de Yacc sont mieux analysés par un analyseur plus puissant que Yacc).

II-A - Premier cas

L'analyse de fichiers texte est un problème commun dans la programmation journalière. En général, l'écriture d'analyseurs prend du temps et est difficile. De nombreux problèmes peuvent être évités en utilisant des expressions régulières : faciles et amusantes à écrire, elles sont aussi faciles à adapter pour respecter les spécifications changeantes. Cependant, il faut faire attention aux nombreux pièges qui peuvent être évités avec un peu d'attention, comme dans le premier exemple.

Une tâche habituelle est de trouver des paires équilibrées, comme des parenthèses ouvrantes et fermantes, ou bien des balises SGML. Par exemple, cette expression régulière permet de trouver le texte mis en évidence dans un document HTML.

QRegExp rx( "<(em|i)>.*</\\1>" );
rx.setCaseSensitive( FALSE );

L'expression régulière <(em|i)>.*</\\1> signifie :

Rechercher <, puis em ou i, puis >, ensuite zéro ou plus de caractères divers, ensuite </, puis em et i, et finalement, >

Cependant, pour le moment, le HTML accepte des espaces dans les balises, une meilleure expression régulière serait :

QRegExp rx( "<\\s*(em|i)\\s*>.*<\\s*/\\s*\\1\\s*>" );

Par défaut, les expressions régulières sont avides, et essayent de faire correspondre autant de texte que possible. Par exemple, dans la chaîne

Un drapeau <i>noir</i>, <i>jaune</i> et <i>rouge</i>

Cette expression régulière ferait correspondre <i>noir</i> <i>jaune</i> <i>rouge</i >, au lieu de simplement <i>noir</i>. La solution est d'appeler

rx.setMinimal( TRUE );

Pour demander à QRegExp de sélectionner le strict minimum, c'est-à-dire <i>noir</i>.

Une alternative qui ne requiert pas setMinimal() et qui donne des résultats équivalents serait de remplacer .* par [^<]*, qui va être mis en relation avec seulement < au lieu de rien du tout. Malheureusement, ces deux solutions sont très fragiles, parce qu'elles ne peuvent réussir sur des paires enchâssées, comme, par exemple :

Un peu de txte <i><i><i>fort</i>ement</i> en <i>i</i>talique</i>.

Ceci est un problème régulier avec les expressions régulières, et une des raisons pour lesquelles des analyseurs complets sont requis dans certaines situations. D'un autre côté, si vous pouvez être garanti que le HTML est libre de telles constructions (sûrement parce que le code est généré par votre application) vous pouvez analyser très simplement du HTML avec des expressions régulières comme celle ci-dessus.

II-B - Deuxième cas

Toute application peut, très facilement, lire et écrire leurs propriétés grâce à QSettings, ce qui, internement, utilise des fichiers de configuration ou le registre Windows. Or, relativement souvent, nous voulons lire et écrire des fichiers de configuration dans un format de fichiers personnel. QRegExp est utile dans ces situations. La majorité des fichiers de configuration, dont les fichiers .pro de qmake, contiennent des entrées de la forme clé = valeur, comme, par exemple :

# calc.pro
SOURCES = appwindow.cpp \
main.cpp
TARGET  = calc

Analyser ce genre de fichiers n'est pas trivial, car le format autorise des quantités très arbitraires d'espaces, et peut avoir des entrées sur plusieurs lignes, avec la barre oblique inverse (\). Nous allons écrire un analyseur très simple de fichiers .pro, avec QRegExp.

QFile in( "calc.pro" );
if ( !in.open(IO_ReadOnly) )
return;
QString text = in.readAll();
in.close();

En premier, nous lisons un fichier, ici calc.pro, dans un QString.

text.replace( QRegExp("#[^\n]*"), "" );
text.replace( QRegExp("\\\\\\s*\n"), " " );
text.replace( QRegExp("\\s*\n\\s*"), "<END>" );
text.replace( QRegExp("="), " = " );
text = text.simplifyWhiteSpace();

Nous canonicalisons la forme du fichier. Les commentaires sont enlevés, et les entrées sur plusieurs lignes, ramenées sur une seule, avec un espace qui finit chaque ligne. Ensuite, nous nous assurons qu'il y a un seul et unique espace entre chaque signe d'égalité. Chaque entrée possède un marqueur <END> à la fin. Nous ne pouvons, en effet, pas garder simplement les \n originaux, car QString::simplifyWhiteSpace les remplace par des espaces.

QStringList lines = QStringList::split( "<END>", text );
QStringList::Iterator line = lines.begin();
while ( line != lines.end() )
{
QStringList toks = QStringList::split( " ", *line );
QStringList::Iterator it = toks.begin();

if ( toks.count() >= 3 && toks[1] == "=" )
{
QString key = *it++;
it++;
while ( it != toks.end() )
{
process_value( key, *it++ );
}
}
++line;
}

Nous séparons tout le texte en quelques lignes, et les séparons en pièces détachées, plus faciles à manier. Nous prenons chacune de ces pièces comme une clé en ignorant le signe d'égalité, et utilisons les pièces restantes comme valeurs. Et c'est tout : un analyseur simple de fichiers .pro en une vingtaine de lignes !

II-C - Troisième cas

Notre troisième application de QRegExp est un programme qui convertit les commentaires // en commentaires /* ... */ Un tel programme pourrait être utile pour porter du code du C++ vers du C.

Il serait tentant d'écrire ceci :

text.replace( QRegExp("//([^\n]*)(\n|$)"), "/*\\1 */\\2" );

Malheureusement, ceci ne fonctionne pas. L'expression régulière remplacerait, en effet, les occurrences de // dans les commentaires /* ... */, et dans les chaînes de caractères.

Une approche plus sophistiquée utiliserait une expression dans ce genre :

QRegExp rx( "(//([^\n]*)(\n|$)|/\\*.*\\*/|\"([^\\\\]|\\\\.)*\"" );
rx.setMinimal( TRUE );

L'expression consiste en trois parties alternatives :

1. //([^\n]*)(\n|$), qui reconnaît les commentaires à la C++ ;

2. /\\*.*\\*/, qui s'occupe des commentaires à la mode C ;

3. \"([^\\\\]|\\\\.)*\", qui identifie les chaînes de caractères.

L'on désire un strict minimum de correspondances, pour les mêmes raisons que dans l'exemple du HTML. Sans cela, en effet, nous pourrions faire commencer un commentaire à un /* et le faire finir au */ d'un autre.

L'expression régulière contient trois paires de parenthèses. Le texte qu'elles récupèrent est disponible avec QRegExp::cap, cap(2), et cap(3). Ici, nous n'utiliserons que cap(1). Nous aurions pu utiliser des parenthèses non-capturantes (?:...) au lieu de (...), dans les deux autres cas.

Nous pouvons utiliser cette expression dans une boucle.

int pos = 0;
while ( (pos = rx.search(text, pos)) != -1 )
{
if ( rx.cap(1).startsWith("//") )
{
QString before = rx.cap( 1 );
QString after = "/*" + before.mid( 2 ) + " */";
text.replace( pos, before.length(), after );
pos += after.length();
}
else
{
pos += rx.matchedLength();
}
}

Ceci marchera dans tous les cas, sauf si un commentaire // contient */. Pour des cas aussi rares, une correction à la main est la solution la plus pratique.

III - Validation

I never metacharacter I didn't like.
Dale Dougherty
(Je n'ai jamais utilisé comme mot-clef ce que je n'aimais pas.)

Les expressions régulières peuvent être utilisées pour valider les entrées d'un utilisateur. Nous présentons un exemple qui utilise QRegExpValidator, une classe ajoutée dans Qt 3.0, pour valider un numéro ISBN (International Standard Book Number, numéro international standardisé d'un livre), pendant qu'il est inséré dans un QLineEdit.

Un numéro ISBN est un nombre unique à 10 chiffres qui identifie un livre. (Récemment ont été introduits les numéros ISBN à 13 chiffres, pour pallier un manque très proche de numéros. Cependant, dans cet article, nous ne traiterons que les anciens numéros.) Le dixième chiffre est une somme de contrôle, de 0 à 10, avec le 10 représenté par le X. Des tirets sont utilisés pour séparer les nombres dans des compartiments, selon un algorithme complexe censé faciliter la lecture.

Une solution qui ne vérifie ni la somme de contrôle, ni les tirets pourrait ressembler à ceci.

QRegExp rx( "([0-9]-?){9}[0-9X]" );
QRegExpValidator *val = new QRegExpValidator( rx, lineEdit );
lineEdit->setValidator( val );

Les valideurs distinguent trois types d'entrées : les invalides, les intermédiaires et les acceptables. Voici un exemple de chaque sorte.

Invalide

Intermédiaire

Acceptable

A

0-340-6

0-340-67997-0

Si nous voulons valider les sommes de contrôle, nous pouvons dériver QRegExpValidator de cette manière.

class IsbnValidator : public QRegExpValidator
{

public:
IsbnValidator( QObject *parent, const char *name )
: QRegExpValidator( parent, name )
{
setRegExp( QRegExp("([0-9]-?){9}[0-9X]") );
}

virtual State validate( QString& str, int& index ) const
{
State state = QRegExpValidator::validate( str, index );
if ( state == Acceptable ) {
int sum = 0;
int multiplier = 10;

for ( int i = 0; i < (int) str.length(); i++ )
{
if ( str[i].isDigit() )
sum += str[i].digitValue() * multiplier--;
else if ( str[i] == 'X' )
sum += 10;
}
if ( sum % 11 != 0 )
state = Intermediate;
}
return state;
}

};

Une classe IsbnValidator plus sophistiquée devrait réimplémenter QValidator::fixup() pour insérer les tirets automatiquement à la bonne place, pendant que l'utilisateur écrit (une tâche peu facile), et pour convertir x en X.

IV - Recherche et filtrage

I define Unix as "30 definitions of regular expressions living under one roof."
Donald E. Knuth
(Je définis UNIX comme 30 définitions des expressions régulières sous un seul et même toit.)

Les expressions régulières ne sont pas forcément codées en dur dans le code par le programmeur. Elles peuvent, en effet, parfois, être entrées par l'utilisateur. Ceci est plus commun dans le monde UNIX, où des applications comme emacs, grep, lex, et vim se basent principalement sur les expressions régulières pour leurs fonctionnalités de base. Les utilisateurs de Windows ne les ont pas entièrement ratées, non plus : la fonction Trouver et remplacer de Microsoft Word a une option qui permet d'utiliser des expressions régulières, avec, comme d'habitude, sa propre syntaxe. De la même manière, les outils Borland supportent traditionnellement les expressions genre UNIX.

En natif, QRegExp supporte deux syntaxes : une semblable à Perl, très puissante, et une, plus simple, réminiscence du MS-DOS, avec des caractères de remplacement. Ceci peut être utile pour laisser l'utilisateur choisir s'il veut des correspondances avec un texte ou utiliser des expressions régulières plus complètes dans une boîte de dialogue Trouver, ou pendant le filtrage de données ou de noms de fichiers. Une chaîne de caractères peut être convertie dans un QRegExp en échappant chaque caractère spécial avec une barre oblique inverse. La fonction suivante s'occupe de ceci.

QString literal( QString str )
{
QString meta = "$()*+.?[\\]^{|}";
int i = 0;

while ( i < (int) str.length() )
{
if ( meta.find(str[i]) != -1 )
str.insert( i++, "\\" );
i++;
}
return str;
}

Cette fonction est disponible nativement dans Qt sous le nom de QRegExp::literal depuis Qt 3.1.

Des applications spécialisées pourraient avoir besoin de supporter d'autres syntaxes. Par exemple, une base de données pourrait proposer une solution avec caractères de remplacement, où % remplace un certain nombre de caractères, et _, un seul.

QString sql = "water%";
sql = literal( sql );
sql.replace( QRegExp("%"), ".*" );
sql.replace( QRegExp("_"), "." );
QRegExp rx( sql );

Toute application peut utiliser QRegExp::isValid pour avertir ses utilisateurs quand ils ont entré une expression régulière non-valide. Depuis Qt 3.1, nous avons même accès à des erreurs textuelles (comme "Parenthèse non attendue en position 2").

V - Optimisations

There are two kinds of parser: fast parsers, and those that use regular expressions.
Rainer M. Schmid
(Il y a deux sortes d'analyseurs : les rapides, et ceux qui utilisent les expressions régulières)

V-A - Optimisations générales

Nous allons maintenant regarder le fonctionnement interne de QRegExp, et revoir quelques techniques pour son utilisation efficace sur de grandes quantités de données. Faites attention : les détails de l'implémentation ici présentés peuvent changer dans une version ultérieure de Qt (NdT : les versions 3.1 et supérieures. Actuellement, seule la 4.5 va apporter quelques changements). De plus, la plupart des programmes n'ont absolument pas besoin de ces optimisations.

QRegExp rx( "de+f" );

Ceci convertit la chaîne de+f dans une structure plus complexe pour des résultats plus prompts. Le processus de conversion d'un texte d'une expression régulière en une structure interne de stockage de données est appelée "compilation d'une expression régulière", et apparaît lors de l'exécution. QRegExp utilise deux optimisations pour réduire le coût de la construction d'un tel objet : le partage implicite et le cache.

Le partage implicite implique que la structure des données de QRegExp est partagée par de multiples objets qui ont la même expression régulière. Ceci est une optimisation très fréquente dans Qt : par exemple, les classes QBrush, QCursor, QFont, QIconSet, QMap, QPalette, QPicture, QPixmap, QRegion, et QString utilisent la même technique.

Concernant le cache, Qt maintient une liste des objets les plus récemment construits pour éviter le coût de leur recompilation. Le cache permet de rendre ce code relativement efficace :

for ( int i = 0; i < 1000; i++ )
{
QRegExp rx( "de+f" );
}

Il est, cependant, une très bonne habitude de ne pas construire d'objets QRegExp dans une boucle lorsque cela est possible.

Certaines constructions des expressions régulières ralentissent considérablement leur compilation ou leur utilisation, tandis que d'autres les accélèrent. Voici quelques astuces.

V-A-1 - Utiliser (?: ... ), au lieu de ( ... ), autant que possible

Ce genre de parenthèses oblige QRegExp à faire plus d'optimisations de lui-même.

V-A-2 - Utiliser ^ ou QRegExp::exactMatch(), dès que possible

L'exemple suivant donne très exactement le même résultat avec ou sans ^, mais est plus rapide s'il est utilisé.

if ( line.find(QRegExp("^(SRC|SOURCE)=")) == 0 )
{
...
}

V-A-3 - Factoriser les sous-expressions

Une expression comme th(?:is|at) est plus rapide que this|that.

V-A-4 - Éviter les références en arrière ( \\1 , \\2 ...), les répétitions ( ({1,500}) )

QRegExp n'est pas optimisé pour ces constructions exotiques.

V-A-5 - Éviter le non-déterminisme

Ceci se produit quand une expression rencontre une chaîne en de nombreuses manières. Par exemple, l'expression (a|a) rencontre la chaîne "a" de deux manières, et (a|a)+, la chaîne "aaaa" de 16 manières différentes. Des exemples plus frappants sont (a+){64} et (a+)+. QRegExp tend à être moins sensible au non-déterminisme que Perl, mais l'est plus qu'AWK.

V-B - Optimisations de search() et heuristiques

D'autres optimisations sont spécifiques à QRegExp::search, une fonction qui recherche dans une potentiellement très grande quantité de texte.

rx.search( "abcdefghijklmnopqrstuvwxyz" );

search() essaye de faire correspond l'expression régulière de+f aux positions 1, 2, 3 ... de la chaîne "abcdefghijklmnopqrstuvwxyz", comme illustré ci-dessous.

abcdefg...

abcdefg...

abcdefg...

abcdefg...

^0

^1

^2

^3

de+f

de+f

de+f

de+f

Quatre essais sont nécessaires avant de trouver une correspondance ("def", en troisième position). Essayer de faire correspondre à chaque position dans la chaîne cible est très coûteux, et peut être évité via l'heuristique. Une analyse de l'expression régulière de+f fournit les informations suivantes :

- La longueur minimale de chaque texte testé est de 3 (par exemple, "def") ;

- Chaque occurrence doit commencer avec le texte "de" ;

- La lettre d apparaît au plus tôt à la position 0, e, à la position 1, et f, à la position 2. Aucun autre caractère ne peut apparaître dans la correspondance.

QRegExp::search utilise ces informations, et sélectionnent automatiquement une des heuristiques suivantes pour localiser les correspondances potentielles : une heuristique de bonne sous-série ou une heuristique de mauvais caractère.

V-B-1 - Heuristique de bonne série

Une bonne série est une chaîne constante qui doit apparaître dans toutes les correspondances à une position plus ou moins définie. Voici quelques exemples.

Expression régulière

Bonne série

Position dans la correspondance

de+f

de

0

while

while

0

a{0,3}while

while

0, 1, 2, ou 3

(worth)?while

while

0 ou 5

for|while

Aucune

Si cette heuristique est sélectionnée, QRegExp::search utilisera uniquement le moteur de correspondance généralisé, quand la correspondance potentielle contient la chaîne fixe dans une position correcte. Par exemple, l'expression complète n'est lancée que deux fois sur vingt-six dans la chaîne suivante :

headed deer ddd eee fff

QRegExp::search localise les bonnes séries avec la fonction QString::find.

V-B-2 - Heuristique de mauvais caractère

Des mauvais caractères sont des caractères qui ne peuvent apparaître dans une correspondance. Si cette heuristique est sélectionnée, QRegExp::serach ne lance le moteur que quand la correspondance potentielle ne contient aucun caractère rejeté. Par exemple, de+f ne peut pas correspondra à "dxf", vu que "x" n'apparaît dans aucune correspondance, il n'y a donc pas d'utilité à utiliser le moteur dessus.

Cette heuristique ne s'arrête pas à distinguer les mauvais des bons caractères : elle reconnaît aussi que quelques bons caractères sont meilleurs que d'autres. Dans de+f, "d" peut apparaître à la position 0, quand, ni "e", ni "f" ne peuvent apparaître.

Le moteur n'est lancé que trois fois sur cette chaîne :

a "hea"ded deer ddd eee fff

Pour bénéficier de cette heuristique, il vaut mieux éviter les grandes expressions, aussi bien que ?, \\d, \\s, \\w, \\D, \\S, \\W. L'heuristique fonctionne mieux quand la majorité des caractères sont mauvais et que seuls quelques uns sont bons.

Respect de la casse et performances La majorité des interpréteurs d'expressions régulières, dont celui de Perl 5.0, implémente la recherche avec respect de la casse avec une conversion de l'expression régulière et un recherche à l'avance dans le texte en minuscule. QRegExp ne souffre pas de ce problème de performances. Cependant, faites attention que cette dernière heuristique n'est disponible que pour les correspondances sensibles à la casse. Les expressions régulières qui n'y sont pas sensibles et qui ne contiennent pas une bonne série peuvent être remplacées par une expression régulière sensible à la casse, si elles sont utilisées fréquemment. Par exemple, changer true|false pour [Tt][Rr][Uu][Ee]|[Ff][Aa][Ll][Ss][Ee], ou bien pour true|TRUE|false|FALSE, si cette solution ne vous convient pas.

V-C - Statistiques

La fonction interne heuristicallyChooseHeuristic() sélectionne l'heuristique la plus appropriée en se basant sur l'expression régulière. Elle calcule des scores pour les deux heuristiques selon une formule mathématique. Le tableau suivant montre les scores avec les deux heuristiques des deux expressions régulières.

Expression régulière

Score pour l'heuristique de bonne série

Score pour l'heuristique de mauvais caractère

while

64

31

\\bwhile\\b

64

31

(worth)?while

59

31

[Ww][Hh][Ii][Ll][Ee]

Inapplicable

31

for|while

Inapplicable

30

[A-Z_a-z][A-Z_a-z0-9]*

Inapplicable

18

.(for|while)

Inapplicable

Inapplicable

Les lecteurs curieux ou enthousiastes peuvent compiler leurs propres statistiques en insérant cette expression vers la fin de heuristicallyChooseHeuristic() dans qregexp.cpp.

qDebug( "gsh %d, bch %d, '%s' at %d..%d",
goodStringScore, badCharScore,
goodString.isNull() ? "" : goodString.latin1(),
goodEarlyStart, goodLateStart );

La fonction interne dump() peut aussi se révéler utile pour de telles investigations.

Les deux heuristiques sont utilisées dans QRegExp::search et QRegExp::find, mais pas dans QRegExp::searchRev ou QRegExp::findRev, ainsi, les recherches inversées peuvent être beaucoup plus lentes.

Le meilleur moyen d'optimiser une expression régulière est de ne pas en utiliser du tout !

Depuis que les expressions régulières sont compilées à l'exécution, elles ne peuvent pas être aussi rapides que du code optimisé à la main qui ne les utilise pas. Par exemple, sur une large entre, cette fonction est ridiculement lente.

text.replace( QRegExp("\r\n"), "\n" );

VI - Futilités mathématiques

Every program has (at least) two purposes: the one for which it was written, and another for which it wasn't.
Alan J. Perlis
(Tout programme a (au moins) deux objectifs : un pour lequel il a été écrit, et un autre pour lequel il ne l'a pas été).

Même si la majorité d'entre nous considèrent les expressions régulières dans le contexte de la manipulation de chaînes de caractères, elles sont aussi capables d'acrobaties dans la théorie des nombres, mieux implémentées avec des techniques traditionnelles de programmation.

Nous allons travailler avec des entiers positifs, des naturels, nous devons donc trouver un moyen utilisable de les représenter. Les scientifiques dans l'informatique sont familiers avec le binaire, l'octal, le décimal et l'hexadécimal. Les logiciens et les enfants non scolarisés, avec des notations unitaires. Nous trouverons que cette notation est la plus appropriée pour atteindre nos buts. Par exemple, les notations de 1, 2, 3, 4, et 5 sont I, II, III, IIII, et IIIII.

Avec le calcul unitaire, l'expression régulière (II)+ correspond aux naturels pairs, et I(II)*, les impairs. Par exemple :

QRegExp("I(II)*").exactMatch("IIII")

Retourne FAUX, car nous avons utilisé l'expression pour impairs, et 4 est pair.

L'expression régulière (I\\1*) correspond aux puissances de 2 : 0, 1, 2, 4, 8, 16, 32 ... Elle repose sur un détail de l'implémentation de QRegExp : \\1 dans la première parenthèse capturante s'étend au texte déjà pris jusque-là. Par exemple, dès que I est pris, un deuxième peut l'être par \\1, puis deux de plus pour nous amener au résultat de 4, puis 4 de plus, et ainsi de suite. De la même manière, (\\1I)+ correspond aux nombres triangulaires : 1, 3, 6, 10, 15, 21, 28 ...

Une expression régulière populaire et régulière dans le monde Perl est celle qui correspond aux nombres composés : (II+)\\1+. Son compagnon, (?!(II+)\\1+$)I*, correspond aux nombres premiers. Ces expressions régulières sont très non-déterministes, dans le sens expliqué ci-dessus. L'approche de QRegExp, dans les cas communs, plus rapide, empêche ces deux expressions de fonctionner correctement. Ceci est seulement un problème pour les expressions qui utilisent les références arrière, d'une manière non documentée.

D'un autre côté, QRegExp est peut-être unique en ce qu'il supporte les nombres de Fibonacci. Ces nombres appartiennent à la séquence 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., où chaque nombre est la somme de ses deux prédécesseurs (8 + 13 = 21 ; 13 + 21 = 34 ; ...). On les trouve généralement dans les livres d'informatique. Les deux expressions suivantes leur correspondent :

(?:((?:^I)?\\2\\3)(\\3\\1|(?=I$))(\\1\\2|(?=I$)))*I

(I(?:(\\1\\3)(\\1\\2))*(?:\\1\\3)?)|
((?:(\\4(?:^I)?\\6)(\\4\\5))*(?:\\4\\6)?)

Les deux contiennent des références arrière, qui précèdent les parenthèses capturantes précédentes, une fonctionnalité qu'aucun autre interpréteur d'expressions régulières ne supporte.

VII - Bogues ?

Cette implémentation de QRegExp a été utilisée au sein de Trolltech depuis août 2000. Très peu de bogues ont été découverts, et tous ont été résolus avant la sortie de Qt 3.0.

En fait, le problème le plus souvent reporté est que ceci ne convertit pas les barres obliques inverses en barres obliques :

text.replace( QRegExp("\\"), "/" );

Réellement, il ne devrait pas le faire. Le code correct est :

text.replace( QRegExp("\\\\"), "/" );

VIII - Références

La théorie à la base des expressions régulières est couverte dans Compilers: Principles, Techniques, and Tools, par Aho, Sethi, et Ullman. Mastering Regular Expressions, d'O'Reilly, par Jeffrey Friedl, est une lecture plaisante pour tous ceux qui s'intéressent aux expressions régulières. Cependant, faites attention à toutes les optimisations qui y sont proposées : elles ne s'appliquent qu'à Perl 5.0. Finalement, les lemmes heuristiques sont inspirés des algorithmes de Boyler-Moore, décrit dans la section 32 de Introduction to Algorithms, par Cormen, Leiserson, et Rivest.

IX - Divers

J'aimerais, ici, adresser un grand merci au groupe Qt, pour toute l'aide et les encouragements apportés lors de la traduction de ces articles, et, plus particulièrement, à yan, Alp, IrmatDen, Buggen25, et kinji1. Un tout grand merci à matrix788 pour la relecture !

Au nom de toute l'équipe Qt, j'aimerais adresser le plus grand remerciement à Nokia pour nous avoir autorisé la traduction de cet article !