Python
C
C++
Alain Chillès – 祁冲 Ada
Java
Théorie des langages de programmation
B
g
P
NF
et
au
r
o
l
o
t
om
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
30 septembre 2016 – 2016年9月30日 –丙申年八月三十
Lisp
APL
Fortran
ates à pile
Forth
Pascal
1
Plan Python C Prolog
Analyse syntaxique
Grammaire BNF −→ programme C
C+
Java Forth
Ada
Pascal
+
Les automates à piles
Auto
Lisp
APL
Fortran
mates à pile −→ C
2
BNF −→ C : Un exemple Python
C
Java Prolog
Soit la grammaire suivante :
BNF
1
2
3
→
Ada
4
5
6
Pascal
Lisp
APL
Fortran
Forth
3
BNF −→ C : Un exemple Python
Java
1
2
la reconnaissance des naturels et des opérateurs peut-être
C
Remarques :
Prolog
effectuée en analyse lexicale ;
il y a quatre types de lexèmes : les naturels, les opérateurs, les parenthèses ouvrantes, les parenthèses fermantes ;
C++
Ada
3 le langage est très simple, on peut donc utiliser un automate…
au départ, on ne peut avoir qu’un naturel ou une parenthèse ouvrante (c’est déjà de la vérification syntaxique) !
Toujours sous-traiter le plus possible à l’étape précédente !
Lisp
APL
Fortran
Forth
Pascal
4
BNF −→ C : Un exemple Python
C
Java Prolog
Forth Ada
[0-9] 0N(O)
”(”
C++ Lisp
+/−
APL
Fortran
”)”
Pascal
5
BNF −→ C : Un exemple Python
[0-9]
Java
C
+/− NO
Prolog
Forth Ada +/−
Pascal APL Fortran
[0-9]
C++ Lisp
[0-9]
0
[0-9] ”(”
”)” ”(”
()
”(” ”)”
6
BNF −→ C : le code (analyseur lexical) Python
Java
Source C
L
APL
Fortran
1
xeme_t;
C
2}
le
#include
1
2
3
4
6 typedef enum lexeme_t C++
7{
8 NOMBRE, 9 Par_ou,
Prolog
#include
#include
5 // Définition des types de lexème
10 Par_fe, 11 OP
// Naturel
// Parenthèse ouvrante
// Parenthèse fermante
is
p
// Opérateurs (+ ou -)
Ada
Pascal
7
BNF −→ C : le code (analyseur lexical)
Source C
Java Prolog
C++
Ada
} lexeme;
21 // Il est plus facile d
→ de lexèmes
22 typedef struct llexeme 23 {
Pascal
25 int N; Lisp
26 } llexeme;
// Le nombre de lexèmes
Python
14 15 16 17 18 19 20
// Définition du type lexème
C
typedef struct lexeme
{
lexeme_t type; // Son type char valeur[20]; // Sa valeur
APL
24 lexeme tab[50]; // Le résultat
e tr
iller (lorsqu’on → utilise la grammaire BNF) avec un tableau
ava
Forth
Fortran
8
BNF −→ C : le code (analyseur lexical) Python
Java
Source C
C
llexeme resultat; // Le résultat de → l’analyse lexicale
28
Source C
56 int main()
Prolog
C++
Forth Ada
57
{
// s est la chaîne à calculer, par exemple
→ 58
59
“(1-2)+(3-4)”
Pascal
Lisp
char s[50];
printf(“Entrez l’expression à calculer :
“);
APL
→
60 scanf(“%49[^\n]s”, s); // On saisit tous
→ les caractères, et on protège la saisie… Fortran
9
BNF −→ C : le code (analyseur lexical) Python
Source C C
62
Java
C++
→ 64
65
→ automate
Ada
Prolog
// Analyse lexicale en utilisant
→ l’automate le plus simple. Il faudrait Forth
→ changer le switch pour le deuxième
63 int i = 0, j = 0; // i est l’indice de
→
parcours de s, j est le nombre de chiffres
lus
→
APL
Fortran
Lisp
resultat.N = 0;
lexeme lu; // Facile à comprendre, c’est le lexème lu !
Pascal
10
BNF −→ C : le code (analyseur lexical)
L
APL
Fortran
77
isp
Python
C // On a trouvé un lexème de type NOMBRE
void add_nombre(void) { Prolog
if (j != 0) {
Source C
67 68 69 70 71 72 73
74
Java Forth
C++
Ada
→ 75
→ 76
// Attention, il faut
impérativement copier la sous-chaîne
}; 79 };
7
8
lu.type = NOMBRE;
strncpy(lu.valeur, s+i-j, j);
lu.valeur[j] = 0; // une chaîne
se termine par un 0
resultat.tab[resultat.N] = lu;
resultat.N += 1;
Pascal
11
BNF −→ C : le code (analyseur lexical)
→
Ada
Python
Source C
C
Java Prolog
add_nombre();
81 82 83 84 85
// On a un autre lexème
void add_divers(int type)
{
Forth
// Pour savoir qu’un nombre est fini,
il faut tomber sur un autre caratère (ou
→ une fin de chaîne) C++
86 j = 0;
87 lu.type = type;
88 strncpy(lu.valeur, s+i, 1);
Pascal
89 lu.valeur[1] = 0;
APL
90 resultat.tab[resultat.N] = lu;
91 resultat.N += 1; Lisp
92 };
Fortran
12
BNF −→ C : le code (analyseur lexical)
C
99
100
101
102
→
→ ’7’: case ’8’: case ’9’:
Source C
94 C do
→ dit
Python
Java
95
96 { 97
Forth
Ada
98
++
j++;
Lisp
add_divers(OP);
break;
103
cas
break;
104 105
Fortran
// L’analyseur lexical proprement
switch(s[i]) Prolog
case ’0’: case ’1’: case ’2’: case
’3’: case ’4’: case ’5’: case ’6’: case
break;
case ’+’: case ’-’:
Pascal APL
e ’(
’:
add_divers(Par_ou);
13
BNF −→ C : le code (analyseur lexical) Python
Java
C
Source C
Pr
break;
default:
99 exit(1);
94
95
96
97
98
case ’)’:
g
C++
printf(“Erreur !”);
100 }
101 102 103
while (s[++i] != 0);
// La ligne peut se terminer par un nombre
→
qui n’a pas été encore pris en compte
104 add_nombre(); Lisp
a
o
dd_
l
d
o
ive
rs(Par_fe);
Forth Ada
Pascal
APL
Fortran
14
BNF −→ C : le code (analyseur syntaxique) Python
Source C C
Java
30
31
// Déclaration pour pouvoir faire la
C++
32
36
37 };
APL
Fortran
Prolog
→ récursivité croisée int somme(int d, int f);
→
Ada
//
Définitions des fonctions de la BNF
Pascal
return((resultat.tab[d].type == NOMBRE));
33
34 int naturel(int d)
35 { // d est le numéro du lexème
Lisp
// Utilisée par
Forth
15
BNF −→ C : le code (analyseur syntaxique) Python
C
Source C Prolog
Java
39 int facteur(int d, int f)
40 { // On lit les lexèmes entre les indices d
→ (début) et f (fin)Ada
41 return((naturel(d) && (d == f)) ||
→ ((resultat.tab[f].type == Par_fe) && C++
→ (resultat.tab[d].type == Par_ou) &&
→ (somme(d+1, f-1)))); 42 };
APL
Fortran
Lisp
Forth
Pascal
16
BNF −→ C : le code (analyseur syntaxique)
Source C
44 45
46 47
Python
Java
F
int somme(int d, int f) C
{ // On lit les lexèmes entre les indices d → (début) et f (fin)
Prolog
o
int i = f-1, b = facteur(d, f);
rth
// Il faut chercher le bon opéra
→ malheureusement, il peut être au milieu
→ d’un facteur et provoquer ainsi une erreur
→ de filtrage… C++
Ada
48 while ((b==0) && (i>d)) 49 {
Pascal
50
b = (resultat.tab[i].type == OP) &&
facteur(i+1, f) && somme(d, i-1);
→
51 i–;
APL
Fortran
52 }; Lisp
53 return(b); 54 };
teu
r,
17
BNF −→ C : le code (analyseur syntaxique) Python
Java
C
Source C 44
→ 45
Prolog
syntaxique
printf(“\n\nL’expression %s est
C++
// Analyse syntaxique : vérification
→ “incorrecte”); 47 return(0);
46
48 } Lisp
Ada
Pascal
APL
Fortran
syntaxiquement %s”, s, somme(0,
→
→ resultat.N-1) ? “correcte” :
Forth
18
Et les arbres ?
Python Prolog
Java
1 2 3 4
Forth Ada
C
Source C
5{ C++
// Définition du type de l’arbre syntaxique
typedef struct noeud * arbre;
struct noeud
6 char * etiquette;
7 arbre fils_gauche;
8 arbre fils_droit;
9 };
Pascal
Lisp
APL
Fortran
19
Et les arbres ?
Python
Source C C
Java
11 12
→ fd) 13 {
Forth
C++
Ada
APL
Fortran
Prolog
// Fonction d’assemblage des fils
arbre assemble(char * nom,arbre * fg,arbre *
14 arbre new = malloc(sizeof(struct noeud));
Lisp
new->etiquette = nom;
15
16 new->fils_gauche = *fg;
17 new->fils_droit = *fd;
18 return(new);
19 };
Pascal
20
Plan Python C Prolog
Analyse syntaxique
C+
Grammaire BNF −→ programme C
Auto
+
Les automates à piles
Lisp
APL
Fortran
mates à pile −→ C
Java Forth
Ada
Pascal
21
Automate fini de départ
C
[0-9]
[0-9] ”(”
[0-9]
Python
Java
Prolog
+/− NO
[0-9]
C++ Lisp
0
Forth Ada +/−
”)” ”(”
()
Pascal
APL
”(” ”)”
Que manque-t-il ? Vérifier le bon parenthésage et préciser la
syntaxe !
Fortran
22
Automate + pile
Python
Java
C
Empiler x : → x
D ́epiler x : x → Prolog
b, a → Forth
a, → a
0 Ada 1
b, a →
C++
Pascal
Lisp
APL
Fortran
Pile
Reconnaˆıtre {an.bn, n ∈ N}
23
Automate + pile
Python
Java Forth
C
Prolog
Qu’est-ce qu’accepter un mot ?
C++
Ada
État terminal d’acceptation ET pile vide
Qu’est-ce que ne pas accepter un mot ?
L’état terminal n’est pas un état d’acceptation ;
la pile n’est pas vide ;
l’automate est bloqué (pas de transition pour un caractère
arrivant) ;
il y a eu un dépilage d’une pile vide.
APL
Fortran
Lisp
Pascal
24
Grammaire BNF et automates à pile
Python C
Java
Théorème
Prolog
Les langages reconnus par les automates à pile sont exactement les Forth langages algébriques (ou hors-contexte), c’est-à-dire ceux reconnus
par une grammaire BNF.
Ada
C++
Démonstration.
Pascal
Admis. Les démonstrations sont encore plus horribles que pour les
langages réguliers.
Lisp
APL
Fortran
25
Automate à pile : exemple
Python
Java
Forth
”)”, P →
C
Prolog
[0−9] [0−9]
+/− 135
[0−9]
[0−9] 0
C++
”(”, → P
Lisp
+/−
”(”, → P
+/− +/− Ada
2 [0−9] 4
”(”,→P [0−9] APL
6 Pascal ”)”,P →
Ici, on fait en même temps l’analyse lexicale et l’analyse syntaxique!
Ce n’est pas raisonnable en général.
Fortran
26
Automate à pile : exemple
Python
Java
C
Prolog
Par ou, → P OP Ada
NOMBRE 135
OP
NOMBRE 0
Par ou, → P C++
OP
OP Par fe, P →
Forth
NOMBRE 246
Pascal
Par ou,→ P Par fe,P →
Lisp
APL
Ici, on fait l’analyse syntaxique sur les lexèmes ! C’est plus
prudent…
Fortran
27
Plan Python C Prolog
Analyse syntaxique
C+
Grammaire BNF −→ programme C
Auto
+
Les automates à piles
Lisp
APL
Fortran
mates à pile −→ C
Java Forth
Ada
Pascal
28
Automate à pile −→ C : exemple
Source C
1
2
3
Python
Java
#include
C++
4
→
strncpy
//
Définition des types de lexème
5
6 typedef enum lexeme_t 7{
8 NOMBRE,
9 Par_ou,
10 Par_fe, Lisp
APL
11 OP
12 } lexeme_t;
Fortran
Prolog
→ fonctions d’entrée/sortie standard #include
Forth Ada
→ exit et malloc
#include
Pascal
// Naturel
// Parenthèse ouvrante
//
Pare
nthèse fermante
// Opérateurs (+ ou -)
29
Automate à pile −→ C : exemple
Source C
Python
Java Forth
14
15
16
17
18
19
// Définition du type lexème
20
C
C++
typedef struct lexeme
{ Prolog
lexeme_t type; // Son type char valeur[20];// Sa valeur
} lexeme;
Ada
21 // Définition d’une liste de lexèmes
22 typedef struct cellule * liste;
23 struct cellule
24 {
25
Pascal
lexeme tete; // Classique 26 liste queue; // Classique
L
APL
2
Fortran
7
28 };
isp
liste fin;
// Fin de la liste
30
Automate à pile −→ C : exemple Python
Java
Source C
C
30
31
32 { 33
Forth
// Addition en fin de la liste
void add_fin(lexeme e,liste *l) Prolog
// Il faut réserver une nouvelle place
liste element = malloc(sizeof(struct → cellule));
35 element->tete = e; C++
Ada
34 // et mettre tous les pointeurs à jour
element->queue = NULL;
element->fin = element;
// Il y a ici trois cas, à cause du pointeur sur la fin
36 37 38
→
39 if ((*l)==NULL) // La liste était vide
L
APL
4
isp
*l = element;
Fortran
0
Pascal
31
Automate à pile −→ C : exemple Python
Java 41 C else if ((*l)->queue == NULL) // La liste
Source C
→ n’avait pas de queue
42 { 43
44
45 }
Forth Ada
46 else C++
47
→ 48
// La liste a plus de deux éléments :
49
50 };
APL
L
5
;
Fortran
1}
sp
i
Prolog
(*l)->queue = element;
(*l)->fin = element;
{
on ne touche plus à la queue
(*l)->fin->queue = element;
(*l)->fin = element;
Pascal
32
Automate à pile −→ C : exemple
Source C
Python
Java
52
// Définition du type de pile. On a besoin de
53
→ mais ce serait moins lisible typedef struct pile
Ada
Forth
C
54 {
C++
→ savoir si elle est vide ou non. Bien sûr, Prolog
→ on pourrait convenir d’un code d’erreur,
55 char (*pop)(void);
56 void (*push)(char);
57
58
59
int (*vide)(void);
} pile;
Pascal APL
60 // Création et initialisation de la pile
61 char data[50]; Lisp
62 int hauteur = 0;
Fortran
33
Automate à pile −→ C : exemple Python
Source C C
Java
63 char pop_aux(void)
Forth Ada
64 {
65 if (hauteur == 0)
66 {
C++
Prolog
67 printf(“Pile vide !\n”);
68
69 }
exit(1);
70 71 72
else
return(data[–hauteur]);
};
Lisp
Pascal
APL
Fortran
34
Automate à pile −→ C : exemple
Source C
74
75
76
77
78
79
Python
Java
void push_aux(char c) C
C++
{
if (hauteur == 50)
80 }
81 else
82
83
84
85
86 {
data[hauteur++] = c;
L
8
7
88 };
};
int vide_aux(void)
Prolog
{
printf(“Pile pleine !\n”);
exit(2);
return(hauteur == 0); isp
Forth Ada
Pascal APL
Fortran
35
Automate à pile −→ C : exemple Python
Java
90 int main() Prolog
91 { // s est la chaîne à calculer, par exemple
Source C C
“(1-2)+(3-4)”
Forth
→
92 93
94 scanf(“%49[^\n]s”, s); // On saisit tous C++
→
→
Li
les caractères, et on protège la saisie…
95 96
Pascal
→ “);
Ada
char s[50];
printf(“Entrez l’expression à calculer :
// Analyse lexicale en utilisant
l’automate le plus simple. Il faudrait
sp
APL
→ changer le switch pour le deuxième
→
automate
Fortran
36
Automate à pile −→ C : exemple Python
Java 97 Cint i = 0, j = 0, etat_courant=0; // i est
Source C →
Prolog
98
numéro de l’état courant
liste resultat = NULL; // Contient la
100
101
102
// Initialisation de la pile
Pascal
10
L
4
l’indice de parcours de s, j est le nombre
de chiffres lus, etat_courant est le
→ →
99 lexeme lu; // Facile à comprendre, c’est C++
→ liste des lexèmes
Ada
→
le lexème lu !
pile Pile; // Pile de l’automate
Pile.pop = pop_aux;
Pile.vide = vide_aux; isp
103 Pile.push = push_aux;
APL
Fortran
Forth
37
Automate à pile −→ C : exemple
C
strncpy(lu.valeur, s+i-j, j); Ada
113
// Attention, il faut
impérativement copier ce qu’il nous faut
Source C
Python
Java
106 107 108 109 110 111 112
C // On a trouvé un lexème de type NOMBRE void add_nombre(void)
++
→
→ 114
→
116
117 };
Pascal
Lisp
add };
115
(lu,
Prolog
{
if (j != 0)
Forth
{
lu.type = NOMBRE;
dans une nouvelle chaîne
lu.valeur[j] = 0; // et ne pas
&resultat); APL
Fortran
oublier qu’une chaîne se termine par un 0
_fin
38
Automate à pile −→ C : exemple Python
119 120 121 122 123
Java
Forth
Source C
C // On a un autre lexème void add_divers(int type)
C++
Ada
124 125 126 127 128
→ une fin de chaîne)
j = 0;
lu.type = type;
strncpy(lu.valeur, s+i, 1);
12
};
L
add_fin(lu,&resultat); APL
9
Prolog
{
add_nombre();
// Pour savoir qu’un nombre est fini, → il faut tomber sur un autre caractère (ou
isp
lu.valeur[1] = 0;
Pascal Fortran
39
Automate à pile −→ C : exemple
Source C
C
Python
Java
131 132 133 134
do // L’analyseur lexical proprement dit switch(s[i])
C++
j++;
Ada
135
136
137
138
139
break;
case ’+’: case ’-’:
→ →
’3’: case ’4’: case ’5’: case ’6’: case
’7’: case ’8’: case ’9’:
Lisp
142
break;
case ’(’:
140
141
add_divers(Par_ou);
{
Prolog
case ’0’: case ’1’: case ’2’: case Forth
Pascal APL
add_divers(OP);
break;
Fortran
40
Automate à pile −→ C : exemple Python
Java
C
Source C
143
144
145
146
147
case ’)’:
g
C++
Ada
148
149 150 151 152
}
while (s[++i] != 0);
Pascal
→
APL
Fortran
Pr
break;
default:
a
o
dd_
l
d
o
ive
rs(Par_fe);
Forth
printf(“Erreur lexicale !\n”);
exit(1);
// La ligne peut se terminer par un nombre
qui n’a pas été encore pris en compte
153 add_nombre(); Lisp
41
Automate à pile −→ C : exemple
Source C
C
Python
Java
155
156 157 158 159
// Analyse syntaxique : vérification
syntaxique
C++
→
Prolog
void error(int e, char c)
{
printf(“Erreur syntaxique à l’état %d, → caractère %d”,e,c);
160 exit(4);
161 162 163
};
Lisp
// La fonction est naturellement
récursive, ce qui permet de lire les
APL
→
→ lexèmes un par un (c’est l’avantage des
→ automates, ils sont faciles à programmer). Fortran
Forth
Ada
Pascal
42
Automate à pile −→ C : exemple Python
Java
Source C
C int analyse_syntaxique(liste llex)
164 165 166 167 168 169
→ 171
172
L
{
Prolog
char c;
if (llex != NULL)
{
C++
switch (etat_courant) Ada
170
{ // Le code est la traduction littérale de l’automate à pile que nous
17
3
→
Pascal
Fortran
isp
APL
{
// llex est le flux d’entrée
avons donné
→ llex->tete.type)
case 0: // État initial switch (c =
Forth
43
Automate à pile −→ C : exemple Python
Java
Source C
C C++
→
case NOMBRE: Prolog etat_courant = 1;
break; Forth case Par_ou:
174 175 176 177 178 179 180 181 182
etat_courant = 2;
Pile.push(’P’);
error(etat_courant, c);
}; break;
183
184 case 1: // Nombre en début
Li
→
d’expression
sp
Ada
break;
default:
Pascal
APL
Fortran
44
Automate à pile −→ C : exemple
Source C
C
Python
Java
Forth
etat_courant = 3;
185
switch (c =
llex->tete.type)
→ 186
187
188
189
191
→ 192
Prolog
C++
break;
default:
190
error(etat_courant,c);
}; break;
Pascal
193
194 switch (c =
→ llex->tete.type) Lisp
195 {
Fortran
{
case OP:
Ada
case 2: // Parenthèse ouvrante
APL
45
Automate à pile −→ C : exemple
Source C
C C++
203
→ 204
205
Java
case NOMBRE: Prolog etat_courant = 4;
break; Forth case Par_ou:
Pile.push(’P’);
196
197
198
199
200
201
202
Ada
Python
error(etat_courant,c);
}; break;
Pascal
case 3: // On a lu un opérateur APL
→
206 switch (c =
Lisp
→ llex->tete.type)
Fortran
break;
default:
46
Automate à pile −→ C : exemple
Source C
Python
Java
C C++
{
207
208
209
210
211
212
213
214 215 216
Prolog
case 4: // On a un n après une parenthèse
re
→
217 switch (c =
→ llex->tete.type) Lisp
218 {
Fortran
APL
case NOMBRE:
etat_courant = 5;
break; Forth case Par_ou:
Ada
break;
}; break;
etat_courant = 2;
Pile.push(’P’);
Pascal
omb
47
Automate à pile −→ C : exemple
Source C
Python
Java
219 220 221 222 223
C
case OP: Prolog etat_courant = 3;
break;
default: Forth
error(etat_courant,c);
→
224 }; break;
225 case 5: // On a un nombre C++
→ 226
→ 227
L
230
{
228
case OP:
22
Fortran
9
après un opérateur
switch (c =
llex->tete.type)
isp
APL
Ada
Pascal
etat_courant = 3;
break;
48
Automate à pile −→ C : exemple Python
Source C
Java Prolog etat_courant = 6;
231 232 233 234 235 236
C
case Par_fe:
Pile.pop();
C++
Ada
237 238
→ 239
L
}; break;
case 6: // On a une parenthèse
24
isp
APL
{
Fortran
0
→ error(etat_courant,c);
fermante
Pascal
switch (c = → llex->tete.type)
break;
default:
Forth
49
Automate à pile −→ C : exemple Python
Java
Source C
C C++
case OP: Prolog etat_courant = 3;
break; Forth case Par_fe:
241 242 243 244 245 246 247 248
Pile.pop();
break;
→ 249
default:
error(etat_courant,c);
}; break;
default:
250 251
APL
25
}
Fortran
L
2
isp
printf(“Impossible !!!”);
Ada
Pascal
50
Automate à pile −→ C : exemple Python
C
Java
o
Source C
253
→ 254
255 256
// Une fois fini, on relance
C++
Ada
l’analys
i
que
sur la queue.
}
analyse_syntaxique(llex->queue); Forth
P
o
g
es
r
yn
257 return((etat_courant == 1) ||
258 259
6));
};
APL
Fortran
→ →
(etat_courant == 5) || (etat_courant ==
→ ! Lisp
tax
l
// Le résultat renvoyé donne 1 si → l’état final est un état d’acceptation.
// À la fin, une seule instruction suffit
Pascal
51
Automate à pile −→ C : exemple Python
C
Prolog
Java Forth
C
return(0);
Source C 260
printf(“La syntaxe de l’expression %s est
261
262 }
Lisp
APL
Fortran
%s !”,s,(analyse_syntaxique(resultat) &&
→
→ Pile.vide()) ? “correcte” : “incorrecte”);
++
Ada
Pascal
52