Compilateurs & Interprètes - Implantation des langages informatiques

Compilateurs & Interprètes - Implantation des langages informatiques

-

Français
580 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Compilateurs & Interpretes Implantation des langages informatiques Jacques Menu mailto: Cours 13X007 – Centre Universitaire d'Informatique Revision 3 du 20 septembre 2011 J. Menu Compilateurs & Interpretes 1 /58020-09-2011 – Rev. 3
  • analyse semantique de lista
  • construction des tables d'analyse lr
  • listasemflexbison concretement
  • evaluation des arguments par besoin
  • gestion specifique de la semantique lista dans bison
  • methode lr
  • creation des identificateurs lista predefinis
  • fichier bison
  • lista
  • analyse lexicale

Sujets

Informations

Publié par
Nombre de lectures 69
Langue Français
Poids de l'ouvrage 3 Mo
Signaler un problème

Compilateurs & Interpretes
Implantation des langages informatiques
Jacques Menu
http://cui.unige.ch/ menu/~
mailto:Jacques.Menu@unige.ch
Cours 13X007 { Centre Universitaire d’Informatique
Revision 3 du 20 septembre 2011
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 1 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres
1 Prologue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1 Supports de cours et bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Emploi des couleurs dans ce document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1 Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Le langage Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Exemple de code source Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Synoptique d’implantation du langage Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 La machine Pilum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.7 Exemple de code objet Pilum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.8 Code binaire Pilum pour l’exemple Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.9 Conventions de nommage dans le code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.10 Evolution de Lista/Pilum en 2006 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.11 de en 2010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.12 Evolution de Lista/Pilum en 2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.13 Gestion des langues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.14 Decodage des options des executables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.15 Construction de l’implantation de Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.16 L’exemple \FonctionsImbriquees" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.17 Le projet pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.18 Remerciements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 2 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (2)
3 Terminologie & exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.1 Caracteristiques des langages informatiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Lexique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4 Semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5 Notion de sur-langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.6 Statique ou dynamique ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.7 Empilement de machines informatiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.8 Analyse et synthese, passes de compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.9 Ordre d’evaluation et notation post xee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.10 Fonctions strictes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.11 Compilation independante ou separee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.12 Auto-interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.13 Un auto-interprete Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.14 Autocompilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.15 Auto de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.16 Autoreproductibilite d’un autocompilateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.17 Generateurs de compilateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4 Specialites du chef . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.1 Somme des 5 premiers carres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.2 Strategies d’evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.3 Variables logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 3 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (3)
4.4 Inference de types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5 Grammaires formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.1 Notion de grammaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2 Exemple de grammaire : expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3 Derivation et reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.4 Arbres de derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5 Exemple d’arbre de derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.6 Langage engendre par une grammaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.7 Grammaires ambigues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.8 du type 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.9 Exemple de grammaire du type 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.10 Grammaires du type 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.11 Aspects theoriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.12 Hierarchie des formalismes grammaticaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.13 Compilation et grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.14 Exemple de speci cation Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.15 de sp Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6 Analyse lexicale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.1 Deux niveaux de grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.2 Relation entre analyseurs lexical et syntaxique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.3 Exemple de Fortran IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.4 Lecture et consommation des caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 4 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (4)
6.5 Algorithme d’analyse d’expressions regulieres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.6 Analyse lexicale predictive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.7 pr de Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.8 Schema de Horner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.9 Gestion des mots cles reserves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.10 ListaLexPredictif concretement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7 L’outil Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.1 Description soumise a Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.2 Qui fait quoi avec Flex ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.3 Premiere partie d’un chier Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.4 Deuxieme partie d’un chier Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.5 Description des terminaux Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.6 La fonction \yywrap ()" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.7 Manipulation des tampons d’entree/sortie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.8 Expressions regulieres acceptees par Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.9 Actions prede nies de Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7.10 Gestion des ambigu tes par Flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.11 ListaLexFlex concretement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8 Analyse syntaxique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8.1 Exemple de grammaire du type 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.2 Le besoin d’algorithmes d’analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
8.3 Les deux methodes deterministes principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 5 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (5)
8.4 Descente recursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.5 Exemple de descente recursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8.6 Grammaires LL(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.7 LL(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.8 Probleme des notions engendrant le vide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.9 Recursion a gauche, ambigu te et type LL(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
8.10 Comportement en cas d’erreurs syntaxiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.11 Rattrapage d’erreurs syntaxiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
8.12 La methode LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
8.13 Positions d’analyse LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
8.14 Etats d’analyse LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
8.15 Transitions LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
8.16 Calcul de la table des etats d’analyse LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
8.17 Conduite de l’analyse LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8.18 Tables d’analyse LR pour \expression" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
8.19 Con its LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
8.20 Exemple de conit LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.21 Limitations de la methode SLR(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
8.22 Construction des tables d’analyse LR(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
8.23 Outils de creation des tables LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
8.24 Algorithme d’analyse LR(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.25 Exemple par la methode LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 6 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (6)
8.26 Comparaison entre LL(1) et LR(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.27 Recursion a droite dans les methodes LR(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
8.28 ListaSyntPredictifDescenteRecursive concretement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
9 Analyse semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
9.1 Bases de l’analyse semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
9.2 Collecte d’informations semantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
9.3 Forme syntaxique et semantique associee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
9.4 Limite entre syntaxe et s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
9.5 Semantique de Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
9.6 Inference de type en Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
9.7 Variables logiques pour l’inference de type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
9.8 Realisation de l’inference de type pour Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
9.9 Exemple d’inference de type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
9.10 Description des types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
9.11 des types Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
9.12 Description des constantes autode nies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
9.13 des identi cateurs Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
9.14 Recuperation des types Lista inferes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
9.15 Description des niveaux de declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
9.16 Structure de la table des symboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
9.17 Le cas des langages a structure de blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
9.18 Exemple de table des symboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 7 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (7)
9.19 Point de declaration d’un identi cateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
9.20 Graphes semantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
9.21 s pour Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
9.22 Hierarchie des classes des graphes semantiques Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
9.23 Graphes semantiques et forme post xee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
9.24 Analyse semantique de Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
9.25 Creation des identi cateurs Lista prede nis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
9.26 Description semantique des fonctions Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
9.27 s des parametres formels Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
9.28 Analyse d’une de nition de fonction Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
9.29 Description des appels aux fonctions Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
9.30 Analyse des appels aux fonctions prede nies Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
9.31 des appels auxns utilisateur Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
9.32 Remarque importante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.33 ListaSemPredictifDescenteRecursive concretement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
10 L’outil Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
10.1 Principe de fonctionnement de Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
10.2 Description soumise a Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
10.3 Qui fait quoi avec Bison ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
10.4 Premiere partie d’un chier Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
10.5 Deuxieme partie d’un chier Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
10.6 Troisieme partie d’un chier Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 8 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (8)
10.7 Fonctions a fournir en sus de la speci cation Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
10.8 Mise sous forme post xee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
10.9 Gestion des con its LR par Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
10.10 Exemple de con its "consommer/reduire" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
10.11 de con its "reduire/reduire" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
10.12 Priorites relatives et associativites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
10.13 Gestion des erreurs de syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
10.14 Actions prede nies de Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
10.15 Valeur retournee par les productions Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
10.16 Exemples de valeurs retournees par des productions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
10.17 Interaction entre analyses lexicale et semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
10.18 Une grammaire semantique Bison de Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
10.19 Gestion speci que de la semantique Lista dans Bison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
10.20 ListaSyntFlexBison concretement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
10.21 ListaSemFlexBison concr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
11 Evaluation et parametres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
11.1 Passage de parametres courants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
11.2 Remarques sur les passages de parametres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
11.3 Exemple de passage par nom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
11.4 Strategies d’evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
11.5 Exemple d’ pouvant ne pas se terminer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
11.6 Arbre des appels de fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 9 /580Compilateurs & Interpretes Table des matieres
Liste des gures
Table des matieres (9)
11.7 Evaluation par nom : terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
11.8 paresseuse et passage par besoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
11.9 Inter^et du passage par besoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
11.10 Une autre terminologie pour l’evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
11.11 Fermetures transitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
11.12 Des graphes semantiques a la forme post xee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
11.13 Evaluation directe des graphes semantiques Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
11.14 Contextes d’evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
11.15 Exemple de contextes d’evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
11.16 Evaluations au niveau principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
11.17 Evaluation des graphes semantiques simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
11.18 des iterateurs Lista prede nis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
11.19 Evaluation des arguments d’appel des fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
11.20 des a par valeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
11.21 Evaluation des arguments par nom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
11.22 des a par besoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
11.23 Evaluation des appels de fonction Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
11.24 Passage par nom et e ets de bord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
11.25 Remarque importante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
11.26 ListaSemPredictifDescenteRecursive concretement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
11.27 ListaSemFlexBison concretement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
12 Environnement d’execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
J. Menu Compilateurs & Interpretes 20-09-2011 { Rev. 3 10 /580