Introduction aux Systèmes d’Exploitation

Ce document présente une introduction aux systèmes d’exploitation, destinée aux étudiants en informatique. Il couvre les notions fondamentales de la chaîne de production de programmes, notamment l’analyse lexicale, syntaxique et sémantique d’un langage simple, ainsi que l’édition des liens entre modules dans un programme.

Analyse lexicale d’un langage simple

Le langage étudié est défini par une grammaire formelle qui décrit la structure d’un programme :

<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>

Les unités lexicales (tokens) reconnues sont :

• = + - * / ( ) réel entier PROGRAM FIN ; :
• Identificateurs : une lettre (A à Z)
• Nombres entiers : un chiffre (1 à 9)
• Nombres réels : deux chiffres séparés par une virgule (ex. 3,5)

Les espaces sont ignorés sauf à l’intérieur des unités lexicales où ils sont interdits. Chaque instruction doit être sur une seule ligne.

Exemple d’analyse lexicale

Pour la ligne suivante :

PROGRAM X

Le découpage en unités lexicales est :

• PROGRAM
• X (identificateur)

Pour la ligne :

A : entier $ ereur

On identifie :

• A (identificateur)
• :
• entier
• $ (caractère non reconnu, erreur lexicale)
• ereur (non reconnu comme unité lexicale)

Cette ligne contient donc une erreur lexicale due au symbole "$".

Analyse syntaxique

L’analyse syntaxique vérifie que la suite des unités lexicales forme des phrases conformes à la grammaire. Chaque phrase est soit une déclaration, soit une instruction, suivie d’un point-virgule.

Exemple d’arbre syntaxique pour une instruction

Considérons l’instruction :

C = 3 * C + 2 / (A + 3);

L’arbre syntaxique correspondant est :

phrase
 └─ Instruction ;
    ├─ Identificateur : C
    ├─ =
    └─ expression
       ├─ facteur
       │  ├─ terme : nombre entier 3
       │  └─ *
       │  └─ facteur : terme identificateur C
       ├─ +
       └─ expression
          ├─ facteur
          │  ├─ terme : nombre entier 2
          │  └─ /
          │  └─ facteur
          │     └─ terme : ( expression )
          │        └─ expression
          │           ├─ facteur : terme identificateur A
          │           ├─ +
          │           └─ expression : facteur terme nombre entier 3

Cette structure montre la hiérarchie des opérations et la conformité à la grammaire.

Analyse sémantique

L’analyse sémantique vérifie la cohérence des déclarations et des utilisations des identificateurs :

• Tout identificateur utilisé doit être déclaré.
• Tout identificateur déclaré doit être utilisé.
• Les types doivent être respectés : si un identificateur est déclaré entier, l’expression assignée doit être entière ; si réel, l’expression doit être réelle.

Exemple d’erreurs sémantiques

Pour le programme corrigé :

PROGRAM X
A : entier ;
C : réel ;
C = 3 * C + 12 / (A + 3) ;
C = 3,5 + C * 2 ;
D : entier ;
B = 3 * C ;
FIN

• Type incompatible : L’instruction B = 3 * C ; est incorrecte car B n’est pas déclaré.
• Déclaré mais non utilisé : L’identificateur D est déclaré mais jamais utilisé.

Édition des liens entre modules

Un programme peut être composé de plusieurs modules, chacun ayant :

• Une taille (en octets)
• Des liens à satisfaire (références externes à résoudre)
• Des liens utilisables (fonctions ou variables exportées)
• Une adresse de lancement (point d’entrée)

Les modules étudiés sont :

Module	Taille	Liens à satisfaire	Liens utilisables	Adresse de lancement
GERER_ABONNEMENT	410	CREER_ABONNE, RECHERCHER_ABONNE, PAYER_ABONNEMENT, TROUVER_LIVRE, TROUVER_DVD	ENREGISTRER, RENDRE	100
GERER_ABONNE	1132	ENVOYER_COURRIER, IMPRIMER_CARTE	CREER_ABONNE, RECHERCHER_ABONNE, DETRUIRE_ABONNE
ENTREES_SORTIES	750		ENVOYER_COURRIER, IMPRIMER_CARTE, EDITER_FACTURE
GERER_FOND	1022		TROUVER_LIVRE, TROUVER_DVD, CREER_LIVRE
CAISSE	200	IMPRIMER_FACTURE	PAYER_ABONNEMENT

Calcul des adresses d’implantation

L’adresse d’implantation du premier module est 0. Pour chaque module suivant, l’adresse est la somme de l’adresse d’implantation et de la taille du module précédent :

• GERER_ABONNEMENT : 0
• GERER_ABONNE : 0 + 410 = 410
• ENTREES_SORTIES : 410 + 1132 = 1542
• GERER_FOND : 1542 + 750 = 2292
• CAISSE : 2292 + 1022 = 3314

La taille totale du programme est :

3314 + 200 = 3514

Table des liens

La table des liens associe chaque identificateur externe à son adresse dans le programme, calculée en ajoutant l’adresse d’implantation du module à l’adresse locale de l’identificateur.

Par exemple, après prise en compte du module GERER_ABONNEMENT :

• CREER_ABONNE : 0 + 212 = 212
• RECHERCHER_ABONNE : 0 + 321 = 321
• PAYER_ABONNEMENT : 410 + 212 = 622 (après ajout du module GERER_ABONNE)
• ... et ainsi de suite pour les autres identificateurs.

Adresse de lancement

L’adresse de lancement du programme est l’adresse de lancement du module GERER_ABONNEMENT augmentée de son adresse d’implantation :

0 + 100 = 100

Correction de l’édition des liens

L’édition des liens n’est pas correcte car le lien IMPRIMER_FACTURE demandé par le module CAISSE n’est pas résolu dans la table des liens. Cela signifie qu’il manque une définition ou une correspondance pour ce symbole dans les modules disponibles.

Glossaire des termes clés

• Analyse lexicale : Processus de découpage du texte source en unités lexicales (tokens) élémentaires.
• Analyse syntaxique : Vérification que la séquence de tokens respecte la grammaire du langage, souvent représentée par un arbre syntaxique.
• Analyse sémantique : Vérification de la cohérence des déclarations et des utilisations des identificateurs, notamment les types et la déclaration préalable.
• Unité lexicale (token) : Élément minimal du langage reconnu par l’analyse lexicale (ex. identificateur, opérateur, nombre).
• Module : Partie d’un programme, avec sa propre taille, ses liens à satisfaire (références externes) et ses liens utilisables (exportations).
• Édition des liens : Processus de résolution des références externes entre modules pour former un programme exécutable.
• Adresse d’implantation : Adresse mémoire où un module est chargé dans le programme final.
• Table des liens : Table associant les identificateurs externes à leurs adresses dans le programme final.

Points clés à retenir

• La chaîne de production d’un programme comprend l’analyse lexicale, syntaxique et sémantique.
• Chaque unité lexicale doit être clairement identifiée sans espaces internes.
• L’analyse syntaxique produit un arbre qui reflète la structure hiérarchique des instructions.
• L’analyse sémantique garantit la cohérence des types et la déclaration préalable des identificateurs.
• En édition des liens, chaque module est implanté à une adresse calculée en fonction des modules précédents.
• La table des liens permet de résoudre les références externes entre modules.
• Une édition des liens incorrecte se manifeste par des références non résolues, empêchant l’exécution correcte du programme.