Expressions Régulières

Pourquoi cette annexe ?

Le cours de Web Sémantique commence par une opération si triviale qu'on n'y pense même plus : découper du texte. Un .split() par-ci, un re.findall() par-là, et on obtient des mots. Mais derrière cette apparente simplicité se cache une théorie magnifique qui mêle logique, algèbre, automates et langages formels.

Cette annexe n'est pas un cours d'ingénierie linguistique. C'est un rappel — ou une découverte, selon d'où vous venez — de ce que sont les expressions régulières, comment elles fonctionnent vraiment (automates non déterministes → déterministes), et pourquoi des outils centenaires (dans le monde numérique) comme grep et sed sont encore les meilleurs amis du développeur.

Qu'est-ce qu'une expression régulière ?

Une expression régulière (ou regex) est une notation compacte pour décrire un ensemble de chaînes de caractères. Au lieu de lister « aa, ab, ba, bb », on écrit [ab]{2}. Au lieu de dire « une adresse email », on écrit \w+@\w+\.\w+.

Derrière cette notation, il y a trois opérations de base, définies par Kleene en 1956, et qui suffisent à tout construire :

C'est tout. Trois opérations suffisent à décrire n'importe quel langage régulier. Tout le reste — +, ?, [a-z], \d, les groupes, les lookaheads — n'est que du sucre syntaxique. (Du sucre délicieux, certes, mais du sucre.)

Sucre syntaxique courant

Cette citation célèbre est un avertissement : les regex sont puissantes mais cryptiques. Un ^(?=.*[A-Z])(?=.*\d).{8,}$ est illisible pour un humain normal. Mais bien utilisées, elles restent l'outil le plus efficace pour manipuler du texte.

Des regex aux automates

Une expression régulière, c'est bien joli, mais comment un ordinateur fait-il pour décider si une chaîne correspond ? La réponse, c'est les automates finis.

L'idée est simple : on transforme la regex en une machine abstraite composée d'états et de transitions. On lui donne la chaîne caractère par caractère, et si à la fin on est dans un état « acceptant », la chaîne est reconnue.

Automate Non Déterministe (NFA)

Le plus facile à construire à partir d'une regex. Il a deux super-pouvoirs :

• Il peut avoir plusieurs transitions pour le même caractère (on ne sait pas quel chemin choisir → on les explore tous)
• Il a des transitions ε (epsilon) : des sauts « gratuits » qui ne consomment pas de caractère

Exemple : la regex a(b|c)* donne le NFA suivant (en ASCII, parce que le vrai SVG coûte 50 lignes de code) :

La construction systématique d'un NFA à partir d'une regex s'appelle la construction de Thompson (Ken Thompson, 1968). Chaque opération de base correspond à un petit motif d'automate :

Automate Déterministe (DFA)

Le NFA, c'est bien, mais il a un problème : pour savoir si une chaîne est reconnue, il faut explorer tous les chemins possibles en parallèle. C'est inefficace. La solution : transformer le NFA en DFA (Automate Fini Déterministe), où chaque état ne peut avoir qu'une seule transition par caractère.

La transformation s'appelle la construction par sous-ensembles (ou « powerset construction »). L'idée :

1. On part de l'ε-fermeture de l'état initial du NFA (tous les états atteignables par des ε-transitions).
2. Pour chaque caractère possible, on suit toutes les transitions depuis tous les états de cet ensemble, et on referme par ε.
3. Chaque ensemble d'états du NFA devient un état du DFA.
4. On répète jusqu'à n'avoir plus de nouveaux ensembles.

Résultat : un DFA avec potentiellement exponentiellement plus d'états que le NFA (mais en pratique, c'est très raisonnable).

Minimisation

Une fois le DFA construit, on peut le minimiser en fusionnant les états équivalents (algorithme de Moore ou de Brzozowski). Le résultat est un automate minimal unique pour un langage donné. C'est beau, c'est optimal, et ça s'enseigne en cours de théorie des langages (vous avez suivi, n'est-ce pas ?).

grep — Global Regular Expression Print

grep est l'outil Unix le plus légendaire. Inventé par Ken Thompson en 1974 (en une nuit, paraît-il, pour aider Ed à chercher du texte), il permet de filtrer les lignes d'un fichier qui correspondent à une regex.

Usage de base

bash# Chercher toutes les lignes contenant "error"
  grep 'error' log.txt

  # Compter le nombre de lignes avec "error"
  grep -c 'error' log.txt

  # Afficher le numéro de ligne
  grep -n 'error' log.txt

  # Inverser : lignes qui ne contiennent PAS "error"
  grep -v 'error' log.txt

  # Ignorer la casse
  grep -i 'error' log.txt

Expressions régulières étendues (-E)

Par défaut, grep utilise les regex de base (BRE), où +, ?, |, () doivent être échappés. Avec -E (ERE), on écrit naturellement :

bash# Lignes contenant "foo" ou "bar"
  grep -E 'foo|bar' data.txt

  # Adresses email (version simple)
  grep -E '\b\w+@\w+\.\w+\b' emails.txt

  # Lignes commençant par '#' (commentaires)
  grep -E '^#' config.ini

  # Numéros de téléphone français (10 chiffres, séparés ou non)
  grep -E '(0[1-9])([-. ]?[0-9]{2}){4}' annuaire.txt

Cas pratique — analyse de logs

Imaginez un fichier de log Apache avec des milliers de lignes. Vous voulez trouver les IP qui ont fait des requêtes POST en erreur 500 entre 14h et 15h :

bash# Un petit coup de grep bien senti
  grep -E '14:(0[0-9]|1[0-9]|2[0-9]|3[0-9]|4[0-9])' access.log | \
    grep -E 'POST' | \
    grep -E ' 500 ' | \
    grep -Eo '^[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+' | \
    sort | uniq -c | sort -rn

  # Résultat : liste des IP défaillantes, triées par fréquence

Variantes modernes

sed — Stream EDitor

Si grep est le couteau suisse de la recherche, sed est celui de la transformation. sed lit un fichier ligne par ligne, applique des transformations, et écrit le résultat. Sans ouvrir le fichier dans un éditeur. Sans souris. Sans GUI. Rien que du terminal.

Substitution — le verbe s

La commande la plus utilisée de sed est s/ : substitution. Le pattern classique : s/regex/remplacement/drapeaux.

bash# Remplacer "foo" par "bar" sur chaque ligne
  sed 's/foo/bar/' fichier.txt

  # Remplacer globalement (pas juste la première occurence par ligne)
  sed 's/foo/bar/g' fichier.txt

  # Sauvegarder le résultat dans un nouveau fichier
  sed 's/foo/bar/g' fichier.txt > nouveau.txt

  # Modifier le fichier en place (-i = in-place)
  sed -i 's/foo/bar/g' fichier.txt

Références arrière (backreferences)

Avec \(…\) (BRE) ou (…) (ERE avec -E), on capture des parties de la ligne et on les réutilise dans le remplacement avec \1, \2, etc.

bash# Inverser "Nom, Prenom" → "Prenom Nom"
  sed -E 's/^(.+), (.+)$/\2 \1/' annuaire.txt

  # Standardiser des numéros de téléphone : 06.12.34.56.78 → 0612345678
  sed -E 's/0([1-9])[.-]?([0-9]{2})[.-]?([0-9]{2})[.-]?([0-9]{2})[.-]?([0-9]{2})/0\1\2\3\4\5/g' contacts.txt

  # Ajouter une balise HTML autour d'un mot
  sed -E 's/\b(urgent)\b/\1<\/strong>/gi' emails.txt

bash# Supprimer les lignes vides
  sed '/^$/d' fichier.txt

  # Supprimer les lignes 10 à 20
  sed '10,20d' fichier.txt

  # Afficher seulement les lignes 5 à 8
  sed -n '5,8p' fichier.txt

  # Ajouter une ligne "<hr>" après chaque ligne de titre
  sed '/^# /a <hr>' article.md

bash# Entrée : "Jean DUPONT", "jean@email.com",  "32", "Paris"
# Problème : guillemets, espaces en trop, valeurs mixées

# 1. Enlever les guillemets
sed -E 's/"([^"]*)"/\1/g' data.csv | \
  # 2. Nettoyer les espaces après les virgules
  sed -E 's/, +/,/g' | \
  # 3. Remplacer les points-virgules par des virgules (fichier européen)
  sed 's/;/,/g' | \
  # 4. Ne garder que les lignes avec une adresse email valide
  grep -E '^[^,]+,[^,]+@[^,]+\.\w+,'

  # Résultat : un CSV propre, prêt à être parsé par Python