Ecole Nationale des Sciences
de l'Informatique
Introduction aux Systèmes d’Exploitation
M. SELLAMI
TD : Chaine de production de programmes
Exercice 1 : Compilation
Soit le langage suivant :
<programme> ::= PROGRAM <identificateur> <suite de phrases> FIN
<suite de phrases> ::= <phrase> | <phrase><suite de phrases>
<phrase> ::= <déclaration> ; | <instruction> ;
<déclaration> ::= <identificateur> : <type>
<type>::= réel | entier
<instruction> ::= <identificateur> = <expression>
<expression> ::= <facteur> { + | - } <expression> | <facteur>
<facteur> ::= <terme> { * | / } <facteur> | <terme>
<terme> ::= <identificateur> | <nombre> | ( <expression> )
<nombre> ::= <nombre entier> | <nombre réel>
De ces règles, on peut déduire qu’un tel langage contient déjà les unités lexicales
suivantes:
= + - * / ( ) réel entier PROGRAM FIN ; :
De plus, les identificateurs sont des unités lexicales constituées d’une lettre. Les nombres entiers sont des
unités lexicales constituées d’un chiffre et les nombres réels sont des unités lexicales constituées de deux
chiffres séparés par une virgule. Ceci peut donc se décrire comme suit:
<nombre entier> ::= <chiffre>
<nombre réel> ::= <chiffre> , <chiffre>
<identificateur> ::= <lettre>
<chiffre> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<lettre> ::= A | B ... | Z
L'espace (blanc) est sans signification, mais ne peut se trouver à l’intérieur
d’une unité lexicale.
Les espaces ne peuvent se trouver à l'intérieur d'une unité lexicale, et n'ont pas de signification. Une
instruction doit se trouver toute entière sur une même ligne, et une ligne ne peut contenir qu'une seule
instruction.
1. On s'intéresse d’abord à l'analyse lexicale. Présentez le découpage en unités lexicales en enfermant
celles-ci dans des rectangles. Donner le résultat fourni par l'analyseur lexical pour les lignes
suivantes, en justifiant votre raisonnement. Signalez les éventuelles erreurs lexicales.
PROGRAM X
A : entier $ ereur
C : réel ;
C = 3 * C + 1 2 / ( A + 3 ) ;
C = 3,5 + C * 2 ;
D : entier ;
b = 3 * C 1
erreur
FIN
2. Donner le résultat de l’analyse syntaxique sur les 4 lignes suivantes, en justifiant votre raisonnement.
C = 3 * C + 2 / (A + 3);
C = 3,5 + C * 2 ;
D : entier ;
B = 3 * C 1
On exprimera cette analyse sous la forme d’arbres de syntaxe.
Solution
phrase
Instruction ;
Idetificateur
=
expression
C
facteur
+
facteur
terme
nombre
*
terme
Publicité
/
facteur
identific
terme
terme
Nombre entier
C
3
2
(
expression
)
facteur
terme
+
facteur
terme
Identificat.
nombre
A
nombre entier
3
3. Analyse sémantique.
L'analyse sémantique doit vérifier pour notre langage, les règles suivantes :
• Tout identificateur, utilisé dans une instruction, doit être déclaré.
• Tout identificateur déclaré doit être utilisé dans une instruction ;
• Dans une instruction, si l'identificateur à gauche de "=" est déclaré de type "entier" alors l’expression à
droite ne doit comporter que des valeurs entières. De même, si l'identificateur à gauche de "=" est déclaré de
type "réel" alors alors l’expression à droite ne doit comporter que des valeurs réelles.
.
votre réponse.
• Quelles sont les erreurs signalées par l'analyse sémantique pour notre programme corrigé ? Justifiez
Solution
PROGRAM X
A : entier ;
C : réel ;
C = 3 * C + 12 / (A + 3) ;
C = 3,5 + C * 2 ;
D : entier ;
B = 3 * C ;
FIN
Exercice 2 : Edition des liens
Type incompatible
D : Déclaré mais non utilisé
B : Non déclaré
On dispose d'un ensemble de modules définis comme suit:
module GERER_ABONNEMENT taille 410
liens à satisfaire CREER_ABONNE
RECHERCHER_ABONNE
PAYER_ABONNEMENT
TROUVER_LIVRE
TROUVER_DVD
liens utilisables ENREGISTRER 212
RENDRE 321
adresse de lancement 100
module GERER_ABONNE taille 1132
liens utilisables CREER_ABONNE 212
RECHERCHER_ABONNE 620
DETRUIRE_ABONNE 1010
liens à satisfaire ENVOYER_COURRIER
IMPRIMER_CARTE
module ENTREES_SORTIES taille 750
liens utilisables ENVOYER_COURRIER 120
IMPRIMER_CARTE 324
EDITER_FACTURE 612
Publicité
module GERER_FOND
taille 1022
liens utilisables TROUVER_LIVRE 340
TROUVER_DVD 514
CREER_LIVRE 1011
module CAISSE taille 200
liens utilisables PAYER_ABONNEMENT 124
liens à satisfaire IMPRIMER_FACTURE
On effectue l'édition de liens de tous ces modules. Donnez en justifiant brièvement votre réponse:
.
.
.
.
• les adresses d'implantation de ces modules,
• la taille totale du programme résultant,
• la table des liens,
• l'adresse de lancement du programme résultant.
L’édition des liens est-elle correcte ? Justifiez votre réponse.
Solution de l’exercice 2
L'adresse d'implantation d'un module est 0 pour le premier, et pour les autres, le premier emplacement laissé
libre par le module qui le précède, c'est-à-dire, la somme entre son adresse d'implantation et sa taille:
GERER_ABONNEMENT 0
GERER_ABONNE
ENTREES_SORTIES
GERER_FOND
CAISSE
0+410=410
410+1132=1542
410+1132+750=2292
410+1132+750+1022=3314
taille totale 3314 + 200= 3514
La taille totale du programme est la somme des tailles de tous les modules, ou encore l'adresse du premier
emplacement laissé libre par le dernier module, c'est-à-dire, la somme entre son adresse d'implantation et sa
taille, soit 3514
La table des liens (table globale des identificateurs externes) contient tous les identificateurs présents dans les modules, en
tant que lien utilisable ou lien à satisfaire, ainsi que éventuellement les noms des modules (nous ne les mettrons pas
ici). De plus, la table associe à tout identificateur rencontré comme lien utilisable dans un module, leur adresse dans le
programme, obtenue en ajoutant à leur adresse dans ce module l'adresse d'implantation du module.
Après prise en compte du module GERER_ABONNEMENT
las CREER_ABONNE
las RECHERCHER_ABONNE
las PAYER_ABONNEMENT
las TROUVER_LIVRE
las TROUVER_DVD
lu ENREGISTRER
lu RENDRE
0+212
0+321
410+212
Après prise en compte du module GERER_ABONNE
las CREER_ABONNE
las RECHERCHER_ABONNE 410+620
las PAYER_ABONNEMENT
las TROUVER_LIVRE
las TROUVER_DVD
lu ENREGISTRER
lu RENDRE
lu DETRUIRE_ABONNE 410+1010
0+212
0+321
las ENVOYER_COURRIER
las IMPRIMER_CARTE
410+212
Après prise en compte du module ENTREES_SORTIES
las CREER_ABONNE
Publicité
las RECHERCHER_ABONNE 410+620
las PAYER_ABONNEMENT
las TROUVER_LIVRE
las TROUVER_DVD
lu ENREGISTRER
lu RENDRE
lu DETRUIRE_ABONNE 410+1010
las ENVOYER_COURRIER
las IMPRIMER_CARTE
lu EDITER_FACTURE 1547+612
1547+120
1547+324
0+212
0+321
Après prise en compte du module GERER_FOND
las CREER_ABONNE
las RECHERCHER_ABONNE 410+620
410+212
las PAYER_ABONNEMENT
las TROUVER_LIVRE 2297+340
2297+514
las TROUVER_DVD
0+212
lu ENREGISTRER
lu RENDRE
0+321
lu DETRUIRE_ABONNE 410+1010
las ENVOYER_COURRIER
las IMPRIMER_CARTE
lu EDITER_FACTURE
lu CREER_LIVRE
1547+120
1547+324
1547+612
1547+1011
410+212
3319+124
Après prise en compte du module CAISSE
las CREER_ABONNE
las RECHERCHER_ABONNE 410+620
las PAYER_ABONNEMENT
las TROUVER_LIVRE 2297+340
2297+514
las TROUVER_DVD
0+212
lu ENREGISTRER
0+321
lu RENDRE
lu DETRUIRE_ABONNE 410+1010
las ENVOYER_COURRIER
las IMPRIMER_CARTE
lu EDITER_FACTURE
lu CREER_LIVRE
lu PAYER_ABONNEMENT
lus IMPRIMER_FACTURE
1547+120
1547+324
1547+612
1547+1011
3319+124
L'adresse de lancement est la valeur trouvée dans l'un des modules augmentée de l'adresse d'implantation de
ce module: 0 + 100 = 100.
L’édition des liens n’est pas correcte. La table des liens reste incomplète, le lien ou la référence
IMPRIMER_FACTURE n’est pas résolue.