#Expressions régulièresCopier le lien

Une expression régulière décrit un langage: un ensemble de mots. Elle s'assemble à partir de trois constructions seulement, l'union, la concaténation et l'étoile de Kleene. Tout le reste, classes de caractères, quantificateurs, groupes, est du sucre syntaxique sur ces trois briques. Utilisée dans un moteur (grep, module re de Python, validateurs), la regex sert à chercher, extraire, remplacer et valider; la théorie derrière elle dit précisément ce qu'elle peut et ne peut pas exprimer.

Prérequis: notion de mot et d'alphabet, bases des automates finis (page AFN et AFD de ce module) pour le lien moteur/théorie, manipulation de chaînes en Python.

Objectifs d'apprentissage:

• Décomposer un motif en opérations rationnelles (union, concaténation, étoile) et connaître la précédence des opérateurs.
• Écrire des motifs robustes: ancrages, classes, quantificateurs gourmands vs paresseux, groupes capturants et nommés.
• Expliquer le comportement d'un moteur à retour arrière (correspondance la plus à gauche, gourmandise) et prédire ce qu'un motif va matcher.
• Reconnaître les motifs à backtracking exponentiel et les corriger.

#Les trois opérateurs fondamentauxCopier le lien

Une expression régulière sur un alphabet Σ se définit par induction. Les cas de base: le mot vide ε et chaque symbole a ∈ Σ décrivent les langages {ε} et {a}. Puis, si r et s décrivent L(r) et L(s):

• Union r|s: L(r) ∪ L(s). Le mot correspond à r ou à s.
• Concaténation rs: L(r)·L(s), tous les mots uv avec u dans L(r) et v dans L(s).
• Étoile r*: L(r), zéro ou plusieurs répétitions d'un mot de L(r). Le mot vide est toujours dans L(r).

Les autres opérateurs s'en déduisent: r+ signifie rr*, r? signifie (r|ε), [abc] signifie (a|b|c), [^a] est le complémentaire de a dans l'alphabet. C'est cette grammaire que la construction de Thompson transforme en automate: chaque opérateur devient un petit schéma à ε-transitions, et comme les langages reconnus par automates sont exactement les langages décrits par ces expressions, regex et automates ont le même pouvoir d'expression.

Précédence, de la plus forte à la plus faible: étoile, concaténation, union. Ainsi ab|cd se lit (ab)|(cd) et non a(b|c)d; ab* se lit a(b*). Quand c'est l'intention, les parenthèses sont obligatoires: (ab)* ne décrit pas le même langage que ab* (le premier contient abab, le second non).

#Syntaxe de base en pratiqueCopier le lien

• Littéraux: a, b, 1, @ correspondent à eux-mêmes.
• Classes de caractères: [abc] un caractère parmi a, b, c; [a-z] une lettre minuscule; [0-9] ou \d un chiffre; \w un caractère de mot (lettre, chiffre, underscore); \s une espace; [^0-9] ou \D tout sauf un chiffre.
• Quantificateurs: * zéro ou plus; + un ou plus; ? zéro ou un; {n} exactement n; {n,} n ou plus; {n,m} entre n et m.
• Ancrages: ^ début de chaîne (ou de ligne avec l'option multiligne), $ fin de chaîne ou juste avant un saut de ligne final, \b frontière de mot.
• Groupes: (...) capture; (?:...) groupe non capturant, pour factoriser sans numéro de groupe; (?P<nom>...) groupe nommé.

#Sémantique du moteur: la plus à gauche, puis la gourmandiseCopier le lien

Le module Python re utilise un moteur à retour arrière (backtracking). Sa règle de décision, quand on cherche avec search ou match, tient en deux points:

1. La correspondance la plus à gauche gagne. Le moteur essaie les positions de départ de gauche à droite et s'arrête à la première qui permet une correspondance complète.
2. À position égale, les quantificateurs sont gourmands. * et + consomment le plus possible, puis rendent des caractères un à un (backtracking) si la suite du motif échoue. ? gourmand préfère prendre. Les variantes paresseuses *?, +?, ?? font l'inverse: consommer le moins possible, puis agrandir si nécessaire.

Conséquence fréquente: <.*> sur "<a>texte<b>" capture tout le segment <a>texte<b> car .* est gourmand. La forme paresseuse <.*?> s'arrête au premier >. Savoir prédire ce comportement évite 90 % des surprises de débutant.

#Groupes et captureCopier le lien

Les parenthèses créent des groupes numérotés dans l'ordre d'ouverture, accessibles après la recherche.

1import re2 3text = "John Doe, 25 ans"4match = re.search(r"(\w+) (\w+), (\d+) ans", text)5if match:6    print("Prénom:", match.group(1))7    print("Nom:", match.group(2))8    print("Âge:", match.group(3))

#RemplacementsCopier le lien

re.sub remplace chaque correspondance, avec réutilisation des groupes capturés via \1, \2 ou \g<nom>.

1import re2 3text = "Il y a 3 pommes et 5 oranges."4print(re.sub(r"\d+", "X", text))5# Il y a X pommes et X oranges.6 7text = "Date: 2023-10-05"8print(re.sub(r"(\d{4})-(\d{2})-(\d{2})", r"\3/\2/\1", text))9# Date: 05/10/2023

#Parsing de logs HTTPCopier le lien

Cas d'école: extraire les champs d'une ligne de log d'accès. Le groupe non capturant (?:...) sert à factoriser sans polluer la numérotation.

1import re2 3log = '127.0.0.1 - - [20/Oct/2023:13:55:36 +0000] "GET /index.html HTTP/1.1" 200 2326'4pattern = r'(\d+\.\d+\.\d+\.\d+) - - \[([^\]]+)\] "(\w+) ([^ ]+) HTTP/(\d\.\d)" (\d+) (\d+)'5 6match = re.match(pattern, log)7if match:8    ip, date, method, path, version, status, size = match.groups()9    print(f"IP: {ip}")10    print(f"Date: {date}")11    print(f"Method: {method}")12    print(f"Path: {path}")13    print(f"Version: {version}")14    print(f"Status: {status}")

#Performance et sûreté: le backtrackingCopier le lien

Un moteur à retour arrière explore les choix du non-déterminisme par essais successifs. Sur certains motifs, le nombre d'essais double à chaque caractère supplémentaire: le temps devient exponentiel. Le cas d'école est (a+)+$ (ou (a|a)*$) face à une entrée aaaa...b presque valide: chaque façon de découper les a en groupes est tentée avant l'échec final.

Observez le temps qui double environ à chaque a ajouté, alors que la variante ^a+$ reste instantanée. La différence ne vient pas du langage reconnu (le même ici) mais de l'ambiguïté du motif: (a+)+ autorise un nombre exponentiel de découpages du même texte.

Défenses concrètes:

• Ancrer le motif (^...$) pour éliminer les positions de départ.
• Réduire l'ambiguïté: un quantificateur imbriqué dans un autre quantificateur comparable ((a+)+, (.*)*) est presque toujours une erreur. Le remplacer par une forme équivalente non ambiguë (^a+$).
• Borner les répétitions ({1,20} au lieu de *) quand le domaine s'y prête.
• Grouper sans capturer (?:...) quand les indices de groupes ne servent pas: plus rapide et moins trompeur.
• Poser un timeout côté serveur ou utiliser un moteur garanti linéaire (RE2, regex de Rust) sur des entrées non maîtrisées.

#Références arrière: au-delà des langages rationnelsCopier le lien

Une rétro-référence \1 réutilise le texte capturé par un groupe plus tôt dans le même motif.

1import re2 3text = "C'est un un test."4match = re.search(r"\b(\w+)\s+\1\b", text)5if match:6    print("Mot répété trouvé:", match.group(1))

Point théorique important: \b(\w+)\s+\1\b ne décrit pas un langage rationnel. Les langages de la forme « le mot se répète exactement », comme les palindromes ou a^n b^n, ne sont pas reconnaissables par automate fini (l'argument du pompage le montre). Les moteurs réels dépassent donc le cadre rationnel avec références arrière, assertions ((?=...), (?!...)) et captures. C'est précisément ce qui rend leur temps d'exécution difficile à borner, quand le socle purement rationnel, lui, se compile en automate à temps linéaire.

#Ce que les regex ne peuvent pas exprimerCopier le lien

Les langages rationnels échouent sur toute structure à comptage non borné ou à imbrication arbitraire:

• Parenthèses équilibrées dans le cas général: il faut une pile, donc un automate à pile ou une grammaire algébrique.
• HTML bien formé, langages à balises imbriquées: d'où les parseurs dédiés (HTML Parser, DOM).
• a^n b^n: deux moitiés à comparer exigent de la mémoire proportionnelle à l'entrée, ce qu'un automate fini n'a pas.

Règle pratique: si la validité dépend d'un appariement ou d'un comptage sur une longueur non bornée, la regex pure n'est pas l'outil. Elle reste imbattable pour la structure plate: identifiants, dates, codes, lignes de log, tokens d'un lexer. Quand l'imbrication est bornée et petite, on peut toujours développer le motif à la main, mais chaque niveau supplémentaire double sa taille: c'est la signature d'un langage non rationnel.

#Manipuler un langage: appartenance, énumération, préfixesCopier le lien

Une expression régulière n'est pas qu'un filtre: c'est une description finie d'un ensemble infini, sur laquelle on peut raisonner. Quatre manipulations reviennent constamment dans les exercices et dans la pratique.

#Décider l'appartenance sans exécuter de moteurCopier le lien

Pour tester si un mot appartient au langage décrit par une expression, on décompose le mot selon la structure de l'expression, au lieu de laisser un moteur chercher. C'est la méthode attendue à l'écrit, et elle oblige à comprendre la concaténation.

Soit le mot 10100010 et l'expression $(0^*10)^*$. Il faut découper le mot en blocs de la forme $0^*10$: chaque bloc se termine par 10 et peut avoir des 0 devant. Or 10100010 se lit 10 | 1000 | 10, et chaque bloc est bien de la forme $0^*10$ (avec $0^*$ vide, puis 00). Le mot appartient donc au langage. En revanche, 010111010 face à $(01+10)^*$: la découpe doit alterner exactement les blocs 01 et 10, mais le mot commence par 0 suivi de 1 puis 0 puis 1... la cinquième lettre est 1 alors que le troisième bloc devrait commencer par 0. Le mot est rejeté.

Deux pièges à connaître:

• $(0^*10)^*$ contient le mot vide (l'étoile autorise zéro répétition), contrairement à $0^*10$.
• $(11)^*$ contient le mot vide et 11, 1111, etc. Écrire (0 + (11)^*)^* revient à dire « n'importe quelle suite de 0 et de blocs 11 », donc à peu près tout: cette expression accepte 011100 — non pas parce qu'elle décrit bien quelque chose, mais parce qu'elle est trop permissive.

#Énumérer le langage, puis le trierCopier le lien

Soit $E = (a + ab + abb)(c + bc + cc)$. Le langage est un produit de concaténation de deux ensembles finis, donc il est fini et s'énumère en distribuant:

$L(E) = \{abbbc,\ abbc,\ abbcc,\ abc,\ abcc,\ ac,\ acc\}$

Sept mots. L'ordre lexicographique (avec $a < b < c$, et un mot préfixe d'un autre classé avant lui) donne exactement la liste ci-dessus. Le point important: la taille du langage est $|A| \times |B| = 3 \times 3 = 9$ au plus, et ici $9 - 7 = 2$ collisions — abc s'obtient par a + bc et par ab + c. C'est la première chose à vérifier quand on énumère: le produit cartésien des ensembles de facteurs surestime le langage dès que deux factorisations différentes donnent le même mot.

#L'ensemble des préfixesCopier le lien

L'ensemble $\mathrm{Pref}(L)$ des préfixes des mots de $L$ — c'est-à-dire des débuts de mots, éventuellement le mot entier, éventuellement le mot vide — se calcule mot par mot:

$\mathrm{Pref}(L) = \{\varepsilon,\ a,\ ab,\ abb,\ abbb,\ abbbc,\ abbc,\ abbcc,\ abc,\ abcc,\ ac,\ acc\}$

Douze mots. Noter que $\mathrm{Pref}(L) \neq L$ et que $\mathrm{Pref}(L)$ contient des mots qui ne sont préfixes d'aucun autre mot de $L$ (comme abbb, préfixe de abbbc mais aussi de rien d'autre, et abbbc lui-même). Une expression régulière pour $\mathrm{Pref}(L)$ s'obtient en rendant facultatif chaque facteur terminal: $(a + ab + abb)(\varepsilon + c + bc + cc)$ — mais cette forme est trop large, elle fait apparaître c, bc, cc et abbb manque. La bonne expression est

$(a + ab + abb + abbb)(\varepsilon + c + bc + cc)$

c'est-à-dire: on garde le préfixe du premier facteur (jusqu'au b du milieu inclus, d'où l'ajout de abbb), puis on ajoute le second facteur ou rien. Ce n'est pas une formule mécanique: il faut regarder quels préfixes intermédiaires apparaissent effectivement, ce qui se fait en énumérant d'abord.

#Décrire un langage en français, et réciproquementCopier le lien

Passer d'une expression à une phrase et d'une phrase à une expression est l'exercice le plus formateur. Quelques cas typiques sur $\{0,1\}$:

La dernière mérite un mot: 10 répété donne 1010…, et les deux facteurs facultatifs autorisent à démarrer par 0 et/ou finir par 1, ce qui couvre les mots alternants de toutes les longueurs. C'est le langage $\{\varepsilon, 0, 1, 01, 10, 010, 101, 0101, 1010, \dots\}$.

Trois langages classiques et leurs expressions:

• mots se terminant par 011: $(0+1)^*011$;
• mots contenant le motif 101: $(0+1)^*101(0+1)^*$;
• représentations binaires des entiers impairs sans zéro de tête: $1(0+1)^*1 + 1$ — il faut un 1 en tête (pas de zéro non significatif) et un 1 en queue (parité), les deux se confondant pour le mot 1.

Et un langage qu'aucune expression régulière ne décrit: $\{0^n1^n : n \ge 0\}$. Le motif a l'air d'une concaténation, mais la contrainte « autant de 0 que de 1 » est un comptage non borné: c'est exactement la limite que le pompage met en évidence.

#Le complémentaire d'un langage rationnelCopier le lien

Le complémentaire est toujours rationnel (c'est la clôture par complémentation), mais trouver l'expression demande de raisonner, pas de calculer. Deux cas sur $\{a,b\}$:

• Complémentaire de $(a+b)^*b$ (mots finissant par b): ce sont les mots qui finissent par a, plus le mot vide. D'où $\varepsilon + (a+b)^*a$. Le mot vide est le piège habituel: il ne finit ni par a ni par b, mais il n'appartient pas au langage de départ, donc il est bien dans le complémentaire.
• Complémentaire de $((a+b)(a+b))^*$ (mots de longueur paire): ce sont les mots de longueur impaire, soit $(a+b)((a+b)(a+b))^*$. Là encore le mot vide n'est pas concerné: il est de longueur paire, donc il reste dans le langage initial.

#Les étoiles ne se distribuent pasCopier le lien

Deux identités fausses, à connaître car elles trahissent une intuition erronée:

$(L_1 \cup L_2)^* \neq L_1^* \cup L_2^* \qquad\text{et}\qquad (L_1 \cdot L_2)^* \neq L_1^* \cdot L_2^*$

Contre-exemples minimaux. Prenons $L_1 = \{a\}$ et $L_2 = \{b\}$. Alors $(L_1 \cup L_2)^* = \{a,b\}^*$ contient ab, tandis que $L_1^* \cup L_2^* = a^* \cup b^*$ ne le contient pas: les deux ensembles diffèrent. De même, $(L_1 \cdot L_2)^* = (ab)^*$ contient abab, alors que $L_1^* \cdot L_2^* = a^*b^*$ ne contient pas abab (un mot de $a^*b^*$ n'a jamais de a après un b).

La raison de fond: l'étoile permet de répéter l'alternance entre les deux ensembles, alors que distribuer l'étoile fige chaque ensemble dans sa propre répétition. C'est la même différence qu'entre « une suite de blocs de deux types, dans n'importe quel ordre » et « tous les blocs d'un type, puis tous les blocs de l'autre ».

#Séries génératrices d'un langage rationnelCopier le lien

Compter les mots d'un langage par longueur est un pont direct vers les séries formelles. À une expression régulière $E$ on associe sa série génératrice $S_E(X) = \sum_n a_n X^n$, où $a_n$ est le nombre de mots de longueur $n$ décrits par $E$. Les règles de traduction sont les mêmes que celles de la construction de Thompson:

• un symbole $a$ donne $X$;
• une union $E_1 + E_2$ donne $S_{E_1} + S_{E_2}$;
• une concaténation $E_1 \cdot E_2$ donne $S_{E_1} \times S_{E_2}$;
• une étoile $E^*$ donne $\frac{1}{1 - S_E}$.

Sur les quatre expressions précédentes:

Deux vérifications valent la peine, car elles montrent comment la série prouve la formule:

• Pour $((0+1)(0+1))^*$: chaque facteur de l'étoile a 4 mots de longueur 2, donc $S = \sum_k (4X^2)^k = \frac{1}{1-4X^2}$, et le coefficient de $X^{2k}$ vaut $4^k$. Le décompte direct donne $1, 0, 4, 0, 16, 0, 64$ pour $n = 0, \dots, 6$: conforme.
• Pour $(0+1)^*(00+11)(0+1)^*$: le motif central occupe 2 positions, et les $n-2$ positions restantes sont libres, ce qui donne $n-1$ placements possibles du motif; d'où $(n-1) \cdot 2^{n-2}$. Or $\frac{2X^2}{(1-2X)^2} = 2X^2\sum_{k\ge 0}(k+1)(2X)^k$, dont le coefficient de $X^n$ est $2 \cdot (n-1) \cdot 2^{n-2} = (n-1)2^{n-1}$. Les deux comptages coïncident, et l'accord confirme à la fois le placement du motif et le développement en série.

Cette traduction est exactement celle du cours de séries formelles du semestre 3: $X$ marque une position, le produit décale les positions, l'étoile somme les répétitions. Compter les mots d'un langage rationnel revient donc à lire les coefficients d'une fraction rationnelle.

#Mini-quizCopier le lien

#Exercice: validation d'identifiants et d'emails simplifiésCopier le lien

On veut valider des identifiants techniques et des adresses email simplifiées.

Partie A. Un identifiant valide: une lettre, puis des lettres, chiffres ou underscores (au moins un caractère au total). Écrivez la regex, testez-la sur x, _x, x_1, X9, 9x, a b.

Partie B. Une adresse email simplifiée: partie locale en caractères alphanumériques et ._%+-, un @, un domaine en caractères alphanumériques et .-, un point, puis une extension de 2 à 24 lettres.

1import re2 3id_pattern = re.compile(r'^[A-Za-z][A-Za-z0-9_]*$')4email_pattern = re.compile(r'^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,24}$')5 6def test(nom, pat, cas):7    print(nom)8    for c in cas:9        print(f"  {c!r:35s} -> {bool(pat.fullmatch(c))}")10 11test("Identifiants", id_pattern,12     ["x", "_x", "x_1", "X9", "9x", "a b"])13test("Emails", email_pattern,14     ["test@example.com", "invalid.email", "user@domain.co.uk",

#Correction et méthode de vérificationCopier le lien

Partie A: [A-Za-z][A-Za-z0-9_]* accepte x, x_1, X9 et refuse _x (commence par underscore), 9x (commence par un chiffre), a b (contient une espace et $/^ interdisent toute correspondance partielle).

Partie B: la regex donnée accepte les quatre adresses bien formées et refuse invalid.email (pas de @), @missing.org (partie locale vide) et a@b.c (extension d'une seule lettre, {2,24} exige au moins deux).

Méthode de vérification systématique, valable pour toute regex de validation: dressez un tableau de cas avec, pour chacun, le verdict attendu écrit avant d'exécuter, en incluant les frontières (vide, un caractère, caractère juste avant/après une classe, entrée presque valide). Une regex est validée quand l'exécution confirme le tableau entier, pas quand elle réussit sur quelques exemples choisis.

#Bonus: drapeaux et performancesCopier le lien

• Drapeaux utiles: re.IGNORECASE (i), re.MULTILINE (m: ^ et $ s'ancrent aux lignes), re.DOTALL (s: . accepte aussi le saut de ligne), re.VERBOSE (motif aéré avec commentaires).
• Précompiler: pattern = re.compile(motif) quand il sert dans une boucle; cela économise l'analyse du motif à chaque appel.
• Prefer fullmatch pour valider une entrée entière: cela équivaut à ^...$ sans réfléchir aux ancrages.

#Moteurs pratiques vs théorieCopier le lien

• Le socle rationnel (union, concaténation, étoile) se compile en automate et s'exécute en temps linéaire. Les moteurs DFA (RE2, regex de Rust, grep en mode -F étendu) restent dans ce socle et garantissent un temps linéaire, sans références arrière.
• Les moteurs à retour arrière (PCRE, Python re, Java java.util.regex) ajoutent références arrière et assertions, donc expriment plus que les langages rationnels, mais peuvent prendre un temps exponentiel sur des entrées adverses.
• Changer de moteur peut donc changer à la fois les performances et ce qui est reconnu: documentez toujours les extensions utilisées si le motif doit être portable.