20 janv. 2011

Le futur standard C++ : introduction aux expressions rationnelles

Décidément, ce blog fait la part belle au C++ en ce moment. Mais on ne se refait pas, et plus j'étudie le standard à venir, plus ses possibilités provoquent en moi le désir d'en savoir plus (et de partager avec vous ce savoir). Rajoutez à cela que le projet sur lequel je travaille nécessite de ma part d'écrire un outil de taille relativement modeste dans ce langage, et vous aurez une vision assez claire de ce à quoi je passe mes journées en ce moment. Mais nous ne sommes pas ici pour discuter des turpitudes de ma vie, donc passons au sujet qui nous intéresse.

Le TR1 avait introduit les expressions régulières directement tirées de la librairie Boost. Puisque le TR1 n'a jamais vraiment pris (la faute aux vendeurs de compilateurs, qui ont délaissé cette extension de la librairie jusqu'à récemment), on trouve peu d'exemple d'utilisation de cette fonctionnalité. Profitons donc du fait que les expressions régulières arrivent dans le nom d'espace std pour nous y intéresser.

C'est quoi, une expression régulière ?

D'abord, c'est un mauvais choix de nom. On va lui préférer le plus académique "expression rationnelle", mais l'usage veut qu'on autorise les termes "expression régulières" - la faute à ces satanés informaticiens qui n'ont pas pris le temps de traduire correctement l'anglais. Car en anglais, nous parlons bien de regular expression - sauf que regular est un faux ami dans ce contexte.

Bref. Une expression rationnelle, c'est une chaîne de caractères qui définit, via une syntaxe précise, un ensemble de chaînes de caractères. Si vous êtes curieux, vous trouverez dans cet article de Wikipedia quelques informations sur leur genèse. Voyons un exemple précis : le numéro de téléphone français.

Un numéro de téléphone est composé de 5 fois deux chiffres, séparés ou non par des espaces et des points. Tentons de décrire par une expression rationnelle un tel numéro. Tout d'abord, il faut qu'on se fixe une notation nous permettant de nous exprimer.

  • a est le caractère a (et le caractère espace est bel et bien le caractère espace)
  • X est un ensemble de caractères défini par X = expression rationnelle
  • [abc] est ce qu'on nomme généralement une classe de caractère. La correspondance getc() == [abc] est vraie si getc() renvoie a, b, ou c.
  • . représente n'importe quel caractère.
  • * et ? sont ce qu'on appelle des quantificateurs. X* signifie que X est répété 0 fois ou plus ; X? signifie que X est répété 0 ou une fois.
  • Pour représenter les caractères ., [, ], * et ?, on les préfixe avec un anti-slash (exemple: \*)
  • le caractère espace ' '

Avec ça, on défini :

// on définit la classe de caractères Chiffre 
C = [0123456789]
// l'expression rationnelle d'un numéro de téléphone
T = CC[ \.]?CC[ \.]?CC[ \.]?CC[ \.]?CC

Qu'est ce qui se passe ici ? On a bien 5 groupes de 2 chiffres, séparé par 0 ou 1 caractère choisi dans la classe de caractère [ \.] (soit espace ou point). 06 78 90 12 34 correspond bien à cette forme, de même que 067891234, 06.78.90.12.34 et bien d'autres encore[1] mais 06.78.901.234 ne peut pas correspondre à cette expression rationnelle (deux groupes de trois chiffres).

On peut complexifier à loisir les expressions rationnelles, jusqu'à pouvoir définir de manière complète un langage si besoin - car les expressions régulières partagent beaucoup avec les grammaires[2], dans le sens où l'on sait en dériver de manière sûre un automate fini déterministe. Du coup, de nombreuses librairies existent pour faciliter la vie du programmeur ayant besoin de leur puissance. Il a tout de même fallu attendre la sortie du TR1 pour les retrouver en standard, dans une notation purement C++, dans notre librairie standard.

Le header <regex>

Ce header (qu'on peut aussi retrouver sous la forme <tr1/regex> selon le compilateur) contient l'ensemble des déclarations et définitions nécessaires à la création d'expressions régulières. Les objets qui nous intéressent sont tous déclarés dans le nom d'espace std (voire std::tr1). Ceux qui voudraient tester les expressions rationnelles en C++ mais qui n'auraient pas accès à ces fichiers peuvent télécharger Boost.Regex - l'interface est très similaire, voire identique dans de nombreux cas.

Dans un premier temps, les classes qui vont nous intéresser le plus sont

  • std::basic_regex<> (et les typedef std::regex et std::wregex)
  • std::match_results<> et les typedes cmatch, smatch, ... (dépendant du type du conteneur ; chaine C ou std::string).

La première classe permet de définir des expressions régulières selon une ou plusieurs syntaxe (chaque implémentation est libre d'autoriser autant de syntaxe que nécessaire ; le standard impose les syntaxes suivantes : ECMAScript, basic (POSIX), extended (POSIX), awk, grep, et egrep). La seconde classe permet d'obtenir des informations sur le résultat de l'application d'une expression régulière à une chaîne de caractères particulière via un algorithme de correspondance (std::regex_match().

Construisons avec patience notre première expression régulière. La première chose que nous remarquons, c'est que certaines classes de caractères sont déjà définies :

  • alnum (et son alisa w) contient tous les caractères non accentués minuscule et majuscule, ainsi que les chiffres.
  • alpha contient tous les caractères non accentués minuscule et majuscule.
  • digit (d) contient tous les chiffres
  • blank (s) contient l'espace et la tabulation
  • xdigit contient les chiffres ainsi que [abcdefABCDEF]
  • lower et upper contiennent respectivement les lettres minuscules et majuscules
  • punct contient les caractères de ponctuation
  • ... (il y a encore d'autres classes ; la liste est présente dans votre fichier <regex>).

Une classe de caractère s'utilise avec la notation "[[:name:]]" ou name est le nom de la classe. Certaines classes possèdent un raccourcis sous la forme d'une séquence d'échappement:

  • \w pour [[:w:]]
  • \d pour [[:d:]]
  • \s pour [[:s:]]
  • mais aussi \D pour [^[:d:]] (tout sauf \d)
  • \W pour [^[:w:]]
  • \S pour [^[:s:]]

Du coup, on peut écrire une expression rationnelle correspondant à une adresse email simplifiée de la forme nom.prenom@societe.com[3] :

std::regex rx("\\w+\\.\\w+@\\w+\\.[[:lower:]]{2,3}");

Cette expression rationnelle signifie :

  • 1 ou plus caractère alphanumérique
  • point
  • 1 ou plus caractère alphanumérique
  • @
  • 1 ou plus caractère alphanumérique
  • 2 ou 3 lettres minuscules

C'est bien évidemment une forme très simplifiée (l'expression rationnelle complète est donnée dans la RFC définissant la forme d'une adresse email).

Une fois l'expression rationnelle construite, que devons nous faire ? Et bien pas grand chose. Il nous reste à appliquer un algorithme parmi ceux qui sont définis :

  • std::regex_match(), qui permet de savoir si la chaîne passée en paramètre correspond à l'expression régulière.
  • std::regex_search(), qui permet de savoir si l'expression régulière correspond à une partie de la chaîne passée en paramètre.
  • std::regex_replace(), qui permet de remplacer les parties correspondante de la chaîne paramètre par un autre contenu.

Chacun de ces algorithmes existe en plusieurs versions, implémentées sous la forme de surcharges - j'en compte pas moins de 6 pourstd::regex_search().

 std::smatch mr;
 bool r = std::regex_search(in.begin(), in.end(), match_result, rx); 
 if (r)
 {
   // rx a été trouvée dans in
   // mr0 contient la valeur trouvée. 
 }

Ah. On voit poindre cette histoire de std::match_results<>. Cette classe permet de stocker le résultat d'une recherche - mais pas de n'importe quelle manière. Si l'expression régulière définie ce qu'on appelle des sous-groupes, alors mr[1] à mr[n] contiendront les différentes parties de mr[0] correspondant aux sous-groupes définis. Par exemple :

 std::regex rx("(\\w+[\\._]?\\w*)@(\\w+\\.\\w+)");
 if (std::regex_search(in.begin(), in.end(), mr, rx))
 {
   // mr[0] contient une adresse email complète
   // mr[1] est le nom d'utilisateur
   // mr[2] est le nom de domaine
 }

L'opérateur [] de std::match_results<> renvoie un objet du type std::sub_match qui possède un opérateur de conversion implicite vers std::string (ou std::wstring).

Conclusion

Ce billet, contrairement aux autres de la même série, n'explique pas pourquoi telle ou telle partie a été conçue ainsi, ou les raisons qui sont derrière cette addition au standard. Il y a une raison simple à cela : tout d'abord, les expressions rationnelles sont, de part leur ubiquité, un ajout obligatoire à la bibliothèque. D'autre part, l'architecture de <regex> est directement héritée de celle de Boost. On trouve ici et là quelques faiblesses (par exemple, il n'est pas possible de préciser le type d'allocateur des chaines renvoyées par std::sub_match<>::str() ; dans 99,9% des cas, ça ne posera pas de problèmes. Dans le 0,1% restant, cela rends cette fonctionnalité librairie de la librairie inutilisable) mais dans l'ensemble, <regex> est simple a utiliser et relativement efficace. Le support de plusieurs syntaxes n'est pas pour nous déplaire - encore que là aussi, on entrevoit une faiblesse au niveau architecture, puisqu'il n'est pas possible d'étendre le fonctionnement de std::regex<> avec une autre syntaxe d'expression rationnelle.

On notera tout de même l'existence de systèmes concurrents beaucoup plus expressifs, tels que Boost.Spirit (encore que ce dernier aille bien au delà des expressions régulières), généralement à base de patrons d'expression (expression templates) et qui offrent des performances tout à fait correctes.

Quoi qu'il en soit, il ne nous reste plus qu'à s'en servir de manière avantageuse !

Notes

[1] y compris des formes moins canoniques telles que 06.7890.1234

[2] ça va jusqu'au point où le générateur de compilateurs Coco/R utilise la même syntaxe pour définir une expression régulière et une production de la grammaire

[3] exceptionnellement, pour des raisons de charges, je n'ai pas pu tester tous les exemples présentés ci-dessous. Ils vont être testés dans les prochaines jours, et les corrections nécessaires seront apportées si besoin. Veuillez m'en excuser.

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet