Books Home

INTRODUCTION AUX EXPRESSIONS REGULIERES

 

Bernard Desgraupes

272 pages - ISBN : 2-7117-8680-3

Editions Vuibert Informatique

 

Préface

De même qu'il existait sous l'Ancien Régime un clergé régulier et un clergé séculier, l'informatique moderne a développé la notion d'expressions régulières qui s'opposent à ce que l'on pourrait appeler les expressions textuelles. L'adjectif régulier est employé ici au sens de " qui obéit à des règles ". Les expressions régulières sont en effet un outil descriptif obéissant à des règles précises : ces règles sont une série de conventions de notation et de principes de construction servant à décrire abstraitement des éléments textuels.

Supposons par exemple qu'une certaine action doive être déclenchée chaque fois que l'un des mots tac, tic et toc est rencontré dans un fichier : il serait commode d'avoir une description unique de ces trois mots plutôt que de devoir mener trois fois la même investigation avec chacun d'entre eux. Il est clair que l'on peut les décrire comme étant constitués d'une lettre t, suivie de l'une des lettres a, i ou o, suivie de la lettre c : la syntaxe des expressions régulières permet de représenter cela très exactement au moyen du motif t[aio]c Si l'on veut par la suite inclure le mot tuc il suffira simplement de modifier cette expression en t[aiou]c.

Le degré d'abstraction dépend essentiellement du contexte d'utilisation. Dans certains cas, les mêmes mots pourront être décrits comme une consonne (t ou autre), suivie d'une voyelle, suivie d'une consonne (c ou autre), ce qui élargit considérablement la classe des mots décrits. Le rôle de la syntaxe des expressions régulières consiste donc à représenter de la manière la plus exacte les éléments que l'on souhaite décrire, sans en ajouter ni en omettre.

Elles ne se limitent bien entendu pas à la description de mots isolés mais peuvent représenter n'importe quel assemblage de texte.

Historique des expressions régulières

L'origine des expressions régulières remonte aux premières recherches théoriques menées sur les langages descriptifs symboliques au début des années 50. On en attribue la paternité au mathématicien Stephen Kleene (1909-1994) dont les travaux sur la théorie des algorithmes et des fonctions récursives sont à la base de l'informatique théorique. On lui doit la notion d'ensembles réguliers : les problèmes initialement abordés étaient ceux de la transmission des événements dans les réseaux neuronaux et leur représentation par des automates finis (Stephen C. Kleene, Representation of events in nerve nets and finite automata, Automata studies, Princeton University Press, 1956). Dans le domaine de l'informatique, le problème des expressions régulières est né de la nécessité, rencontrée par les premiers compilateurs, d'adopter une notation simple pour représenter des séquences formelles d'information.

À l'origine leur syntaxe était des plus réduites. Les systèmes d'exploitation possédant une ligne de commandes (tels que Unix ou MS-DOS) ont utilisé, par exemple, dès le début un certain nombre de symboles permettant de décrire de façon générique des noms de fichier. Ainsi, dans un shell Unix, une expression telle que *.html sert à désigner tous les fichiers d'un répertoire dont le nom se termine par l'extension html : le symbole * est dit métacaractère. Pour désigner tous les fichiers dont le nom commence par une des lettres a, b ou c on écrirait [a-c]* sous Unix. Avec MS-DOS, le même métacaractère * peut être utilisé de façon analogue pour désigner abstraitement une série de lettres : on représenterait par exemple tous les fichiers dont le nom commence par les lettres var au moyen de l'expression var*.* sur la ligne de commande. Le symbole * dans ce contexte est parfois qualifié de joker (en anglais wildcard).

Les expressions régulières se sont considérablement développées depuis ces origines lointaines et l'astérisque * a changé de signification. Les conventions de syntaxe décrivant les noms de fichiers s'appellent maintenant motifs globalisants. Elle est toujours en vigueur dans les shells et dans certains environnements mais ne fait pas partie de la syntaxe des expressions régulières.

On peut distinguer trois stades dans l'évolution des expressions régulières: il y a d'abord eu des expressions régulières dites de base (BRE) qui accompagnaient des éditeurs de textes tels que ed, ex, vi, sed ou bien l'utilitaire grep, puis leur syntaxe s'est étoffée de quelques ajouts que l'on a appellés les expressions régulières étendues (ERE) avec le développement du langage awk ou de l'utilitaire egrep. Les derniers développements sont apparus avec les versions récentes de langages de scripts évolués tels que Perl dans ses versions 5 ou supérieures, Tcl dans ses versions 8 ou supérieures ou encore Python à partir de sa version 1.5. On parle alors d'expressions régulières avancées. Enfin une nouvelle ère dans l'évolution des expressions régulières a été ouverte récemment avec l'introduction du support de l'encodage Unicode qui a fait son apparition avec les nouvelles versions de Perl, de Tcl et de Python. Nous y reviendrons en détail au chapitre 5.

Les expressions régulières doivent leur succès à tous les outils qui les ont rendues accessibles aussi bien aux programmeurs qu'aux simples utilisateurs. C'est en particulier l'ancien éditeur de lignes ed sur les premiers systèmes Unix qui est à l'origine du surnom de motifs grep qui est parfois donné aux motifs réguliers. Cet éditeur avait une commande appelée global, qui pouvait être simplement abrégée par la seule lettre g et qui permettait d'appliquer une commande à toutes les lignes comportant un certain motif sous la forme suivante :

    g/motif/commande
 

Par exemple avec la commande print, abrégée en p, on pouvait obtenir toutes les lignes contenant le mot Linux avec l'instruction :

    :g/Linux/p
 

Cette instruction utilisée avec une expression régulière re (abréviation de regular expression en anglais) devient ainsi formellement

    :g/re/p
 

Ceci explique l'origine du mot grep qui est le nom d'un des utilitaires les plus fameux du monde Unix.

Champs d'application

Les domaines d'utilisation des expressions régulières sont nombreux : elles interviennent dans le cadre de l'édition de toutes sortes de textes de même qu'en programmation. Dans le premier cas, elles feront gagner à leur utilisateur un temps considérable pour réaliser des tâches de recherche ou de substitution. Dans le second cas, elles seront irremplaçables dans tous les programmes interactifs : elles permettent d'analyser la nature d'une information, le contenu d'une variable ou d'un flux de données, de détecter la présence de telle ou telle information dont on connaît la structure mais dont le contenu n'est pas déterminé par avance etc.

L'apprentissage des expressions régulières, d'un autre côté, ne demande pas d'effort particulier : leur syntaxe est quasi rudimentaire et un peu de pratique permettra très rapidement d'assimiler leur utilisation et d'apprendre à détecter les quelques pièges à éviter.

De nos jours, l'essentiel de la syntaxe de base et de la syntaxe étendue est supporté par la plupart des applications, des langages et des utilitaires qui ont recours à la technique des expressions régulières pour exécuter certaines de leurs fonctions. Il s'agit en quelque sorte d'un dénominateur commun. Cela n'empêche pas de rencontrer ici ou là de réelles différences ou simplement des divergences par rapport à la syntaxe commune : il s'agit dans l'ensemble de détails mineurs mais il faut être conscient des différences et des idiosyncrasies lorsque l'on a affaire à un nouvel outil. À titre d'exemple, certains éditeurs de texte utilisent le symbole # pour représenter des nombres entre 0 et 9 : c'est le cas par exemple de BBEdit sur Macintosh. Il s'agit là d'une pratique particulière : un nombre entre 0 et 9 est habituellement représenté par la séquence \d (syntaxe qui est aussi reconnue par BBEdit bien entendu).

Pour assurer une certaine cohérence à l'ensemble de la syntaxe régulière, des règles ont été préconisées par la norme POSIX. Aucun outil actuellement n'implémente la norme POSIX dans son intégralité mais presque tous s'en inspirent. On sera donc amenés chaque fois à s'interroger sur ce qui est disponible ou pas.

Comment lire cet ouvrage

La syntaxe des expressions régulières est extrêmement simple et son apprentissage ne présente pas de difficulté particulière. Une fois maîtrisées, les expressions régulières se révèlent être un outil d'une extraordinaire puissance. Elles permettent dans de nombreuses situations de gagner un temps considérable. Leur utilisation néanmoins demande à la fois pratique et doigté : il n'y a pas une manière unique de décrire une situation au moyen d'une expression régulière mais il y aura certainement des solutions meilleures que d'autres.

Comme nous le verrons à travers les chapitres consacrés aux utilisations spécifiques des expressions régulières, celles-ci n'ont de véritable intérêt pratique qu'à travers les programmes qui les utilisent. Elles sont un outil extrêmement puissant mais c'est l'environnement dans lequel on les utilise qui fait leur efficacité : en particulier, jointes à un langage de script qui permet de traiter les expressions identifées, il n'y a quasiment pas de limites aux possibilités de traitement des données textuelles les plus variées.

Nous serons donc amenés successivement dans cet ouvrage à étudier la syntaxe des expressions régulières d'un point de vue abstrait et formel puis ensuite à examiner les principaux outils qui en font usage et à souligner toutes leurs particularités. Le chapitre 1 commence par exposer les principes de base des expressions régulières. Le chapitre 2 a pour but de mettre en pratique les notions générales à travers des exemples de situations couramment rencontrées : les exemples sont progressifs et sont choisis afin de mettre en lumière des techniques et des aspects particuliers.

Aujourd'hui les langages de scripts majeurs que sont Tcl, Python et Perl offrent des fonctionnalités évoluées qui puisent toutes à la syntaxe préconisée par la norme POSIX : c'est ce qui sera exposé au chapitre 3. La lecture de ces trois premiers chapitres est indispensable et permettra de faire un apprentissage complet des expressions régulières.

Les chapitres qui suivent sont tous consacrés à un langage ou bien à des outils spécifiques faisant usage des expressions régulières : ils sont destinés à faire le point sur les syntaxes acceptées par ces programmes, sur les idiosyncrasies liées à tel ou tel environnement etc. Ils exposent les caractéristiques des expressions régulières de la manière la plus complète possible mais supposent bien entendu que le lecteur soit déjà quelque peu familier avec la syntaxe générale de ces programmes. La lecture de ces chapitres suppose d'avoir assimilé les trois premiers et y fait constamment référence. On trouvera donc des chapitres consacrés aux langages de scripts majeurs que sont Tcl (chap.4), Perl (chap.5), Python (chap.6), awk (chap.7) et JavaScript qui est devenu une référence pour la constitution de pages Web interactives (chap.8).

Le chapitre 9 se consacre à l'utilisation des expressions régulières comme outil de recherche et étudie les programme de la famille grep. Le chapitre 10 présente les expressions régulières dans le cadre de quelques éditeurs de textes : parmi le très grand nombre d'éditeurs disponibles qui acceptent les expressions régulières, nous avons choisi de retenir l'éditeur de flux sed qui a énormément contribué à leur popularisation ainsi que deux éditeurs fameux, emacs et Alpha, qui ont ceci de remarquable qu'ils sont programmables, ce qui leur confère un intérêt supplémentaire du point de vue qui nous intéresse ici.

Bien que le présent ouvrage entende se limiter à une introduction aux expressions régulières et à leur utilisation, nous évoquerons en annexe les problèmes théoriques liés à la modélisation de ces expressions et à leur implémentation dans des programmes informatiques. Si la syntaxe est simple, sa réalisation en revanche peut conduire à des problèmes logiques et algorithmiques complexes : nous tenterons d'en donner un aperçu afin d'orienter le lecteur vers des lectures plus poussées. Ce sont des détails qui ne concernent en rien le simple utilisateur des expressions régulières.

Enfin une annexe constituée de tableaux synoptiques pour la référence rapide, un lexique anglais-français et quelques adresses Internet sont réunis à la fin de l'ouvrage.

Le vocabulaire des expressions régulières

Tout au long de cet ouvrage, nous adoptons quelques conventions de langage que nous précisons ici. Les expressions régulières sont parfois appelées motifs réguliers ou simplement motifs : il y a des motifs de recherche et des motifs de remplacement. Dans chaque cas, il s'agit d'une expression littérale qui emploie la notation définie par la syntaxe des expressions régulières. Le mot chaîne ou encore chaîne de caractères est employé pour désigner aussi bien toute portion de texte qui sert de support à une recherche qu'une variable d'un programme ayant le type chaîne (en anglais string) : il n'y a en principe aucune ambiguïté possible. Lorsqu'une expression régulière a réussi à identifier ou à représenter une portion de texte, on dit qu'il y a correspondance : de manière générale on appelle correspondance toute chaîne de caractères trouvée à l'intérieur d'un fichier ou d'une autre chaîne et qui correspond exactement à ce que décrit une expression régulière particulière. On dit aussi que l'expression régulière a trouvé une correspondance ou encore que la chaîne est reconnue par l'expression régulière. Enfin, nous utiliserons souvent le verbe échapper dans un sens particulier : échapper un symbole signifie simplement le faire précéder d'une contre-oblique \ ce qui concerne, nous le verrons, les symboles jouant un rôle de métacaractère et a pour effet de les désactiver.

Tous les autres termes techniques utilisés seront définis au moment où ils seront rencontrés. Nous évitons le terme de motif grep utilisé dans certaines documentations et dans certains programmes. Il est simplement synonyme de motif régulier. Les expressions régulières sont parfois appelées aussi expressions rationnelles. On les trouve aussi très souvent désignées dans la littérature informatique anglo-saxonne par les simples lettres re ou RE (abréviation pour regular expression) ou encore sous une forme contractée : regex ou encore regexp.

Bernard Desgraupes

Paris, janvier--mars 2001