Introduction aux Systèmes d’Exploitation

D'après le document Introduction aux Systèmes d’Exploitation

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

Programming, Math, Lexical Analysis, Syntax Analysis, Semantic Analysis · PDF · 3 pages

Afficher l'aperçu du document

Consulter le document original →

Ce document présente une introduction aux systèmes d’exploitation à travers deux exercices pratiques : l’analyse lexicale, syntaxique et sémantique d’un langage de programmation simple, puis l’édition des liens entre modules dans un programme. Il s’adresse aux étudiants en informatique souhaitant comprendre les étapes fondamentales du traitement des programmes et la gestion des modules dans un système.

Analyse lexicale d’un langage simple

Le langage étudié est défini par une grammaire formelle décrivant 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 seule 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 pour séparer les unités lexicales. Chaque instruction doit tenir sur une seule ligne, qui ne contient qu’une instruction.

Exemple d’analyse lexicale

Considérons la ligne :

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

Le découpage en unités lexicales est :

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

Ici, "12" est un nombre entier formé de deux chiffres, ce qui n’est pas conforme à la définition stricte du nombre entier (un seul chiffre). Cela constitue une erreur lexicale. Le nombre réel "3,5" est correct car il correspond à la définition.

Analyse syntaxique

L’analyse syntaxique vérifie que la séquence d’unités lexicales respecte la grammaire. Elle produit un arbre de syntaxe représentant la structure hiérarchique du programme.

Exemple d’arbre de syntaxe pour une instruction

Pour l’instruction :

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

L’arbre de syntaxe peut être schématisé ainsi :

Instruction
- Identificateur : C
- =
- Expression
  - Expression
    - Facteur
      - Terme : 3
    - *
    - Facteur
      - Terme : C
  - +
  - Expression
    - Facteur
      - Terme : 12
    - /
    - Facteur
      - Terme : (Expression)
        
        Expression
        
        Facteur : A
        
        +
        
        Expression : 3

Si une ligne contient des erreurs syntaxiques, comme une instruction incomplète ou mal formée, l’analyseur syntaxique les signale.

Analyse sémantique

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

Tout identificateur utilisé doit avoir été déclaré.
Tout identificateur déclaré doit être utilisé dans une instruction.
Le type des expressions doit correspondre au type de l’identificateur affecté :

Si l’identificateur est de type entier, l’expression doit contenir uniquement des valeurs entières.
Si l’identificateur est de type réel, l’expression doit contenir uniquement des valeurs réelles.

Exemple d’analyse sémantique

Considérons 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

Analyse :

Déclarations : A, C, D sont déclarés ; B est utilisé mais non déclaré → erreur.
Utilisations : A, C, B sont utilisés. D est déclaré mais non utilisé → erreur.
Types : B est affecté avec une expression contenant C (réel), or B n’est pas déclaré, donc erreur. Si B était déclaré entier, affecter une expression réelle serait une erreur.

Les erreurs sémantiques sont donc :

Utilisation de B non déclaré.
Déclaration de D non utilisée.

Édition des liens entre modules

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

Une taille (en octets)
Des liens à satisfaire (fonctions ou procédures externes qu’il utilise)
Des liens utilisables (fonctions ou procédures qu’il fournit aux autres modules)
Une adresse de lancement (pour le module principal)

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 (212), RENDRE (321)	100
GERER_ABONNE	1132	ENVOYER_COURRIER, IMPRIMER_CARTE	CREER_ABONNE (212), RECHERCHER_ABONNE (620), DETRUIRE_ABONNE (1010)
ENTREES_SORTIES	750		ENVOYER_COURRIER (120), IMPRIMER_CARTE (324), EDITER_FACTURE (612)
GERER_FOND	1022		TROUVER_LIVRE (340), TROUVER_DVD (514), CREER_LIVRE (1011)
CAISSE	200	IMPRIMER_FACTURE	PAYER_ABONNEMENT (124)

Calcul des adresses d’implantation

Les modules sont placés en mémoire de façon contiguë à partir de l’adresse de lancement du programme principal, ici 100 (adresse de GERER_ABONNEMENT) :

GERER_ABONNEMENT : adresse 100, taille 410 → occupe 100 à 509
GERER_ABONNE : adresse 510 (100 + 410), taille 1132 → occupe 510 à 1641
ENTREES_SORTIES : adresse 1642 (1641 + 1), taille 750 → occupe 1642 à 2391
GERER_FOND : adresse 2392 (2391 + 1), taille 1022 → occupe 2392 à 3413
CAISSE : adresse 3414 (3413 + 1), taille 200 → occupe 3414 à 3613

Taille totale du programme

Somme des tailles : 410 + 1132 + 750 + 1022 + 200 = 3514 octets

Table des liens

La table des liens associe les références externes aux adresses des modules qui les fournissent :

CREER_ABONNE : adresse 212 (GERER_ABONNE)
RECHERCHER_ABONNE : 620 (GERER_ABONNE)
DETRUIRE_ABONNE : 1010 (GERER_ABONNE)
ENREGISTRER : 212 (GERER_ABONNEMENT)
RENDRE : 321 (GERER_ABONNEMENT)
ENVOYER_COURRIER : 120 (ENTREES_SORTIES)
IMPRIMER_CARTE : 324 (ENTREES_SORTIES)
EDITER_FACTURE : 612 (ENTREES_SORTIES)
TROUVER_LIVRE : 340 (GERER_FOND)
TROUVER_DVD : 514 (GERER_FOND)
CREER_LIVRE : 1011 (GERER_FOND)
PAYER_ABONNEMENT : 124 (CAISSE)

Adresse de lancement du programme

L’adresse de lancement est celle du module principal, ici GERER_ABONNEMENT : 100.

Validité de l’édition des liens

Pour que l’édition des liens soit correcte :

Tous les liens à satisfaire doivent être satisfaits par des liens utilisables dans un autre module.
Les adresses doivent être cohérentes et non chevauchantes.