Fondements mathématiques des expressions régulières

Dans ce premier article de la série, nous étudierons leurs origines mathématiques au milieu du XXe siècle. Bien que certains termes utilisés dans cet article puissent sembler étrangers ou effrayants au premier abord, veuillez persévérer : nous montrerons à quel point les concepts des expressions régulières sont simples à la base.

Langages formels

Avant de pouvoir commencer à parler des expressions régulières, nous devons faire un détour pour expliquer le concept de langages formels, car les expressions régulières ont leurs racines dans cette branche à la croisée de la logique, des mathématiques, de l'informatique et de la linguistique.

Pour simplifier, un langage formel est un ensemble de mots composés de lettres provenant d'un alphabet prédéfini ainsi qu'un ensemble de règles qui définissent comment former des mots valides à partir de ces lettres.

Nous utiliserons un exemple très terre à terre (pour nous les programmeurs) tout au long de la série d'articles : le langage des dates dans le format ISO 8601.

Pour réutiliser la même terminologie, le langage des dates dans le format ISO 8601 est l'ensemble de toutes les dates valides (mots) dans ce format de 0000-01-01 jusqu'à 9999-12-31. Ces mots sont composés de lettres de l'alphabet des dix chiffres et du caractère tiret { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-' } en utilisant des règles qui définissent des mots valides: quatre chiffres pour l'année, suivis d'un tiret, suivi de deux chiffres de 01 à 12 pour le mois, suivi d'un tiret, suivi de deux chiffres de 01 à 31 pour le jour.

1951 : Événements réguliers

En 1951, le mathématicien Stephen Cole Kleene a publié un article intitulé Representation of Events in Nerve Nets and Finite Automata où il présentait une notation pour décrire une séquence d'événements, qu'il a nommée événements réguliers, dans un réseau biologique de neurones (à ne pas confondre avec les réseaux neuronaux de l'IA). Cette notation simple, mais puissante et concise, maintenant appelée expressions régulières, permet de décrire un ensemble de langages formels appelés langages réguliers.

En théorie des langages formels, les expressions régulières sont composées de constantes, qui dénotent des ensembles de chaînes de caractères, et d'opérations sur ces ensembles.

Étant donné un alphabet fini Σ, les constantes suivantes sont définies comme expressions régulières :

• ∅ dénotant l'ensemble vide,
• ε dénotant l'ensemble ne contenant que la chaîne de caractères vide,
• a pour chaque a ∈ Σ dénotant l'ensemble ne contenant que le caractère a.

Étant donné les expressions régulières R et S, les opérations suivantes sur elles produisent des expressions régulières:

• RS dénotant la concaténation de R et S, l'ensemble de chaînes de caractères que l'on peut obtenir en concaténant une chaîne de caractères acceptée par R et une chaîne de caractères acceptée par S,
• R | S dénotant l'union de R et S, l'ensemble des chaînes de caractères acceptées par R ou S,
• R *, appelé l'étoile de Kleene, dénotant l'ensemble de chaînes de caractères que l'on peut obtenir en concaténant un nombre fini (y compris zéro) de chaînes de caractères de l'ensemble accepté par R.

Exemple 1 : Ex-aequo

Par exemple, décrivons le langage des différentes orthographes du mot ex-aequo à l'aide d'une expression régulière : ex-((a|ε)e|æ|é)quo qui utilise la concaténation et l'union. Cette expression régulière indique que les mots doivent :

• ex- : commencer par les lettres e, x et -,
• suivi de:
  • (a|ε)e : la lettre a ou la chaîne vide, suivie de la lettre e,
  • æ : ou de la lettre æ,
  • é : ou de la lettre é,
• quo : et se terminer par les lettres q, u, et o.

Remarquez que dans la deuxième partie de cette expression, la constante chaîne vide est utilisée pour rendre la lettre a facultative. Nous en verrons plus à ce sujet dans le deuxième article de la série.

Exemple 2 : Nombres

Prenons un exemple un peu plus complexe qui utilise l'étoile de Kleene. Voici une expression régulière pour représenter les nombres entiers et décimaux comme 42, 0 ou 12.34 :

(0|((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*))(((0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)|ε)

Laissez-moi le formater et le commenter pour vous :

(                          # La partie entière:
  0                        #   - 0
  |                        #   ou
  (
    (1|2|3|4|5|6|7|8|9)    #   - un chiffre entre 1 et 9,
    (0|1|2|3|4|5|6|7|8|9)* #     suivi de n'importe quel nombre de chiffres entre 0 et 9.
  )
)
(                          # La partie décimale:
  (
    .                      #   - un point,
    (0|1|2|3|4|5|6|7|8|9)  #   - suivi d'un chiffre entre 0 et 9,
    (0|1|2|3|4|5|6|7|8|9)* #   - suivi d'un nombre quelconque de chiffres entre 0 et 9.
  )
  |                        #   ou
  ε                        #   - la chaîne vide (rendant la partie décimale facultative).
)

Certains autres lecteurs pourraient faire remarquer que cela est très verbeux alors que les formes \\d et [1-9] auraient pu réduire la taille de cette regex. Mais cette syntaxe ne fait pas partie des mathématiques formelles des expressions régulières.

Exemple 3 : Dates ISO 8601

Revenant au langage des dates formatées ISO 8601, voici une expression régulière simple (mais verbeuse) pour la décrire :

((0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9))-(0(1|2|3|4|5|6|7|8|9)|1(0|1|2))-(0(1|2|3|4|5|6|7|8|9)|1(0|1|2|3|4|5|6|7|8|9)|2(0|1|2|3|4|5|6|7|8|9)|3(0|1))

D'accord, j'avoue, c'est vraiment pénible. Encore une fois, ce sera plus facile à lire avec un peu de mise en forme et de commentaires :

(                          # L'année:
  (0|1|2|3|4|5|6|7|8|9)    #   - millénaire
  (0|1|2|3|4|5|6|7|8|9)    #   - siècle
  (0|1|2|3|4|5|6|7|8|9)    #   - décennie
  (0|1|2|3|4|5|6|7|8|9)    #   - année
)
-
(                          # Le mois:
  0(1|2|3|4|5|6|7|8|9)     #   - janvier à septembre
  |                        #   ou
  1(0|1|2)                 #   - octobre à décembre
)
-
(                          # Le jour:
  0(1|2|3|4|5|6|7|8|9)     #   - 1er à 9e
  |                        #   ou
  1(0|1|2|3|4|5|6|7|8|9)   #   - 10e à 19e
  |                        #   ou
  2(0|1|2|3|4|5|6|7|8|9)   #   - 20e à 29e
  |                        #   ou
  3(0|1)                   #   - 30e ou 31e
)

Le lecteur astucieux remarquera que cette expression régulière "simple" produit certaines dates invalides, comme 2023-02-31. Bien sûr, février n'a pas 31 jours. Une expression régulière plus sérieuse gérerait ces cas, mais restons simples.

La suite

Comme nous venons de le voir à travers les trois exemples, les expressions régulières de Kleene sont simples, mais semblent assez puissantes pour représenter une grande variété d'expressions régulières. Dans le prochain article, nous quitterons le domaine des mathématiques et nous plongerons dans les premières applications des expressions régulières en informatique. De plus, nous démontrerons que malgré l'introduction d'une nouvelle syntaxe, ces expressions régulières "étendues" n'ajoutent pas plus de puissance expressive aux expressions régulières de Kleene et que les quelques constantes et trois opérations que nous avons découvertes ici sont en fait suffisantes pour représenter toutes les expressions que vous avez écrites.