Expression régulière

vignette|Stephen Cole Kleene, dont les travaux ont fondé le concept d'expression régulière. En informatique, une expression régulière ou expression rationnelle ou expression normale ou motif est une chaîne de caractères qui décrit, selon une syntaxe précise, un ensemble de chaînes de caractères possibles. Les expressions régulières sont également appelées regex (un mot-valise formé depuis l'anglais regular expression). Les expressions rationnelles sont issues des théories mathématiques des langages formels des années 1940. Leur capacité à décrire avec concision des ensembles réguliers explique qu’elles se retrouvent dans plusieurs domaines scientifiques dans les années d’après-guerre et justifie leur adoption en informatique. Les expressions régulières sont aujourd’hui utilisées pour programmer des logiciels avec des fonctionnalités de lecture, de contrôle, de modification, et d'analyse de textes ainsi que dans la manipulation des langues formelles que sont les langages informatiques. Les expressions régulières ont la qualité de pouvoir être décrites par des formules ou motifs (en anglais patterns) bien plus simples que les autres moyens. Dans les années 1940, Warren McCulloch et Walter Pitts ont décrit le système nerveux en modélisant les neurones par des automates simples. En 1956, le logicien Stephen Cole Kleene a ensuite décrit ces modèles en termes d’ensembles réguliers et d'automates. Il est considéré comme l'inventeur des expressions régulières. En 1959, Michael O. Rabin et Dana Scott proposent le premier traitement mathématique et rigoureux de ces concepts, ce qui leur vaudra le prix Turing en 1976. Dans ce contexte, les expressions régulières correspondent aux grammaires de type 3 (voir grammaire formelle) de la hiérarchie de Chomsky ; elles peuvent donc être utilisées pour décrire la morphologie d’une langue. Ken Thompson a mis en œuvre la notation de Kleene dans l’éditeur qed, puis l’éditeur ed sous Unix, et finalement dans grep.