Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

INF1070 > CHAP 4 Expressions régulières > Flashcards

CHAP 4 Expressions régulières Flashcards

1
Q

DEF Expressions régulières

A
  • Un motif sous forme de chaîne de caractères
  • Qui représente un ensemble (potentiellement infini) de chaînes
    de caractères
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

OBJECTIF Expressions régulières

A
  • Identifier du texte ou des parties de texte
  • Chercher dans du texte
  • Transformer du texte
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Autres motifs permis
* Point d’exclamation [!…] — caractère qui n’est pas dans la
liste
* Intervalles [<debut>-<fin>] — caractère entre <debut> et <fin></fin></debut></fin></debut>

A

Exemple
* « ls [!co] » — ne terminent ni par c ni par o
* « ls [f-i] » — commencent par f, g, h ou i

Entre crochets, les caractères deviennent littéraux
* « cat [][!?] » — commence par ], [, !, ? ou *

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Glob ≠ expression régulière

Différences

A
  • glob → noms de fichier
  • expressions régulières → texte
  • Les conventions sont différentes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Qui utilise les expressions régulières ?
Outils de manipulation de texte

A
  • Éditeurs de texte: vi, et tous les éditeurs modernes, …
  • Outils autonomes: grep, sed, …
  • Base de données: MySQL, MariaDB, Oracle, …

Langages de programmation
* De base en Perl, Python, Java, JavaScript, etc.
→ Opérations sur le texte
→ Vérification et sanitarisation de données

Autres utilisations
* Colorateur syntaxique colorie les mots clés
* Serveur web filtre et transforme des requêtes HTTP
* Compilateur reconnaît les éléments textuels d’un programme

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Différentes conventions ⋆
De nombreux outils et usages
Font que la syntaxe et les mécanismes varient

A
  • POSIX Basic regular expression (BRE)
  • POSIX Extended regular expression (ERE)
  • Extensions GNU à POSIX
  • Perl compatible regular expression (PCRE)
  • Spécificités de chaque langage et outil

Exemple de différences
* Échappement des caractères spéciaux
* Classes de caractères
* Mécanismes plus avancés (lookahead, références relatives, etc.)

Dans le cours: BRE et ERE (POSIX)
Plusieurs commandes les utilisent, notamment grep et sed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

La commande grep: rappel
grep — cherche les lignes correspondant à un motif

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

BRE =

A

basic regular expressions
* Une des versions syntaxiques POSIX (l’autre étant ERE)
* Reconnue par la plupart des commandes Unix
* Reconnue par plusieurs éditeurs de texte (Vi/Vim, Emacs)
* Syntaxe de base plus ou moins universelle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

JOKER
Le point « . » correspond à n’importe quel caractère sauf NUL

A

Note
* Équivalent au « ? » en glob
* Utiliser « . » pour reconnaître un point
* Certains outils ou options n’incluent pas la fin de ligne dans « . »

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

L’étoile: répétition ⋆
L’étoile * indique une répétition d’un motif
* 0 fois
* 1 fois
* ou plusieurs fois

A

$ cat fruits.txt
banane
mangue
pomme
$ grep -o ‘m*e’ fruits.txt
e
e
mme

Note
* Protéger l’étoile du shell

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Ancrage ⋆
Deux caractères spéciaux permettent de forcer une position
* Le circonflexe « ^ » indique le début de la chaîne (ou ligne)
* Le dollar « $ » indique la fin de la chaîne (ou ligne)

A

$ grep ‘^fricas ‘ /usr/share/dict/french
fricassée
fricassées
fricasser
$ grep ‘key$ ‘ /usr/share/dict/french
hockey
jockey
$ grep ‘^mettre$ ‘ /usr/share/dict/french
mettre

  • -x équivaut à ajouter des ^ et $ implicites
  • Protéger $ du shell
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Crochets : liste de caractères ⋆
« [] » listent un choix parmi plusieurs caractères

A

$ echo “mes aieux” | grep -o ‘[aeiou]*’
e
aieu

Note
* Protéger « [ » et « ] » du shell

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Crochets : négation de classe ⋆
* Entre les crochets,
* On peut interdire un ou plusieurs caractères
* En commençant par le circonflexe « ^ »

A

$ echo “mes aieux” | grep -o ‘[^aeiou]*’
m
s
x

Note
* Le circonflexe ^ joue deux rôles (ancrage et négation)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Crochets : intervalles ⋆
* Entre les crochets, on peut préciser un intervalle
* Avec le caractère « - »

A

$ grep ‘[x-z][a-c][y-z]’ /usr/share/dict/french
zézayer

$ grep -o ‘[x-z][a-c][y-z]’ /usr/share/dict/french
zay

$ echo ‘!@#$%^&-=+()[]’ | grep –color ‘[!-*]’

Les intervalles peuvent dépendre
* De la locale (détails plus tard)
* ou du codage (ASCII, Unicode, etc.) man ascii

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Classes de caractères POSIX
Certains ensembles de caractères sont plus fréquents

A
  • [:lower:] : minuscules
  • [:upper:] : majuscules
  • [:digit:] : chiffres
  • [:alpha:] : minuscules et majuscules
  • [:alnum:] : minuscules, majuscules et chiffres
  • [:punct:] : ! . ; + # / \ | etc.
  • [:blank:] : espace et tab
  • [:space:] : espace, tab, \r, \n, etc.
  • [:cntrl:] : caractères de contrôle (NUL, BS, ESC, DEL, etc.)
  • [:graph:] : caractères graphiques, [:alnum:] et [:punct:]
  • [:print:] : caractères affichables, [:graph:] et espace
  • [:xdigit:] : caractères hexadécimaux

Les classes dépendent de la locale (détails plus tard)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Autres classes de caractères
GNU, Perl et de nombreux outils reconnaissent d’autres classes

A
  • \w : lettre, chiffre ou souligné « _ »
  • \W : l’inverse de \w
  • \s : un espace
  • \S : l’inverse de \s
  • \d : un chiffre (pas GNU)
  • \D : l’inverse de \d (pas GNU)
  • \b : frontière entre mot et non-mot
  • \B : l’inverse de \b
  • < : début de mot
  • > : fin de mot

En fonction des outils, les classes dépendent (ou non) de la locale

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Classes d’équivalence POSIX 
* [=c=] : classe d’équivalence du caractère c
* Par exemple [=e=] inclut eéèêë

A

$ grep ‘[[=e=]][[=e=]][[=e=]]’ /usr/share/dict/french
agréée
agréées
créée
[…]
suppléées

Attention aux doubles crochets
$ echo ‘e + é = è’ | grep -o ‘[=e=]’
e
=

Les classes d’équivalence dépendent aussi de la locale

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Collations POSIX

A
  • digraphe = 2 caractères qui en forment un seul
  • Certaines langues ont des digraphes
  • Exemple, en tchèque, ch est une lettre entre h et i
  • En croate, lj est une lettre entre l et m
  • Avant, en allemand, ss était une lettre à part (maintenant 𝛽)
  • La norme POSIX permet de gérer ces doubles caractères
  • Dans le cours, on ne s’en préoccupera pas (pas de problème en
    français/anglais)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Rechercher tous les mots du français qui ne contiennent aucune
voyelle parmi a, e, i, o, u

A
  • grep ‘[^aeiou]’ /usr/share/dict/french
    → reconnaît oiseau à cause du s
  • grep ‘[^aeiou]*’ /usr/share/dict/french
    → reconnaît tout car * accepte 0 répétitions
  • grep ‘^[^aeiou]*$’ /usr/share/dict/french
    → reconnaît âgé à cause des accents
  • grep ‘^[^aâàeéèêëiîïoôuûü]*$’
    → fonctionne (même si ù manque)
  • grep ‘^[^[=a=][=e=][=i=][=o=][=u=]]*$’
    → fonctionne aussi

Avec les options de grep
* grep -x ‘[^[=a=][=e=][=i=][=o=][=u=]]*’
* grep -v ‘[[=a=][=e=][=i=][=o=][=u=]]’

20
Q

La commande sed (1/3)
sed (stream editor) filtrer et transformer du texte

  • -n mode silencieux
  • -f, –file lecture des transformation à partir d’un fichier
  • -i, –in-place modifie le fichier (au lieu d’afficher sur stdout) (GNU)
  • -E passer en mode étendu (GNU)
  • –posix désactive les extensions GNU (GNU)
A

Commandes spécifiques à sed
* sed lit une ou plusieurs commandes
* Et les exécutent une à une
* Par exemple, s/ancien/nouveau/ pour substituer ancien par nouveau
* Scriptable: on peut les regrouper dans un fichier
* Nous ne verrons que quelques-unes de ces commandes

Permet (entre autres) de remplacer un motif par un autre
$ cat form.txt
Nom: <nom>
Prénom: <prénom>
Code permanent: <code>
Courriel: <courriel></courriel></code></prénom></nom>

$ sed ‘s/<prénom>/Alexandre/' form.txt
Nom: <nom>
Prénom: Alexandre
Code permanent: <code>
Courriel: <courriel></courriel></code></nom></prénom>

$ cat remplir.sed
s/<nom>/Blondin Massé/
s/<prénom>/Alexandre/
s/<code>/BLOA00000000/
s/<courriel>/blondin_masse.alexandre@uqam.ca/</courriel></code></prénom></nom>

$ sed -f remplir.sed form.txt
Nom: Blondin Massé
Prénom: Alexandre
Code permanent: BLOA00000000
Courriel: blondin_masse.alexandre@uqam.ca

21
Q

Mythologie de grep

A

Éditeur ed (POSIX)
* Développé par Ken Thompson
* g/re/p est une commande de ed
* globally search the regular expression then print the line

Outil grep (POSIX)
* Développé comme un outil autonome plus rapide
* Popularisé l’utilisation (et la notation) des expressions régulières

Dans le dictionnaire: nom et verbe

22
Q

Expressions étendues
Différences avec BRE

A

Syntaxe différente
* Plus de caractères spéciaux
* Plus d’opérations

Pour l’avoir
* grep -E (POSIX), egrep (pas POSIX)
* sed -E (GNU)
* Par défaut dans de nombreux outils
→ C’est le défaut quand les gens pensent expressions régulières

Note
* Certains caractères spéciaux BRE existent sous forme échappée
* « (i.|.i){6} » en ERE équivaut à
* « (i.|.i){6} » en BRE

Sous-expressions ⋆
* Les parenthèses « () » forment des groupes
* Les opérateurs comme * s’appliquent sur les groupes

$ grep -Ex ‘hu(.i)*ent’ /usr/share/dict/french
huaient
huent
humidifiaient

23
Q

Expressions étendues
Motif optionnel ⋆
« ? » rend un motif optionnel

A
  • On peut rendre un caractère optionnel
    $ grep -xE ‘p?r?is’ /usr/share/dict/french
    pis
    pris
    ris
  • Ou une sous-expression complète
    $ grep -Ex ‘t(rav)?aill((er)?ions)?’\
    > /usr/share/dict/french
    taillerions
    taillions
    travaillerions
    travaillions
24
Q

Expressions étendues
Répétition stricte ⋆
* L’étoile « * » accepte lorsqu’il y a 0 occurrence

A

$ grep -xE ‘(cher)(as)’ /usr/share/dict/french
as
cher
chercher
chercheras

  • Le plus « + » force au moins 1 occurrence
    $ grep -xE ‘(cher)+(as)+’ /usr/share/dict/french
    chercheras
25
Q

Expressions étendues
Répétitions d’un nombre précis d’occurrences
À l’aide d’accolades « { } »
* {m} : exactement m fois
* {m,} : m fois ou plus
* {,n} : n fois ou moins
* {m,n} : entre m et n fois

A

$ echo ‘aaaaaabaabaaa ‘ | grep -oE ‘a{5}’
aaaaa

$ echo ‘aaaaaabaabaaa ‘ | grep -oE ‘a{3,4}’
aaaa
aaa

26
Q

Quels mots du français ont
* un i une lettre sur deux
* et au moins trois i?

A

$ grep -Ex ‘.?i(.i){2,}.?’ /usr/share/dict/french

27
Q

Répétitions en bref
Plusieurs façons de gérer les répétitions

A
  • *, {0,} ou {,} : 0, 1 ou plusieurs fois
  • ?, {0,1} ou {,1} : 0 ou 1 fois
    • ou {1,} : 1 fois ou plus
  • {m} : exactement m fois
  • {m,n} : entre m et n fois
  • {m,} : m fois ou plus
  • {,n} : n fois ou moins
28
Q

Avarice
En POSIX, les répétitions ont un comportement avare (greedy)
* Elles consomment le plus possible de caractères qui
correspondent
* Elles trouvent les répétitions les plus longues possibles

A

$ cat cobal
cobalourdeaubobardumbadaududos

$ grep -o ‘b.*d’ cobal
balourdeaubobardumbadaudud

29
Q

Questions d’avarices
Seulement les chaînes qui commencent par « b »
et finissent par le « d » le plus proche?

A

$ grep -o ‘b[^d]*d’ cobal
balourd
bobard
bad

30
Q

Seulement les chaînes qui commencent par « ba »
et finissent par le « ud » ou le « rd » le plus proche?

A

$ grep -o ‘ba[^d]*[ur]d’ cobal
balourd
bard

$ grep -o ‘ba[^ur]*[ur]d’ cobal
bard
badaud

31
Q

Anti-avarice
PCRE permet le contrôle de l’avarice des répétitions
* Une répétition suivie d’un point d’interrogation ?
* N’est plus avare
L’option -P de grep active le mode PCRE (GNU)

A

$ grep -oP ‘b.*?d’ cobal
balourd
bobard
bad

$ grep -oP ‘ba.*?[ur]d’ cobal
balourd
bard
badaud

32
Q

Alternance
* Équivalent au ou logique ou à l’union ensembliste

A

$ grep -E ‘comberio|ustibi ‘ /usr/share/dict/french
combustibilité
incomberions
incombustibilité
succomberions

$ grep -E ‘e(cou|pli)(sse|é)$’ /usr/share/dict/french
replié
replisse
secoué
secousse

33
Q

Priorités
Il y a une priorité sur les opérateurs

A

$ grep -Ex ‘pro|ton*s?’ /usr/share/dict/french

34
Q

Problème
* Qu’en est-il du et logique?
Rechercher tous les mots qui contiennent au moins une fois chaque
voyelle a, e, i, o, u.
Quel est le problème de « a.e.i.o.u » ?

Solution
Solution simple: utiliser un tube

A

$ grep a.e.i.o.u /usr/share/dict/french
garde -chiourme
gardes -chiourme
gardes -chiourmes

Solution
Solution simple: utiliser un tube

$ grep a /usr/share/dict/french | grep e | grep i\
> | grep o | grep u
abasourdie
abasourdies
[…]
zygomatiques

  • Pas optimal, car relit plusieurs fois chaque ligne
  • Mais pas d’autres solutions avec grep
  • Il existe des solutions plus puissantes, par exemple Perl (plus
    tard…)
35
Q

Capture de sous-chaîne
* On peut réutiliser une ou plusieurs sous-chaîne
* Une sous-chaîne correspond à une sous-expression
* On y réfère avec « \i », où « i » est le numéro de la
sous-expression

A

$ grep -Ex ‘(….)..\1’ /usr/share/dict/french
rentrèrent
saisissais
sentissent

$ grep -Ex ‘(…)(…)\2\1’ /usr/share/dict/french
entassassent

36
Q

Sous-expressions imbriquées
* On peut imbriquer des sous-expressions
* Et réutiliser les sous-chaînes associées

A
37
Q

Question
Quels mots ont 2 fois la même paire de lettres répétées ?
Exemple: « gouttelette » (deux fois « tt »)

A

$ grep -E ‘((.)\2).*\1’ /usr/share/dict/french

Même question mais sans prendre en compte les « ss » et « nn » ?
$ grep -E ‘(([^sn])\2).*\1’ /usr/share/dict/french

38
Q

Transformations
La capture est utile pour les transformations
* sed
* rechercher/remplacer des éditeurs
Exemple: Inverser les deux premières lettres de chaque ligne

A

$ sed -E ‘s/^(.)(.)/\2\1/’ fruits.txt
abnane
amngue
opmme

Pour sed, l’esperluette « & » dénote le motif complet
$ echo “8 chiens 15 chats” | sed -E ‘s/[0-9]+/&/g’
8 chiens 15 chats

39
Q

Question
Extraire la partie centrale des mots qui
* Commencent par « inter »
* Et finissent par « aux ».
* Exemple: « intercontinentaux » → « continent »

A

$ sed -En ‘s/^inter(.*)aux$/\1/p’ /usr/share/dict/french

40
Q

Assertion avant et arrière 
PCRE permet de définir des contextes (lookahead, lookbehind)
* (?= assertion positive en avant
* (?<= assertion positive en arrière
* (?! assertion négative en avant
* (?<! assertion négative en arrière
Les assertions ne consomment pas les caractères

A

$ grep -Po ‘(?<=inter).*(?=aux)’ /usr/share/dict/french

Question
Rechercher tous les mots qui contiennent au moins une fois chaque
voyelle a, e, i, o, u. (le retour!)

$ grep -P ‘(?=.a)(?=.e)(?=.i)(?=.o)(?=.u).’\
> /usr/share/dict/french

41
Q

Aller plus loin
On a déjà vu beaucoup de puissance
* POSIX BRE et ERE
* Les extensions GNU
* Un peu de PCRE

PCRE (et d’autres normes)
* Réinitialisation « \K »
* Options de chaînes « (?i) » et cie.
* Sous-chaines nommées
* Référence arrière récursives
* Contrôle de la marche-arrière (backtracking)
* Structures conditionnelles
→ voir la doc PCRE

A
42
Q

Limites des expressions régulières ⋆

Ne permet pas de tout faire
Exemple classique: les constructions récursives ne fonctionnent pas
* HTML, XML
* JSON
* Expression arithmétiques avec des parenthèses
C’est une limite théorique

Rapidement illisible
* ^(?\d{3})?[ -]\d{3}[ -]\d{4}$ → numéros de téléphone
* ^M{,4}(CM|CD|D?C{,3})(XC|XL|L?X{,3})(IX|IV|V?I{,3})$
→ nombres romains valides
* ^@%*&+#$ → sans doute un juron

A
43
Q

Théorie des langages
Expressions régulières
Formellement, une expression régulière est construite à partir

A
  • D’un alphabet et de la chaîne vide
  • Des opérateurs de concaténation, d’alternance et de l’étoile
    de Kleene
44
Q

Complexité des langages
Plusieurs types de langages formels: Hiérarchie de Chomsky

A
  • Langages réguliers (regular, type 3)
  • Langages algébriques (context free, type 2)
  • Langages contextuels (context sensitive, type 1)
  • Langages généraux (type 0)
45
Q

Comment ça marche ?

  • Expressions régulières utilisent des automates à états finis
    → Très efficaces
  • Grammaires algébriques utilisent des automates à pile
    → Très efficaces aussi
  • Les captures et extensions PCRE utilisent des algorithmes
    récursifs et du backtrack
    → Potentiellement très inefficaces
A

INF1070 (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions