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

Python
C
C++
Alain Chillès – 祁冲 Ada
Java
Théorie des langages de programmation
P
An
g
r
a
o
lyse
syn
lo
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
26 septembre 2016 – 2016年9月26日 –丙申年八月廿六
Lisp
APL
Fortran
taxique
Forth
Pascal
1

Plan Python
C Prolog
Java
Analyse syntaxique
Arbres syntaxiques
Grammaire BNF
Forth Ada
C++
Questions sur les grammaires BNF
Limitation des grammaires BNF Jeu
Pascal
Lisp
APL
Fortran
2

Rôle de l’analyse syntaxique
C
Prolog
Python
Java
Vérifier que les objets sont syntaxiquement corrects ;
vérifier les parenthèses, crochets, accolades et guillemets ;
reconnaître et séparer les opérateurs des opérandes ;
vérifier que les opérateurs ont le bon nombre d’arguments (peut être fait lors de l’analyse sémantique) ;
C++
Ada
gérer les priorités d’opérateurs ;
…
produire un arbre syntaxique correct.
Lisp
Pascal
APL
Fortran
Forth
3

Arbre syntaxique : exemple −(1 + 2) + (3 − 4) × (−5)
C
Prolog
Python
Java
Dans cette expression, on a essentiellement trois problèmes
particuliers :
F
t
1 le ’-’ désigne, soit un opérateur unaire (un seu
r
h
comme dans −(1 + 2)), soit un opérateur binaire (deux
opérandes) ;
2 il faut bien décider si −5 est un nombre, ou un opérateur
C++
devant un nombre (du ressort de l’analyse lexicale) ; 3 la multiplication × est prioritaire sur l’addition et la
soustraction.
Lisp
Pascal
Ada
APL
Fortran
l op
éra
o
nd
e
4

Arbre syntaxique : exemple −(1 + 2) + (3 − 4) × (−5)
C
Java Forth
Python
+
Prolog
−×
Ada
+ −−5 Pascal
APL
C++
Lisp
Fortran
1234
5

Rappel : vocabulaire des arbres
C
lé racine. +
Exemple
Ada
C
+
Python
Java
Définition
Pour un arbre donné, on appelle nœud, là d’où partent des
P
r
o
lle
fe
l
o
branches :
nœud
g
;
on a
e, là d’où ne partent pas de Forth
ppe
uill
branche ; on appelle étiquette les noms qui sont dans les nœuds et
les feuilles. Les sous-arbres d’un nœud sont appelés fils, le nœud au
dessus d’un sous-arbre est appelé père, le nœud père de tout l’arbre
est
appe
Pascal
Dans l’arbre précédent, les étiquettes des nœuds sont : +, −,
×;
APL
Lisp
les étiquettes des feuilles sont : 1, 2, 3, 4 et −5.
Fortran
6

Plan Python
C Prolog
Analyse syntaxique
Arbres syntaxiques
Grammaire BNF
Java
C++
Ada
Questions sur les grammaires BNF
Limitation des grammaires BNF Jeu
Pascal
Lisp
APL
Fortran
Forth
7

Description de la syntaxe : grammaire BNF (Backus Naur
Form)
Python
Java
C
Prolog
BNF
1 ::= “0” | “1” | “2” | “3” | “4” |
􏹪→ “5” | “6” | “7” | “8” | “9”
2 ::= |
􏹪→ C++
Ada
3 ::= | “+” | 􏹪→ “-”
4 ::= “+” | “-” | “x” | “/”
5 ::= |
􏹪→ | “(” “)”
Lisp
APL
Fortran
Forth
Pascal
8

Description de la syntaxe : grammaire EBNF (Extended
Backus Naur Form)
Python
Java
C
Prolog
::= “0” | … | “9”
Forth
BNF
1
2
::= [ “+” | “-” ] Ada
3 C++
::= { }
4
5 ::= | Pascal
::= “+” | “-” | “x” | “/”
r> APL
Fortran
􏹪→ | “(” 2 La mémorisation
C++
BNF
􏹪→ “)” Lisp
Pascal
Python
Java Prolog
BNF
Forth Ada
2 ::= |
5
􏹪→ | “(”
::= |
APL
Fortran
10

Plan Python
C Prolog
Analyse syntaxique
Arbres syntaxiques
Grammaire BNF
Java
C++
Ada
Questions sur les grammaires BNF
Limitation des grammaires BNF Jeu
Pascal
Lisp
APL
Fortran
Forth
11

Grammaire ambiguë
Avec la règle
Python
Java
Forth Pascal
C
BNF
P
l’expression 1 + 2 × 3 peut être alors lue comme :
1
::= |
C++
1+(2×3) ou (1+2)×3,
􏹪→
rolog
Ada
BNF
1 ::= | 􏹪→ APL
Fortran
Lisp
elle ne sera lue que comme : 1+(2×3).
12

Grammaire surabondante
Avec les règles
Python
Java
1 2
::= [ “+” | “-” ]
C
BNF
Prolog
Forth
Ada
1 + −3 qui ne sont pas usuelles,Pascal
on souhaiterait les écrire :
1 + (−3), APL
C++
::= |
􏹪→
on s’autorise des expressions du type :
Lisp
Fortran
et ne pas autoriser les écritures précédentes. Comment faire ? des
termes positifs et des termes négatifs…
13

Problème de l’associativité
C
C++
Ada
Python
Java
Associativité à gauche : 1+2+3 se lit (1+2)+3
BNF
Prolog
1 ::= | “+”
􏹪→
Associativitéàdroite: a=b=c selita=(b=c)
Forth
BNF
Pascal
1 ::= “=”
Lisp
APL
Fortran
􏹪→ |
􏹪→ “=”
14

Problème des priorités
C
Python
Java
BNF
o
P
o
r
g
l
1 2 3
::
Forth
C++
Ada
=”
+”
|
”


::= |
::= “x” | “/”
􏹪→ | “(” “)”
4 ::= |
-”
􏹪→ permetdereconnaîtrecommeonveutlesexpressiPonsdautsypceal
APL
Fortran
Lisp
1+2×3 ou 1×2+3, etc.
15

Erreur logique
C
BNF
Python Prolog
Java
Forth
1 ::=
C++
Ada
Pascal
provoque une récursion infinie !
Lisp
APL
Fortran
16

Plan Python
C Prolog
Analyse syntaxique
Arbres syntaxiques
Grammaire BNF
Java
C++
Jeu
Lisp
Ada
Questions sur les grammaires BNF
Limitation des grammaires BNF
APL
Fortran
Forth
Pascal
17

Ce qui est possible avec les grammaires BNF
C
avec
BNF
{an.bn, n ∈ N} Prolog
Python
Java
Forth
On peut reconnaître les langages du type
1 ::= ε
2 ::= | “a”
C++
􏹪→ “b”
Définition
algébrique ou langage hors contexte. Lisp
Ada
Pascal
APL
Fortran
Un langage reconnu par une grammaire BNF est dit langage
18

Ce qui est possible avec les grammaires BNF
Python C
Java
grammaire BNF suivante :
Prolog
On peut décrire les langages rationnels. Par exemple, le langage
reconnu par l’expression rationnelle [a-z]+ peut être décrite par la
Forth
BNF
Ada
C++
2
Lisp
1 ::= “a” | … | “z”
::= | Pascal
APL
Fortran
19

Ce que l’on ne peut pas faire avec les grammaires BNF
Python C
Java
Reconnaître des langages (dits contextuels), par exemple Prolog
{an.bn.cn, n ∈ N} ;
savoir si un identificateur a été défini (avant, après, ailleurs) ;
C++
Ada
c’est du ressort de l’analyse sémantique ;
vérification des types ; c’est du ressort de l’analyse
sémantique ; …
Lisp
Pascal
APL
Fortran
Forth
20

Plan Python
C Prolog
Analyse syntaxique
Arbres syntaxiques
Grammaire BNF
Java
C++
Jeu
Lisp
Ada
Questions sur les grammaires BNF
Limitation des grammaires BNF
APL
Fortran
Forth
Pascal
21

Arithmétique
Python C
Java
C++ Lisp
Prolog
Produire une grammaire BNF, pour une calculatrice où :
les entiers peuvent avoir un signe + ou − devant ; Forth
les expressions peuvent être parenthésées (et précédées d’un
signe) ;
les opérations possibles sont
Ada
+, −, ×
on interdit les écritures inhabituelles du type + − 3… ;
et / ; on doit gérer les priorités entre opérateurs.
Pascal
APL
Fortran
22