Journal Expressions régulières ou expressions rationnelles ?

Sommaire

• • Aux prémisses de l'informatique : la théorie des langages
  • L’intégration de la théorie des langages à la langue française
  • De la théorie à la pratique : enrichissements et usages modernes
  • Conclusion

Je partage mon premier journal sur LinuxFr pour partager mes conclusions personnelles sur un débat ancien de plusieurs décennies : faut-il dire "expression rationnelle" ou "expression régulière" ? C'était encore un débat relativement fréquent dans ces colonnes il y a une quinzaine d'années. Il me semblait qu'il s'était éteint avec une victoire de fait du terme "expression régulière", mais je viens d'en voir passer un écho tout récemment : s'agit-il bien d'une victoire légitime ? Tentons une rétrospective.

Aux prémisses de l'informatique : la théorie des langages

Le mathématicien et logicien Stephen Cole Kleene est l'un des ancêtres de l'informatique. Fondateur de la théorie de la calculabilité, c'est lui qui invente les concepts d'expression régulière/rationnelle et de langage régulier, sans doute juste après la fin de la seconde guerre mondiale. Il définit un langage régulier comme un ensemble de mots pouvant être écrits à partir d'un alphabet et de 3 opérations : la concaténation (coller deux lettres ou mots ensembles), l'union ensembliste (avoir le choix entre deux lettres ou mots) et l'étoile de Kleene (répéter une lettre ou un mot un nombre arbitraire de fois).

Un langage régulier permet de décrire tous les mots constructibles par un automate fini, une autre invention toute récente. Il est décrit par une "regular expression". Kleene lu-même ne semble pas très à l'aise avec sa terminologie : Dans un article de 1951, il écrit lui-même, : "We would welcome any suggestions as to a more descriptive term" ("Nous sommes intéressé par toute proposition pour un terme plus descriptif" (section 7, page 49). La première pierre fondatrice de la discorde qui hante les moules de LinuxFr depuis des décennies est posée.

L’intégration de la théorie des langages à la langue française

L'outil Book Ngram Viewer permet de visualiser l'entrée de ces concepts dans la langue française. L'intérêt de la recherche pour ces concepts semble se manifester à partir de 1960 : dans la langue anglaise, l'usage de "rational expression" et "regular expression" se développe, avec quasiment immédiatement une préférence pour la seconde. Dans la langue française, il est difficile de relever une inflexion significative des usages. Néanmoins, "expression régulière" dépasse pour la première fois "expression rationnelle" vers 1960 : ces concepts ont donc probablement bien franchi l'Atlantique à cette date.

Et effectivement, on en trouve trace dans les écrits du chercheur français Marcel-Paul Schützenberger, l'un des pionniers de l'informatique théorique en France. Dans un article de 1959 (pp. 197-202), il présente une analogie entre les langages rationnels et les nombres rationnels : les opérations sont essentiellement les mêmes et, en enrichissant ces langages, on obtient l'analogue des nombres algébriques. Langages rationnels, nombres rationnels, … la boucle est bouclée, la terminologie correct que Kleene appelait de ses vœux est donc bien "expression rationnelle" ! Une expression rationnelle est une expression obtenue par des opérateurs rationnels. Ces opérateurs sont dits rationnels parce qu'ils permettent de générer tous les nombres rationnels et seulement eux. Fin du débat, allez mouler ailleurs.

De la théorie à la pratique : enrichissements et usages modernes

Ce serait bien si c'était si simple. Mais non, le terme "expression rationnelle" ne se répand pas significativement. En 1966, même Schützenberger, le maître et pionnier, utilise "expression régulière" en français dans ses cours (p. 62). Tout ça c'est de la faute des Américains et de leur langue pleine de mots ? En effet, on doit pouvoir admettre qu'à cette date "expression régulière" est un anglicisme, impropre, car "expression rationnelle" donne une représentation plus exacte du concept.

Pire, à partir de 1998, "expression régulière" commence à se répandre et s'impose face à sa concurrente. Pourquoi diantre les Français s'intéressent-ils tout d'un coup à l'informatique théorique et aux algèbres de Kleene ? Un indice : avec un temps d'avance, la tendance est identique en langue anglaise. Cela est bien sûr dû à l'entrée de l'informatique dans nos vies et à la bulle internet. Encore un coup des Américains ? Oui, mais pas que.

En trouvant des applications pratiques, les expressions régulières ont évolué. Elles ont gagné en fonctionnalité, en richesse d'expression, et expriment des langages plus riches que les langages rationnels. Un enrichissement en particulier leur permet de décrire des langages non rationnels : les références arrières (backreference). Exemple : l'expression régulière (a+)b\1 permet de reconnaître tous les mots de la forme aⁿ baⁿ, où les "a" sont répétés n fois à droite et à gauche du "b". Ce langage ne peut pas être décrit à l'aide d'expressions rationnelles classiques. Aujourd’hui, tous les moteurs d'expression régulière intègrent cette fonctionnalité.

Conclusion

En français, dans le contexte qui nous intéresse, les termes "expression régulière" et "expression rationnelle" sont sans doute aussi anciens l'un que l'autre. Bien que "rationnel" et "régulier" soient en général employés de manière synonymes, le premier terme semble préféré en théorie des langages. Au contraire, en informatique appliquée, "régulier" est clairement favorisé. Cette différenciation va de pair avec une nuance sémantique : parfois, on cherche à désigner des langages représentables par des automates finis. D'autres fois, on cherche à désigner des motifs sans se soucier de la théorie sous-jacente.

Il me semble donc pertinent de réserver le terme "expression rationnelle" aux propriétés des langages rationnels, tandis que "expression régulière" s'applique mieux aux outils pratiques. Cette distinction, loin d'être un barbarisme, reflète une évolution des usages adaptée aux besoins des théoriciens et des développeurs.

Et vous, avez-vous des raisons particulières de préférer un terme à l'autre ?