C
P
Lisp
Python
Java
Théorie des langages de programmation –
Gra
g
r
m
o
ma
l
ir
o
es
formelles
Forth
Alain Chillès – 祁冲 Ada
C++
17 octobre 2016 – 2016年10月17日 –丙申年P九月a十s七cal
APL
Fortran
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
1
Plan Python C Prolog
Grammaires formelles Règles et applications Classes de langages
Java
Forth Ada
Pascal
C++
Jeu
Lisp
APL
Fortran
2
Qu’est-ce qu’une grammaire formelle ?
Définition
Python
Java
C
Une grammaire formelle est la donnée
d’un ensemble de symboles terminaux T (les symboles de Prolog
l’alphabet du langage) ;
d’un ensemble de symboles non-terminaux N ;
d’un ensemble de règles de production R (permet de déduire des non-terminaux du langage à partir de ceux que l’on
C++
Ada
Pascal
connaît).
Forth
Exemple
Le langage {an.bn, n ∈ N} peut être défini par :
les symboles terminaux T = {a, b} ;
APL
les symboles non-terminaux N = {S} ; Fortran Lisp
les règles de production R = {S → a.S.b, S → ε}.
3
Dérivation
Définition
Python
2
elle, on dit que u produit v (ou u se dérive en v ou v dérive de
C
Java
Soit L un langage, (u,v) ∈ L , G = (T ,N,R) une grammaire
form
u)si∃(α,β)∈(T ∪N)∗2,∃S∈N et∃w∈L: Prolog
On écrit alors
C++
u = α.S.β, v = α.w.β et S → w ∈ R. Forth
u→v Ada
S’il existe un k ∈ N∗, et des mots (u ,…,u
1 k −1
) tels que Pascal
Lisp
u → u1, u1 → u2,…,uk−1 → v, APL
on écrit
u →k v ou plus généralement u →∗ v Fortran
4
Langage reconnu par une grammaire
Python
Java
Définition
C
note
Prolog
Forth
G = (T ,N,R) une grammaire formelle S ∈ N, on appelle
Soit
langage reconnu par la grammaire G, à partir de l’axiome S et on
LG(S) = {v ∈ T ∗, S →∗ v}
C’est donc le langage que l’on peut obtenir à partir des symboles
C++
Ada
terminaux, en produisant de nouveaux mots à l’aide des règles de
production, la première partant de S. Exemple
Pascal
T = {a,b}, N = {S}, R = {S → a.S.b, S → ε}, en appliquant la deuxième règle on produit ε, on appliquant ensuite la première
Lisp
APL
règle, on produit
22
a.b, a .b , …
Fortran
5
Plan Python C Prolog
Grammaires formelles
Règles et applications
Java
Forth Ada
Pascal
C++
Classes de langages
Jeu
Lisp
APL
Fortran
6
Linéarité à gauche (ou à droite) d’une grammaire
Définition
Python
Java
Une grammaire est dite linéaire à gauche (resp. à droite) si toutes C
les règles de production sont de la forme S → ε, ou S → a où a∈T,ouS→T.a(resp.S→a.T)oua∈T etT∈N,oùS
Prolog
désigne un symbole non-terminal.
Forth
Exemple
Ada
C++
LagrammairedéfinieparT ={a,b},N={S}etR={S→ε,
S → a.b.S} est une grammaire linéaire à droite. (On peut la voir comme N = {S,T} et R = {S → ε, S → a.T, T → b.S}). Elle
définit le langage
Pascal
qu
s
L
p
LG(S)={(a.b) , n∈N},
e l’o
i
n
pe
APL
ut décrire par l’expression rationnelle
(ab)∗
Fortran
n
7
Langages rationnels
Théorème
Python
Java
C
Les langages rationnels sont les langages reconnus par les
Prolog
grammaires linéaires à gauche ou à droite.
Exemple
Forth
On peut facilement produire l’automate déterministe associé à la
grammaire ci-dessus
Ada
C++
LispS APL T
a
b Fortran
Pascal
8
Grammaires algébriques
Python C
Définition
Java
o
P
C++
Théorème
g
r
On appelle grammai
l
re al
géb
o
riq
ue
un
règles sont de la forme X →?? où X est un non-terminal. Forth
e grammaire dont toutes les
Exemple
} et Ada
OnadéjàvuT ={a,b},N ={S
R=
{S → ε, S → a.S.b} Pascal
Les langages algébriques sont les langages reconnus par les
grammaires algébriques.APL Lisp
Fortran
9
Langages algébriques
Exemple
Python
Java
C
BNF
Prolog
1
2
3
4
Forth Ada
→
5
“+” | “-”
T = {0,1,2,3,4,5,6,7,8,9,+,−,(,)},
Lisp
“0” |
APL
N = {CNN,C,N,O,F,S}, R = {CNN → 1, CNN → 2,…
CNN → 9, C → 0, C → CNN, N → C, N → CNN.N, O → +,
O → −, F → N, F → (.S.), S → F, S → S.O.F}
Fortran
10
Grammaires et langages contextuels
C
Python
Java
Définition
On appelle grammaire contextuelle une grammaire où les règles de production sont de la forme
C++
Prolog
r
u.S.v → u.s.v, où (u,v) ∈ T ∗2, s ∈ T +, F
th
condition que S n’apparaisse jamais dans un membre droit d’une
règle de R. Remarque
texte défini par u et v. Lisp
Pascal
Ada
on convient souvent de rajouter le mot vide au langage reconnu par la grammaire à partir de l’axiome S, en rajoutant la règle S → ε, à
S∈ o
N
,
da
c
ns le
on
APL
Fortran
On peut lire que S peut être remplacé par s, à condition d’être
11
Un exemple contextuel
Exemple
Python
Java
Soit la grammaire définie par T = {a, b, c}, N = {S, B} et C
On a alors
R= S →a.b.c, S →a.S.B, c.B →B.c, b.B.c →b .c
Prolog 22
C++
LG(S) = {an.bn.cn, n ∈ N∗} 333
Forth Ada
Démonstration.
Regardons, par exemple, comment obtenir a .b .c :
a.b.c 2 a2.b.c.B 2 a3.b.c.B.B 3 a3.b.B.c.B 4 a3.b2.c2.B
puis
APL
Lisp
a3.b2.c2.B a3.b2.c.B.c a3.b2.B.c2 a3.b3.c3
334
Pascal
Fortran
12
Plan Python C Prolog
Grammaires formelles
Règles et applications
Java
Forth Ada
Pascal
C++
Classes de langages
Jeu
Lisp
APL
Fortran
13
Reconnaître un langage contextuel ?
C
Python
Java
Soit la grammaire G définie par Prolog
Forth
T ={a,b,c}, N ={S,T,C,X}etR=T →T.C,
T →b.C C.b → b.C X → c
C++
que vaut
Lisp
T → C, Ada
LG(S) ? APL
C . X → X . c , Pascal
S → a.T.b.X, S → a.b.X
T → a.T.b.C, T → T.b.C
Fortran
14