Python
C
Java
C++
Alain Chillès – 祁冲 Ada
Théorie des langages de programmation Expressions régulières/rationnelles
Prolog
Forth
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
Pascal
13 septembre 2016 – 2016年9月13日 –丙申年八月十三
Lisp
APL
Fortran
1
Plan
C
Python Prolog
Java
Analyse lexicale
Jeu
Forth Ada
Pascal
Reconnaissance de motif
C++ Lisp
APL
Fortran
2
Recherche de motif (Pattern matching) Python
C
Java
Prolog
chaîne S.
Ada
Quelques questions possibles (on travaille sur une chaîne de
caractères sur une ou plusieurs lignes ou sur un fichier) sur la
La chaîne de caractères « Alain » est-elle une sous-chaîne de
S? C++
Quelles sont les adresses mail dans S ? Y a-t-il des dates précisées ?
etc.
Pascal
Lisp
APL
Fortran
Forth
3
Recherche de motif : exemple
Soit le fichier :
Java Prolog
Python
C
Texte
Paris, le 12 septembre 2016
Bonjour Alain,
tu trouveras l’information que tu souhaites
sur http://www.sjtu.edu.cn.
C++
Ada
Tu pourras me contacter à l’adresse
alain.chilles@sjtu.edu.cn
Pascal
Ne te trompe pas comme la dernière fois !
Ce n’est pas alain.chilles@sjtu
Lisp
APL
ni alain.chilles@sjtu.cn
Fortran
Bonne journée $$^
Forth
4
Recherche de motif : grep Python
Java
C
Terminal
$ grep -e “Alain” Grep1.txt Prolog
Bonjour Alain,
Terminal
Forth Ada
C++
$ grep -En
→ “[a-z]+[.][a-z]+@[a-z]+[.]([a-z]+[.]*){1,}”
→ Grep1.txt 8:alain.chilles@sjtu.edu.cn 12:ni alain.chilles@sjtu.cn
Pascal
Lisp
APL
Fortran
5
Recherche de motif : grep -En Python
C
Prolog
Java Forth
Terminal
C+
Ada
$ grep -En “[0-9]+( janvier | f(e|é)vrier | mars
→ | avril | mai | juin | juillet | ao(u|û)t |
+
→ septembre | octobre | novembre |
Lisp
d(é|e)cembre )[0-9]{4}” Grep1.txt Pascal
APL
Fortran
→
1:Paris, le 12 septembre 2016
6
Recherche de motif : grep -Eno Python
Java
Terminal
C
$ grep -Eno
Prolog
→ “[a-z]+[.][a-z]+@[a-z]+[.]([a-z]+[.]*){1,}”
→ Grep1.txt 8:alain.chilles@sjtu.edu.cn 12:alain.chilles@sjtu.cn
C++
$ grep -Eno “[0-9]+( janvier | f(e|é)vrier | Pascal
→ mars | avril | mai | juin | juillet |
→ ao(u|û)t | septembre | octobre | novembre |
Forth Ada
Terminal
Lisp
APL
→ d(é|e)cembre
)[0-
}” Grep1.txt
1:12 septembre 2016
Fortran
9]{4
7
Expressions rationnelles : pratique
1 2
Plusieurs « normes » : POSIX, PCRE…
Supportées par plusieurs langages informatiques (Java,
Python C Prolog
Java Forth
Python, R, Matlab,etc.)
3 Supportés par quelques outils (grep, sed, geany (l’éditeur sur
C++
Ada
la clef !), etc.)
4 Utilisables en C avec la commande #include
APL
Fortran
Lisp
Pascal
8
La norme POSIX étendue
Python
Java
Règles :
Un caractère normal ‘a‘ est le motif pour… lui-même ! De
C
même qu’une succession de caractères.
Terminal
Prolog
3:Bonjour Alain,
C++
peut-être le saut de ligne.
Terminal
Lisp
Les caractères spéciaux sont : \^$.|?*+()[{
Le caractère . représente n’importe quel caractère (sauf,
Forth Ada
$ grep -En “Alain” Grep1.txt
Pascal
APL
$ grep -En “Bon..” Grep1.txt
Fortran
3:Bonjour Alain,
14:Bonne journée $$^
9
La norme POSIX étendue (suite)
Lisp
Terminal
Forth
Python Java
CLe caractère | permet (à l’intérieur de parenthèses) de faire un ou de plusieurs motifs.
Prolog
C++
$ grep -Eno “(info|ad)” Grep1.txt
4:info 7:ad
APL
Fortran
$ grep -Eno “(s|p)ou” Grep1.txt
4:sou
7:pou
Ada
Le motif jou de « journée » n’est pas reconnu.
Pascal
10
La norme POSIX étendue (suite)
Python
CLe caractère [ permet d’ouvrir un ou de plusieurs caractères.
Java
Terminal
$ grep P
5:cn
8:cn
10:rn
12:cn
14:rn
o
-En
l
r
n” Grep1.txt g
o
C++
Forth Ada
Terminal
o
“[a
bc
dr]
On peut aussi faire des intervalles de caractères !
Pascal
Lisp
APL
$ grep -Eno “[a-z]ni” Grep1.txt
10:rni
Fortran
11
La norme POSIX étendue (suite)
Python
J
va
On peut faire, dans les crochets « tout sauf… »,
Ccaractère ^. Terminal
a
$ grep
→ Grep1.txt
Z0-9 .,:;’@/$]” Forth
-En
r
o
“[^
a-
zA-
10:! 14:^
Ada
o
l
Les caractères ^ et $ indiquent respectivement le début de C++
ligne et la fin de ligne.
Terminal
o
g
ave
c le
P
Pascal
7:T
4:s 7:e
$ grep -Eno “^[tT]” Grep1.txt
Lisp
4:t
APL
$ grep -Eno “[a-z] $” Grep1.txt
Fortran
12
La norme POSIX étendue (suite)
Python
a TerminalProlog
Le caractère spécial \ (dit d’échappement) perme
v
les
Ccaractères spéciaux !
$ grep -Eno “!$” Grep1.txt
Forth
J
td
a
’uti
liser
C++
Ada
grep -Eno “Grep1.txt” Grep1.txt
$ grep -Eno “\!$” Grep1.txt
10:!
On a ainsi les caractères \\, \^, \$, etc. Pour certains il est préférable de les mettre entre crochets.
Terminal
Pascal
Lisp
APL
14:Bonne journée $$^
$ grep -En “[$]” Grep1.txt
14:Bonne journée $$^
$ grep -En “\^” Grep1.txt
Fortran
13
La norme POSIX étendue (suite)
Python Java CLes caractères ?, + et * sont des itérateurs. Ils signifient :
C++
Ada
exactement x
(3)
(4)
Lisp
Prol
o
g
0 ou 1 (1)
?
+ = aumoins1 (2)
=
∗ = aumoins0
Forth
On peut préciser le nombre de la manière suivante :
{x} = {x,} = {,x} =
APL
Fortran
Pascal
au moins x (5)
au plus x
{x,y} = aumoinsx etauplusy (7)
(6)
14
La norme POSIX étendue (fin) : exemple d’itérateurs
C
Python
Java
Forth
Terminal
Prolog
$ grep -Eno “(w{2,}|r{2})” Grep1.txt
5:www 7:rr
Ada
8:alain.chilles@sjtu.edu.cn
12:ni alain.chilles@sjtu.cn
$ grep -En “([^.]+\.){2,}” Grep1.txt
C++
5:sur http://www.sjtu.edu.cn.
$ grep -En “([^.]+\.){4}” Grep1.txt
5:sur http://www.sjtu.edu.cn.
Lisp
APL
Fortran
Pascal
15
Plan
C
Python Prolog
Java
Analyse lexicale
Jeu
Forth Ada
Pascal
Reconnaissance de motif
C++ Lisp
APL
Fortran
16
Reconnaissance d’expressions rationnelles
Python C
Java
Prolog
Que veulent dire les expressions rationnelles suivantes ? Et
qu’obtient-on sur le fichier Grep1.txt ?
Forth
C++ Lisp
Ada
^[A-Z] ␣$
^$
([^o]+o){2,}
[-+]?[0-9]*\.?[0-9]*
Pascal
APL
Fortran
17
Écriture d’expressions rationnelles
Python C
Java
Prolog
Produire une expression rationnelle permettant (avec l’outil grep
ou sous un éditeur) de trouver les motifs suivants :
Les mots commençant par une majuscule.
Les lignes qui contiennent au moins 4 fois le caractère ‘t‘
C++
Ada
Les lignes qui ne sont pas vides et qui ne se terminent pas par
un caractère blanc
Les lignes vides et celles qui ne se terminent pas par un blanc
Lisp
APL
Fortran
Forth
Pascal
18
Corrections
Python
Java
C
Prolog
^[A-Z] filtre toutes les majuscules en début de ligne.
Terminal
Forth Ada
$ grep -Eno “^[A-Z]” Grep1.txt
1:P
7:T C++3:B
10:N
11:C
14:B
Lisp
Pascal
APL
Fortran
19
Corrections
Python C
Java
Prolog
␣$ filtre tous les espaces en fin de ligne.
Terminal
Forth Ada
Pascal
$ grep -Eno ” $” Grep1.txt C++3:
4: 7:
Lisp
APL
Fortran
20
Corrections
Python
Java
C
Prolog
^$ filtre toutes les lignes vides.
Terminal
Forth Ada
Pascal
$ grep -En “^$” Grep1.txt C++2:
6: 9: 13:
Lisp
APL
Fortran
21
Corrections
Python
Java
C
([^o]+o){2,} filtre toutes les lignes contenant au moins 2 fois le caractère ‘o‘ séparés par d’autres caractères.
Terminal
Prolog
Forth
$ grep -Eno “([^o]+o){2,}” Grep1.txt
C++3:Bonjo
4:tu trouveras l’information que tu so
14:Bonne jo
APL
Fortran
Lisp
Ada
7:Tu pourras me co
10:Ne te trompe pas comme la dernière fo
Pascal
22
Corrections
C
Python Prolog
Java
[-+]?[0-9]*\.?[0-9]* (trouvé sur Internet). Veut filtrer les nombres, mais comme tout est optionnel, contient le motif vide…
qui filtre tout ! Il faut corriger en [-+]?[0-9]+\.?[0-9]*
Cela prend en compte des nombres comme 12.53, mais pas .23. Si
C++
Ada
on veut pouvoir filtrer les deux types, on doit utiliser :
Lisp
APL
Fortran
([-+]?[0-9]+\.?[0-9]*|[-+]?\.[0-9]+)
Forth
Pascal
23
Corrections
Python
Java
C
Mots commençant par une majuscule.
Terminal
Prolog
$ grep -Eno “[A-Z][a-zA-Z]*” Grep1.txt
1:Paris
3:Bonjour C++3:Alain
Lisp
7:Tu
10:Ne
11:Ce
13:Quelques
14:Bonne APL
Forth Ada
Pascal
Mais cela filtrerait aussi le Maxima du mot wxMaxima. Fortran
24
Corrections
Python
Java
Mots commençant par une majuscule. On pourrait regarder ce qu’il y a avant la majuscule !
C
Prolog
Terminal
$ grep -Eno “(^| +)[A-Z][a-zA-Z]*” Grep1.txt
1:Paris C++3:Bonjour
Lisp
3: Alain
7:Tu
10:Ne
11:Ce
13:Quelques
14:Bonne APL
Pascal
Forth Ada
Mais on trouve aussi ␣Alain, il y a un blanc de trop ! Fortran
25
Corrections
Python
Java
Mots commençant par une majuscule. Il faut pouvoir exprimer un début (en fait un bout de mot, donc aussi les fins de mots) de
C
mot : le caractère \b n’est pas standard (mais exprime le début de mot avec grep -E).
Terminal
Prolog
Forth
$ grep -Eno “\b[A-Z][a-zA-Z]*” Grep1.txt
C++1:Paris 3:Bonjour
3:Alain
7:Tu
10:Ne
Ada
Pascal
Fortran
Lisp
11:Ce
APL
13:Quelques
14:Bonne
26
Lignes contenant au moins 4 fois ‘t‘
C
Python
Java
Terminal
Prolog
$ grep -Eno “^([^t]*t){4,}.*$” Grep1.txt
→ souhaites Terminal
C++
Forth Ada
4:tu trouveras l’information que tu
$ grep -Eno “^([^t]*t){3,}.*$” Grep1.txt
4:tu trouveras l’information que tu
→ souhaites
5:sur http://www.sjtu.edu.cn.
Lisp
APL
Fortran
Pascal
27
Lignes qui ne sont pas vides et qui ne se terminent pas par
un caractère blancPython
Java
C
Prolog
Terminal
$ grep -Eno “.*[^ ]$” Grep1.txt
1:Paris, le 12 septembre 2016
5:sur http://www.sjtu.edu.cn.
Forth
C++ Ada
Lisp
APL
Fortran
8:alain.chilles@sjtu.edu.cn
10:Ne te trompe pas comme la dernière → fois!
11:Ce n’est pas alain.chilles@sjtu
12:ni alain.chilles@sjtu.cn
14:Bonne journée $$^
Pascal
28
Les lignes vides et celles qui ne se terminent pas par un blanc
Facile !
Python
Java
C
Terminal
$ grep -En “(.*[^ ]$|^$)” Grep1.txt Prolog
1:Paris, le 12 septembre 2016 Forth 2:
5:sur http://www.sjtu.edu.cn.
8:alain.chilles@sjtu.edu.cn C++6: Ada
→ fois!
9:
10:Ne te trompe pas comme la dernière
11:Ce n’est pas alain.chilles@sjtu
Lisp
14:Bonne journée $$^
13:
APL
Fortran
12:ni alain.chilles@sjtu.cn
Pascal
29