程序代写代做代考 Java python Fortran c++ ada prolog ER C

C
C++
Alain Chillès – A≤ Ada
Python
Java
Théorie des langages de programmation Expressions régulières/rationnelles (Compléments)
Prolog
Forth
ParisTech Shanghai Jiao Tong ⌦w§’–ÙŒÿ—SäÂ↵fb
Pascal
18 septembre 2016 – 2016t918Â –⇡3tkAk
Lisp
APL
Fortran
1

Plan
C
Analyse lexicale
Les expressions rationnelles dans grep
Python Prolog
Java Forth
Un peu de théorie
Expressions rationnelles en langage C
C++
Jeu
Lisp
APL
Fortran
2
Ada
Pascal

Quelques notations particulières supplémentaires.
\b=le bord d’un mot. Exemple : trouver les mots de 9 lettres
(minuscules).
Python
Java
C
C++
Terminal
Prolog
$ grep -Eno “\b[a-z]{9}\b” Grep1.txt
1:septembre
4:trouveras
4:souhaites
7:contacter
Forth Ada
[:alnum:]=[a-zA-Z0-9] (À l’intérieur de []).
Terminal
Pascal
Lisp
$ grep -Eno “[[:alnum:]]\.e” Grep1.txt
5:u.e
APL
8:u.e Fortran C’est aussi long à écrire ! Pas très utile !
3

Terminal
Forth
Python
Java
Quelques notations particulières supplémentaires (suite).
[:punct:]=[!”#$%&’()*+,-.\/:;?@[\\\]_‘{|}~] Remarquer les \
Prolog
5:://
14:$$^ C++
C
$ grep -Eno “[[:punct:]]{3}” Grep1.txt
$ grep -Eno “[[:punct:]]+$” Grep1.txt
5:.
10:!
14:$$^
Lisp
Pascal
Ada
APL
Fortran
4

Plan
C
Analyse lexicale
Python Prolog
Les expressions rationnelles dans grep
Un peu de théorie
Expressions rationnelles en langage C C++
Jeu
Lisp
APL
Fortran
5
Java Forth
Ada
Pascal

Langage
Python
Java
Définition
1 2
3
On appelle alphabet un ensemble fini de lettres et de symboles. On appelle mot ou chaîne une succession finie d’éléments de
C
Prolog
mots.
Forth Ada
l’alphabet.
On appelle langage tout ensemble (fini ou infini) constitué de
C++
Exemple
1 Alphabet binaire : {0, 1}.
2 Alphabet français : {a, …, z, A, …, Z, é, É, è, È, ç, Ç, à, À,
L
APL
3
Langage des mots sur 16 bits : reconnu par (0|1){16} Fortran
6
â , ä , ê , ë , ˆy , ÿ , û , ü , î , ï , ô , ö , œ , Œ , æ , Æ , ù , . . . }
isp
Pascal

Opérations sur les langages
Si L et M sont deux langages. Union : L [ M
C
Python
Java Forth
Concaténation : LM, où Prolog
LM = {st, s 2 L, t 2 M}. Notation L0 = ✏ (où ✏ est le mot vide) et
k+1 k k C++ 8k2N,L =LL =LL.
Fermeture de Kleene de L : L⇤, où
L⇤ = [ Lk.
k2N Fermeture positive de L : L+, où
Pascal
Lisp
AP[ L +k⇤⇤
Ada
L = L = LL = L L.
k 2N⇤
Fortran
7

Quelques exemplesPython
Java
C
Exemple
Prolog
Si L l’ensemble des lettres est reconnu par [a-zA-Z] et C l’ensemble
des chiffres est reconnu par [0-9], alors
L [ C est reconnu par [a-zA-Z0-9].
LC est reconnu par [a-zA-Z][0-9].
C++
L⇤ est reconnu par [a-zA-Z]*
C+ est reconnu par [0-9]+. Définition
Pascal
Forth Ada
Tout langage reconnaissable par une expression rationnelle est appelé langage rationnel.
Lisp
APL
Fortran
8

Langages rationnels… ou pas ?
C
Python
Java
Exemple
L’ensemble des mots de k éléments de l’alphabet est un
langage rationn
langage rationnel.
P
el.
Forth
rolog
L’ensemble des lexèmes d’un langage informatique est un
Si l’alphabet est {a, b}, le langage Ada
C++ {anbn, n 2 N} n’est pas un langage rationnel !
Pascal
L’ensemble des expressions bien parenthésées (autant de parenthèses ouvrantes que fermantes, et dans le bon ordre)
n’est pas un langage rationnel ! Lisp
Fortran
APL
9

Plan
C
Analyse lexicale
Python Prolog
Les expressions rationnelles dans grep
Un peu de théorie
Expressions rationnelles en langage C C++
Jeu
Lisp
APL
Fortran
10
Java Forth
Ada
Pascal

Un rappel sur scanf Python
Java C Prolog
Lecture sécurisée Source C
Forth Ada
4{ C++
1 #include 2
3 int main()
5 char s[100];
6 scanf(“%99[^\n]”, s);
7 return(0);
8}
Lisp
Pascal
APL
Fortran
11

Un complément sur printf : le format %.*s Python
Écriture d’un début de chaîne Source C
C
C++
Java Prolog
1 #include 2
3 int main()
4{
Forth
5 char s[] = “abcdefghijklmn”;
6 printf(“%.*s\n”
s+
7 return(0); 8}
Ada
4);
, 7,
Pascal
APL
Fortran
Exécution C
$ ./subprint
Lisp
efghijk
12

La librairie regex Python Source C
561 562
563
Java
C
/* POSIX compatibility. */
Prolog
extern int regcomp (regex_t *__restrict
,! __preg,constchar*__restrict__pattern,
,! int__cflags);
extern int regexec (const regex_t *__restrict
,! size_t__nmatch,regmatch_t C++
56
te
Fortran
L
APL
5e
rn void regfree (regex_t *__preg);
Ada
,! __preg,constchar*__restrict__string,
,! __pmatch[__restrict_arr],int__eflags);
564 extern size_t regerror (int __errcode, const Pascal
,! regex_t*__restrict__preg,char
,! *__restrict__errbuf,size_t
i
x
s
p
,! __errbuf_size);
Forth
13

La librairie regex Python
C
Java
Elle définit
Le type d’un expression rationnelle regex_t
1 2
3
donnée par une expression rationnelle regexec Pascal
P
ltat
re
t (avec 2 champs rm_so –
r
o
gma
l
tc
o
4 Une fonction d’exécution du filtrage d’une chaîne de caractères C++
5 Une gestion permettant de comprendre les erreurs dans la compilation d’une expression rationnelle regerror
Lisp
APL
6 Une fonction de libération de la mémoire regfree
h_
g
Le type du résu Forth début du filtrage et rm_eo – fin du filtrage)
Une fonction de compilation d’une expression rationnelle (et qui en vérifie donc la validité) regcomp
Ada
Fortran
14

La librairie regex : détail Python
C
Java Prolog
Source C 31
regex_t myregexp;
if (regcomp(&myregexp, expr,
32
33 {
Forth
,! REG_EXTENDED|REG_NEWLINE))
34 printf(“Mauvaise expression
35 36 37
Lisp
C++
Ada
,! rationnelle:%s”,expr); regfree(&myregexp);
return(2); }; APL
Pascal Fortran
15

La librairie regex : détail Python
Java
C
Source C
9 10
char expr[100], texte[100]; Prolog
char* p = texte;
Source C 38
Forth Ada
C++
regmatch_t pmatch[100];
Source C 43
Pascal
Lisp
APL
Fortran
16
,! pmatch,0);
res = regexec(&myregexp, p, 1,

Le fichier source
Python
Source C C
Java Prolog
#include #include
1
2
3
4 5{
Forth
C++
int main()
Ada
6 // expr est l’e
7 8
on rationnelle
// texte est le texte à lire
xpre
// p est un pointeur sur le début à
,! lire
char expr[100], texte[100];
9
10 char* p = texte;
Lisp
APL
Fortran
ssi
Pascal
17

Le fichier source
Source C
C
Python
Java
// Noter la commande sécurisée du
11
12
13 14
15 char c = getchar();
16 if (c != ’\n’)
17 { 18
Fortran
Prolog
,! scanf
printf(“Donner l’expression régulière
,! :”);
scanf(“%99[^\n]”, expr);
Forth
,! arrêtédelire C++
Ada
19
,! longue!”);
Lisp
return(1);
20 };
// Il faut savoir comment on s’est
printf(“Erreur, ligne trop
APL
Pascal
18

Le fichier source
C
Ada
return(1); }; APL
Python
Source C C
Java
23 24
,! :”);
scanf(“%99[^\n]”, texte);
25 26
{ ,! longue!”);
printf(“Erreur, ligne trop
27 28
Pascal Fortran
19
++
if ((c = getchar()) != ’\n’)
Lisp
Prolog
21 22
// On recommence avec le texte
printf(“Donner le texte à reconnaître
Forth

Le fichier source
Python
29 C // D’abord, vérifier l’expression
Source C
,! rationnelle
30 31
Java
Prolog
Forth
// La fonction regerror pourrait
,! préciserl’erreur regex_t myregexp;
32 if (regcomp(&myregexp, expr,
,! REG_EXTENDED|REG_NEWLINE)) C++
33 { 34
Pascal
35 36
return(2); APL
L
3
isp
};
7
Fortran
Ada
printf(“Mauvaise expression
,! rationnelle:%s”,expr); regfree(&myregexp);
20

Le fichier source
Source C
Python
Java
38
39
40
41
42
C regmatch_tpmatch[100];
int res = 0, debut, fin, offset = 0;
do
{
Prolog
Forth
// On filtre à partir de p
43 res = regexec(&myregexp, p, 1,
,! pmatch,0); C++
44 45 46
// On récupère les ,! informations
4
fin = pmatch[0].rm_eo; Fortran
21
7
isp
APL
Ada
if (res) break; // regexec
,! s’estplantéoun’arienfiltréPascal
L
debut = pmatch[0].rm_so;

Le fichier source
Python
Source C
Java
o
48 49
// Noter le %.* qui permet
C
P
g
C++
Ada
,! d’affich
er
un
51 offset += fin; 52 }
Pascal Fortran
22
53 54 55
56 }; Lisp
while (res == 0);
regfree(&myregexp);
return(0); APL
r
o
es
l
o
us-
chaîne
printf(“%.*s (%d, %d)\n”, Forth
,! fin-debut,p+debut,debut+offset,
,! fin+offset-1);
50 p += fin;

Exemple
Python C
Exécution C
Java Prolog
C++
lain (1, 4)
hill (7, 10)
s (13, 13)
Pascal
Lisp
APL
Fortran
23
Forth Ada
$ ./mygrep
Donner l’expression régulière : [a-z]+
Donner le texte à reconnaître : Alain Chillès

Plan
C
Analyse lexicale
Python Prolog
Java Forth
Les expressions rationnelles dans grep
Un peu de théorie
Expressions rationnelles en langage C
C++
Jeu
Lisp
APL
Fortran
24
Ada
Pascal

Langage rationnel ou pas ?
2
reconnaître.
Pascal
Python
Java
Exercice 3.3.2, page 125. Décrire les langages reconnus par les 1C
expressions rationnelles suivantes :
Prolog
1 a(a|b)*a
2 (a?b*)*
3 (a|b)*a(a|b)(a|b)
4 a*ba*ba*ba*
5 (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*
Ada
Exercice 3.3.5, pages 125-126. Les langages suivants sont-ils
C++
rationnels ? Si oui, proposer une expression rationnelle pour les
1 Une chaîne de caractères constituée de minuscules et qui
Lisp
APL
contient les 5 voyelles dans l’ordre.
(a ! e ! i ! o ! u ! y)
2 Une chaîne de caractères constituée de minuscules dont les
lettres vont strictement croissantes. (Comme dans bip, car
b < i < p) Fortran Forth 25 Langage rationnel ou pas ? C C+ ne l’est pas) Ada 5 Une chaîne de caractères constituée de ‘a‘ et de ‘b‘ et 6 Une chaîne de caractères constituée de ‘a‘ et de ‘b‘ et qui ne Lisp Python Java 3 Un commentaire en langage C, il commence par /* et finit par Prolog */, il ne doit pas y avoir un */ à l’intérieur, à moins d’être compris entre deux guillemets ". 4 Une chaîne de caractères constituée de chiffres, dont deux chiffres consécutifs sont différents. (2016 est bon, mais 2005 + contenant un nombre impair de ‘a‘ et un nombre pair de ‘b‘. contient pas la sous-chaîne "abb". APL Fortran Forth Pascal 26