1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2.5cm]{geometry}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{}
\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{}
\newcommand{\manfntsymbol}[1]{%
{\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
\hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{TP \texttt{egrep} — Corrigé}
\else
\title{TP \texttt{egrep}}
\fi
\author{David A. Madore}
\maketitle
\centerline{\textbf{INF105}}
{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}
\pretolerance=8000
\tolerance=50000
%
%
%
Le programme Unix \texttt{egrep} a pour fonction de rechercher
(\emph{filtrer}) les lignes d'un fichier dont une partie (au sens :
facteur d'un mot) vérifie une certaine expression rationnelle. La
syntaxe est : « \texttt{egrep} \textit{regexp} \textit{fichiers} » où
\textit{regexp} désigne l'expression à chercher et \textit{fichiers}
la liste des fichiers (un par argument) dans lesquels la recherche
doit être menée : par exemple, « \texttt{egrep toto monfichier} »
cherche dans \texttt{monfichier} toutes les lignes contenant
\texttt{toto} ; en retour, \texttt{egrep} produit les lignes
recherchées, éventuellement précédées du nom du fichier où elles ont
été trouvées, et en colorisant éventuellement la partie qui vérifie
l'expression (selon les options passées et/ou la colorisation).
\texttt{egrep} comporte de nombreuses options et particularités
d'expressions rationnelles, dont la liste peut être connue en
consultant le manuel (« \texttt{man egrep} »). Par exemple, l'option
\texttt{-c} sert à compter le nombre de lignes trouvées au lieu de les
afficher.
Il faut prendre garde au fait que le shell Unix va interpréter
certains caractères spéciaux : le moyen le plus simple de l'éviter est
d'entourer le paramètre à protéger de caractères \texttt{\char"27}
(apostrophe droite, ou guillemet simple), qui protège tous les
caractères jusqu'au prochain caractère \texttt{\char"27} rencontré.
Par exemple, « \texttt{egrep \char"27xy*z\char"27{} monfichier} »
cherche dans \texttt{monfichier} toutes les lignes dont une partie
vérifie l'expression rationnelle \texttt{xy*z}, c'est-à-dire, les
lignes contenant un \texttt{x} suivi d'un nombre quelconque
(éventuellement nul) de \texttt{y} et d'un \texttt{z}.
Pour rechercher les lignes vérifiant une certaine expression
rationnelle du début à la fin, on peut utiliser les caractères
spéciaux \texttt{\char"5E} et \texttt{\char"24} qui servent à ancrer
l'expression au début et à la fin de la chaîne respectivement : par
exemple, « \texttt{egrep \char"27\char"5Ex\char"27{} monfichier} »
renvoie les lignes de \texttt{monfichier} qui commencent par
\texttt{x}, et « \texttt{egrep \char"27\char"5Exy*z\char"24\char"27{}
monfichier} » renvoie celles qui sont exactement formées d'un
\texttt{x} (en début de ligne) suivi d'un nombre quelconque de
\texttt{y} et d'un \texttt{z} (en fin de ligne).
\exercice
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,
par exemple en tapant \texttt{cat \char"7Emadore/inf105/liste1} pour
l'afficher dans le terminal.) Utiliser \texttt{egrep} pour répondre
aux questions suivantes :
(a) Combien de mots de cette liste ne contiennent aucun \texttt{a} ?
(b) Combien de mots commencent par \texttt{b} ?
(c) Combien de mots sont formés d'un nombre quelconque de \texttt{a}
suivi d'un nombre quelconque de \texttt{b} ?
(d) Combien de mots sont formés d'un nombre non nul de \texttt{a}
suivi d'un nombre non nul de \texttt{b} ?
(e) Dans combien de mots chaque \texttt{a} est-il suivi d'(au moins)
un \texttt{b} ?
(f) Dans combien de mots le nombre de \texttt{a} est-il congru à $1$
modulo $3$ ?
\begin{corrige}
(a) \verb=egrep -c '^b*$'= (ou bien \verb='^[^a]*$'=)
renvoie $5$.
(b) \verb=egrep -c '^b'= (ou bien \verb='^b(a|b)*$'= ou encore
\verb='^b[ab]*$'=) renvoie $9$.
(c) \verb=egrep -c '^a*b*$'= renvoie $14$.
(d) \verb=egrep -c '^aa*bb*$'= (ou bien \verb='^a+b+$'=) renvoie $5$.
(e) \verb=egrep -c '^b*(abb*)*$'= (ou bien \verb='^b*(ab+)*$'=)
renvoie $11$.
(f) Si l'alphabet ne contenait que la lettre \texttt{a}, l'expression
rationnelle désignant le langage constitué des mots formé d'un
nombre de $a$ congru à $1$ modulo $3$ s'écrirait \texttt{a(aaa)*}.
On intercale des \texttt{b*} dans cette expression de manière à les
ignorer : \verb=egrep -c '^b*a(b*ab*ab*a)*b*$'= (ou bien
\verb='^b*ab*(ab*ab*ab*)*$'= ou toutes sortes d'autres variantes)
renvoie $11$.
\end{corrige}
%
%
%
\end{document}
|
