summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-09 14:53:36 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-12-09 14:53:36 (GMT)
commitf56f57e1462ea3e065943b94ae3c2eb352296099 (patch)
tree328ef0142cc53ae3fe76b53263d9260b7c7cb54d
parent2b4d6434bf41db0befe832114c89f273276eb8d6 (diff)
downloadinf105-f56f57e1462ea3e065943b94ae3c2eb352296099.zip
inf105-f56f57e1462ea3e065943b94ae3c2eb352296099.tar.gz
inf105-f56f57e1462ea3e065943b94ae3c2eb352296099.tar.bz2
Exercise on backreferences.
-rw-r--r--tp1-files/liste23
-rw-r--r--tp1.tex90
2 files changed, 82 insertions, 11 deletions
diff --git a/tp1-files/liste2 b/tp1-files/liste2
index c47b811..f77f2a4 100644
--- a/tp1-files/liste2
+++ b/tp1-files/liste2
@@ -2,8 +2,11 @@
* *
* * *
alcatraz
+allez
+allume-gaz
aujourd'hui
*coucou*
regexp
+tonton
toto
turlututu chapeau pointu
diff --git a/tp1.tex b/tp1.tex
index 8a22749..e9ea79d 100644
--- a/tp1.tex
+++ b/tp1.tex
@@ -139,6 +139,9 @@ renvoie les lignes de \texttt{monfichier} qui commencent par
\exercice
+{\footnotesize (Le but de cet exercice est d'utiliser \texttt{egrep}
+ dans un cadre proche du cadre théorique vu en cours.)\par}
+
Le fichier \texttt{\char"7Emadore/inf105/liste1} contient 25 mots sur
l'alphabet $\{\texttt{a},\texttt{b}\}$, tous distincts, à raison de un
par ligne. (On pourra commencer par jeter un coup d'œil au fichier,
@@ -191,6 +194,11 @@ modulo $3$ ?
\exercice
+{\footnotesize (Le but de cet exercice est d'introduire quelques
+ fonctionalités de \texttt{egrep} qui ne dépassent pas le cadre
+ théorique des expressions rationnelles mais qui sont néanmoins
+ utiles en pratique.)\par}
+
Le fichier \texttt{\char"7Emadore/inf105/liste2} contient des mots
(tous distincts) sur l'alphabet ASCII ; ces lignes peuvent contenir,
notamment, des espaces et des caractères spéciaux pour \texttt{egrep}.
@@ -211,7 +219,7 @@ caractère n'appartenant pas à l'intervalle entre \texttt{a} et
\texttt{z} ? (On rappelle pour cela la syntaxe « \texttt{.} »
d'\texttt{egrep} qui permet de désigner un caractère quelconque.)
-(c) Combien de lignes contiennent une astérisque ? (On rappelle qu'on
+(c) Combien de lignes contiennent un astérisque ? (On rappelle qu'on
peut « échapper » un caractère spécial pour \texttt{egrep} en le
faisant précéder d'un backslash (\texttt{\char"5C}).) Au moins deux
astérisques ? Exactement deux astérisques ?
@@ -226,19 +234,79 @@ moins trois fois le caractère \texttt{u} ? Exactement six fois le
caractère \texttt{u} ?
\begin{corrige}
-(a) \verb=egrep -c '^[A-Za-z]*$'= pour uniquement des lettres, et
- \verb='[^A-Za-z]'= pour un caractère qui n'est pas une lettre.
+(a) \verb=egrep -c '^[A-Za-z]*$'= pour uniquement des lettres
+ (renvoie $5$), et \verb='[^A-Za-z]'= pour un caractère qui n'est pas
+ une lettre (renvoie $7$).
+
+(b) \verb=egrep -c '^a.*z$'= (renvoie $3$)
+
+(c) \verb=egrep -c '\*'= pour un astérisque (renvoie $4$),
+ \verb='\*.*\*'= pour au moins deux (renvoie $3$), et enfin
+ \verb='^[^*]*\*[^*]*\*[^*]*$'= pour exactement deux astérisques
+ (renvoie $2$).
+
+(d) \verb=egrep -c '^.{6}$'= pour exactement six caractères
+ (renvoie $2$), \verb='^.{4,8}$'= pour entre quatre et huit
+ caractères (renvoie $7$), \verb='(u.*){3,}'= pour au moins trois
+ fois \texttt{u} (renvoie $2$), et \verb='^[^u]*(u[^u]*){6}$'= pour
+ exactement six \texttt{u} (renvoie $1$).
+\end{corrige}
-(b) \verb=egrep -c '^a.*z$=
+%
+%
+%
+
+\exercice
-(c) \verb=egrep -c '\*'= pour une astérisque, \verb='\*.*\*'= pour au
- moins deux, et \verb='[^*]*\*[^*]*\*[^*]*'= pour exactement deux
- astérisques.
+{\footnotesize (Le but de cet exercice est d'évoquer une fonctionalité
+ de \texttt{egrep} souvent importante dans la pratique et qui dépasse
+ le cadre des expressions rationnelles au sens mathématique : les
+ \emph{références arrière}.)\par}
+
+La syntaxe \texttt{\char"5C$n$} d'\texttt{egrep}, où $n$ est un
+chiffre entre $1$ et $9$, constitue une \emph{référence arrière} (ou
+\emph{backreference} en anglais) : cette extension au mécanisme
+général des expressions rationnelles permet de demander une répétition
+du même facteur qui a été « capturé » par un bloc de parenthèses
+antérieur (les blocs de parenthèses étant numérotés dans l'ordre de
+leurs parenthèses ouvrantes : ainsi \texttt{\char"5C{}1} désigne la
+chaîne de caractères qui a été vérifié par le bloc de parenthèses
+s'ouvrant à la première parentèse ouvrante). Par exemple,
+\texttt{(foo|bar)x*\char"5C{}1} recherche une occurrence de
+\texttt{foo} ou bien \texttt{bar}, suivi d'un nombre quelconque de
+\texttt{x}, suivi de la \emph{même} chaîne \texttt{foo} ou
+\texttt{bar} que précédemment (c'est donc équivalent à
+\texttt{(foox*foo|barx*bar)} mais pas à
+\texttt{(foo|bar)x*(foo|bar)}).
+
+(a) Comment utiliser \texttt{egrep} pour rechercher les lignes de
+\texttt{liste1} qui sont formées d'un certain nombre de \texttt{a},
+puis de \texttt{b}, puis du \emph{même} nombre de \texttt{a} que
+précédemment ?
+
+(b) Montrer qu'on ne pourrait pas faire cette recherche sans la
+fonctionalité additionnelle des références arrière, au sens où la
+recherche faite dans la question précédente ne définit pas un langage
+rationnel au sens mathématique.
-(d) \verb=egrep -c '^.{6}$'= pour exactement six caractères,
- \verb='^.{4,8}$'= pour entre quatre et huit caractères,
- \verb='(u.*){3,}'= pour au moins trois fois \texttt{u}, et
- \verb='^[^u]*(u[^u]*){6}$'= pour exactement six \texttt{u}.
+\begin{corrige}
+(a) On utilise \verb=egrep '^(a*)b\1$'= (qui renvoie trois lignes).
+
+(b) Il s'agit de montrer que le langage $L := \{a^n b a^n :
+ n\in\mathbb{N}\}$ constitué des mots formées d'un certain nombre de
+ $a$, suivis de $b$ puis du même nombre de $a$, n'est pas rationnel.
+ On utilise pour cela le lemme de pompage : supposons par l'absurde
+ que $L$ soit rationnel, et soit $k$ tel que donné par le lemme de
+ pompage ; considérons alors le mot $t := a^k b a^k \in L$ : il
+ devrait admettre une factorisation $t = uvw$ vérifiant (i) $|v|\geq
+ 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\in
+ \mathbb{N}$. La propriété (ii), vu que $t$ commence par $a^k$,
+ garantit que $u$ et $v$ sont formés entièrement de la lettre $a$,
+ disons $u = a^m$ et $v = a^n$ (où $m = |u|$ et $n = |v|$), en notant
+ que $n \geq 1$ d'après (i) ; on a alors $w = a^{k-m-n} b a^k$, et
+ $uv^iw = a^{m + in + (k-m-n)} v a^k = a^{k+(i-1)n} b a^k$ est censé
+ appartenir à $L$ pour tout $i$ ; en prenant $i \neq 1$, on a une
+ contradiction (puisque $k+(i-1)n \neq k$).
\end{corrige}