CHAP 4 Expressions régulières

Question 1

DEF Expressions régulières

Answer 1

• Un motif sous forme de chaîne de caractères
• Qui représente un ensemble (potentiellement infini) de chaînes
  de caractères

Question 2

OBJECTIF Expressions régulières

Answer 2

• Identifier du texte ou des parties de texte
• Chercher dans du texte
• Transformer du texte

Question 3

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>

Answer 3

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 *

Question 4

Glob ≠ expression régulière

Différences

Answer 4

• glob → noms de fichier
• expressions régulières → texte
• Les conventions sont différentes

Question 5

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

Answer 5

• É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

Question 6

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

Answer 6

• 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

Question 7

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

Question 8

BRE =

Answer 8

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

Question 9

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

Answer 9

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

Question 10

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

Answer 10

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

Note
* Protéger l’étoile du shell

Question 11

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)

Answer 11

$ 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

Question 12

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

Answer 12

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

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

Question 13

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

Answer 13

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

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

Question 14

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

Answer 14

$ 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

Question 15

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

Answer 15

• [: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)

Question 16

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

Answer 16

• \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

Question 17

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

Answer 17

$ 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

Question 18

Collations POSIX

Answer 18

• 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)

Question 19

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

Answer 19

• 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=]]’

Question 20

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)

Answer 20

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

Question 21

Mythologie de grep

Answer 21

É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

Question 22

Expressions étendues
Différences avec BRE

Answer 22

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

Question 23

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

Answer 23

• 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

Question 24

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

Answer 24

$ 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

Question 25

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

Answer 25

$ echo 'aaaaaabaabaaa ' | grep -oE 'a{5}' aaaaa $ echo 'aaaaaabaabaaa ' | grep -oE 'a{3,4}' aaaa aaa

Question 26

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

Answer 26

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

Question 27

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

Answer 27

* *, {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

Question 28

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

Answer 28

$ cat cobal cobalourdeaubobardumbadaududos $ grep -o 'b.*d' cobal balourdeaubobardumbadaudud

Question 29

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

Answer 29

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

Question 30

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

Answer 30

$ grep -o 'ba[^d]*[ur]d' cobal balourd bard $ grep -o 'ba[^ur]*[ur]d' cobal bard badaud

Question 31

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)

Answer 31

$ grep -oP 'b.*?d' cobal balourd bobard bad $ grep -oP 'ba.*?[ur]d' cobal balourd bard badaud

Question 32

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

Answer 32

$ 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

Question 33

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

Answer 33

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

Question 34

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

Answer 34

$ 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…)

Question 35

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

Answer 35

$ grep -Ex '(....)..\1' /usr/share/dict/french rentrèrent saisissais sentissent $ grep -Ex '(...)(...)\2\1' /usr/share/dict/french entassassent

Question 36

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

Question 37

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

Answer 37

$ 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

Question 38

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

Answer 38

$ 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

Question 39

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

Answer 39

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

Question 40

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 * (?

Answer 40

$ 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

Question 41

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

Question 42

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

Question 43

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

Answer 43

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

Question 44

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

Answer 44

* 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)

Question 45

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