Chapitre : Analyse Sémantique

Chapitre : Analyse Sémantique 1 / 48

Sommaire I

1 Introduction

2 Tables des symboles

3 Types

4 Inférence de type

5 Polymorphisme

Chapitre : Analyse Sémantique 2 / 48

Sommaire

1 Introduction

2 Tables des symboles

3 Types

4 Inférence de type

5 Polymorphisme

Chapitre : Analyse Sémantique 3 / 48

Introduction à l'analyse sémantique

Dénition
L'analyse sémantique transforme l'entrée syntaxique en une représentation
simpliée adaptée à la génération de code.
Objectifs principaux :
Relier les identicateurs à leurs déclarations
Vérier le respect des règles de portée
Vérier la cohérence des types
Éléments étudiés :
Tables des symboles
Typage des programmes
Grammaires attribuées

Chapitre : Analyse Sémantique 4 / 48

Sommaire

1 Introduction

2 Tables des symboles

Introduction
Portée des identicateurs
Représentation
Représentation des symboles
Schéma de vérication

3 Types

4 Inférence de type

5 Polymorphisme

Chapitre : Analyse Sémantique 5 / 48

Tables des symboles - Introduction

Rôle des tables des symboles

Stocker et de gérer des informations sur les identicateurs (variables,
fonctions, etc.) d'un programme, en servant de structure de données
essentielle pour un compilateur.

Identicateurs : symboles désignant des objets (variables, procédures,

types...)
Deux opérations principales :
Mise à jour : lors des déclarations d'identicateurs
Consultation : lors des utilisations d'identicateurs
Informations stockées :
Type de l'objet
Position pour le calcul d'adresse
Valeur

Chapitre : Analyse Sémantique 6 / 48

Tables des symboles (espaces de noms) multiples
Gestion de plusieurs tables
Langages objets : classes, méthodes
ML : types, modules, valeurs
Résolution des conits par séparation syntaxique

Exemple : Java
Le corps d'une méthode peut utiliser d'autres méthodes de la même
classe qui peuvent être dénies plus loin, ceci nécessite de traiter en
bloc les dénitions de classes.
On peut dénir dans une même classe plusieurs méthodes de même
nom, le type de leurs arguments permet de choisir statiquement la
méthode qui s'applique.
De nombreuses classes peuvent redénir les mêmes méthodes. Si les
classes sont disjointes, cette ambiguïté de nom sera résolue par le
typage.
Chapitre : Analyse Sémantique 7 / 48
Portée des identicateurs

Concept de bloc
Partie délimitée du code où les variables sont utilisables.
Avantages :
Ecacité mémoire
Robustesse du code
Vérications :
Variables déclarées avant utilisation
Variables visibles au moment de l'utilisation

Chapitre : Analyse Sémantique 8 / 48

Règles de portée par langage
C ML
Variables locales ou globales let id = ...
Portée limitée aux procédures Portée restreinte à l'expression
Pascal après in
Déclaration avant utilisation Modules avec noms qualiés
"forward" pour récursivité let rec pour fonctions
mutuelle récursives
Accès aux variables des Java
procédures englobantes Méthodes utilisables dans toute
la classe
Surcharge par type d'arguments
Résolution dynamique avec
super : super est un mot-clé
utilisé pour faire référence à la
classe parente d'une classe lle
Chapitre : Analyse Sémantique 9 / 48
Représentation de la table des symboles

Approches possibles
Table de hachage : Qui à chaque chaîne associe un entier unique.
Cette approche ore une bonne performance, notamment en temps
moyen pour l'insertion et la recherche
Arbre de recherche binaire : Un autre choix courant, qui maintient
les symboles triés et permet des opérations ecaces de recherche et
de maintenance
Recherche linéaire : Moins ecace pour les grandes tables, mais
peut être utilisée pour des cas simple

Gestion de la visibilité : procédures

Ajout de nouveaux identicateurs
Recherche rapide des identicateurs visibles
Retrait des identicateurs en n de bloc
Chapitre : Analyse Sémantique 10 / 48
Exemple d'analyse de portée

Expression ML
let x = (let y = 2 in y*y + 2*y +1) in x+y

Table initiale T

Analyse de let y = 2 T' = T + y :entier
Analyse de y*y + 2*y +1 avec T'
x :entier ajouté à T
Analyse de x+y avec y de T (déclaration antérieure : problème de
portée)

Chapitre : Analyse Sémantique 11 / 48

Implémentation fonctionnelle vs impérative

Approche fonctionnelle Approche impérative

Tables immuables (ne peuvent Tables modiables
pas être modiées après leur Ajout/retrait explicite
création) Plus ecace
Ajout sans modication Gestion explicite de la pile
Plus facile à raisonner
Moins ecace en mémoire

Chapitre : Analyse Sémantique 12 / 48

Code d'analyse de visibilité 1/4

Approche fonctionnelle : code

symbol_table_stack = [ ]

def enter_scope ( ) :
s y m b o l _ t a b l e _ s t a c k . append ( { } )

def exit_scope ( ) :
s y m b o l _ t a b l e _ s t a c k . pop ( )

d e f d e c l a r e ( name , v a l u e ) :
s y m b o l _ t a b l e _ s t a c k [ = 1 ] [ name ] = v a l u e

d e f l o o k u p ( name ) :
f o r t a b l e in r e v e r s e d ( symbol_table_stack ) :
i f name i n t a b l e :
r e t u r n t a b l e [ name ]
r a i s e NameError ( f " U n d e f i n e d s y m b o l : {name}" )

Chapitre : Analyse Sémantique 13 / 48

Code d'analyse de visibilité 2/4

Approche fonctionnelle : execution

enter_scope ()
d e c l a r e ( "x" , 1)

enter_scope ()
d e c l a r e ( "y" , 2)
p r i n t ( lookup ("x" )) # 1 ( t r o u v e e dans l a p o r t e e x t e r n e )
p r i n t ( lookup ("y" )) # 2 ( portee locale )
exit_scope ()

p r i n t ( lookup ("x" )) # 1 ( toujours accessible )

p r i n t ( lookup ("y" )) # erreur : 'y ' n existe plus

Chapitre : Analyse Sémantique 14 / 48

Code d'analyse de visibilité 3/4

Approche fonctionnelle : code

type env = ( s t r i n g * i n t ) l i s t

l e t empty_env = [ ]

l e t e x t e n d name v a l u e env =
( name , v a l u e ) : : env

l e t r e c l o o k u p name env =
match env with
| [ ] => f a i l w i t h ( " U n d e f i n e d s y m b o l : " ^ name )
| ( n , v ) : : r e s t =>
i f n = name then v e l s e l o o k u p name r e s t

Chapitre : Analyse Sémantique 15 / 48

Code d'analyse de visibilité 4/4

Approche fonctionnelle : exécution

l e t g l o b a l = e x t e n d " x " 1 empty_env
l e t l o c a l = extend "y" 2 g l o b a l

lookup "x" l o c a l (* 1 *)
lookup "y" l o c a l (* 2 *)

( * Enq u i t t a n t l a p o r t e e *)
let after_block = global
lookup "x" a f t e r _ b l o c k (* 1 *)
lookup "y" a f t e r _ b l o c k (* E r r e u r *)

Chapitre : Analyse Sémantique 16 / 48

Tables de hachage avec chaînage

Les tables de hachage avec chaînage : chaque case (ou "bucket") de la

table contient une liste chaînée pour gérer les collisions. Lorsque plusieurs
clés sont hachées au même indice, elles sont ajoutées à la liste chaînée
associée à cet emplacement. Ajout de nombre illimité d'éléments : bien que
la performance puisse se dégrader si les listes deviennent trop longue

Avantages pour les tables de symboles

Gestion naturelle du masquage
Ajout/suppression en pile
Ecacité des opérations

Gestion des blocs

Pile des blocs ouverts
Liste des identicateurs par bloc
Retrait groupé en n de bloc
Chapitre : Analyse Sémantique 17 / 48
Optimisation des symboles

Représentation par entiers

Conversion des chaînes en entiers uniques
Comparaisons plus rapides
Table de hachage inverse pour correspondance

Attention
L'optimisation ne doit pas apporter de surcoût de gestion.

Chapitre : Analyse Sémantique 18 / 48

Schéma de vérication de portée

Processus
1 Entrée : arbre de syntaxe abstraite avec noms

2 Création de table des déclarations

3 Remplacement des utilisations par index

4 Table visible : associations nom 

index

Représentation impérative
Table des symboles visibles
Pile pour structure des blocs
Gestion explicite des entrées/sorties de blocs

Chapitre : Analyse Sémantique 19 / 48

Sommaire

1 Introduction

2 Tables des symboles

3 Types
Types et relations de typage
Types et constructeurs
Égalité sur les types
Surcharge d'opérateurs

4 Inférence de type

5 Polymorphisme

Chapitre : Analyse Sémantique 20 / 48

Dénitions des types

Concept
Les types sont des expressions qui classient les objets du langage.

Exemples : int, bool, oat...

Relation de typage : e : τ (e à le type τ )
Environnement : e = f (x1 , x2 , . . . xn ) ⇒ x1 : τ1 , . . . , xn : τn ⊢ e : τ

Chapitre : Analyse Sémantique 21 / 48

Règles d'inférence de type

Système de règles

x1 : τ1 , . . . , xn : τn ⊢ xi : τi
Γ ⊢ e1 : int Γ ⊢ e2 : int
Γ ⊢ e1 + e2 : int

Prol des fonctions

σ1 × . . . × σp → τ

Γ ⊢ e1 : σ1 . . . Γ ⊢ ep : σp
Γ ⊢ f (e1 , . . . , ep ) : τ

Chapitre : Analyse Sémantique 22 / 48

Utilité des types

Avantages
Détection précoce : erreurs à la compilation
Résolution d'ambiguïtés : opérations surchargées
Allocation mémoire : taille des objets
Documentation : intention du programmeur

Chapitre : Analyse Sémantique 23 / 48

Classication des systèmes de typage

Statique vs Explicite vs Implicite Monomorphe vs

Dynamique Explicite : Polymorphe
Statique : annotations de type Monomorphe : un
vérication à la Implicite : inférence type par expression
compilation automatique Polymorphe :
Dynamique : plusieurs types
vérication à possibles
l'exécution

Chapitre : Analyse Sémantique 24 / 48

Polymorphisme

Formes de polymorphisme
Ad-hoc : même syntaxe, sémantique diérente
Exemple : + sur entiers et ottants
Paramétrique : même code, types diérents
Exemple : quicksort sur entiers et chaînes
Héritage : méthodes redénies dans sous-classes

Type principal
τ type principal de e dans Γ si :

Γ⊢e:σ⇔τ ≤σ

Chapitre : Analyse Sémantique 25 / 48

Propriétés attendues

Caractéristiques souhaitables
Décidabilité : vérication algorithmique
Inférence : détermination automatique des types
Ecacité : temps et espace raisonnables
Validité : absence d'erreurs à l'exécution

Limitations
Impossible de vérier par typage :
Appartenance d'un indice au domaine d'un tableau
Terminaison d'une fonction

Chapitre : Analyse Sémantique 26 / 48

Constructeurs de type

Types structurés
Produit : τ1 × τ2
Record : {lab1 : τ1 , . . . , labn : τn }
Tableau : array [n, τ ]
Statique : taille connue à la compilation
Dynamique : taille connue à l'exécution
Pointeur : ↑ τ

Chapitre : Analyse Sémantique 27 / 48

Égalité et nommage des types

Problèmes d'égalité
Tests d'égalité fréquents lors du typage
Représentation approchée pour ecacité (on ignorera par exemple le
domaine des tableaux)
Égalité structurelle vs nominale : deux types sont égaux s'ils ont la
même structure interne (même composition), peu importe le nom. Et
deux types sont considérés égaux seulement s'ils portent le même nom,

Nommage
Abréviations pour expressions de type complexes
Égalité des noms vs égalité structurelle
Types récursifs représentés par graphes

Chapitre : Analyse Sémantique 28 / 48

Règle d'équivalence

Γ⊢e:τ τ ≡σ
Γ⊢e:σ

Application
Vérication de l'équivalence lors de l'application de fonctions
Adaptation des types d'arguments aux types attendus

Chapitre : Analyse Sémantique 29 / 48

Surcharge d'opérateurs

Dénition
Une expression est surchargée si elle peut correspondre à plusieurs objets.

Une expression est surchargée, si à un moment donné cette expression peut

correspondre à plusieurs objets. On parle d'opérateurs surchargés (pour les
opérateurs arithmétiques par exemple), mais une constante peut être
également surchargée, par exemple le symbole 4 peut représenter un entier
ou bien un ottant.
Exemples : opérateurs arithmétiques, constantes
Rejetée dans certains langages (ML) pour simplicité
Autorisée dans d'autres (Ada, java) avec résolution statique

Chapitre : Analyse Sémantique 30 / 48

Surcharge à la manière Ada

Principe
Identicateur ou constante = ensemble ni d'objets visibles
Expression bien typée si aectation unique possible : si on sait associer
à chaque constante ou identicateur un objet unique telle que
l'expression ainsi interprétée soit correctement typée
Résolution par information de type ; ce qui interdit a priori que le
même identicateur soit associé à deux objets distincts de même type

Prol d'opérateur
τ1 × · · · × τn → τ
τi : type du i-ème argument (domaine)
τ : type du résultat (image)
n : arité du prol

Chapitre : Analyse Sémantique 31 / 48

Algorithme de résolution Ada

1 Phase ascendante : calcul des types possibles pour chaque

sous-expression
2 Phase descendante : assignation de types uniques
3 Vérication : prol unique pour chaque opérateur
Condition de succès
Type unique au sommet de l'expression
Type unique pour chaque sous-expression
Prol unique pour chaque opérateur ( τ1 × · · · × τn → τ )

Chapitre : Analyse Sémantique 32 / 48

Exemple de surcharge

Expression
(1 + 4) + 3.2

+ : int × int → int , float × float → float

1,4 : types int et oat
(1+4) : types int ou oat
3.2 : type oat
Résultat : type oat
Conversion implicite des entiers en ottants

Chapitre : Analyse Sémantique 33 / 48

Surcharge à la manière Java
Dans Java, pour résoudre statiquement les problèmes de surcharge, on ne
regarde que les types des arguments et pas le contexte dans lequel ils sont
utilisés. Par contre il faut prendre en compte le sous-typage entre classes.
Ainsi lorsqu'une méthode m est appliquée à un objet de classe A avec des
paramètres e1 , ‘ . . . , en en de types A1 , . . . , An , on cherche parmi toutes les
dénitions possibles de méthodes m à n-arguments dans les sur-classes de
A s'il en existe exactement une plus petite qui s'applique au prol des
arguments et de l'objet.
Spécicités
Résolution basée uniquement sur les types des arguments -Prise en compte
du sous-typage entre classes- Recherche de la méthode la plus spécique
applicable

Processus
1-Recherche dans les sur-classes 2- Sélection de la plus petite méthode
applicable 3- Résolution statique
Chapitre : Analyse Sémantique 34 / 48
Sommaire

1 Introduction

2 Tables des symboles

3 Types

4 Inférence de type
Langage pour l'inférence de type
Schémas de type (ou Inférence de type)
Unication
Algorithme d'inférence

5 Polymorphisme

Chapitre : Analyse Sémantique 35 / 48

Langage pour l'inférence de type

Éléments du langage
Constantes : type donné (notées c )
Opérateurs primitifs : type donné (opérations arithmétiques par
exemple)
Identicateurs : x = e (e= Expression)
Fonctions utilisateur : f (x1 , . . . , xn ) = e
Fonctions récursives : rec f (x1 , . . . , xn ) = e

Types
Types de base : τ
Types fonction : τ1 × . . . × τn → τ

Chapitre : Analyse Sémantique 36 / 48

Programme bien formé
On vérie qu'un programme est bien formé et on lui associe un
environnement qui est une suite d'association de types à des identicateurs
x1 : τ1 , . . . , xn : τn .
Construction d'environnement
Le programme composé d'aucunes déclarations correspond à un
environnement vide.
Si un programme p est bien formé et correspond à un environnement
Γ:
si Γ ⊢ e : τ alors le programme composé de p et de x = e est bien
formé et correspond à l'environnement Γ, x : τ ;
si Γ, x1 : τ1 , . . . , xn : τn ⊢ e : τ alors le programme composé de
Γ, f (x1 , . . . , xn ) = e est bien formé et correspond à l'environnement
Γ, f : τ1 × . . . × τn → τ ;
si Γ, f : τ1 × . . . × τn → τ, x1 : τ1 , . . . , xn : τn ⊢ e : τ alors le programme
composé de Γ, rec f (x1 , . . . , xn ) = e est bien formé et correspond à
l'environnement Γ, f : τ1 × . . . × τn → τ .
Chapitre : Analyse Sémantique 37 / 48
Schémas de Type

Un schéma de type est une expression qui peut contenir des variables
de type et éventuellement des quanticateurs, représentant une famille
de types possibles plutôt qu'un type spécique.
Objectif : vérier qu'un programme est bien formé et de calculer
l'environnement associé.
On introduit une notion de schéma de type, qui est construit comme
les types du langage mais avec une notion supplémentaire : les
variables de type notées α, β .
On peut substituer à une variable α dans un schéma de type σ un
schéma de type σ ′ , obtenant ainsi une instance de σ .
Un type est un cas particulier de schéma de type sans variables.
Un schéma de type avec variables représente un ensemble de types
obtenus par substitution.
Exemple : array[τ ] est une instance de array[α].
Chapitre : Analyse Sémantique 38 / 48
Problème d'inférence contraint

On se pose maintenant un problème plus général que celui de l'inférence de

type qui est :
Formulation générale
étant donnés des schémas de type σ1 , . . . , σn et σ , existe-t-il une
substitution ρ de types pour les variables de type, tels que si τi = ρ(σi ) et
τ = ρ(σ) alors x1 : τ1 , . . . , xn : τn ⊢ e : τ .
On dit alors que ρ est une solution au problème d'inférence contraint par
σ1 , . . . , σn et σ .
Soit σ1 , . . . , σn et σ des schémas de type, on notera
x1 : σ1 , . . . , xn : σn ⊢ e : σ si toute substitution ρ est une solution au
problème d'inférence donné par σ1 , . . . , σn et σ .

Notation
x1 : σ1 , . . . , xn : σn ⊢ e : σ si toute substitution ρ est une solution.

Chapitre : Analyse Sémantique 39 / 48

Unication

Dénition
Deux expressions contenant des variable a et b sont uniables s'il existe
une substitution ρ des variables par des termes tels que ρ(a) = ρ(b) et que
lorsqu'il existe un unicateur, il existe un unicateur principal c'est-à-dire
ρ0 tel que ρ0 (a) = ρ0 (b) et si ρ(a) = ρ(b) alors il existe un unicateur ρ′
tel que ρ = ρ′ ◦ ρ0 .

Unicateur principal
ρ0 tel que ρ0 (a) = ρ0 (b)
Pour tout ρ avec ρ(a) = ρ(b), il existe ρ′ tq : ρ = ρ′ ◦ ρ0

Chapitre : Analyse Sémantique 40 / 48

Exercice d'unication

Décrire l'ensemble des unicateurs des couples de termes suivants :

int et α
int et bool
α et β
α et array[β]

Chapitre : Analyse Sémantique 41 / 48

Algorithme d'inférence contraint
Pour résoudre le problème d'inférence contraint pour σ1 , . . . , σn et σ , on
calcule une substitution de schémas de types aux variables de types, telle
que x1 : ρ(σ1 ), . . . , xn : ρ(σn ) ⊢ e : ρ(σ).
On cherche une solution principale, c'est-à-dire que toute autre solution est
une instance de celle-ci.
On se donne donc un environnement qui associe un schéma de type σi à
chaque variable xi , une expression e et un schéma de type σ . On construit
la substitution ρ par récurrence sur la structure de e .
Approche récursive : Construction de ρ par structure de e :
Variable xi : unication de σi et σ
Constante : ltrage de σ avec type connu
Application : appels récursifs sur arguments + unication du résultat
Fonction : nouvelles variables de type + inférence sur le corps
Récursion : ajout du prol de fonction à l'environnement
Chapitre : Analyse Sémantique 42 / 48
Détails de l'algorithme

Si e est la variable xi alors la substitution cherchée est l'unicateur

principal de σi et σ car les substitutions ρ cherchées sont exactement
celles qui vérient ρ(σi ) = ρ(σ). L'inférence échoue si σi et σ ne sont
pas uniables.
Si e est une constante de type τ alors on cherche une substitution ρ
telle que ρ(σ) = τ qui est un cas particulier d'unication dans lequel
un des membres ne contient pas de variables, appelé problème de
ltrage.
Dans le cas d'un appel de fonction f (e1 , . . . , en ) on regarde le prol de
la fonction qui est τ1 × . . . × τn → τ , on appelle récursivement
l'inférence sur :
Inférence sur e1 avec type τ1 
ρ
ρ1
Inférence sur e2 avec environnement ρ1 (Γ) 2

ρ
...
Inférence sur en n

Chapitre : Analyse Sémantique 43 / 48

Détails de l'algorithme

On compare alors ρn (. . . (ρ1 (σ)), . . .) avec le type attendu τ de la

fonction, s'il existe une substitution ρ telle que
ρ(ρn (. . . (ρ1 (σ)), . . .)) = τ alors la substitution résultat est
ρn ◦ ρn−1 ◦ . . . ρ1 .
inférence des prols des fonctions : Si la fonction est dénie par
f (x1 , . . . , xn ) = e , on introduit de nouvelles variables de type
α1 , . . . , αn pour chaque variable xi et α pour le résultat, puis on
applique l'algorithme d'inférence de type à e . La substitution résultat
nous fournit le type des xi et du résultat.
Pour une fonction récursive on introduit une nouvelle règle
f : α1 × . . . × αn → α.
La solution à l'inférence de type est unique si la substitution résultat ρ est
telle que ρ(σi ) et ρ(σ) sont des types (pas de variables de type).

Chapitre : Analyse Sémantique 44 / 48

Exemple d'inférence

f(x) = x
g(x,y) = y or f(x) > 3

Chapitre : Analyse Sémantique 45 / 48

Sommaire

1 Introduction

2 Tables des symboles

3 Types

4 Inférence de type

5 Polymorphisme

Chapitre : Analyse Sémantique 46 / 48

Polymorphisme avec schémas de type

Extension de l'approche
Association d'un schéma de type unique à chaque expression
Représentation d'une famille de types
Adaptation de l'algorithme d'inférence

Exemple
Fonction identité : f (x) = x
Type : τ → τ pour tout τ
Schéma de type : α → α

Chapitre : Analyse Sémantique 47 / 48

Avantages du polymorphisme

Flexibilité
Réutilisation du code avec diérents types
Abstraction des détails d'implémentation
Expressivité accrue du langage

Sécurité maintenue
Vérication statique préservée
Absence d'erreurs à l'exécution garantie
Meilleure détection des erreurs

Chapitre : Analyse Sémantique 48 / 48