La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

cours de compilation

93 pages
etCompilationUniversitéPPParisdeSudChristineMasteraulin-Mohringd'InformatiqueMarcM1ouzet20082009Courshercrance,utilesbuleCeetdeprésenformelstedelestaillebphasesundeAladed'unvdeunbienprqu'iloourgrEvammeestquietittransforme59uneN,suiterésultatsdeexpressionsarap-actèrd'Inesdereprésenlatanlestestunqu'ilprégalemenoestgrêtreammedoncenunedusuitemoexamenl'unitéquipréalisé.ourronTéléphonets'exécuterypd'utiliserourutiliseprolesduiredansletroisièmer(automatesésultatgrammaires).dutprogramme.tUn"PrincipdesmetdeuxièmeenÀ÷uvrel'étudedesnousméthoàdesdesetUnoutilsprogrammed'ortananalyseilaleêtreetplussyntaxiqueortan;exemptled'écrirenedédétailleraprogram-pasQuelqueslepagefonctionnemen:t:deetanalysesLemaiss'inprotéresseraàunleurlateurmiseordonnéesenélectronique÷uvre72dansBureaule-d'unersité,étage.LestlangagesPréamdelesprogrammationsurmolangagesdernesvusdelehautdenivannéeeaupropnis,osenrégulières,tIluneégalemenunprécoprofondissemendudesdeerreursegraceterprétationàLangages"unelaanalyseannéesémantiquesouvtraenerstdeprésentesousheronslaformed'unlangagesprogrammation.deuntdeypimpes ...
Voir plus Voir moins

Vous aimerez aussi

et
Compilation
Univ
ersité
P
P
P
aris
de
Sud
Christine
Master
aulin-Mohring
d'Informatique
Marc
M1
ouzet
20082009
Coursherc
rance,
utiles
bule

Ce
et

de
présen
formels
te
de
les
taille

b
phases
un
de
A
la


de
d'un


v

de
un
bien
pr
qu'il
o
our
gr
Ev
amme
est
qui
etit
transforme
59
une
N,
suite
résultats
de


expressions
ar
ap-
actèr
d'In
es
de
représen
la
tan
les
t
est
un
qu'il
pr
égalemen
o
est
gr
être
amme
donc
en

une
du
suite
mo

examen

l'unité
qui

p
réalisé.
ourron
Téléphone
t

s'exécuter
y
p
d'utiliser
our
utilise
pro
les
duire
dans
le
troisième
r
(automates
ésultat
grammaires).
du
t
programme.
t
Un
"Princip

des
met
deuxième
en
À
÷uvre
l'étude
des
nous
métho
à
des
des
et
Un
outils
programme
d'
ortan
analyse


il
ale
être
et
plus
syntaxique
ortan
;
exempt
le
d'écrire


ne

détaillera
program-
pas
Quelques
le
page
fonctionnemen
:
t
:
de


et
analyses
Le
mais

s'in
pro
téressera

à
un
leur
lateur
mise
ordonnées
en
électronique
÷uvre
72
dans
Bureau
le
-


d'un
ersité,

étage.
Les
t
langages
Préam
de
les
programmation
sur
mo
langages
dernes
vus
de
le
haut
de
niv
année
eau

prop
nis,
osen
régulières,
t
Il
une
égalemen

un
préco
profondissemen

du
des
de
erreurs
e
grace
terprétation
à
Langages"
une
la
analyse
année
sémantique

souv
tra
en
ers
t
de
présen

te

sous
herons
la

forme

d'un
langages

programmation.


de
un
t
de
yp
imp
es.
te
La
est
dernière
de
phase

de
doit
la
t


est
de
la
il
génér
imp
ation
t
de
soit

d'erreurs;
o

de
un
qui
on
se
est
fait
un
en
p
plusieurs
tout
étap
meur
es
hevronné.

informations
ondan
La
t
WEB
à

diéren
http://www.lri.fr/~paulin/COMPIL
ts
aluation
langages
Le
in
dule
termédiaires
orte
a
partiel
v
un
an
nal.
t

d'ab
asso
outir
à
au


jet
de
programmation
exécutable
au
de
duquel
la
p


hine.
sera
Nous
Co
étudierons
:
plus
dresse
particulièremen

t
01
l'organisation
92
de
05
la
INRIA
mémoire
y
p
Île-de-F
our
P
la
Orsa
gestion
Univ
des
Bat
app
1er
els
Merci
de
prioritairemen
pro
le

électronique.
Ce
.
.
.
able
.
des
21
matières
.
1
.
In
.
tro
.

.
à
.
la
.

.
2
.
1.1
.
Rapp
.
els
.
de
.
notation
.
.
2.1.1
.
.
.
.
.
.
.
.
.
La
.
.
.
.
.
2.1.9
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
motifs
.
.
2
.
1.2
.
Qu'est-ce

que
.
la
.

.
?
.
.
18
.
.
.
.
.
.
.
Génération
.
.
.
Représen
.
.
.
l'en
.
.
.
2.2.7
.
.
.
.
.
.
.
du
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
régulière
.
.
.
.
.
Qu'est-ce
.
.
.
.
2
.
1.2.1
Construction
À
.
quoi
.

.
sert
l'automate
?
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
de
.
.
.
.
.
Construction
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
régulières
.
.
.
.
2
.
1.2.2
.
Les
.
dicultés
.
.
.
.
table
.
.
.
.
.
T
.
.
.
.
.
.
.
.
.

.
.
.
.
.
t
.
.
.
.
.
.
.
21
.
.
.
.
.
.
.
.
.
T
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
qu'une
1.2.3
.
Les
.
métho
.
des
.
.
.
.
13
.
automate
.
.
.
.
.
.
.
.
.
.
.
.
.
14
.
l'automate
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.5
.
.
.
.
.
.
.
.
.
.
.
.
.
15
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.7
3
he
1.2.4
.
Un
.
exemple
.
d'analyse
.
.
.
.
.
.
16
.

.
.
.
.
.
.
.
.
.
.
.
.
.
prop
.
de
.
.
.
.
.
.
.
.
.
17
.

.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.1
.
de
.
.
.
.
.
.
3
.
1.2.5
.
Qu'attend-on
.
d'un
Outils

.
?
.
.
.
.
.
.
.
.
.
.
.
.
2.2.3
.
.
.
.
.
.
.
.
.
.
.
.
.
19
.
l'analyseur
.
.
.
.
.
.
.
.
.
.
.
.
.
20
.
de
.
transitions
5
.
1.2.6
.
Quelques
.
notions
.
de
20
séman
t
tique
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
terprétation
.
l'analyseur
.
.
.
.
.
.
.
.
.
T
.
unités
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Le
.
.
6
.
1.3
.
Les
.
diéren
.
tes
.
phases
.
de
.
la
21

.
.
.
.
.
.
.
.
13
.
Ob
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
13
1.3.1
Qu'est-ce
Analyse
expression
.
?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.3
.
qu'un
.
?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.4
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
.
1.3.2
.
Syn
.
thèse
.
.
.
.
14
.
Rendre
.
déterministe
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.6
.
minimalisation
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
16
.

.
herc
.
de
9
.
1.3.3
.
T
.
able
.
des
.
sym
.
b
.
oles
.
.
.
.
.
.
.
.
.
.
.
.
2.1.8
.
des
.
taires
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
.
A
.
os
.

.
la
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
.
1.4
.

2.2

d'analyseurs
d'un
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
.
F
.
t
.
l'analyseur
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.2
.
d'analyse
10
.
1.4.1
.
In
.
terpréteur
.
v
.
ersus
.
Compilateur
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
.
Expressions
.
étendues
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.4
.
de
11
.
1.4.2
.

.
hine
.
virtuelle
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.5
.
tation
.
la
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.6
.
raitemen
.
de
.
trée
.
.
.
.
.
.
.
.
.
.
11
.
1.4.3
.
Dans
.
quel
.
langage
.
écrire
.
un
.

.
?
.
.
20
.
In
.
vs
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.3
.
raitemen
.
des
.

.
.
12
.
2
.
Analyse
.

.
13
.
2.1
.
Les
.
bases
.
théoriques
.
.
.
.
.
.
.
.
.
.
2.3.1
.
rôle
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
.
.35
.
.
b
.
er
.
11,
.
2008
.
4
.
2.3.2
.
A
en

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
du
.
.
.
.
.
.
.
36
.
37
.
.
.
.
.
.
.
.
.
.
.
tique
.
.
.
.
.
.
.
.
.
.
.
.
22
.
2.3.3
.
Liaison
.
en
.
tre
.
l'analyseur
.

.
et
.
l'analyseur
.
syn
.
taxique
.
.
.
.
3.6.2
.
.
.
3.6.3
.
.
.
.
.
.
.
.
.
.
.
.
22
.
2.3.4
.
T
.
ok
.
ens
Le
dans
.
o
.

.
.
3.7.6
.
.
.
.
.
.
.
Analyse
.
.
.
oles
.
.
.
.
.
.
.
.
.
iden
.
.
.
tation
.
.
.
sym
.
.
.
de
.
.
.
yp
.
.
.
.
.
es
.
.
.
Septem
.
.
.
.
.
.
.
.
22
Conits
3
.
Analyse
.
syn
.
taxique
.
23
Grammaires
3.1
.
Généralités
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ull,
.
.
.
.
.
.
.
des
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.7.1
.
.
.
.
.
.
.
.
.
simples
.
.
.
.
.
.
.
LR(
.
.
.
.
.
.
.
.
.
)
.
.
.
.
.
.
.
.
.
tes
23
.
3.1.1
.
Ob
erreurs

.
.
.
.
.
.
des
.
.
.
.
.
.
.
grammaires
.
.
.
42
.
ables
.
.
.
.
.
.
.
.
.
4.1.1
.
.
.
.
.
.
.
.
.
4.1.2
.
.
.
.
.
.
.
.
.
des
.
.
.
.
.
4.1.4
.
.
.
.
.
.
.
46
.
p
.
.
.
.
.
.
23
.
3.1.2
.
Arbre
.
de
.
syn
.
taxe
46
abstraite
t
.
.
.
.
.
.
.
manc
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
.
.
.
.
.
.
.
.
23
.
3.1.3
.
T
.
raitemen
.
t
.
de
3.6.1
l'analyse
.
syn
.
taxique
.
.
.
.
.
.
.
.
.
.
.
.
.
.
de
.
premier
.
an
.
.
.
.
.
.
.
.
.
.
.
t
.
LL(1)
.
.
.
.
.
.
.
.
.
L'analyse
.
.
24
.
3.2
.
Grammaires
.
.
.
.
.
.
.
.
.
.
.
.
.
.
e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Utilisation
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Le
.
)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
.
LALR(
.
.
.
.
.
.
.
.
.
.
24
.
3.2.1
.
Dénitions
.
.
3.7.5
.
les
.
de
.
.
.
.
.
.
.
.
.
ération
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.7.7
.
d'actions
.
.
.
.
.
.
.
.
.
.
.
42
.
partir
.

.
.
.
.
.
.
.
Analyse
.
4.1
.
sym
.
.
.
.
.
.
.
.
24
.
3.2.2
.
Arbre
.
de
.
dériv
.
ation
tro
syn
.
taxique
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ortée
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.1.3
.
la
.
b
.
.
.
.
.
.
.
.
.
.
.
tation
25
oles
3.2.3
.
Quelques
.
exemples
.
.
.
.
.
.
.
.
Sc
.

.
.
.
.
.
.
.
.
.
.
.
.
.
4.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T
.
relations
.
.
.
.
.
.
.
.
.
.
.
.
25
29
3.2.4
Les
Grammaire
hes
et
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.5.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
.
3.2.5
.
Analyse
.
descendan
.
te/ascendan
.
te
.
.
.
.
.
.
3.6
.
LL(1)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32
.
Dénitions
26
.
3.3
.
Automates
.
à
.
pile
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32
.
Calculs
.
n
.
du
.
et
.
suiv
.
t
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32
.
Commen
.

.
grammaires
.
.
.
.
.
.
.
.
26
.
3.3.1
.
Dénitions
.
.
.
.
.
.
3.7
.
LR(
.
)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
36
.

.
général
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
.
3.3.2
.
Construction
.
d'un
.
automate
.
à
.
pile
.
.
3.7.2
.
d'items
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.7.3
.

.
.
.
général
.
.
.
.
26
.
3.4
.
Analyse
.
descendan
.
te
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.7.4
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
.
Liens
.
tre
.
diéren
.

.
grammaires
.
.
27
.
3.4.1
.
In
.
tro
.

.
.
.
.
42
.

.
des
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
42
.
Compression
.
tables
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.8
.
à
27
de
3.4.2
non
F
textuelles

.
t
.
de
.
l'analyse
.
descendan
.
te
.
.
4
.
séman
.
43
.
T
.
des
.
b
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
.
3.4.3
.
Écriture
.
fonctionnelle
.
d'un
.
analyseur
43
descendan
In
t

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
.
3.4.4
.
Gestion
.
des
43
erreurs
P
.
des
.
ticateurs
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
.
Représen
.
de
.
table
.
sym
.
oles
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
29
Représen
3.5
des
Analyse
b

.
te
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.1.5
.
héma
.
v
.
de
.
ortée
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
46
.
T
.
es
.
.
.
.
.
.
.
.
.
.
29
.
3.5.1
.
F
.

.
t
.
général
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.2.1
.
yp
.
et
.
de
.
ypage
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
46
.
3.5.2
1
1
1.
.
jet
b
.
er
.
11,
.
2008
.
1
.
4.2.2
.
T
81
yp
.
es
.
et
.

.
de
particulière
t
.
yp
.
e
le
.
Allo
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
des
48
.
4.2.3
.
Égalité
.
sur
.
les
.
t
.
yp
v
es
.
.
5.2.4
.
.
.
termédiaire
.
.
.
.
.
.
.
.
.
es
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Utilisation
.
.
.
.
.
.
.
.
.
données
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
.
4.2.4
.
Surc
.
harge
.
d'op
.
érateurs
.
.
.
.
.
.
.
.
.
.
ester
.
.
.
.
.
.
.
87
.
.
.
5.2.3
.
.
.
.
.
.
.
.
.
d'activ
.
.
.
.
.
5.3
.
.
.
.
.
.
.
.
.
69
.
.
.
.
.
.
.
.
.
69
49

4.2.5
.
Inférence
69
de
.
t
.
yp
.
e
5.3.4
à
.
l'aide
.
de
.
sc
.
hémas
5.3.5
de
.
t
.
yp
.
e
els
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.5
.
.
.
.
.
.
.
.
.
5.5.1
.
.
.
.
51
.
4.2.6
.
P
.
olymorphisme
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
Compilation
.
tro
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
84
.
.
.
.
.
.
.
.
.
84
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
53
6.2.4
4.2.7
.
Le
.

.
du
.
Septem
faut

.
simplemen
.
t
.
t

yp
lo
é
.
.
.
.
.
.
.
.
.
.
.
.
.
.
du
.
.
.
.
.
.
.
.
.
.
.
.
.
de
.
.
.
.
.
.
.
.
.
.
.
.
54
.
4.2.8
.
Autres
.
analyses
In
séman
.
tiques
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Les
.
base
.
à
.
.
.
.
.
.
.
Expressions
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ariables
.
.
.
.
.
.
.
.
57
.
4.3
.
A
.
ttributs
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
5.3.6
.
pro
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
76
.
registres
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
tation
.
.
.
.
58
.
4.3.1
.
A
.
ttributs
81
syn
dynamique
thétisés
.
ou
.
hérités
.
.
.
.
.
.
.
.
.
.
Allo
.
.
.
.
.
.
.
.
.
.
.
.
.
5.5.4
.
implicite
.
.
.
.
.
.
.
.
.
.
.
82
.
langage
.
6.1
.
.
.
.
.
.
58
.
4.3.2
.
Év
.
aluation
.
des
.
S-attributs
.
.
.
.
6.2
.
jets
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Visibilité
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T
.
.
.
.
.
.
.
.
.
.
60
.
4.3.3
.
Év
.
aluation
.
des
6.2.3
L-attributs
à
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Ce
.
retenir
.
.
.
.
.
.
.
.
.
.
.
65
.
A
.
aux
.
ariables
.

60
.
5
.
Génération
.
de
.

.
de
.
in
.
termédiaire
.
62
.
5.1
.
In
.
tro
.

.
.
67
.
Organisation
.
tableau
.
ation
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
68
.
Co
.
in
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.3.1
.
tro
.
.
.
.
62
.
5.1.1
.
Mo
.
dèle
.
d'exécution
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.3.2
.

.
de
.
d'une
.
hine
.
pile
.
.
.
.
.
.
.
.
.
.
.
.
.
5.3.3
.
arithmétiques
.
.
.
.
.
.
.
.
.
.
.
.
62
.
5.1.2
.
Allo
.

.
.
.
.
.
.
.
.
70
.
V
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
71
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
62
.
5.1.3
.
V
74
ariables
App
.
de
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.4
.
des
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
79
63
Allo
5.1.4
dans
Séman
tas
tique
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
81
.
Représen
.
des
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.5.2
.

.
.
.
.
.
.
.
.
63
.
5.1.5
.
Pro
.

.
et
.
fonctions
.
.
.
.
.
.
.
.
.
.
.
.
5.5.3
.

.
explicite
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
82
.
Allo
.

.
.
.
.
.
.
.
.
.
.
.
.
63
.
5.1.6
.
Organisation
.
de
.
l'en
.
vironnemen
.
t
6
.
d'un
.
ob
.
84
.
In
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
64
.
5.2
84
T
Compilation
ableau
ob
d'activ
.
ation
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6.2.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
65
.
5.2.1
6.2.2
Données
ypage
à
.

.
er
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
84
.
T
.

.
une
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
65
86
5.2.2
Optimisations
P
.
assage
.
de
.
paramètres
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
.
qu'il
.
88
.
.
λ(P
particulier

1

In
eau
tro
des

la
à
une
la
Du

texte
1.1
base
Rapp
Une
els
un
de
hargé
notation
texte
On
Exemples
app
.)
elera
de
alphab
virtuelle
et
langage
un
T
ensem

ble
ots)
ni
ompilateur
don
prend
t
t
les
et
élémen
le
ts
s'agira
seron
le
t
par
app
de
elés
C++,
lettr
langage
es
v
.
langage
Un

mot
langage
sur
ord)
un
est
alphab
une
et
langages
Chapitre
langages
est

une
écialisés
suite
2
nie
Un
d'élémen
un
ts
traducteur
de
en
programme.
représen
.
programme
Un
d'un
mot
est
de
pro
longueur
de
du
pratique,

traduire
osé
tan
des
v
lettres

ternes

in
D'un

niv
pro
F
les
.
par
ers
utilisées
bleur.

d'assem
données
du
sera

noté
haut
des
ers
ers

v


description
de
Latex,
haîne
ers


d'une
traduit
:
p
.
te.
Le
t
mot
écialisés
vide
données
est
(Esterel,
noté
de
programme
v
.

La
mobiles,

.
de
des
deux
.
mots

d'un
est
trées

et
de
en
qui
des
en
est
trée
notée
mot
t
tan
traitemen
.
le

our
description
.

L'ensem
qui
ble

des
de
mots
duire
sur
résultat
p

est
En
noté
il
utile
de
t
un
(monoide
représen
libre).
t
Un

langage
ers
sur
suite
un
exécutables
alphab
la
et
hine.
égalemen

est
langage
un
haut
ensem
eau
ble

de
ortran,
mots
ML,
de
.
est
v
ie
un
une
d'assem
partie

de
langage
taxique,
bleur
syn
ers
.

1.2
binaire.
Qu'est-ce
D'un
que
de
la
niv

v
?
les
1.2.1
d'une
À
hine
quoi
(JVM).

D'un
sert
de
?
de
Un
(HTML,
tr
W
aducteur
v
est
le
un
p
programme
qui
qui
lui-même
transforme
en

d'impression
haque
our
mot
impriman
d'un

langage
raitemen
l'analyse
de
÷uvre,
sp
sur
:
un
de
alphab
(SQL),
et
réactifs
en
Lustre)
mises
langages
en

un
Compilation
mot
ers
d'un
pro
langage
sp
hniques
(téléphones

téléviseurs,rob
sur

un
.
alphab
et
un
A A n
a ,...,a a a ...a ǫ1 n 1 2 n
w w w w1 2 1 2
∗A A
∗A A A
L1
A L A1 2 2biguë
v
à
b
et
er
Univ
11,
faut
2008
signe
3
utilisan
1.2.2
ou
Les
suiv
dicultés
arithmétique:

ten
Un
à

soustraction.
est
son
un
on
programme
eut

Commen
qui
s'eectuer

arithmétique
en
v
général

de
tités.
passer
oir
par
juxtap
de
tière
nom-
b
breuses
les

ticateur
in
naturelles
termédiaires
univ
:
à
Chaîne
linéaire
de
:

érateurs
liste
les
de
la
"mots",
Un
arbre
le
de
une
syn
forme
taxe
v
abstraite,
implan

tiel
de
les
in
qu'il
termédiaire.
tité
Comme
de
dans

b
t
eaucoup
une
de
à
problèmes
terprété
informatiques,
représen
il
signe
sera
y
essen
hoisir
tiel
arithmétique
de
qui

pilateurs.
hoisir
un
les
in
b
le
onnes


non
p
une
our
On
une
Les
application

particulière
les
qui
implicites:
seron

t
haîne
souv

en
p
t
d'analyse
des
t

d'une
en
vue
tre
de
les
expression
imp
Si
ératifs

de
d'une

Le

langage
en
p
temps
est
et
ord
en
tes

deux

tions
Un
une

sa
traite
iden
souv
aleur
en
Les
t
et
des
représen
programmes
en

v
il
te
faut
v

.
les
est
erreurs
un
et
sp
faire
t
un
le
diagnostic
autorisé

ticateurs
p
am
our
faudrait
l'utilisateur.
tre

et
Un
en

Ces
doit
paraissen
p

ermettre
En
d'exécuter
t

langage
t
ersel
les
termédiaire

réduit
1.2.3
problème
Les
la
métho
de
des
am
On
transformations.
distingue
notation
une
adopter
phase
p
d'analyse
ou
qui



qu'une
t:

asso
haîne
op
de
t


est
règles
la
et
description
Langage

ersel
d'un


t
L'analyse
qu'en

eut
à
1.2.4
partir
exemple
de
L'exemple
l'en
ne
trée
illustre
d'une
passage

expression
haîne
simple,
de


suite
une

donnée
une

sous
(app
d'arbre.
elée
on
arbre
eut
de
la
syn
aleur
taxe
expression
abstraite).

Cette
ter.
analyse
à
est
haque
largemen
our
t
d'expliciter
indép
essen
endan
il
te
d'ab
du

langage
diéren

en
de
Les
la


et
Vien
représen
t
t
ensuite
en
une
à
phase
v
de
un
synthèse
ticateur
qui,
v
à
en
partir
.
de
deux


donnée
des

osés
v
ten
a
une

tité
le
sa
résultat
oir


une
en
description
de
du
aleur
même
liées

Le
dans
fait
un
in
langage

plus
sym
pro
ole

écial
he
tan
du
la
langage
Si

même
hine.
était
La
dans

iden
de
il
lourde:
aurait
langages
biguïté
p
il
our

plus
en

l'iden

y-41

l'expression
a
y
priori
t
la
.
réalisation
règles
de
nous
eaucoup
t
b
an
mais
Septem
n p n×p
n+p
L L L1 2 nL L L1 2 n
M M M1 2 p M M M1 2 p
x1+(y−41−z)∗−t
x 1
x1 4 1
41 −
−41
(y−41)−z y−(41−z)
x1+((y−41−z)∗−t) (x1+(y−41−z))∗−t
x1+(((y−41)−z)∗−t)ou
Ces
asa
b
prend
er
taille(cte(a))=1
11,
:
2008

4
un
ou
taille(val_droite(a))
bien
précéden
a
bool
v
int
oir
dénir

La
à
yp
une
asa
notation
est_moins(a)
arb
aussi

Un
te.
oper

est_opp
d'op

érations

se
:

p
t
op
aisémen
t
t
est

un
des
et
pro
s'écrira

(a)

sinon
es
1
par
taille(val_opp(a))
rapp
par
ort
taille(opp(a))=1+taille(a)
à
qui
la
id

Moins
de
id
l'arbre
asa
représen
of
tan

t
Binop
l'expression.
asa
Les
val_droite,
feuilles
int
de
élémen

t
arbres
t
son
par
t
sur
formées
e.
des
de
iden
fonction
ticateurs
argumen
ou
(de
des
asa

v
tes.
tier.
Les
taille
n÷uds
int
son
si
t
alors
soit
est_plus(a)
binaires
est_mult(a)
dans

le
1

p
de
la
Septem
:
,
taille(moins(a,b))=1+taille(a)+taille(b)
of
de
ou
de
Opp
te
soit
:
unaire
string
dans
Plus
le
Mult

Ident
de
Cte
l'opp
:
osé
oper
(
et
|
fonctions
unaire).
fonctions
En
val_ident
pratique
asa
la
id
manipulation
:
d'une
|
telle
val_gauche,

val_opp
arb
asa

asa
te
fonctions
se
taires
fait
ermetten
en
de
in
simplemen
tro
une
duisan
ération
t

un
turelle
t
le
yp
yp
e
Exemple
(abstrait)
taille
a
l'arbre
v
une
ec
qui

en
type
t
asa
arbre

t
ident
e
:
)
id
ren
asa
oie
asa
en

Elle
:
:
int
:
*
of
asa
taille
plus,moins,mult
=
:
est_ident(a)
asa*asa

asa
1
asa
si
opp
ou
:
ou
asa
alors
*
+
asa
+
La
sinon
manipulation
+
des
On
ob
eut
jets
utiliser
dans
notation
un
ltrage
tel
taille(ident(n))=1
t
taille(plus(a,b))=1+taille(a)+taille(b)
yp
taille(mult(a,b))=1+taille(a)+taille(b)
e
Co
se
Ocaml
fait

par
CAML
l'in
implan
termédiare
l'exemple
des
t
fonctions
type
de
=
test
type
:
=
fonctions
|
de
|
test
type
est_ident,
=

of
est_plus,
|
est_moins,
asa
est_mult,
des
+ − ∗ −








→then
de
de
b

er
ter
11,
oles
2008
Qu'attend-on
5

let
langage.

Les
taille
de
=
et
function
en
Ident(_)
erreurs
Septem
Expressions
1
.
|
asso
Cte(_)
utilisen
un
hines
1
des
|
les
Binop(_,a1,a2)
tester
dans
en
1

+

taille(a1)
in
+
Un
taille(a2)
du
|
mal
Opp(a)
Les
ornes

1
de
+
par
taille(a)
grammaire

de
Sp
ticateurs
écier
moires,
et


euv
par


est
sur
un
la
tes

La
de
garder
l'arbre

une
in
fonction
étap
valeur
euv
qui

étan
sans
t
syn
donné
La
une
ouv
fonction

mem

asso
Exemple

syn
t
ées
à
.

non
haque
else
iden
La
ticateur
de
une
se
v

aleur,
à
et

un
Les
arbre
niv
de
des
syn
our
taxe

abstraite
langages
représen
t
tan
des
t
ticateurs
une
t
expression,
longs

b
sa
mémoire.
v
justié
aleur.
tôt
Remarque
tier
Dans
les
les
et
TP
t
asso
de

ermet
au


un
nous
de
utiliserons
représen
le

langage
simples,
Ob
d'analyse

thèse
e
t
Caml.
et
Ce

langage
seule
est
la
particulièremen
d'arbre
t
abstraite.
bien

adapté
des
à
doit
l'écriture

de
qui

pas
en
et
particulier
rep

à
la
Iden
notion

de

t
t
yp
3
es
.
de
.
données


Références
(tels
4.5
que
"toto"
les

arbres)

s'y
l'arbre
implan
syn
te
abstraite

fera
t.
un
Remarques
d'attributs


Le
la

qui
hoix
le
d'une

b
langages
onne
haut

eau
d'arbre
t
de
iden
syn
p
taxe
représen
abstraite
des
est
mé-
essen
les
tiel

p
utilisen
our
par
la
tre
phase
adresses.
d'analyse
iden
séman
p
tique
en
et
être
de
mots
syn
qui
thèse.
t
Il
eaucoup
représen
place
te
Il
de
donc
manière
de
non-am

biguë
par
et
en
non
an
redon-
partager
dan
diéren
te,

la
de

rapidemen
du
l'égalité.

table
à
symb
eectuer.
p
Les
de
expressions
une
de
ondance
t
tre
yp
nom
e
u
asa
l'utilisateur
et
une
les
tation
expressions
terne
arithmétiques
Dans
bien

formées
les
son
es
t
et
en
syn

p
p
en
ondance
être

binées
e.
le
Ce
de
n'est
engendré
pas
une
vrai
passe
p

our

l'ensem
termédiaire
ble
de
des
taxe
mots
1.2.5

d'un
sur
?
l'alphab

et
erreurs
b

des
p
t
oir
dépassemen
les
du
statiques
ou
ne
zéro
t
par
l'exécution
division
programme
la
être
de
de
exemple
orter
par
erreur
s'agit
l'utilisateur.
il

dynamiques
ticateurs
erreurs
formés
les
Constructions
t
taxiques
ellen

s'app
mal
l'exécution
yp
à
if

tableau.
erreurs
taxe
→ →


{x,y,z,0,1,2,3,4,5,6,7,8,9,+,∗,−,(,)}le
ariables
en
b
à
er
une
11,
deux
2008
à
6
de

Septem
Le
l'adresse
programme
k
de



doit

être
dié
si
pas
p
formes
ossible
mémoire.
rapide
te
(en
Un
particulier
mémoire
ne
le
pas
asso
b
programmme

teurs
et
t
pro
ond
duire
v
un
et

une
de
v
qui
l'en
s'exécutera
l'état
rapidemen

t.
des
La
Mem

an
Un
de

vironnemen
doit
v
être
ter

p

aleurs.
que
d'un
le
:

dans

v
dans
t
le
pas
langage
les
de
aleur,
haut
déterminé
niv
de
eau
emplacemen
doit
teurs,
être
en
eectiv
osition
emen
p
t



exécuté
en
par
si
la


pas
hine.
téressera
Dans
Il
la
que
pratique,
ées.
la
l'ensem
séman
de
tique
y:=x+1+y;
des
:
langages
alors
de
l'exemple
programmation
v
est
mémoire
très
.
souv
et
en
manipule
t


à
t
zones
sp
lesquelles
éciée.
sto
Cette
des
situation
our
p
ortemen
ose
on
des
osan
problèmes
vironnemen
p
une
our
mémoire
assurer

la
Si


des
des
applications
ne
(co
p
de
ne
mobile
des
Ja
par
v
l'en
a).

Le
la
résultat
haque
d'un
ariable
même
t
programme
mémoire.
p
p
ourra

donc
p
v

arier
même
suiv
la
an
vironnemen
t
être
le


asso
utilisé
aleur
.
emplacemen
.
mémoire
.
t
La
non
mo
mémoire
dularité
Exemple
Lorsque
langage
l'on
t

dié
un
On
gros
transformations
dév
la
elopp
a
emen
séman
t,
illustrerons
il
k
est
Nous
imp
Mem
ortan
ble
t
états
de
la
p
Si
ouv
x:=1;
oir
et
proter
est
de
adresse
la
t

suiv
ompilation
représen
sép
la
ar
aleur
é
la
e
à
.
sur
Chaque
En
mo
t
dule
état
p
programme
eut
des
être
ariables,

serv
sans
t

représen
l'implan
des
tation
de
de
dans
toutes
on
les
eut
fonctions

qu'il
er
utilise.
v
On
P
se



ten
t
te
programme,
en
distingue
général

d'une
tes
signatur
l'en
e
t
donnan

t
place
par
la
exemple
à
les
haque

de
de
ariables.
t
le
ypage
ne
des
tien
op
que
érations.
v
Le
globales,
même
manipule
programme
de

oin
p
et
ourra
passe
être
paramètres
utilisé
pro
dans
que
des
v

alors
textes
vironnemen
diéren
est
ts.
t
1.2.6
à
Quelques

notions

de

séman
v
tique

A
exactemen
un
un
langage
t
de
En
programmation
de
est
oin
en
deux
général
de
asso
ariable

euv
une
t
séman
ondre
tique
la
qui
p

dans
le
mémoire,
sens
l'en
du
t

eut
L'eet
mo
du
au

du
est
l'état
une

mo
v
dication
à
de
haque
l'état
t
de
la
la
(év

tuellemen
hine.
une
L'état
aleur
de
dénie
la
la
mémoire
n'est
p
initialisée).
eut
On
être
un
mo

délisé
vironnemen

n'est
une
mo
fonction
par
de

l'ensem
s'in
ble
aux
des
de
places
de
mémoires
mémoire.
(adresses)
y
v
plusieurs
ers
de
les
tique
v
nous
aleurs
skip
sto
notons
m∈ i
m(i) i

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin