path: root/tp1.tex

%% 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}

%
%
%

\exercice

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}.

(a) Combien de lignes ne contiennent que des lettres de l'alphabet
latin (de A à Z sans diacritiques, majuscules comme minuscules) ?  (On
rappelle pour cela la syntaxe « \texttt{[abc]} » d'\texttt{egrep} qui
permet de désigner un caractère parmi \texttt{a}, \texttt{b} et
\texttt{c} (c'est donc synonyme de \texttt{(a|b|c)} mais uniquement
pour des caractères individuels) et « \texttt{[a-f]} » qui désigne un
caractère entre \texttt{a} et \texttt{f}.)  Combien de lignes
contiennent un caractère autre que les lettres de l'alphabet latin ?
(On rappelle que « \texttt{[\char"5Ea-f]} » permet de désigne un
caractère n'appartenant pas à l'intervalle entre \texttt{a} et
\texttt{f}.)

(b) Combien de lignes commencent par un \texttt{a} et finissent par un
\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
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 ?

(d) Combien de lignes contiennent exactement six caractères ?  (On
rappelle les syntaxes « \texttt{$r$\{$n$\}} » et
« \texttt{$r$\{$m$,$n$\}} » et « \texttt{$r$\{$m$,\}} » et
« \texttt{$r$\{,$n$\}} » pour chercher respectivement exactement $n$,
entre $m$ et $n$, au moins $m$, et au plus $n$ occurrences de
l'expression régulière $r$.)  Entre quatre et huit caractères ?  Au
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.

(b) \verb=egrep -c '^a.*z$=

(c) \verb=egrep -c '\*'= pour une astérisque, \verb='\*.*\*'= pour au
  moins deux, et \verb='[^*]*\*[^*]*\*[^*]*'= pour exactement deux
  astérisques.

(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}.
\end{corrige}


%
%
%
\end{document}