Remarks on regexp notations in the real computer world.

1 files changed, 85 insertions, 10 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 925301a..1aad5d4 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -679,6 +679,14 @@ On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
 lorsque ce mot appartient au langage qu'elle dénote (i.e., $w \in
 L_r$).  Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$.
 
+\thingy Deux expressions rationnelles $r_1,r_2$ sont dites
+\textbf{équivalentes} lorsqu'elles dénotent le même langage.  À titre
+d'exemple, sur l'alphabet $\{a,b\}$, les deux expressions rationnelles
+$(ab){*}a$ et $a(ba){*}$ sont équivalentes (toutes les deux dénotent
+le langage $\{a, aba, ababa, \ldots\}$ formé des mots commençant et
+finissant par un $a$ et dans lesquels chaque paire de $a$ est séparée
+par un unique $b$).
+
 \thingy La convention de parenthésage introduite ci-dessus est
 inambiguë mais parfois inutilement lourde : on se permettra parfois de
 l'alléger, par exemple d'écrire $(r_1|r_2|r_3)$ pour $((r_1|r_2)|r_3)$
@@ -698,9 +706,14 @@ après, et la barre de disjonction $|$ est la moins prioritaire
   subtilité qui n'a que très peu d'importance).\par}
 
 La barre de disjonction que nous avons notée ${|}$ est souvent plutôt
-notée $+$ par les mathématiciens.  Il y a ici un risque de confusion
-lié au fait que, en informatique, le symbole \texttt{+} est utilisé
-par de nombreux moteurs d'expressions régulières (par exemple,
+notée $+$ par les mathématiciens\footnote{Dans le même contexte
+  mathématique, il est alors fréquent de noter $0$ pour ce que nous
+  avons noté $\bot$ (c'est un élément neutre pour la disjonction), et
+  on en profite souvent pour noter $1$ pour $\varepsilon$ et/ou
+  $\underline{\varepsilon}$ (c'est un élément neutre pour la
+  concaténation).}.  Il y a ici un risque de confusion lié au fait
+que, en informatique, le symbole \texttt{+} est utilisé par de
+nombreux moteurs d'expressions régulières (par exemple,
 \texttt{egrep}) pour dénoter l'opération évoquée en \ref{kleene-plus},
 i.e., « au moins une répétition » alors que l'étoile signifie « un
   nombre quelconque de répétitions » : si on veut, $r{+}$ a le même
@@ -708,13 +721,75 @@ sens que $rr{*}$.  Dans le même contexte, le symbole \texttt{?} est
 souvent utilisé pour désigner « au plus une répétition » : si on veut,
 $r{?}$ a le même sens que $(\underline{\varepsilon}|r)$.
 
-\thingy Deux expressions rationnelles $r_1,r_2$ sont dites
-\textbf{équivalentes} lorsqu'elles dénotent le même langage.  À titre
-d'exemple, sur l'alphabet $\{a,b\}$, les deux expressions rationnelles
-$(ab)*a$ et $a(ba)*$ sont équivalentes (toutes les deux dénotent le
-langage $\{a, aba, ababa, \ldots\}$ formé des mots commençant et
-finissant par un $a$ et dans lesquels chaque paire de $a$ est séparée
-par un unique $b$).
+
+\subsection{Remarques sur les moteurs d'expressions régulières en informatique}
+
+\thingy Dans le monde informatique, il existe de nombreux
+\emph{moteurs d'expressions régulières}, c'est-à-dire outils (qu'il
+s'agisse de primitives d'un langage, de bibliothèques externes, de
+programmes en ligne de commande, ou autres) permettant de savoir si un
+mot est reconnu par une expression régulière (=rationnelle), autrement
+dit, s'il appartient au langage dénoté par elle.  L'un de ces moteurs
+est le programme \texttt{egrep} standard sous Unix/POSIX.
+
+\thingy Les expressions régulières au sens de ces différents moteurs
+sont généralement plus puissantes que les expressions rationnelles au
+sens mathématique défini ci-dessus : différentes extensions permettent
+de désigner des langages qui ne sont pas rationnels au sens
+mathématique.  L'extension la plus fréquente est celle des
+\emph{références arrière} (ou \emph{backreferences} en anglais) qui
+permettent de demander qu'un facteur du mot se retrouve à un autre
+emplacement.  Par exemple, pour beaucoup de moteurs (notamment
+\texttt{egrep}), l'expression régulière \texttt{(a*)b\char"5C\relax 1}
+désigne le langage $\{a^nba^n : a\in\mathbb{N}\} = \{b,aba,
+aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis
+d'un $b$ puis de la \emph{même suite de $a$}, et ce langage
+\emph{n'est pas rationnel} au sens mathématique (ce sera une
+conséquence du « lemme de pompage »).
+
+\thingy Il existe aussi un certain nombre de constructions qui, sans
+dépasser la puissance des expressions rationnelles au sens
+mathématique, apportent des commodités d'écriture dans un contexte
+informatique.  On a déjà mentionné les symboles \texttt{+} (pour « au
+  moins une répétition » : $r{+}$ est équivalent à $rr{*}$) et
+\texttt{?} (pour « au plus une répétition » : $r{?}$ est équivalent à
+$(\underline{\varepsilon}|r)$).  Parmi d'autres constructions du
+genre, mentionnons encore le point \texttt{.} qui désigne un caractère
+quelconque de l'alphabet (on peut le voir comme une abréviation pour
+$(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$ sont tous les éléments
+de $\Sigma$ — ce qui serait très fastidieux à écrire si on devait
+énumérer tout Unicode), ou bien \texttt{[$xyz$]} qui désigne un
+caractère quelconque parmi ceux listés (c'est donc la même chose que
+$(x|y|z)$ mais cela ne fonctionne qu'avec des caractères individuels ;
+en contrepartie, on peut écrire des intervalles comme \texttt{[a-z]}
+qui désigne un caractère quelconque entre \texttt{a} et \texttt{z}
+dans l'ordre ASCII/Unicode, ou bien des négations d'intervalles comme
+\texttt{[\char"5Ea-z]} qui désigne un caractère qui \emph{n'est pas}
+entre \texttt{a} et \texttt{z}).
+
+\thingy Une autre subtilité est que la plupart des moteurs
+d'expressions régulières en informatique vont, par défaut,
+\emph{rechercher un facteur} (appelé « sous-chaîne » en informatique)
+vérifiant l'expression à l'intérieur de la chaîne donnée, plutôt que
+tester si la chaîne elle-même vérifie l'expression.  Pour éviter ce
+comportement, on peut utiliser des \emph{ancres}, typiquement
+commandées par les caractères \texttt{\char"5E} et \texttt{\char"24}
+qui servent à ancrer l'expression au début et à la fin de la chaîne
+respectivement : c'est-à-dire que rechercher \texttt{a} recherche un
+\texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher
+\texttt{\char"5E\relax a} demande que le \texttt{a} soit au début de
+la chaîne donnée rechercher \texttt{a\char"24} demande que le
+\texttt{a} soit à la fin de la chaîne donnée, et rechercher
+\texttt{\char"5E\relax a\char"24} demande que la chaîne donnée soit
+exactement \texttt{a} (cet exemple n'est donc pas très utile, mais de
+façon générale, trouver si une chaîne vérifie une expression
+rationnelle $r$, revient à y chercher \texttt{\char"5E\relax
+  $r$\char"24}).
+
+\thingy Il existe malheureusement de nombreuses différences, parfois
+très subtiles, entre moteurs, ne serait-ce que dans les notations : un
+moteur pourra par exemple noter \texttt{(?)} ce qu'un autre note
+\texttt{\char"5C(\char"5C?\char"5C)} et vice versa.
 
 
 \section{Automates finis}