Python
C
Java
C++ Lisp
Ada
Prolog
Théorie des langages de programmation
Alain Chillès – 祁冲 ParisTech Shanghai Jiao Tong
Forth
上海交大–巴黎高科卓越工程师学院
12 septembre 2016 – 2016年9月12日 –丙申年八月十二
APL
Fortran
Pascal
1
Livre de référence Python
Java Forth
C Prolog
Compilateurs. Principes, techniques et outils Alfred Aho, Ravi Sethi et Jeffrey Ullman
C++ Lisp
Ada
Pascal
APL
Fortran
2
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement Analyse lexicale Analyse syntaxique Analyse sémantique Jeu
Lisp
3
Histoire des langages de programmation
1
2
3
Les langages fondateurs : FORTRAN (1954), LISP (1958) et
C
Python
Java
COBOL (1959) Prolog Forth Les langages novateurs : Simula (1962), Forth (1968), SQL (1970), SmallTalk (1972), Prolog (1972) et TEX (1977)
Les descendants : C (1972), C++ (1983), Postscript (1983), VHDL (1987), Python (1991), Java (1995), C# (2002), etc.
C++
Ada
Pascal
Lisp
APL
Fortran
Plusieurs milliers de langages informatiques !
4
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement Analyse lexicale Analyse syntaxique Analyse sémantique Jeu
Lisp
5
Différents types de langages – dans la manière d’écrire
1 2
Impératifs (on donne des ordres à la machine) Forth
Fonctionnels (on compose des fonctions qui renvoient des
C+
3
Déc
C
Python Prolog
Java
résultats)
Ada
+
Lisp
laratifs (on dit ce que l’on veut)
Pascal
APL
Fortran
6
Différents types de langages – dans le contexte
1
Séquentiel (les choses se font dans un ordre prédéfini)
C
Python Prolog
Java
Événementiel (on réagit aux événements) C++
2
Forth Ada
Pascal
3 Parallèle ou concurrentiel (plusieurs utilisateurs et/ou plusieurs
ma
chines)
Lisp
APL
Fortran
7
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement Analyse lexicale Analyse syntaxique Analyse sémantique Jeu
Lisp
8
Différentes implémentations
1
2
Interprétation (interactif, chaque instruction est
Python C
Java
immédiatement exécutée)
Forth
Prolog
Compilation en machine virtuelle (le programme est transformé en un sous-langage très simple ; il faut alors un runtime pour
C++
Ada
l’exécuter)
3 Compilation (le programme est transformé en un langage dédié
à la machine hôte) 4 etc.
Lisp
Pascal
APL
Fortran
9
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement Analyse lexicale Analyse syntaxique Analyse sémantique Jeu
Lisp
10
Points communs = ce que nous allons étudier
1
2
On écrit toujours un programme (interactif, sous éditeur ou dans un environnement spécialisé)
C
Python
Java
Prolog
Ce programme doit être :
vérifié (analyse lexicale → analyse syntaxique → analyse sémantique) Ada
traduit pour la machine.
Pascal
Lisp
C++
Quel que soit l’objectif et les choix, on a toujours ces tâches à effectuer
APL
Fortran
Forth
11
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement Analyse lexicale Analyse syntaxique Analyse sémantique Jeu
Lisp
12
Fonctionnement : analyse lexicale
Python C Prolog
Java Forth
On tape une instruction : que se passe-t-il ? 1R:
2 Wxmaxima C++
a<-2;
Ada
Pascal
a<-2; a <- 2
;
Lisp
APL
Fortran
a
<
-2
;
13
Fonctionnement : analyse lexicale
Python C
Java
Définition
Prolog
On appelle lexème, toute lettre, chiffre, symbole ou assemblage de Forth
lettres, chiffres et symboles autorisés par le langage.
Ada
l’analyse lexicale s’appelle analyseur lexical (lexer)
APL
Fortran
C++
Définition
On appelle analyse lexicale la transformation d’une chaîne de caractères donnée en une liste de lexèmes. L’outil qui réalise
Lisp
Pascal
.
14
Fonctionnement : analyse lexicale
Python C Prolog
Java
Un analyseur lexical
F
rth
sépare la chaîne de caractères en potentiels lex
o
vérifie que ces lexèmes sont autorisés par le langage ; génère des erreurs si ces opérations échouent ;
C++
Ada
produit une liste de lexèmes (qui sera l’entrée de l’analyseur
syntaxique).
Lisp
Pascal
APL
Fortran
èm
es ;
15
Fonctionnement : analyse lexicale
1R
> 2b<-3
Java
Erreur : unexpected symbol in "2b"
C
Prolog
2C
int 2i;
C++
F
Python
o
3
Matlab
^ Pascal APL
» 2b=1
Lisp
2b=1
Fortran
’:
code.c:3:9: error: expected identifier
code.c: In function ‘m
Ada
or ‘(’ before numeric constant
int 2i;
Compilation échouée.
|
Error: Unexpected MATLAB expression.
ain
rth
16
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement
Analyse lexicale
Analyse syntaxique
Analyse sémantique Jeu
Lisp
17
Fonctionnement : analyse syntaxique
C
Prolog
Python
Java
Définition
On appelle arbre syntaxique un arbre dont les étiquettes des nœuds
gage étiquettes des feuilles sont des identificateurs valides du langage.
Ada
correspondent à des opérateurs autorisés par le lan
et
le
C++
F
o
r
t
s
h
Définition
On appelle analyse syntaxique la transformation d’une liste de lexèmes en un arbre syntaxique. L’outil qui réalise l’analyse
syntaxique s’appelle analyseur syntaxique (parser).
APL
Fortran
Lisp
Pascal
18
Fonctionnement : analyse syntaxique
C
est transformée en
C++ Lisp
Java Prolog
La liste de lexème :
Python
×
8
( 12 + 24 )
Forth
×
Ada
+8
APL
Fortran
Pascal
12 24
19
Fonctionnement : analyse syntaxique
R
1C
> b=(1+2;
2C
Erreur : ’;’ inattendu(e) in “b=(1+2;”
C++
Ada
i=(1+2;
i=(1+2;
Matlab
Lisp
Pascal
3
b=(1+2;
|
Python
Java
Prolog
Forth
code.c:4:11: error: expected ‘)’
before ‘;’ token
^
Compilation échouée.
4 b=(1+2;
APL
Error: Unbalanced or unexpected
parenthesis or bracket.
Fortran
20
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement
Analyse lexicale Analyse syntaxique Analyse sémantique Jeu
Lisp
21
Fonctionnement : analyse sémantique
C
Prolog
Définition
Python
Java
On appelle analyse sémantique la phase qui vérifie qu’un arbre Forth
syntaxique est valide dans le langage (c’est-à-dire qu’il a une chance de pouvoir être exécuté). Ada
C++
Certains implémentations de langages ne réalisent pas cette phase et génèrent des erreurs à l’exécution ! D’autres, font des
Lisp
corrections syntaxiques.
APL
Fortran
Pascal
22
Fonctionnement : analyse sémantique
Python
Java
C Prolog
Forth de sémantique du langage ; Ada
L’analyseur sémantique
renvoie un arbre syntaxique respectant les règles de syntaxe et
C++ Lisp
éventuellement, corrige les erreurs de syntaxe…
Pascal
APL
Fortran
23
Fonctionnement : analyse sémantique (erreurs)
Python
Java
C
Prolog
1C
int *p,*q;
p+q;
C++
Forth
Matlab
» A=1:3; » A*A
Lisp
2
code.c:4:6: error: invalid operands
to binary + (have ‘int *’ and ‘int *’)
p+q;
Ada
Pascal
APL
Fortran
^
Compilation échouée.
Error using *
Inner matrix dimensions must agree.
24
Fonctionnement : analyse sémantique (correction)
C
1R
Python Prolog
Java
> A<-matrix(c(1,2,3),nrow=3) > A*A
[,1]
[2,] 4
[3,] 9
Lisp
C++
[1,] 1
Forth Ada
Pascal
APL
Fortran
25
Plan
Python
C
Java
Forth Ada
Pascal
APL
Fortran
Langages de programmation
Histoire Prolog Différents types
Différentes implémentations
Points communs
C++
Fonctionnement
Analyse lexicale Analyse syntaxique Analyse sémantique Jeu
Lisp
26
Où est l’erreur ? Python
Java
C Prolog
C++ Lisp
syntaxique ou sémantique).
Forth Ada
Dans les exemples suivants, il faut
trouver la ou les erreurs ;
Pascal
APL
Fortran
préciser la phase qui reconnaîtra l’erreur (analyse lexicale,
27
Où est l’erreur (langage C) Python
C
1 int main()
2{
3 int i=1;
Java Prolog
4 p r i n t f ( ” i =%d ” , i ) ;
Forth Ada
Pascal
5 return (0); C++
6}
Lisp
APL
Fortran
28
Où est l’erreur (langage C) Python
C
1 int main()
2{
3 int Chillès =1;
Forth Ada
Pascal
5} C++
4 return(2∗ Chillès );
Lisp
APL
Fortran
Java Prolog
29
Où est l’erreur (langage C) Python
C
1 int main()
2{
3 int i=1,j,k;
Java Prolog
4 k=i+j ;
Forth Ada
5 return ( k ) ; C++
6}
Lisp
APL
Fortran
Pascal
30
Où est l’erreur (langage C) Python
C
1 int main() 2{
3 int i =1;
Java Prolog
4
5
6
7 8}
if (i==1) return (0)
Forth Ada
Pascal
C++
else
Lisp
APL
Fortran
return (1);
31
Où est l’erreur (langage C) Python
C
1 int main() 2{
3 int i =1;
Java Prolog
4
5
6
7 8}
if (i=1) return (0);
Forth Ada
Pascal
C++
else
Lisp
APL
Fortran
return (1);
32