From f56f57e1462ea3e065943b94ae3c2eb352296099 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 9 Dec 2016 15:53:36 +0100 Subject: Exercise on backreferences. --- tp1-files/liste2 | 3 ++ tp1.tex | 90 +++++++++++++++++++++++++++++++++++++++++++++++++------- 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} -- cgit v1.2.3