La sortie du processus est redirigée vers un fichier :

Les commandes grep et egrep comportent des options qui permettent de modifier leurs comportements :

• -c : affiche un décompte des lignes comprenant le motif.
• -v : affiche les lignes ne contenant pas le motif.
• -n : chaque ligne contenant le motif est précédée du nuémro de ligne

Format d'utilisation des commandes avec options :

2.1.8. Exercices avec grep/egrep 

Se reporter au document : td4 avec grep et egrep.

Expressions régulières : aide-mémoire

OP...RATEUR    FONCTION              EXEMPLE                                          
.               joker                80.86         suites 80186, 80a86, etc.          
*              0 ou n fois           (.*)          n caractères à         
                                                   l'intérieur de parenthèses         
+              1 ou n fois           -+            suite non nulle de tirets          
[]             classe de caractères   [-=:]        soit -, soit =, soit :             
[^]            complémentaire        [^ ]+         suite de caractères                
                                                   à l'exclusion du       
                                                   blanc                              
^              début de ligne        ^[^ ]+        suite de caractères                
                                                   à l'exclusion du       
                                                   blanc en début de ligne            
$              fin de ligne          ^$            ligne vide                         
|              ou                    chapitre|sec                                     
                                     tion                                             
\              sens littéral d'un    \.            le point                           
               caractère spécial                                                      
                                                                                      
()             groupement            19(89|90)                                        
               d'expressions                                                          
\{n,m\}        entre n et m          \*\{4,10\}    entre 4 et 10 étoiles              
               occurrences                                                            
?              zéro ou une                                                            
               occurrence                                                             

2.2. Le langage des expressions régulières

2.2.1. Rappel sur les ensembles

* Ensemble, élément

Un ensemble est une collection d'objets distincts (concrets ou abstraits).

L'ensemble A est constitué des objets a, b et c. Ces derniers sont aussi appelés des éléments de a. On dit que ces éléments appartiennent à A.

Notation :

a Î A, b Î A, c Î A, d Ï A

* Ensemble vide

L'ensemble vide s'écrit ø.

* Sous-ensemble

Un ensemble A est sous-ensemble d'un ensemble B lorsque tous les éléments de A sont aussi éléments de B. Formellement, on écrit :

B Ì A <=> " x Î A, x Î B

" : quantificateur universel qui se lit " pour tout ", i.e. "] x se lit " pour tout x ".

$ : quantificateur existenciel qui se lit " il existe au moins un ", i.e. $ x se lit " il existe au moins un x ".

* Réunion

La réunion de deux ensembles A et B est un ensemble qui contient tous les éléments qui appartiennent à A ou à B ou aux deux, sans répétition.

union(A,B) = {x / x Î A ou x Î B}

* Intersection

L'intersection de deux ensembles A et B est un ensemble qui contient tous les éléments qui appartiennent à A et à B.

intersection(A,B) = {x / x Î A et x Î B}

* Composition par concaténation (produit)

On définit le produit par concaténation d'éléments de deux ensembles A et B comme l'ensemble de toutes les chaînes composées d'un élément de A et d'un élément de B.

A.B = AB = {xy / x Î A, y Î B}

On peut étendre cette notion de produit à celle d'élévation à la puissance :

A.A = A² = {xy / x Î A, x Î A}

Exemple :

A = {a,b,c}, B={s,u}

AB = {as,au,bs,bu,cs,cu}

AA = A² = {aa,ab,ac,bb,ba,bc,cc,ca,cb}

Par convention:

A¹ = A et A⁰ = { l }, où l désigne l'élément neutre dans l'opération de concaténation : i.e. a. l = a.

* Extension d'un ensemble

On appelle extension d'un ensemble la réunion de toutes les puissances entières (non négatives) de cet ensemble.

Exemple : A = {a,b,c}, a Î A*, baba Î A*.

2.2.2. Notion de langage

Un langage formel est un ensemble de chaînes construites sur un vocabulaire donné.

* Vocabulaire

Un vocabulaire est un ensemble fini de symboles

V={a, b, c...z}

* Chaîne

Une chaîne sur un vocabulaire V est un concaténation de symboles

x = ab

* Concaténation de chaîne

La concaténation de deux chaînes a pour résultat une chaîne obtenue en juxtaposant ces deux chaînes.

avec x = ab y=cd

on obtient xy = abcd

* Langage

Rappel : V^* est l'ensemble de toutes les chaînes sur le vocabulaire V.

Par définition un langage est un sous-ensemble de V^*.

* réunion

Si L est la réunion des langages L₁ et L₂, il est composé des chaînes appartenant à L₁ ou à L₂ ou aux deux.

Exemple :

Si V = {a,b} et L₁ = {a,b,ab,ba,aa,bb}, L₂ = {ab,aab,aabb,abb}

union(L₁,L₂) = {x / x Î L₁ ou x Î L₂} = { a,b,ab,ba,aa,bb,aab,aabb,abb}

* intersection

Si L est la réunion des langages L₁ et L₂, il est composé des chaînes appartenant à L₁ et à L₂.

Exemple :

Si V = {a,b} et L₁ = {a,b,ab,ba,aa,bb}, L₂ = {ab,aab,aabb,abb}

intersection(L₁,L₂) = {x / x Î L₁ et x Î L₂} = { ab}

Il est important de se rappeler que les langages sont des ensembles construits sur des vocabulaires donnés, il faut donc toujours spécifier le vocabulaire associé à un langage.

* produit

Le produit par concaténation de deux langages L₁ et L₂ contient toutes les chaînes formées par la concaténation d'une chaîne de L₁ avec une chaîne de L₂.

L₁.L₂ = {xy / x Î L₁, x Î L₂}

Exemple :

V = {a,b,...z}

L₁ = {mo,po,ri,ru}

L₂ = {t,che}

L₁.L₂ = {mot,moche,pot,poche,rit,riche,rut,ruche}

* extension

L'extension d'un langage est la réunion de tous les langages obtenus en élevant le langage à toutes les puissances entières (non négatives).

Exemple : si L = {a,b,....z}, L* est l'ensemble de toutes les chaînes de longueur quelconque formées des lettres de L.

Exercices sur les langages : TP GF

2.2.2. Les expressions régulières

On dispose d'un langage pour définir lLes expressions régulières. La valeur de chaque expression est un motif constitué d'ensemble de chaînes, souvent appelé un langage. On appellera L(E) le langage défini par une expression régulière E.

Dans l'algèbre des expressions régulières on trouve les opérandes atomiques et les langages correspondants suivants :

1. un caractère quelconque x. Le langage L(x) = {x} est un ensemble contenant une chaîne unique composée du seul caractère x.

2. le symbole l qui représente la chaîne vide. L(l) = { l } est le langage dont l'unique élément est la chaîne vide.

3. le symbole ø représente l'ensemble de chaînes vide. L(ø) = ø .

Trois opérateurs permettent de combiner les expressions régulières

* Union (notée | )

L(R|S) = L(R) union L(S), L(R) et L(S) étant des ensembles de chaînes

* Concaténation (pas de symbole)

L(RS) est construit à partir de L(R) et L(S) : pour chaque chaîne r de L(R) et chaque chaîne s de L(S), la chaîne rs, issue de la concaténation de r et de s, est une chaîne de L(RS).

* Extension/Fermeture (postfixe et unaire, noté *)

R* : fermeture de l'ER R : zéro occurrence ou plus des chaînes de R

Si R = a, L(R*) = {l, a, aa, aaa, aaaa, aaaaa, ...}

Si R = a|b, L(R*) contient toutes les chaînes de a et de b de longueur quelconque

priorités : fermeture > concaténation > union

Ex : a|bc*d

1. On commence par s'intéresser aux signes *.

2. On les regroupe avec leur opérande : a|b(c*)d

3. Ensuite on s'intéresse aux concaténations.

4. Premiére concaténation : a|(b(c*))d

5. Deuxiéme concaténation : a|((b(c*))d).

Enfin, on considére les unions : (a|((b(c*))d)) mais les parenthéses extérieures sont redondantes

2.3. Notions de grammaire formelle

2.3.1 Introduction

La théorie des grammaires formelles qui remonte à la fin des années cinquante est
due à Chomsky . Les grammaires formelles peuvent être définies comme des ensembles
de règles parfaitement explicites, applicables de façon mécanique, qui transforment
une entrée en une sortie particulière. L'entrée correspond au symbole initial
et la sortie à une chaîne de caractères.

L'intérêt de cette formalisation pour le TAL est surtout d'avoir permis
établir et de prévoir la complexité informatique qu'engendre l'utilisation de ces grammaires dans des applications de traitement automatique.

Un langage est un ensemble de chaînes construites sur un vocabulaire donné.

Exemple : un langage naturel est un sous-ensemble de l'extension d'un certain vocabulaire.

Une grammaire doit donc au moins servir à définir quelles sont les chaînes qui appartiennent à un langage.

Sur le plan formel, une grammaire est un système constitué d'un nombre fini de composants et destiné à la description d'un langage.

* Système de production

Un système de productions est un couple (V, P) où V est un vocabulaire fini de symboles et P est un ensemble finis de productions.

Les productions ont la forme x -> w où x et w sont des chaînes sur V (mais x ne peut être vide), c'est-à-dire x Î V⁺ et w Î V^*.

Pour définir un système de productions. Il suffit de définir ses deux composantes V et P. Ainsi:

V = {a. b, c} et P = [ba --> ab, ca --> ac, cb --> bc]

constituent un système de productions.

* Dérivation

Un système de productions permet de réécrire des chaînes à partir d'autres chaînes en appliquant des productions.

* Dérivation directe (-->)

On dit que y-->z si et seulement si il existe u, v Î V^*, tel que y = uxu, z = uwu et x --> w est une production de P.

Dans le système donné précedemment bbbaaa --> bbabaa est une dérivation directe car on a :

u = bb, v = aa. x = ba et w = .ab

aba --> aab est aussi une dérivation directe (ici v = l).

* Dérivation ( => )

On dit que y => z si et seulement si il existe une suite de chaînes X_O, X₁ X₂, ... X_r (r >= 0), telle que:

y = X_o

z = X_r

X_i --> X_(i+l) pour i = 0.1.2..r-1

Dire que z dérive de y signifie donc que, partant de y, on peut aboutir à z par un certain nombre de dérivations directes successives. On dit que r est la longueur de la dérivation.

2.3.2 Définition d'une grammaire formelle

Une grammaire formelle est un quadruplet

G = {V_n, V_t, P, S}

où V_t est un vocabulaire terminal fini. C'est sur ce vocabulaire que sont formées les chaînes (phrases) du langage que la grammaire définie. Ces chaînes appartiennent donc à V_t^*.

V_n est un vocabulaire non terminal fini. C'est un vocabulaire auxiliaire utilisé dans les règles de grammaire. Le plus souvent V_n contient les éléments du métalangage utilisé pour dénommer les constituants:

V_n et V_t n'ont aucun élément en commun ; le vocabulaire V de la grammaire est la réunion de V_t et V_n.

Le couple (V. P) est un système de productions. P est un ensemble de productions, appelées dorénavant règles de la grammaire de la forme : x A y --> z où A appartient à V_n et x, y, z appartiennent à V^*.

Les deux membres d'une règle sont appelés " partie gauche " et " partie droite " : la partie gauche contient toujours au moins un élément de V_n ; si l'on considère chaque règle x --> y comme un couple (x, y), on peut alors dire que P est un sous-ensemble du produit cartésien V⁺ x V^*.

S est un élément particulier de V_n appelé le symbole initial ou axiome de la grammaire. Une grammaire n'a toujours qu'un seul symbole initial.

Le langage défini par une grammaére G s'écrit L(G). Une phrase de L(G)est toute chaîne x de V_t^*, telle que S => x. Le langage défini par une grammaire G est:

L(G) = { x / x appartient à V_t^* et S => x}

Exemple : Soit la grammaire G:

V_n = {S, GN, GV. D. N. V}

(I) S-->GN GV

(2) GV-->V GN

(3) GN-->D N

(4) D-->le

(5) N-->chat

(6) N-->poisson

(7) V-->mange

(8) V-->dévore

Cette grammaire reconnaît la phrase : le chat dévore le poisson. Voici la dérivation de cette phrase. Pour chaque dérivation on a indiqué le numéro de la règle appliquée :

(I) GN GV

(3) D N GV

(4) le N GV

(5) le chat GV

(2) le chat V GN

(8) le chat dévore GN

(3) le chat dévore D N

(4) le chat dévore le N

(6) le chat dévore le poisson

2.3.2 La hiérarchie des grammaires formelles

2.4. Expressions régulières et automates

2.4.1. Les automates

On peut se représenter le comportement d'un programme destiné à reconnaître un motif particulier comme un cheminement dans un graphe orienté. Les nœuds constituent les états du programme. Les arcs sont étiquetés par des ensembles de caractères. Il existe un arc de l'état s vers l'état t étiqueté par l'ensemble de caractères C si, quand on se trouve dans l'état s, on passe à l'état t uniquement après avoir rencontré un des caractères de l'ensemble C. On dit que l'on effectue une transition de l'état s vers l'état t sur le symbole x qui appartient à l'ensemble C. Les arcs sont pour cette raison appelés transitions. Un nœud est appelé état de départ: c'est celui par lequel commence la recherche du motif. D'autres nœuds sont appelés états d'acceptation: lorsqu'on atteint un de ces nœuds, c'est que le motif a été intégralement reconnu (on dit accepté).

Un tel graphe porte le nom d'automate fini. Un tel automate reçoit une suite de caractères appelée séquence d 'entrée. Il est alors dans l'état de départ, prêt à lire le premier caractère de la séquence d'entrée. Si ce caractère correspond à une transition possible (éventuellement vers le même état), il effectue cette transition et examine le caractère suivant de la séquence d'entrée. Et ainsi de suite. Si l'automate a examiné tous les caractères de la séquence d'entrée et se trouve sur un état d'acceptation, on dit que cet automate accepte ou reconnaît la séquence d'entrée. Si, par contre, l'automate se trouve dans un état où il n'existe aucune transition pour le caractère examiné ou si l'automate se trouve dans un état d'acceptation alors qu'il reste des caractères à examiner, on dit que l'automate rejette la séquence d'entrée. Un automate reconnaît donc une séquence d'entrée s'il existe un chemin de l'état de départ à un état d'acceptation. Ce chemin doit être constitué d'arcs dont les étiquettes contiennent les symboles de la séquence d'entrée dans le bon ordre.

Par convention, les états d'acceptation sont figurés par des doubles cercles. Une flèche arrivant de nulle part signale l'état de départ. Dans le cas où l'ensemble C qui étiquette une transition est réduit à un singleton, c'est-à-dire qu'il ne comporte qu'un seul symbole, on utilise ce symbole comme étiquette, par exemple x et non le singleton {x}. La lettre grecque lambda (L) représente l'ensemble des caractères. L'expression {L - x} recouvre l'ensemble des caractères moins le caractère x. La figure suivante correspond ainsi au graphe de l'automate de reconnaissance du motif constitué par les séquences c'est à dire, c'est-à-dire, c'est-à dire, et c'est à-dire, précédées et suivies d'un nombre arbitraire de caractères quelconques.

cet automate va entamer la reconnaissance de c'est-à-dire, mais quand il sera arrivé dans l'état 8, après avoir examiné c'est à, il ne trouvera pas de transition pour le caractère courant P. La séquence sera donc rejetée, quand bien même elle comporte effectivement une occurrence de c'est-à-dire un peu plus loin. Une variante non déterministe de cet automate pourrait comporter à la place de la transition de l'état 0 sur l'état 0 sur {L - c} une transition sur L. Le résultat de cette transformation est le suivant. Dans l'état 0, si l'on rencontre le caractère c, deux hypothèses sont explorées simultanément: il s'agit du début de c'est-à-dire (on passe dans ce cas à l'état 1), cette hypothèse débouche sur un échec à la rencontre de P, ou il ne s'agit pas du début de c'est-à-dire (on reste dans l'état 0). Quand est rencontré le deuxième c, on poursuit l'hypothèse demeurant en lice (en restant dans l'état 0) et on essaie une nouvelle hypothèse, celle que la séquence cherchée commence à cet endroit (en passant à l'état 1). Sur les trois hypothèses examinées, une seule, la troisième, conduit à un état d'acceptation.