From 0f49e47629141621e91f797db14eec61b8bb3583 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 25 Nov 2016 15:56:23 +0100 Subject: Remarks on regexp notations in the real computer world. --- notes-inf105.tex | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 85 insertions(+), 10 deletions(-) (limited to 'notes-inf105.tex') 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} -- cgit v1.2.3