Théorie des Langages et Compilation

(TLC)
Fabrice Lamarche
[email protected]
ESIR

1
 Historique
• 1946 : Création de l’ENIAC (Electronic Numerical Integrator and Computer)
– P. Eckert et J. Marchly

• Quelques chiffres
– 17468 tubes à vide
– 7200 diodes
– 1500 relais
– 70000 résistances
– 10000 condensateurs
– 30 tonnes
– Occupe une surface de 67m2
– Consomme 150 Kilowatts

• Performances
– Horloge à 100KHz
– 5000 additions / seconde
– 330 multiplications / seconde
– 38 divisions / seconde

2
 Historique
• ENIAC
– 30 Unités autonomes
• 20 accumulateurs 10 digits
• 1 multiplicateur
• 1 Master program capable de gérer des boucles

– Mode de programmation
• Switchs
• Câblage des unités entre elles 

3
 Historique
• Ceci est un programme sur l’ENIAC…

Une cause fréquente de panne

était la combustion d’un insecte
sur un tube chaud.

Naissance du mot BUG 

4
 Historique
• 1950 : Invention de l’assembleur par Maurice
V. Wilkes de l’université de Cambridge
– Avant : programmation en binaire

• 1951 : Grace Hopper crée le premier

compilateur pour UNIVAC 1 : le A-O system.
– Permet de générer un programme binaire à
partir d’un « code source »

• 1957 : Grace Hopper travaille chez IBM

• défend l’idée qu’un programme devrait pouvoir être écrit
dans un langage proche de l’Anglais

• 1959 : Grace Hopper crée le langage COBOL

5
 Historique
1950
Fortran, COBOL, Lisp
1960
Basic, Logo, Apl, Pl/1
1970
Pascal, Prolog, SmallTalk, C, Awk, Ada, Rexx
1980
Dbase, C++, Eiffel, Perl, Tcl/Tk, Mathematica, Maple
1990
Java, Javascript, Php, Mysql, VisualBasic
2000
Java 2, Php 4.3.3, Perl 5.8.1, C#
2010

6
 Les langages de programmation
• Langages de programmation compilés
– Génération de code exécutable i.e. en langage machine
– Ex : C / C++
• Les langages de programmation interprétés
– Un langage interprété est converti en instructions exécutables par la machine
au moment de son exécution
– Ex : PHP, Javascript, Ruby
• Les langages P-code
– Langages à mi-chemin entre l’interprétation et la compilation
– Java
• La phase de compilation génère du « byte code »
• Le « byte code » est interprété par une machine virtuelle lors de l ’exécution
– Exécution plus rapide que les langages interprétés
– Exécution plus lente que les langages compilés
– Machine virtuelle pour chaque processeur => portabilité du code compilé

7
 Catégories de langages de
programmation
• Programmation impérative
– la programmation impérative est un paradigme de programmation qui décrit
les opérations en termes de séquences d'instructions exécutées par
l'ordinateur pour modifier l'état du programme.
– Programmation procédurale
• Paradigme de programmation basé sur le concept d'appel procédural. Une
procédure, aussi appelée routine, sous-routine ou fonction contient simplement
une série d'étapes à réaliser. N'importe quelle procédure peut être appelée à
n'importe quelle étape de l’exécution du programme, incluant d'autres procédures
voire la procédure elle-même
– Programmation objet
• Paradigme de programmation qui consiste en la définition et l'interaction de
briques logicielles appelées objets ; un objet représente un concept, une idée ou
toute entité du monde physique. Il possède une structure interne, un
comportement et sait communiquer avec ses pairs. Il s'agit donc de représenter ces
objets et leurs relations ; la communication entre les objets via leur relation permet
de réaliser les fonctionnalités attendues, de résoudre le ou les problèmes.
8
 Catégories de langages de
programmation
• Programmation fonctionnelle
– La programmation fonctionnelle est un paradigme de programmation qui
considère le calcul en tant qu'évaluation de fonctions mathématiques et
rejette le changement d'état et la mutation des données. Elle souligne
l'application des fonctions, contrairement au modèle de programmation
impérative qui met en avant les changements d'état.
– Ex: CAML

• Programmation logique
– La programmation logique est une forme de programmation qui définit les
applications à l'aide d'un ensemble de faits élémentaires les concernant et de
règles de logique leur associant des conséquences plus ou moins directes. Ces
faits et ces règles sont exploités par un démonstrateur de théorème ou
moteur d'inférence, en réaction à une question ou requête.
– Ex : PROLOG

9
 Pourquoi TLC ?
• Culture de l’ingénieur
– Vous utilisez des compilateurs, des interpréteurs etc…
• Savez vous comment ils fonctionnent ?
– Qu’est-ce qu’un langage ?
– Comment le définir ?
– Comment le reconnaitre ?
– Comment l’interpréter, le compiler ?

• Les concepts sous tendant la compilation sont utilisés partout

– Les formats de fichiers définissent une structuration de l’information
• Ils ont donc un langage associé…
– Les gros logiciels offrent des langages de script parfois dédiés
– Et bien d’autres…

• Certaines descriptions dans les langages standards peuvent être longues

et fastidieuses
• Création d’un compilateur : langage dédié, simple (Domain Specific Language: DSL)
• Le compilateur s’occupe de la partie fastidieuse et systématique
10
 Logiciels et langages de script
• Les gros logiciels offrent souvent des langages de script

– Ouverture du logiciel vers les utilisateurs

• Ajout de nouvelles fonctionnalités
• Automatisation de tâches

– Proposition de langages pertinents par rapport au domaine

applicatif
• Souvent plus simples que Java / C++
• Pas forcément besoin d’être informaticien pour l’utiliser

– Fermeture de l’API du programme

• Parfait contrôle des fonctionnalités mises à disposition
• Contrôle de l’utilisation des fonctionnalités

11
THÉORIE DES LANGAGES

12
 Motivation historique
• Reconnaissance automatique de structure
dans des séquences finies
– Structure : loi, régularité
– Séquence : agencement spatial ou temporel
• Avant / après, gauche / droite, dessus / dessous…

Il faut s’assurer que le reconnaisseur est

correct !

13
 Exemples
• Télécommunications : séquences de signaux
(Shanon 1916-2001)

• Langue naturelle : séquences de mots

(Chomsky 1928-…)

• Formats de fichiers : séquences de codes

14
 Exemples
• Protocoles :
– Séquences de symboles formant des messages
– Séquences de messages
 2 niveaux d’analyse

• Langages de programmation
– Séquences de caractères pour former des mots
– Séquences de mots
 2 niveaux d’analyse
15
 Exemple : le morse
• Suite de traits et de points forme des lettres
• Les silences séparent les lettres et les mots
– Jamais deux silences à suivre

Trait

Point
Trait,
Point
Séparateur de lettres

Séparateur de mots

16
 Exemple : grammaire de formes
• Description de la structure d’une forme géométrique

• Le « flocon de Koch »

17
 Théorie des langages
• Etudie les moyens de caractériser des langages
– Ces moyens sont eux-mêmes des langages
– Notion de métalangage

• Théorie très outillée car très formalisée

• Champ d’application immense

– Texte, séquences d’événements, chimie, musique…

18
 Applications (1)
• Spécification syntaxique
– Le langage est le plus souvent infini
• Point de vue extensionnel
– Trouver une description formelle finie
• Point de vue intentionnel
• description => (description)
• (description) = langage engendré

• Difficultés
– Sur-générer :
– Sous-générer :

19
 Applications (2)
• Vérification syntaxique pour la conformité
– Langages de programmation, protocoles réseau,
format de fichier…

• La vérification doit être automatique

 Il faut un algorithme
– Calculabilité de ?
– Complexité de ?
– Question qui se pose par exemple pour la langue
naturelle…

20
 Applications (3)
• Analyse syntaxique
– Recherche du sens (sémantique)

• Difficultés
– Ambiguïté syntaxique
• Jean a vu Pierre avec ses lunettes
• « ses » réfère à Jean ou à Pierre ?
– Ambiguïté sémantique
• Cet avocat véreux est dégoutant
• Quel « avocat », le fruit ou l’homme de loi ?

21
Notions de base

Lettres, mots, langages

22
 Lettre
• Utilisation d’un alphabet (ou V)
– Ensemble fini de lettres ou de symboles
– On parle aussi de vocabulaire

• Symboles génériques
– Chiffre, ponctuation, majuscule….
– Correspond à des classes de symboles

23
 Mot
• Un mot m (ou w)
– Suite finie de symboles appartenant à
– On note le mot vide

• * est l’ensemble de tous les mots

24
 Langage
• Un langage est un ensemble de mots
(possiblement vide ou infini)

• est le langage vide

• * est le plus gros langage sur

– Ensemble infini de tous les mots finis que l’on peut former
sur

• ) est l’ensemble infini de tous les langages sur

– Rq : )

25
 Attention
• : le langage vide
– Aucun mot

• : le mot vide
– Un mot, aucune lettre

• : le langage du mot vide

– Un seul mot, le mot vide

26
 Opérations sur les mots
• Concaténation (noté )

– Tel que m contient les lettres de m1 puis de m2

– Ex :
– On écrit aussi bien que

27
 Opérations sur les mots
•
– =
• est un élément neutre
–
• La concaténation est associative
– En général :
• La concaténation n’est pas commutative

• ( , ) forme un monoïde libre

– i.e. un groupe sans élément symétrique

28
 Opérations sur les langages
• Somme de langages : (ou
) ) )

Ex :

• Propriétés
– =
–

29
 Opérations sur les langages
• Produit de langages : (ou
) ) )

Ex :

• Propriétés
– =
–

30
 Opérations sur les langages
• Fermeture de Kleene :
) )

Ex :

31
 Conclusion
• Les mots sont des séquences de lettres
– Concaténation

• Les langages sont des ensembles de mots

– Opérations ensemblistes
– Produit
– Fermeture

32
Expressions régulières

33
 Motivation
• Expression de langages en termes de langages
plus simples

• Décrire un nouveau langage en combinant des

langages existants

• Décrire des langages en utilisant des

opérations sur les langages
34
 Expressions régulières (RE)
• Formule désignant un ensemble de mots
construits sur un alphabet ∑

• Construction à partir des lettres de l’alphabet

∑ et de trois opérations sur les mots
– L’union notée R | S = {s | s є R ou s є S }
– Le produit de deux ensembles R et S, notée R S.
– La fermeture de Kleene de R, notée R* =

35
 Expression régulières (RE)
• Définition plus formelle
– Soit ∑ un alphabet
– Si ∑, a est une RE
– est une RE
– est une RE
– est une RE si est une RE
– est une RE si et sont des RE
– est une RE si et sont des RE

36
 Expressions régulières
• Langage engendré et propriétés

• Soit (r) le langage engendré par la RE r

– est une fonction de )
– si ∑
–
–
– si r est une RE
–
–

37
 Variations de notations
• Objectif : simplifier la description
• [abc]=(a|b|c)
• [a-z] = (a | b | c | … | z)
• )
•

n fois

38
 Exemples
• Expression régulière correspondant à un entier
– 0 | [1..9][0..9]*

• Expression régulière correspondant à un identifiant

– ([a..z] | [A..Z])([a..z] | [A..Z] | [0..9])*

• Quelle est l’expression régulière décrivant un

flottant ?
– Rq : le mot vide est autorisé

39
 Les limites des langages réguliers
• Les expressions régulières construisent des langages
dits réguliers sur la base de trois opérations
– La concaténation, l’union, la fermeture

• Essayez de décrire une RE reconnaissant des

expressions parenthésées composées des
identificateurs ‘a’ et ‘b’, de ‘+’, ‘-’, ‘*’, ‘/’ et ‘(‘, ‘)’
– Quel problème se pose ?

• La langages réguliers ne sont donc pas suffisants pour

décrire et analyser la syntaxe des langages que nous
utilisons…

40
 Conclusion
• Description qui emploie les opérations sur les langages
– Construire un langage complexe à partir de langages simples

• Les expressions régulières sont des grammaires de langages

réguliers

• Une notation qui fait partie du langage de l’informaticien

– Utilisée dans les utilitaires unix, presentes dans les
bibliothèques standard de nombreux langages (java, c++, c#,
python…)…

• Mais comment les reconnaitre ?

41
Les automates à états finis

Reconnaissance d’expressions
régulières

42
 Automate fini déterministe
• Un automate fini déterministe est donné par un
quintuplet (S, ∑, δ, s0, SF)
– S est un ensemble fini d’états
– ∑ est un alphabet fini
– δ : S x ∑ -> S est la fonction de transition
– s0 est l’état initial
– SF est l’ensemble des états finaux
• Automate déterministe
– l’état courant + un caractère défini un unique état suivant.
• La structure de l’automate ainsi que ses transitions
définissent des mots reconnus sur l’alphabet ∑
43
 Automate fini déterministe
• Automate reconnaissant le mot ‘fee’
f e e
S0 S1 S2 S3

• S = {S0, S1, S2, S3}

• ∑ = {f,e}
• δ = {δ(S0,f)->S1, δ(S1,e)->S2, δ(S2,e)->S3}
• S0 : état initial
• SF = { S3 }

44
 Automate fini déterministe
• Automate reconnaissant les mots ‘fee’ et ‘feu’

f e e
S0 S1 S2 S3
u

S4

45
 Automate fini déterministe
• Possibilité de reconnaitre des mots de
longueur infinie
– Rebouclage sur un état
0-9

1-9
S0 S3 Que reconnait cet automate ?
0

S4

46
Automates finis non déterministes
• Automates pouvant atteindre plusieurs états en lisant
un seul caractère
• Deux représentations possibles
– On autorise plusieurs transitions sur un même caractère
• δ devient une fonction de S x ∑ -> 2S
– On autorise les Ԑ-transitions
• Transitions sur le mot vide

• Remarque : on peut démontrer que les automates finis

déterministes et non déterministes sont équivalents en
terme de langage reconnu

47
Automates finis non déterministes
a

Ԑ a b
S0 S1 S2 S3

• Reconnaissance d’un mot vide, composé

uniquement de a ou se terminant par ab

48
 Des expressions régulières aux
automates non déterministes
Minimisation
Code d’analyseur
lexical
Expressions Automates finis
régulières déterministes

Construction Déterminisation
de Thompson Automates finis
non
déterministes

49
 Des expressions régulières aux
automates non déterministes
• Pour construire un automate reconnaissant un
langage régulier, il suffit d’avoir un mécanisme
qui reconnait
– La concaténation
– L’union
– La fermeture

• Exemple sur a(b | c)*

50
Des expressions régulières aux
automates non déterministes
a
S0 S1 Automate reconnaissant a

b
S2 S3 Automate reconnaissant b

c
S4 S5 Automate reconnaissant c

51
 Des expressions régulières aux
automates non déterministes

b
Ԑ S2 S3 Ԑ

S6 S7 Automate reconnaissant
b|c
c
Ԑ S4 S5 Ԑ

52
 Des expressions régulières aux
automates non déterministes
Ԑ

b
Ԑ S2 S3 Ԑ
Ԑ
Ԑ
S8 S6 S7 S9
c
Ԑ S4 S5 Ԑ

Automate reconnaissant (b|c)*

53
 Des expressions régulières aux
automates non déterministes
a
S0 S1

Ԑ
Ԑ

b
Ԑ S2 S3 Ԑ
Ԑ
Ԑ
S8 S6 S7 S9
c
Ԑ S4 S5 Ԑ

Automate reconnaissant a(b|c)*

54
 Des expressions régulières aux
automates non déterministes
• Oui mais…

• Les automates non déterministes sont peu

efficaces
– nécessitent l’exploration de plusieurs états suite à la
lecture d’une lettre de l’alphabet

• Transformation d’un automate non déterministe

en automate déterministe
– Algorithme de déterminisation et de minimisation

55
 Algorithme de déterminisation
• s0 : état initial de l’automate
• Ԑ-fermeture(S) : collecte tous les états accessibles par Ԑ-transition depuis les états contenus
dans S
• Δ(S,c) : collecte tous les états atteignables depuis les états de S en lisant le caractère c

q0 <- Ԑ-fermeture(s0)
initialiser Q avec q0
WorkList <- q0
Tant que WorkList non vide
Prendre qi dans WorkList Exercice
Pour chaque caractère c de ∑ Déterminisez l’automate
q <- Ԑ-fermeture(Δ(qi, c)) reconnaissant a(b|c)*
Δ[qi,c] <- q
Si q n’est pas dans Q
Ajouter q à WorkList
Ajouter q à Q
Fin si
Fin pour
Fin tant que

56
 Algorithme de déterminisation
• Déterminisation de l’automate pour a(b|c)*
b

b q2

a
q0 q1
c b
c

q3

57
 Algorithme de minimisation
• S : ensemble des états de l’automate
• SF : ensemble des états finaux de l’automate

P <- { SF, S- SF }
Tant que P change
T <- ensemble vide
Pour chaque ensemble p de P Exercice
T <- T union Partition(p) Minimisez l’automate
P <- T reconnaissant a(b|c)*
Fin tant que

Partition(p)
Pour chaque c de ∑
Si c sépare p en { p1,…,pk } return { p1,…,pk }
Return p

58
 Algorithme de minimisation
• Minimisation de l’automate pour a(b|c)*
b

b q2 b

a a
q0 q1 s0 s1
c b
c
c
q3

59
 Algorithme de reconnaissance
• Codage de l’automate par une table de transition

char <- prochain caractère

state <- s0
Tant que char != EOF
State <- δ(state, char), erreur si pas de transition
Char <- prochain caractère
δ a b c autre
si state est dans SF s0 s1 - - -
alors accepter s1 - s1 s1 -
sinon rejeter - - - - -

60
 Conclusion
• Les expressions régulières décrivent ce qui doit être
reconnu

• Les automates reconnaissent

• Les RE et les automates finis parlent le même langage

• Méthodologie
– Spécifier avec une expression régulière
– Transformer l’expression régulière en automate
– Reconnaitre avec l’automate

61
 Analyse lexicale
• Les langages réguliers sont utilisés pour décrire les jetons (ou tokens) reconnus lors
de l’analyse lexicale
– Constantes numériques
– Chaines de caractères
– Mots clefs du langage
– Identifiants
– …

• Pour reconnaitre ces différents jetons, il faut :

– Construire un automate non déterministe par jeton
• Chaque état final identifie le jeton reconnu
– Construire un automate non déterministe correspondant au « ou » entre tous les jetons
– Déterminiser et minimiser l’automate obtenu

• A partir de l’automate obtenu, il est possible d’écrire / générer un analyseur lexical

– Entrée : texte à analyser
– Sortie : suite de jetons utiles à l’analyse syntaxique

62
Les classes de grammaires

La hiérarchie de Chomsky
(formalisée en 1959)

63
 Grammaire : définition

Une grammaire est un formalisme permettant

de décrire une syntaxe et donc un langage
formel i.e. un ensemble de mots admissibles sur
un alphabet donné.

64
 Les grammaires : formalisation
• La grammaire d’un langage est constituée de quatre
objets
– T est l’alphabet terminal
• Ensemble des symboles qui constituent les phrases à reconnaitre (Cf. sections
précédentes)
– N est l’alphabet non terminal
• Un non-terminal est une variable syntaxique désignant des ensembles de
chaines de symboles terminaux
– S est un symbole particulier de N, l’axiome
• Symbole non-terminal qui désigne l’intégralité du langage
– P est un ensemble de règles de production (ou de dérivation)
• Leur forme générale est la suivante :
avec ∗ ∗ et ∗

• Cela signifie que si l’on a A, il est correct de le remplacer par B (production)

• Ou que si l’on trouve B, nous avons en réalité reconnu A (analyse)

65
 Les grammaires : formalisation
• En fonction de la nature des règles de production,
plusieurs classes de langages peuvent être identifiées

• La hiérarchie de Chomsky comporte 5 classes de

grammaires :
– Générales (type 0)
– Contextuelles (type 1)
– Algébriques (type 2)
– Régulières (type 3)
– A choix fini (type 4)

• Pour simplifier les notations, posons

66
 Grammaires générales (type 0)
• Règles de la forme avec et

• Génère un très grand nombre de mots

• Temps pour savoir si un mot appartient ou non à la

grammaire n’est pas forcément fini
– Appartenance : temps fini
– Non appartenance : possibilité de bouclage sans réponse
– Indécidable…

67
Grammaires contextuelles (type 1)
• Règles de la forme avec
–
–
–

• Contextuelles car le remplacement d’un non

terminal peut dépendre des éléments autour de
lui

• Appartenance : décidable et PSPACE complet

68
 Grammaires algébriques (type 2)
• Règles de la forme avec
–
–

• Les non-terminaux sont traités individuellement,

sans prise en compte du contexte

• Reconnaissance des langages algébriques

– Algorithmes efficaces

69
 Grammaires régulières (type 3)
• Règles de la forme
et avec et
et avec et
 On ne peut pas autoriser les deux types de règles
simultanément au risque de sortir des langages réguliers

• Reconnaissance des langages réguliers

– Equivalent aux expressions régulières
– Reconnus par automates à états finis
• Algorithmes de reconnaissance très efficaces
• Cf. partie précédente

70
 Grammaire à choix fini (type 4)
• Règles de la forme avec et

• Classe très restreinte…

• Utilisé pour décrire des macros

71
Les langages de programmation usuels
• La description d’un programme est un texte
– Une simple suite de caractères

• L’analyse du texte se fait en deux étapes

1. On découpe la suite de caractères en mots, en
vérifiant que les mots appartiennent au langage
2. On analyse la suite de mots pour vérifier que les
phrases sont correctes

72
Les langages de programmation usuels
1. Analyse lexicale
– Découpe du texte en petits morceaux appelés jetons
(tokens) correspondant à des suites de caractères
– Chaque jeton est une unité atomique du langage
• Mots clés, identifiants, constantes numériques…
– Les jetons sont décrits par un langage régulier
• Description via des expression régulières
• Reconnaissance via des automates à état finis

• Le logiciel effectuant l’analyse lexicale est appelé

analyseur lexical ou scanner

73
Les langages de programmation usuels
2. Analyse syntaxique
– Analyse de la séquence de jetons pour identifier la
structure syntaxique du langage
– S’appuie sur une grammaire algébrique définissant la
syntaxe du langage
– Produit généralement un arbre syntaxique qui pourra être
analysé et transformé par la suite
– Détection des erreurs de syntaxe
• Constructions ne respectant pas la grammaire

• Le logiciel effectuant l’analyse syntaxique est appelé

analyseur syntaxique ou parser

74
 Chaine de compilation
• Analyse lexicale
– Découpe du texte en petits morceaux appelés jetons
(tokens)
– Chaque jeton est une unité atomique du langage
• Mots clés, identifiants, constantes numériques…
– Les jetons sont décrits par un langage régulier
• Détection via des automates à état finis
• Description via des expression régulières

• Le logiciels effectuant l’analyse lexicale est appelé

analyseur lexical ou scanner

75
 Chaine de compilation
• Analyse syntaxique

– Analyse de la séquence de jetons pour identifier la structure

syntaxique du langage

– S’appuie sur une grammaire formelle définissant la syntaxe du

langage

– Produit généralement un arbre syntaxique qui pourra être

analysé et transformé par la suite

– Détection des erreurs de syntaxe

• Constructions ne respectant pas la grammaire

76
 La hiérarchie de chomsky (1/2)
• Extraction de 5 classes de grammaires

– Générales (type 0)
• Règles de la forme : avec
• Génère un très grand nombre de mots
• Temps pour savoir si un mot appartient ou non à la grammaire n’est
pas forcément fini
– Appartenance : temps fini
– Non appartenance : possibilité de bouclage sans réponse
– Indécidable…

– Contextuelles (type 1)
• Règles de la forme avec
• Contextuelles car le remplacement d’un non terminal peut dépendre
des éléments autour de lui

77
La hiérarchie de chomsky (2/2)
– Hors contexte (type 2)
• Règles de la forme , avec
• Les éléments terminaux sont traités individuellement, sans prise
en compte du contexte
• Reconnaissance des langages algébriques

– Régulières (type 3)
• Règles de la forme et et avec
• Reconnaissance des langages rationnels (reconnus par automates
à états finis)

– A choix fini(type 4)
• Règles de la forme avec
• Classe très restreinte…

78
Les grammaires algébriques

L’analyse syntaxique

79
Grammaire algébrique (hors contexte)
Définition
• Définition: une grammaire algébrique est un quadruplet

• G = (N, T, S, P) où:
– N est l’alphabet non terminal
– T est l’alphabet terminal
– S est un symbole particulier de N, l’axiome
– P est un ensemble de règles de production (ou de
dérivation), de la forme:
A  w, avec AN et w(N  T)*

80
 Grammaire algébrique
Langage engendré
• Dérivations
• m  m’ si m = uAv et m’=uwv et A->w  P

• m0  mn s'il existe une suite mk, k=0, .., n-1 et mk  mk+1

• Langage engendré
• L(G) = { m  T*, S  m }

• Langage algébrique:
– Définition: un langage L est dit algébrique (ALG) ou "context free"
(CFL) si il existe une grammaire algébrique G, tel que L = L(G)
– Propriété des langages algébriques
• la partie gauche d’une règle est un non-terminal

81
 Grammaire algébrique
Arbre de dérivation syntaxique
• Un mot m est reconnu par une grammaire algébrique s’il
existe un arbre de dérivation syntaxique
– Les nœuds internes contiennent des symboles non terminaux
– Les feuilles contiennent des symboles terminaux
– La racine est le symbole initial
– Dans un parcours infixe, les feuilles donnent le mot m
– Si un nœud interne étiqueté X a des sous-arbres t1…tn alors
X -> t1…tn est une règle de la grammaire

• Attention: ne pas confondre

– Arbre de dérivation syntaxique : associé à la grammaire
– Arbre de syntaxe abstraite : associé au langage

82
 Grammaire algébrique
Exemple
• Exemple de grammaire décrivant des expressions simples (sans
parenthèses)
– N = {EXP}, S = {EXP}, T = {var, cst, +, *}
– P={ EXP
EXP -> var,
EXP -> cst, EXP + EXP
EXP -> EXP + EXP,
EXP -> EXP * EXP
– } EXP * EXP cst

• Exemple de dérivation de EXP cst var

– EXP -> EXP + EXP -> EXP * EXP + EXP
– EXP *-> EXP * EXP + EXP Arbre de dérivation syntaxique
pour cst * var + cst
– EXP *-> cst * var + cst

• Le langage engendré est un langage algébrique et un langage régulier

• (var | cst) ( (+ | *) (var | cst) )*

83
 Grammaire algébrique
Exemple
• Exemple de grammaire décrivant des expressions parenthésées
– N = {EXP}, S = {EXP}, T = {var, cst, +, *, (, ) }
– P={
EXP -> var,
EXP -> cst,
EXP -> EXP + EXP,
EXP -> EXP * EXP,
EXP -> ( EXP )
– }

• Exemple de dérivation de EXP

– EXP -> EXP * EXP -> EXP * (EXP) -> EXP * (EXP + EXP)
– EXP *-> EXP * ( EXP + EXP )
– EXP *-> cst * ( var + cst )

• Le langage engendré est algébrique et n’est pas régulier

– L’utilisation de la règle EXP -> ( EXP ) permet de s’assurer qu’une parenthèse fermante est
toujours associée à une parenthèse ouvrante

84
 Grammaire algébrique
Alphabet et langage de programmation
• L'alphabet non terminal N correspond
– soit à des constructions sémantiques du langage de programmation: programme,
déclaration, instruction, boucle, etc..
– soit à des constructions syntaxiques: liste, etc..

• L'axiome S correspond à la construction compilable de plus haut niveau:

– classe ou interface pour Java.
– définition de type, fonction, implémentation de méthode pour C++

• L'alphabet terminal T correspond aux jetons (unités lexicales) renvoyées par l'analyseur
lexical:
– mots clés,
– identificateurs,
– séparateurs,
– opérateurs,
– …

85
 Un exemple de texte structuré
• Exemple de deux adresses postales
Fabrice Lamarche Bernard Truc
IRISA 25 avenue Bidule
263 avenue du général Leclerc 35000 Rennes
35062 Rennes CEDEX

• Que peut-on remarquer ?

– Une structure similaire
• Un nom, un numéro et un nom de rue, un code postal et une ville
– Mais quelques variantes
• Le nom peut être complété avec un nom d’entreprise ou être
simplement un nom d’entreprise
• La ville peut être suivie de « CEDEX » ou non

86
Notations usuelles des grammaires
• BNF : Backus Naur Form ou Backus Normal Form
– Description de grammaires algébriques ou context free

• Notations
– Définition d’une règle : opérateur ::=
• Non terminal ::= expression
– Non terminaux : <non-terminal>
• Identifiant entre < >
– Terminaux : "terminal"
• Chaine de caractères entre " "
– Alternative : opérateur |
• "toto" | <regle>
• signifie une alternative entre toto et ce qui est reconnu par le non terminal <regle>

• Cette notation est suffisante pour décrire les grammaires algébriques

87
 Grammaire en notation BNF
La grammaire pour les adresses
<adresse> ::= <identite> <adresse-rue> <code-ville>
<identite> ::= <nom-personne> <EOL> |
<nom-personne> <EOL> <nom-entreprise> <EOL>
<nom-personne> ::= <prenom> <nom>
<prenom> ::= <initiale> "." | <mot>
<nom> ::= <mot>
<nom-entreprise> ::= <mot> | <mot> <nom-entreprise>
<adresse-rue> ::= <numero> <type-rue> <nom-rue> <EOL>
<type-rue> ::= "rue" | "boulevard" | "avenue"
<nom-rue> ::= <mot> | <mot> <nom-rue>
<code-ville> ::= <numero> <ville> <EOL> | <numero> <ville> "CEDEX" <EOL>
<ville> ::= <mot> | <mot> <ville>

88
 Grammaires en notation BNF
• Certaines choses sont « longues » à décrire et pas forcément lisibles
– Rendre quelque chose d’optionnel
• <rule-optional> ::= <element> | ""
• Rq : "" est le mot vide
– Répétition d’un élément 0 à n fois
• <rule-repeat> ::= <element> <rule-repeat> | ""
• Utilisation de la récursivité et du mot vide
– Répétition d’un élément 1 à n fois
• <rule-repeat-one> ::= <element> <rule-repeat>
• Utilisation de deux règles car pas de groupement

• Des extensions à la notation BNF ont été proposées

– EBNF, ABNF etc…
– Rôle : augmenter la lisibilité et simplifier l’écriture des grammaires

89
 Notations usuelles des grammaires
Grammaires en notation EBNF
• EBNF : Extended BNF
– Même expressivité que les grammaire BNF
– Plus facile à écrire et à comprendre

• Notations :
– Définition d’une règle : operateur =
– Fin de règle : symbole ;
– Alternative : symbole |
– Elément optionnel : utilisation de [ … ]
– Répétition de 0 à n fois : { … }
– Groupement : utilisation de ( … )
– Terminal : "terminal" ou ‘terminal’
– Commentaire : (* commentaire *)

• Apparition d’une notation pour les élément optionnels, les groupements et la

répétition
– Simplification de notation et amélioration de la lisibilité
– Evite la récursivité (pour les cas simples) et l’utilisation du mot vide

90
 Exemple BNF vs EBNF
• Exemple: langage de déclaration de plusieurs variables de
type int ou float.

– Grammaire en notation BNF

<declaration-vars> ::= <declaration-var> <declaration-vars> | ""
<declaration-var> ::= <type> <identifiant> ";"
<type> ::= "int" | "float"

– Grammaire en notation EBNF

declarationVars = { ("int" | "float") identifiant ";" } ;

91
 La grammaire pour les adresses
La grammaire en notation EBNF
adresse = identite adresseRue codeVille ;
identite = nomPersonne EOL [nomEntreprise EOL] ;
nomPersonne = prenom nom ;
prenom = initiale "." | mot ;
nom = mot ;
nomEntreprise = mot {mot} ;
adresseRue = numero typeRue nomRue EOL ;
typeRue = "rue" | "boulevard" | "avenue" ;
nomRue = mot {mot} ;
codeVille = numero ville ["CEDEX"] EOL ;
ville = mot {mot} ;

92
 La notation graphique
Diagrammes de syntaxe
• Exemple sur la règle de déclaration de méthode en Java

method_declaration ::= { modifier } type identifier

"(" [ parameterList ] ")" { "[" "]" }
( statement_block | ";" )

93
 Notations usuelles des grammaires
Variante basée sur expressions régulières
• Simple d’utilisation
• Notation similaire à celle utilisée pour l’analyseur lexical
• Notation utilisée dans certains logiciels
– Ex : ANTLR qui sera utilisé en TP.

• Notations
– Alternative : symbole |
– Groupement : utilisation de ( … )
– Répétition 0 à n fois : utilisation de *
– Répétition 1 à n fois : utilisation de +
– Elément optionnel : utilisation de ?

• Retour sur l’exemple précédent dans cette notation :

– declarationVars = ( ("int" | "float") identifiant ";" )* ;

94
 La grammaire pour les adresses
Variante EBNF basée exp. régulières
adresse = identite adresseRue codeVille ;
identite = nomPersonne EOL (nomEntreprise EOL)? ;
nomPersonne = prenom nom ;
prenom = initiale "." | mot ;
nom = mot ;
nomEntreprise = mot+ ;
adresseRue = numero typeRue nomRue EOL ;
typeRue = "rue" | "boulevard" | "avenue" ;
nomRue = mot+ ;
codeVille = numero ville "CEDEX"? EOL ;
ville = mot+ ;

95
 Exercice

• Ecrivez la grammaire (notation EBNF) d’un

langage reconnaissant des expressions
booléennes pouvant être parenthèsées et
prenant en compte la priorité des opérateurs
– Opérateurs binaires: and, or
– Opérateur unaire : not
– Parenthèses : (, )
– Valeurs (true, false) ou identifiants pour les termes

96
 Reconnaissance du langage
• Une fois la grammaire écrite, il faut la reconnaitre

• Deux grands types d’approche

– L’analyse ascendante
• Construction de l’arbre de dérivation syntaxique à partir des
feuilles
• Utilisée dans des logiciels type YACC

– L’analyse descendante
• Construction de l’arbre de dérivation syntaxique à partir de la
racine
• Utilisée dans des logiciels type ANTLR(utilisé en TP)

97
 L’analyse ascendante
• Aussi appelée analyse LR
– Il analyse l'entrée de gauche à droite (Left to right) et produit une dérivation à
droite (Rightmost derivation)
– On parle d’analyseur LR(k) où k est le nombre de symboles anticipés et non
consommés utilisés pour prendre une décision d’analyse syntaxique

• Construit l’arbre de dérivation syntaxique en partant des feuilles

• On garde en mémoire une pile.
– Cette pile contient une liste de non-terminaux et de terminaux.
– Correspond à la portion d’arbre reconstruit
• Deux opérations
– Lecture (shift) : on fait passer le terminal du mot à lire vers la pile
– Réduction (reduce) : on reconnait sur la pile la partie droite x1…xn d’une règle
X ::= x1…xn et on la remplace par X
• Le mot est reconnu si on termine avec le mot vide à lire et le symbole
initial sur la pile.

98
 L’analyse descendante
• Aussi appelée analyse LL
– Il analyse l'entrée de gauche à droite (Left to right) et en construit une dérivation à gauche (Leftmost
derivation)
– On parle d’analyseur LL(k) où k est le nombre de symboles anticipés et non consommés utilisés pour
prendre une décision d’analyse syntaxique

• Reconstruction de l’arbre syntaxique à partir de la racine

– Entrée : un mot m (suite de jetons produits par l’analyseur lexical)
– Une fonction associée à chaque terminal et non terminal
• Reconnaissance de la structure du non terminal / terminal
– Suppose qu’étant donné le non terminal et le mot, on peut décider de la règle à appliquer
– Pour reconnaitre le mot, on part de la fonction associée au symbole initial et on vérifie que l’on atteint la fin
de la chaine

• Construit (implicitement) un arbre de racine le symbole initial dont les feuilles forment le préfixe de
m

• Chaque fonction renvoie

– le reste du mot m à analyser
– Eventuellement une information associée (ex : arbre de dérivation syntaxique)

99
 Limites de l’analyse descendante
• On ne peut pas toujours décider facilement de la règle à appliquer
– Combien de terminaux faut-il explorer pour déterminer la règle à appliquer ?
– Si k terminaux à explorer : analyseur LL(k)
– La plupart du temps, on s’intéresse aux grammaires LL(1)
• Les grammaires récursives gauches (X::=Xm) ne sont pas LL(1)
• Par contre, les grammaires récursives droite (X::=mX) le sont

• Exemple de grammaire LL(2)

– bonjour = bonjourMonsieur | bonjourMadame ;
– bonjourMonsieur = "bonjour" "monsieur" ;
– bonjourMadame = "bonjour" "madame" ;

• Même grammaire en LL(1)

– bonjour = "bonjour" (monsieur | madame)
– monsieur = "monsieur" ;
– madame = "madame" ;

• Remarque : le plus souvent, il est possible de passer d’une grammaire LL(k) à une grammaire LL(1)

• Remarque 2 : de nos jours, grâce à certains outils (ANTLR par exemple), il n’est plus nécessaire
d’effectuer cette transformation

100
Vers les arbres de syntaxe abstraite
• Arbre de dérivation syntaxique
– Résulte du parcours de la grammaire lors de l’analyse syntaxique
– Possède beaucoup d’informations « inutiles »
• Lexèmes servant à désambigüiser l’analyse
• Lexèmes servant à identifier les priorités sur les opérations
– Exemple : parenthèses dans une expression numérique
• Délimitation de début / fin de bloc
• …
• Arbre de syntaxe abstraite
– Plus compacte que l’arbre de dérivation syntaxique
– Représente la sémantique du langage
– Supprime les informations « inutiles »
• Ex : Une syntaxe sous forme d’arbre représente implicitement les priorités des
opérations, pas besoin de parenthèses
– S’obtient par réécriture de l’arbre de dérivation syntaxique

101
 Retour sur les adresses
Arbre de dérivation syntaxique
• Adresse exemple :
Fabrice Lamarche
IRISA INRIA Rennes
265 avenue du General Leclerc
35042 Rennes CEDEX

102
 Retour sur les adresses
Arbre de syntaxe abstraite
• Adresse exemple :
Fabrice Lamarche
IRISA INRIA Rennes
265 avenue du General Leclerc
35042 Rennes CEDEX

103
 Retour sur les adresses
Arbre de dérivation syntaxique
• Adresse exemple :
Bernard Truc
25 avenue Bidule
35000 Rennes

104
 Retour sur les adresses
Arbre de syntaxe abstraite
• Adresse exemple :
Bernard Truc
25 avenue Bidule
35000 Rennes

105
 ANTLR

Un compilateur de compilateurs

106
 Introduction
• Un outils pour la reconnaissance de langages
– Ecrit par Terence Parr en Java

• Plus facile d’utilisation que la plupart des outils similaires

• Propose un outils de mise au point

– ANTLRWorks
• Editeur graphique de grammaire et debuggeur
• Ecrit par Jean Bovet

• Utilisé pour implémenter

– De vrais langages de programmation
– Des langages spécifiques à un domaine
• Ex : fichiers de configuration

• Pour tout savoir : http://www.antlr.org

– ANTLR + ANTRLWorks
– Libre et open source

107
 Introduction
• Compilateur de compilateur
– Fichier source
• Une description du langage
– Grammaires EBNF
• Éventuellement annotée
– Association de différents types d’opérations aux règles de la grammaire
– Produit
• Le code pour l’analyseur lexical
• Le code pour l’analyseur syntaxique
– Le code produit peut être intégré dans les applications

• Supporte plusieurs langages cible

– Java, Ruby, Python, C#, C et bien d’autres…

108
 Introduction
• Supporte les grammaires LL(*)
– Ne supporte que les grammaires récursives à droite
– LL(k) : Regarde k lexèmes en avance pour lever des
ambigüités
– LL(*) : Regarde autant de lexèmes que nécessaire pour
lever les ambigüités

• Avantage du LL(k)
– Améliore la lisibilité des règles de la grammaire
– Simplifie la description
– Simplifie l’ajout de nouvelles règles

109
 Introduction
• Trois grands types d’utilisation
1. Implémentation de « validateurs »
– Valident si un texte en entrée respecte une grammaire
– Pas d’action spécifique effectuée
2. Implémentation de « processeurs »
– Valide un texte en entrée
– Effectue les actions correspondantes
– Les actions peuvent inclure
• Des calculs (langages de script ou avoisinés)
• De la mise à jour de base de données
• L’initialisation d’une application à partir d’un fichier de configuration
• …
3. Implémentation de « traducteurs »
– Valide un texte
– Le transforme dans un autre format
• Ex : Java vers C++

110
Etapes de développement avec ANTLR
• Ecriture d’une grammaire

• Tester de debugger la grammaire sous ANTLRWorks

– Offre la visualisation
• d’arbres de dérivation syntaxique
• d’arbres de syntaxe abstraits
– L’exécution pas à pas de l’analyse d’un texte
– Supporte la cible Java par défaut
• i.e. vous pouvez inclure du code Java dans vos grammaires !

• Générer les classes depuis la grammaire

– L’analyseur lexical et l’analyseur syntaxique

• Ecriture de l’application qui utilise les classes générées

• Remarque : dans les exemples et dans les TP, le langage Java sera utilisé

111
 Structure d’un fichier de grammaire
• grammar nom-grammaire ;
– nom-gramaire : Nom donné à la grammaire
– Doit correspondre au nom du fichier contenant la grammaire avec l’extension « .g »

• options-de-grammaire [optionnel]
– Options permettant de décrire ce qui doit être généré par ANTLR

• attributs-methodes-lexer-parser [optionnel]
– Ensemble des attributs et méthodes ajoutés aux classes d’analyseurs lexical et syntaxique

• lexemes
– Ensemble des lexèmes utilisés dans la grammaire

• regles
– Ensemble des règles définissant la grammaire

112
 Les options des grammaires
• Syntaxe :
option
{
name = value ;
}

• Où name peut (principalement) prendre les valeurs suivantes

– backtrack
• Si backtrack = true : la grammaire est considérée comme LL(*)
– language
• Permet de signaler dans quel langage les classes doivent être générées
– Ex : language = java, les classes sont générées en Java
– output
• La valeur associée à output définit le type de structure de donnée générée par l’analyseur syntaxique
– Ex : output = AST, l’analyseur syntaxique génère un arbre syntaxique abstrait
– k
• Signale le nombre de lexèmes à utiliser pour choisir les règles
– Ex : k = 1, signale que la grammaire est LL(1)

113
 Ajout d’informations pour
les classes et fichiers générés
• Ajout d’un en-tête au fichier généré
– @lexer::header { … }
• Signale des instructions à ajouter à l’en-tête du fichier contenant l’analyseur lexical
– @parser::header { … }
• Signale des instructions à ajouter à l’en-tête du fichier contenant l’analyseur syntaxique
– Utile pour des inclusions de classes ou définition de package par exemple

• Ajout de méthodes / attributs

– @lexer::members { … }
• Fournit des méthodes / attributs définis par l’utilisateur pour l’analyseur lexical
– @parser::members { … }
• Fournit des méthodes / attributs définis par l’utilisateur pour l’analyseur syntaxique
– Utile pour la factorisation de traitements pour les analyseurs ou encore pour
ajouter des attributs permettant de partager des informations entre règles

114
 Définition des lexèmes
• La syntaxe de définition des lexèmes est la suivante
– NomLexeme : expression-regulière ;
• Où
– NomLexeme est l’identifiant d’un lexème
• Cet identifiant DOIT commencer par une majuscule
– expression-regulière est une expression régulière décrivant les mots
associés au lexème
• ‘x’ : le caractère ‘x’
• ‘a’..’t’ : l’ensemble des caractères dans l’intervalle [‘a’; ‘t’]
• a|b : décrit l’alternative entre a et b
• . : n’importe quel caractère
• ~ : tous les caractères saufs ceux à droite de ~
• ( ) : sert à regrouper des éléments
• + : répétition 1 à n fois de l’élément à gauche de +
• * : répétition 0 à n fois de l’élément à gauche de *
• ? : rend optionnel l’élément à gauche de ?

115
 Définition des lexèmes
• Exemples

• Lexème reconnaissant un identifiant

– ID : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')* ;

• Lexème reconnaissant un commentaire sur une ligne

– COMMENT : '//' ~('\n'|'\r')* '\r'? '\n' ;

• Lexème reconnaissant un commentaire sur plusieurs lignes

– COMMENT2 : '/*' .* '*/' ;
– Attention : fonctionnement particulier du .*
• Normalement, reconnait toute séquence de caractère
– On ne s’arrête pas avant la fin du fichier
• Mais avec ANTLR
– On sort de la séquence dès que ce qui vient après est reconnu
– Donc, dans l’exemple, dès que '*/' est trouvé
– Pratique 

116
 Définition des lexèmes
• Par défaut, l’analyseur lexical possède deux canaux de sortie
pour les lexèmes
– DEFAULT : le canal de sortie par défaut. Le lexème est consommé par
l’analyseur syntaxique
– HIDDEN : lorsqu’un lexème est sorti sur ce canal, il n’est pas traité par
l’analyseur syntaxique
• Utile pour les commentaires par exemple

• Lorsqu’un lexème est reconnu, une action peut-être effectuée

avant que ce dernier soit transmis à l’analyseur syntaxique
– Syntaxe :
Lexeme : expression-reguliere { actions } ;

117
 Définition des lexèmes
• Exemples d’actions
– $channel = HIDDEN ;
• Provoque la sortie sur le canal HIDDEN. Le lexème n’est donc
pas traité par l’analyseur syntaxique
– skip() ;
• Le lexème qui vient d’être reconnu est simplement omis

• Retour sur l’exemple des commentaires :

COMMENT : '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
| '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
;
– Force les commentaires à être ignorés

118
 Définition des règles
• Les règles sont décrites via la syntaxe EBNF inspirée par
les expression régulières

• Syntaxe :
regle : corps-regle ;

• Où
– regle est le nom de la règle
• Commence forcément par une minuscule
– corps-regle est une expression décrivant ce qui doit être
reconnu

119
 Définition des règles
• Syntaxe du corps de la règle
– identifiant
• Si commence par une majuscule, réfère à un lexème préalablement
déclaré qui doit être reconnu
• Si commence par une minuscule, réfère à une règle qui doit être
reconnue
– ‘chaine’ : reconnait le mot ‘chaine’
• Utilisé pour les mots clefs du langage par exemple
• Ajoute « automatiquement » un lexème prioritaire
– a | b : reconnait soit la sous-règle a, soit la sous règle b
– a* : reconnait 0 à n fois la sous-règle a
– a+ : reconnait 1 à n fois la sous-règle a
– a? : rend optionnelle la reconnaissance de la sous règle a
– () : sert à regrouper des sous-règles

120
 Définition de règles
• Exemple de définition de règles

// Declaration de méthode à la C++

methodDecl : (primitiveType | ID) ID ‘(‘ (varDecl (‘,’ varDecl)*)? ‘)’ ‘const’? ‘;’ ;
// Types primitifs autorisés
primitiveType : ‘char’ | ‘int’ | ‘float’ | ‘double’ | ‘bool’ ;
// Déclaration de variable / paramètre
varDecl : (primitiveType | ID) ID ;

121
 Définition de règles
• Vu d’ANTLR, une règle correspond à une méthode
de l’analyseur syntaxique

• Elle peut posséder

– Des paramètres
– Une valeur de retour
– Du code à exécuter
• Au début de la règle
• En fin de règle
• À n’importe quel stade de l’analyse (en cours de règle)

122
 Définition et utilisation des règles
• Syntaxe des règles
regle [ Type1 param1, Type2 param2] returns [TypeR1 id1, TypeR2 id2]
@init { /* code en initialisation de règle */ }
@after { /* code en fin de règle */ }
: corps-règle { /*code en cours de règle */ } ;

• Manipulation des paramètres et valeurs de retour

– $param1 : valeur du paramètre1
– $id1 : valeur de retour

• Utilisation des paramètres et valeurs de retour

– regle2 : ret=regle[p1,p2] ;
– p1 et p2 sont les paramètres
– ret designe une structure contenant les valeurs de retour de regle
– $ret.id1 et $ret.id2 désignent les deux valeurs de retour de regle

123
 Exemple : la calculatrice en notation
polonaise inverse en ~20 lignes
grammar calculatrice;

@parser::members
{ java.util.Stack<Integer> m_stack = new java.util.Stack() ; }

INT : '0'..'9'+ ;

WS : (' ' | '\t' | '\r' | '\n') { $channel = HIDDEN ; } ;

expression
@after
{ System.out.println("Value on top: "+ m_stack.pop()) ; } :
( v = value { m_stack.push($v.val) ; }
| v = operation[m_stack.pop(), m_stack.pop()] { m_stack.push($v.val) ; }
)* ';' ;

value returns [Integer val] : a=INT { $val = Integer.valueOf($a.text) ; } ;

operation [Integer v1, Integer v2] returns [Integer val] :

('+' {$val = $v1 + $v2 ; }
| '-' {$val = $v1 - $v2 ; }
| '*' {$val = $v1 * $v2 ; }
| '/' {$val = $v1 / $v2 ; }
);
124
 Exemple : la calculatrice en
notation polonaise inverse
import java.io.*;
import java.util.Scanner;
import org.antlr.runtime.*; Evaluation interactive
public class Processor { des expressions
public static void main(String[] args) throws IOException, RecognitionException {
new Processor().processInteractive();
}

private void processInteractive() throws IOException, RecognitionException {

Scanner scanner = new Scanner(System.in);
while (true) {
System.out.print("calculatrice> ");
String line = scanner.nextLine().trim();
if ("quit".equals(line) || "exit".equals(line)) break;
Integer result = processLine(line);
System.out.println("Resultat: "+result) ;
}
}

private Integer processLine(String line) throws RecognitionException {

calculatriceLexer lexer = new calculatriceLexer(new ANTLRStringStream(line));
calculatricParser tokenParser = new calculatriceParser(new CommonTokenStream(lexer));
calculatriceParser.expression_return parserResult = tokenParser.expression(); // start rule method
return parserResult.resultat ;
}
}
125
 Exemple : la calculatrice en
notation polonaise inverse
import java.io.*;
import java.util.Scanner; Evaluation des
import org.antlr.runtime.*;
expressions à partir
public class Processor { d’un fichier
public static void main(String[] args) throws IOException, RecognitionException {
if (args.length == 1) { // name of file to process was passed in
Integer result = new Processor().processFile(args[0]);
System.out.println(result) ;
}
else { // more than one command-line argument
System.err.println("usage: java Processor file-name");
}
}

private Integer processFile(String filePath) throws IOException, RecognitionException {

FileReader reader = new FileReader(filePath) ;
calculatriceLexer lexer = new calculatriceLexer(new ANTLRReaderStream(reader));
calculatriceParser parser = new calculatriceParser(new CommonTokenStream(lexer)) ;
calculatriceParser.expression_return parserResult = parser.expression() ;
return parserResult.resultat ;
}
}
126
 Attributs des règles
• Les règles possèdent des attributs accessibles via
– $nomRègle.attribut, accès direct à l’attribut
– a=nomRègle et $a.attribut, récupération valeur de retour et accès à
l’attribut

• Attributs prédéfinis
– $r.text : String, le texte reconnu par la règle
– $r.start : Token, le premier token à reconnaitre
– $r.stop : Token, le dernier token à reconnaitre
– $r.tree : Object, l’arbre AST généré par la règle

• Attributs correspondant aux valeurs de retour

– Si valRet est une valeur de retour
– $r.valRet permet d’accèder à la valeur de retour de la règle r

127
 Attributs des tokens
• Les tokens possèdent des attributs accessibles via
– $NomToken.attribut, accès direct à l’attribut
– a=NomToken et $a.attribut, récupération valeur de retour
et accès à l’attribut

• Attributs prédéfinis
– $t.text : String, le texte associé au token t
– $t.line : int, le numéro de ligne du premier caractère du
token (commence à 1)
– $t.pos : int, la position de ce caractère sur la ligne
(commence à 0)

128
 Le code généré
• Lors de la compilation, deux fichiers sont générés :
– Un « lexer » (analyseur lexical)
– Un « parser » (analyseur syntaxique)

• Ces fichiers contiennent une classe associée à chaque

analyseur

• Soit une grammaire nommée Grammar

– La classe GrammarLexer contiendra le « lexer »
– La classe GrammarParser contiendra le « parser »

129
 Le code généré pour l’analyseur
syntaxique
• Les valeurs de retour des règles
– Une classe générée par règle
– Cette classe contient un attribut publique par valeur de retour de règle
– Une référence vers l’arbre de syntaxe abstrait (si présent)
• Accessible via getTree()
– Nom normalisé : nomRegle_return

• Une règle = une méthode

– Paramètres équivalents aux paramètres de la règle

• Les lexèmes (tokens) sont listés

– Constantes de type int
– Correspondent au « type » du lexème
– Portent le nom du lexème
– Permettra de faire la correspondance pour les arbres de syntaxe abstraits

130
 Arbres de syntaxe abstraits
• ANTLR propose des fonctionnalités pour la
construction d’arbres de syntaxe abstraits

• Objectifs d’un arbre de syntaxe abstrait

– Stocker les lexèmes pertinents
– Encoder la structure grammaticale sans information
superflue
– Etre facile à manipuler

Il s’agit d’une structure encodant la sémantique du

langage et simplifiant les traitements futurs

131
 Structure des arbres de syntaxe
abstraits
• En ANTLR un arbre de syntaxe abstrait :
– Est composé de nœuds
– Ces nœuds peuvent avoir de 0 à n fils
– Les étiquettes associées aux nœuds sont des lexèmes
– Rq : à partir des lexèmes, possibilité de récupérer le texte associé et
donc de l’interpréter

• Construction d’un AST

– ^(Token son1 son2)
• Token est l’étiquette de l’AST
• son1 et son2 sont des sous arbres
• Rq : si son1 et / ou son2 sont des lexèmes, ils sont automatiquement convertis
en AST
– ^(ast1 son1 son2)
• Construit un AST en ajoutant les sous arbres son1 et son2 à l’AST désigné par
ast1

132
Exemples d’arbres de syntaxe abstraits
+ • Arbre correspondant à l’expression 3+4*5
• Encode la priorité des opérateurs
3 *
• Notation en ANTLR
4 5 – ^(‘+’ 3 ^(‘*’ 4 5))

VARDEF • Arbre correspondant à la déclaration d’une

variable i de type int
int i
• VARDEF est un lexème « imaginaire »
• Non présent dans la grammaire
• Ajouté pour donner une sémantique
• Notation en ANTLR
– ^(VARDEF ‘int’ i)

133
 Construction d’arbres de syntaxe abstraits
à partir de règles de réécriture
• Manière recommandée de construire des arbres de syntaxe
abstraits (AST)

• Notation :
rule : « alt1 » -> « créer-ceci-suivant-alt1 »
| « alt2 » -> « créer-ceci-suivant-alt2 »
…
| « alt2 » -> « créer-ceci-suivant-alt2 »
;

• Remarques :
– les règles peuvent générer 1 AST ou une liste d’AST
– Par défaut : génération d’une liste d’AST correspondant aux éléments
de la règle (si omission de l’opérateur -> )

134
 Exemples simples
• stat: 'break' ';' -> 'break‘
– Renvoie un AST composé d’un nœud avec l’étiquette ‘break’
– Supprime le ‘;’

• decl : 'var' ID ':‘ type -> type ID ;

• type : ‘int’ | ‘float’
– Renvoie deux AST contenant le type (int ou float) et l’identifiant
– L’utilisation de type dans la production réfère à l’AST produit par la
règle type
– Rq : réordonne les éléments lus

• decl : ‘var’ ID ‘:’ type -> ^(VARDEF type ID)

– Renvoie un AST avec comme racine le lexème VARDECL
– Et comme fils l’AST renvoyé par type et un AST contenant le token ID

135
 Les lexèmes ‘imaginaires’
• La règle précédente :
– decl : ‘var’ ID ‘:’ type -> ^(VARDEF type ID)
– Utilise un lexème nommé VARDEF
– Ce lexème
• n’a pas d’expression régulière associée
• n’est pas présent dans la grammaire
• Est ajouté pour donner de la sémantique à une opération

• Déclaration des lexèmes ‘imaginaires’

– Sous la description des options, ajouter :
tokens
{
VARDEF ;
IM2 ; // Un autre lexème imaginaire…
}

136
 AST et règles de réécriture
• Collecte d’une suite d’éléments
– list : ID (',' ID)* -> ID+
• Retourne la liste des AST correspondant aux identifiants ID
– formalArgs : formalArg (',' formalArg)* -> formalArg+
• Retourne la liste des AST retournés par la règle formalArg
– decl : 'int' ID (',' ID)* -> ^('int' ID+) ;
• Retourne un AST avec ‘int’ comme étiquette et un ensemble de fils
correspondant à la liste des identifiants
– compilationUnit : packageDef? importDef* typeDef+
-> ^(UNIT packageDef? importDef* typeDef+) ;
• Retourne un AST ayant comme étiquette UNIT
• Un fils optionnel contenant l’AST retourné par packageDef
• Une suite de 0 à n fils contenant les AST retournés par importDef
• Une suite de 1 à n fils contenant les AST retournés pas typeDef

137
 AST et règles de réécriture
• Duplication de nœuds et d’arbres
– dup : INT -> INT INT ;
• Retourne deux AST désignant le même lexème
– decl : 'int' ID (',' ID)* -> ^('int' ID)+ ;
• Retourne 1 à n AST ayant ‘int’ pour étiquette et un AST contenant
le token ID comme fils
– decl : type ID (',' ID)* -> ^(type ID)+ ;
• Retourne 1 à n AST en duplicant l’AST retourné par type et en
ajoutant ID comme fils
– decl : modifier? type ID (',' ID)* -> ^(type modifier? ID)+ ;
• Retourne 1 à n AST comme dans la règle précédente mais ajoute
l’AST retourné par modifier comme sous arbre si celui-ci est
présent

138
 AST et règles de réécriture
• Choix des arbres en fonction de conditions
– Possibilité d’ajouter des conditionnelles en tête des
règles de réécriture
– Choix de la règle en fonction du résultat de la
conditionnelle

a[int which] : ID INT -> {which==1}? ID

-> {which==2}? INT
-> // Rien : pas d’arbre
;

139
 AST et règles de réécriture
• Possibilité d’utiliser des labels dans les règles de réécriture

– decl : ‘var’ i=ID ‘:’ t=type -> ^(VARDEF $t $i)

• i désigne la valeur de retour de ID
• t désigne la valeur de retour de t
• $i et $t sont utilisés pour construire l’arbre

– prog: main=method others+=method*

-> ^(MAIN $main) $others* ;
• main désigne la valeur de retour de method
• others est une liste des valeurs (opérateur +=) de retour de method*
• Produit une liste d’AST, le premier ayant pour racine MAIN les autres
les AST correspondant à method*

140
 AST et règles de réécriture
• Règles de réécriture dans les sous-règles
Ifstat :
'if' '(' equalityExpression ')' s1=statement
('else' s2=statement -> ^('if' ^(EXPR equalityExpression) $s1 $s2)
| -> ^('if' ^(EXPR equalityExpression) $s1)
)
;
– Retourne deux arbres différents en fonction de la présence de ‘else’
– La présence du ‘else’ indique la règle de réécriture à utiliser

141
 AST et règles de réécriture
• Parfois une simple réécriture n’est pas suffisante
– Exemple
+
expr : INT ('+’ INT)*
À l’analyse de 1+2+3 nous souhaitons générer + 3
^(’+’ ^(’+’ 1 2) 3)
1 2

• Il faut construire l’arbre itérativement

– expr : (INT -> INT) ('+' i=INT -> ^('+' $expr $i) )* ;
• Où $expr réfère au dernier AST construit dans la règle expr

142
 Comment utiliser un AST
• Par défaut, ANTLR utilise
– org.antlr.runtime.tree.CommonTree pour représenter les AST
– org.antlr.runtime.Token pour représenter les lexèmes

• Lorsque les AST sont générés, les types de retour des règles
contiennent une méthode getTree() renvoyant l’AST
– Attention l’arbre est renvoyé via une référence sur Object
– (CommonTree)valRet.getTree() pour convertir en CommonTree
– Pas très beau mais possibilité d’inclure ses propres classes d’AST
• Cf. livre sur ANTLR
The Definitive ANTLR Reference: Building Domain-Specific Languages
Terence Parr, ISBN: 978-0-9787-3925-6

143
 org.antlr.runtime.tree.CommonTree
• Manipulation du lexème associé à l’arbre
– Token getToken()
• Récupération du lexème
– int getType()
• Récupération du type du lexème

• Manipulation des fils

– int getChildCount()
• Nombre de fils
– Tree getChild(int i)
• Fils à partir de son index
– List getChildren()
• Liste des fils
– Tree getFirstChildWithType(int type)
• Le premier fils d’un type donné

144
 Conclusion
• ANTLR est un outils puissant
– Description des grammaires LL(*) en EBNF
– Paramètres et valeurs de retour pour les règles
– Association de code aux règles
– Gestion des arbres de syntaxe abstraits
– Règles de réécriture
– Simple d’utilisation étant donné sa puissance… 

• Ne faites plus d’analyse à la main

– ANTLR est votre ami…
– Fichiers de configuration, lecture de fichiers structurés
– Interaction avec des langages de script

• Utilisez les arbres de syntaxe abstraite

– Ex : multiplicité des langages de description de géométrie pour la 3D
– Plusieurs analyseurs mais 1 seul AST… i.e. une seule phase de génération par
analyse de l’AST
145
 Pour aller plus loin…

The Definitive ANTLR Reference: Building Domain-Specific Languages

Terence Parr, ISBN: 978-0-9787-3925-6

• Une description complète de ANTLR

• Le contenu détaillé de cette partie du cours
• Autres informations :
– Gestion des erreurs
– Utilisation des patrons pour la réécriture
– …

146
Compilation

147
 La compilation
• Un compilateur est un programme informatique qui traduit un
langage, le langage source, en un autre, appelé le langage cible, en
préservant la sémantique du texte source

• Traduction d’un langage en instructions machines

– Ex : C / C++

• Traduction d’un langage de haut niveau vers un autre

– Ex : Traduction de Pascal en C

• Traduction d’un langage quelconque vers un langage quelconque

– Ex : Word vers html, pdf vers ps

• Rq: Un langage décrit une information structurée

– Utile dans tous les domaines
148
 Compilation : recontre GL / OS
• Langage de programmation
– impératifs génie logiciel…
• …lisibilité
• …maintenabilité
• …orientation métier

• Langage d'exécution – impératifs système

d'exploitation…
– …gestion des ressources
149
 GL vs OS

GL OS

Structures de données, tableaux, objets… Mémoire plate, hiérarchie de mémoire

(registres, caches, mémoire vive, swap)
Structures de contrôle, boucles, goto L, ifz R goto L, pipe-line,
itérateurs… branchement spéculatif…
Types de données, classes, héritage 1, 8, 16, 32, 64 bits…

Introspection du code Programme ~ données

150
 Les compilateurs
• Un logiciel parmi les plus sûrs
– Composantes très automatisées
• Analyse lexicale, syntaxique
– Des composantes bien formalisées
• Analyse sémantique, analyse statique
– Une approche très régulière
• Génération de code

• La compilation
– Une théorie qui marche
– NB : ce qui est théorisé marche le mieux…

151
Qu’est-ce qu’un compilateur ?

152
153
 Programme source

Front end
Analyse lexicale

Suite de tokens
Analyse syntaxique
Arbre de syntaxe abstraite
Analyse sémantique
Table des
Arbre de syntaxe abstraite enrichi Erreurs
symboles
Génération de code
intermédiaire
Code intermédiaire (ex. code 3 adresses)
Middle end
Optimisation de code
Code intermédiaire optimisé
Back end
Génération de code

Code objet

154
 Chaine de compilation
• Analyse lexicale
– Découpe du texte en petits morceaux appelés jetons
(tokens)
– Chaque jeton est une unité atomique du langage
• Mots clés, identifiants, constantes numériques…
– Les jetons sont décrits par un langage régulier
• Détection via des automates à état finis
• Description via des expression régulières

• Le logiciels effectuant l’analyse lexicale est appelé

analyseur lexical ou scanner

155
 Chaine de compilation
• Analyse syntaxique

– Analyse de la séquence de jetons pour identifier la structure

syntaxique du langage

– S’appuie sur une grammaire formelle définissant la syntaxe du

langage

– Produit généralement un arbre syntaxique qui pourra être

analysé et transformé par la suite

– Détection des erreurs de syntaxe

• Constructions ne respectant pas la grammaire

156
 Chaine de compilation
• Analyse sémantique
– Ajout d’information sémantique à l’arbre d’analyse
– Construction de la table des symboles
• Ex : noms de fonction, de variables etc…
– Réalise des vérifications sémantiques
• Vérification de type
• Vérification de la déclaration des variables, des fonctions
• Vérifie que les variables sont initialisées avant utilisation
• …
– Emission d’erreurs et / ou d’avertissements
– Rejet des programmes « incorrects »

157
 Chaine de compilation
• Génération de code intermédiaire
– Code indépendant de la machine cible
– Généralement : utilisation du code 3 adresses
• Nombre « infini » de registres

int main(void) i := 0 ; assignment

{ L1: if i >= 10 goto L2 ; conditional jump
int i; t0 := i*i
int b[10]; t1 := &b ; address-of operation
for (i = 0; i < 10; ++i) t2 := t1 + i ; t2 holds the address of b[i]
{ b[i] = i*i; } *t2 := t0 ; store through pointer
} i := i + 1
goto L1
L2:
158
 Chaine de compilation
• Optimisation de code
– Accélération du programme
– Suppression des calculs inutiles
– Elimination des sous expressions communes
– Propagation des copies
– Propagation des constantes
– Extraction des calculs invariants
– Elimination de code mort
– Inlining
– …
• Transforme le code mais ne change pas sa sémantique
• La première optimisation est algorithmique !
– Un compilateur ne changera pas votre algorithme…

159
 Chaine de compilation
• Génération de code
– Transformation du code intermédiaire en code machine
– Connaissance des particularités du processeur
• Nombre de registres
• Utilisation du jeu d’instruction du processeur
– Ex : instructions vectorielles de type SSE
• Ordonnancement des instructions

• La seule phase réellement dépendante du processeur

• Possibilité d’avoir des compilateurs multi-cible

– La différence réside dans la génération de code

160
 Avantage de la structuration
front / middle / back end
• Front end
– Dépendant du langage source
– Un front end par langage
• Back end
– Transforme le code intermédiaire (IR) en langage cible
– Un back end par langage cible
• Ex : IR -> assembleur x86-64, IR -> assembleur ARM etc…
• Middle end
– Produit une IR optimisée à partir d’une IR
– L’IR est indépendante du langage source et du langage cible !

• En conclusion :
– Au tout départ, N langages sources et M langages cibles = NxM développements de
compilateurs
– Compilateurs modernes, N langages sources et M langages cibles = production de N front ends
et M back ends i.e. N+M développements et réutilisation du middle end !

161
 Un compilateur moderne : LLVM
• Front ends pour Ada, C, C++, D, Delphi, Haskell, Julia,
Objective-C, Rust, swift…

• Back ends pour IA-32, x86-64, ARM, Qualcom hexagons

(DSP), MIPS, Nvidia parallel thread execution (cartes
graphiques), Power PC etc…

• IR : un assembleur portable de haut niveau (plus évolué

que du code 3 adresses mais avec des propriétés similaires)
– Plusieurs dizaines de passes d’analyse et de transformation déjà
fournies
– Ex : suppression de code mort, inlining, vectorisation…

162
Analyse sémantique

GRAMMAIRES À ATTRIBUTS

163
 Introduction
• Analyse syntaxique
– Permet de vérifier que les mots appartiennent à la grammaire
– Ne présume en rien des propriétés sémantiques du langage

• Les grammaires à attributs

– Prise en compte de la sémantique du langage
– Réalisation de calculs dirigés par la syntaxe
• Calculatrice : évaluer le résultat en cours d’analyse
• Langage : est-ce que les variables sont déclarées avant d’être utilisées
?
• Construction de l’arbre de syntaxe abstraite
• …

164
 Notion d’attribut
• Pour tout symbole terminal ou non terminal de la grammaire
– On associe zéro, un ou plusieurs attributs
– Un attribut est une information jugée utile en cours du processus de
compilation
• Valeur, type de donnée, numéro de ligne, de colonne dans le fichier source…
– L’attribut est définit par un nom et un type (le type de la donnée qu’il porte)

• En se plaçant dans le contexte de l’arbre de dérivation syntaxique,

distinction de deux types d’attributs:
– Les attributs synthétisés
• Passés du nœud fils vers les nœuds parents
– Les attributs hérités
• Passés du nœud parent vers les nœuds fils
– Rq : Un nœud et ses fils correspondent à une règle
• Nœud père = partie gauche de la règle
• Nœuds fils = partie droite de la règle

165
 Règles sémantiques
• On associe à chaque règle de production une
règle sémantique

• Une règle sémantique est une fonction

associée à une production syntaxique

• Elle est exécutée lorsque la production est

effectuée i.e. lorsque la règle est utilisée
166
 Exemple de grammaire attribuée
Règles de production Règles sémantiques

1. Exp -> (- Exp Exp) 1. Exp.v = Exp1.v – Exp2.v

2. Exp -> (+ Exp Exp) 2. Exp.v = Exp1.v + Exp2.v
3. Exp -> (* Exp Exp) 3. Exp.v = Exp1.v * Exp2.v
4. Exp -> (/ Exp Exp) 4. Exp.v = Exp1.v / Exp2.v
5. Exp -> nb 5. Exp.v = valeur(nb)
On associe un attribut numérique nommé v à Exp
 Permet d’évaluer l’expression en cours d’analyse
Note : Exp1 et Exp2 sont utilisés pour différencier les
occurrences du non terminal Exp
167
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
Exp.v=Exp1.v+Exp2.v
v=20

( + Exp Exp )
Exp.v=Exp1.v*Exp2.v
v=2 v=10

nb ( * Exp Exp )
v=2 v=5

nb nb

168
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
v=? v=?

169
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
v=? v=?

170
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
v=2 v=?

Exp.v = valeur(nb)
nb

171
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
v=2 v=?

nb ( * Exp Exp )
v=? v=?

172
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
v=2 v=?

nb ( * Exp Exp )
v=? v=?

173
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
v=2 v=?

nb ( * Exp Exp )
v=2 v=?

Exp.v = valeur(nb)
nb

174
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
v=2 v=?

nb ( * Exp Exp )
v=2 v=5

nb nb

175
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
v=?

( + Exp Exp )
Exp.v=Exp1.v*Exp2.v
v=2 v=10

nb ( * Exp Exp )
v=2 v=5

nb nb

176
 Exemple de grammaire attribuée
• Texte en entrée : (+ 2 (* 2 5))
Exp
Exp.v=Exp1.v+Exp2.v
v=12

( + Exp Exp )
Exp.v=Exp1.v*Exp2.v
v=2 v=10

nb ( * Exp Exp )
v=2 v=5

nb nb

177
 Grammaires attribuées
• Dans l’exemple précédent, les attributs sont
synthétisés
– Les attributs du nœud parent dépendent des
attributs des nœuds fils

• Il est aussi possible de mixer attributs hérités

et synthétisés
– Ex : déclaration / utilisation de variable

178
 Exemple déclaration /utilisation
Règles de production Règles sémantiques

• S -> (Decl | Use)* • {Use.ts = Decl.ts ; S.ok = Use.ok}

• Decl -> d ; Decl • {Decl.ts = {d.decl} U Decl1.ts}
• Decl -> d • {Decl.ts = {d.decl}}
• Use -> u ; Use • {Use1.ts = Use.ts,
Use.ok = u.use Use.ts Use1.ok}
• Use -> u • {Use.ok = u.use Use.ts}

Attribut ts : Ensemble des symboles déclarés

Attribut ok : Vrai si les symboles utilisés ont tous été déclarés
Attribut decl : Le symbole déclaré
Attribut use : Le symbole utilisé

179
 Exemple déclaration /utilisation
Règles de production Règles sémantiques

• S -> (Decl | Use)* • {Use.ts = Decl.ts ; S.ok = Use.ok}

• Decl -> d ; Decl • {Decl.ts = {d.decl} U Decl1.ts}
• Decl -> d • {Decl.ts = {d.decl}}
• Use -> u ; Use • {Use1.ts = Use.ts,
Use.ok = u.use Use.ts Use1.ok}
• Use -> u • {Use.ok = u.use Use.ts}

Attribut ts : Hérité et synthétisé

Attribut ok : Synthétisé
Attribut decl : Synthétisé
Attribut use : Synthétisé

180
 Exemple déclaration /utilisation

S { ok = …}

Decl { ts={x,y} } Use { ts={x,y}, ok=… }

d { decl=x } Decl { ts={y} } u { use=…} Use { ts={x,y}, ok=…}

d {decl=y} u { use=…} Use { ts={x,y}, ok=…}

u { use=…}

181
 Exemple déclaration /utilisation

S { ok = …}

Decl { ts={x,y} } Use { ts={x,y}, ok=… }

d { decl=x } Decl { ts={y} } u { use=…} Use { ts={x,y}, ok=…}

d {decl=y} u { use=…} Use { ts={x,y}, ok=…}

u { use=…}

182
 Evaluation des attributs
• Deux difficultés

– Possibles dépendances circulaires entre règles

sémantiques

– Difficulté d’entrelacer (dans la mise en œuvre)

• Construction de l’arbre
• Création des instances d’attributs
• Evaluation des règles sémantiques

183
 Dépendances circulaires
• A B C {B.x = C.x ; C.y = B.y}
• B b {B.y = b.text}
• B ε {B.y = B.x}
• C ε {C.x = C.y} A

B{xy} C{xy}

b { text } ε
184
 Dépendances circulaires
• A B C {B.x = C.x ; C.y = B.y}
• B b {B.y = b.text}
• B ε {B.y = B.x}
• C ε {C.x = C.y} A

B{xy} C{xy}

ε ε
185
 Détecter la circularité
Après construction de l’arbre
• Algorithme de tri topologique
– Entrée : Toutes les instances d’attributs, ensemble A

– Sortie : Un ordre total < sur A, tel que

• Rq : se lit a est dépendant de a’

– Si l’ordre total ne peut pas être produit : échec
(lié à des dépendances circulaires)
– Rq : l’ordre total n’est pas forcément unique

• Complexité : O(Card(A))

186
 Détecter la circularité
Après construction de l’arbre
• Semble efficace

• Mais…
– … que faire en cas d’échec de l’analyse ?
• Echec dû à une grammaire mal formée
– Cela ne regarde pas l’utilisateur final !

Il faut détecter la circularité en amont

187
 Détecter la circularité
Avant la construction de l’arbre
• Ne doit pas dépendre du mot en entrée

• Il faut monter que

– le graphe de dépendance produit par
l’analyse de m ne contient pas de cycle

• Algorithme de Knuth (1968) et variantes

– Idée : représenter la fermeture transitive des
dépendances connues de chaque non terminal
– Complexité exponentielle : en pratique, non utilisable.
188
 Critères de non-circularité
• Distinguer les attributs synthétisés et hérités
• Synthétisés
–
• Hérités
–
–
• Tête = partie gauche de la règle, corps = partie
droite
189
 Critères de non circularité
• Si synthétisé seulement
 Pas de circularité
– Ex : YACC

• Si hérité et synthétisé
 Risque de circularité

• Si hérité et synthétisé, mais héritage seulement

 Pas de circularité

190
 Bilan des tests de non circularité
• Tri topologique
– Grammaire attribuée et mot connus

• Algorithme de Knuth
– Grammaire attribuée connue
– Conclusion pour tout mot

• Critères de non-circularité
– Sous-langage de Grammaire attribuée connu
– Conclusion pour toute Grammaire attribuée du sous-
langage et tout mot

191
 Méthodologie des grammaires
attribuées : étude
• Identifier ce qu'on veut calculer

• Élaborer des cas d'étude

• Tracer les arbres de syntaxe

• Imaginer la circulation de l'information nécessaire au calcul

• Définir les attributs qui opèrent la circulation

• Les identifier comme synthétisés ou hérités

192
 Méthodologie des grammaires
attribuées : réalisation
• Lister les attributs synthétisés

• Lister les attributs hérités

• Définir les règles sémantiques

• Faire attention aux initialisations

• Tester la non-circularité

193
 Mise en œuvre en ANTLR
• A ributs synthé sés ≡ résultat d’appel de
fonction

– Toute règle peut produire un résultat ≡ a ributs

synthétisés

– Exemple
expr returns [int v] : term '+' expr
{$v = $term.v + $expr.v} ;

194
 Mise en œuvre en ANTLR
• A ributs hérités ≡ paramètres d'appel de
procédure

– Toute règle peut dépendre de paramètres ≡ a ributs

hérités

– Exemple
expr [TS ts] returns [int v] :
term [ts] '+' expr [ts] {$v = $term.v + $expr.v} ;

Note : ts représente une table des symboles contenant (entre

autres) toutes les variables déclarées dans le contexte

195
 Construction de l’arbre vs évaluation
• Analyse par descente récursive

– Chaque règle ≡ procédure

– Expansion ≡ appel de procédure

• Héritage d’attributs

– Réduc on ≡ retour de procédure

• Synthèse d’attributs

• Entrelacement possible, mais...

…Attention à la circularité !!!
196
 Stratégie recommandée
• Limiter l’usage des attributs de la grammaire
– Construction arbre de syntaxe abstraite (ASA)
– Contrôles syntaxiques simples

• Programmer des passes d’analyse sur l’ASA

pour des calculs plus sémantiques
– Utilisation de visiteurs sur l’ASA
• Possibilité d’ajouter des attributs
• Eventuellement d’en supprimer si devenus inutiles
– Transformations de l’ASA éventuellement possibles
• Réécritures ne changeant pas la sémantique

197
 Conclusion
• La grammaire attribuée est l'outil de base pour les
calculs dirigés par la syntaxe

• Penser global – agir local

• Concevoir en termes de
– Grammaire abstraite
– Attribut synthétisé/hérité

S'adapter dans un second temps

selon la mise en oeuvre

198
ANALYSE SEMANTIQUE

199
Limites des grammaire algébriques
• Comment prévenir la définition multiple d’une même
fonction ?

• Comment différencier des variables de type différent ?

• Comment s’assurer qu’une classe implémente toutes

les méthodes d’une interface ?

• Etc…

 Seule, une grammaire ne peut pas tout vérifier…

200
 Analyse sémantique
• Objectif : assurer que le programme a un sens

• Vérification de propriétés non captées par l’analyse lexicale et

syntaxique
– Les fonctions utilisées sont bien définies
– Les variables sont déclarées avant leur utilisation
– Les variables sont initialisées avant leur utilisation
– Deux variables de même identifiant ne sont pas déclarées dans le
même contexte
– Les expressions ont un type correct
– …

• Une fois l’analyse sémantique terminée, nous savons que le

programme est correct

201
 Challenges
• Rejeter le plus grand nombre de programmes
incorrects

• Accepter le plus grand nombre de

programmes corrects

• Le faire rapidement…

202
Analyse sémantique : implémentation
• Grammaires à attributs
– Augmenter les règles pour faire la vérification durant le parsing
• Complexe et peu lisible
• Peu modulaire et extensible

• Parcours récursif de l’arbre de syntaxe abstraite (ASA)

– Construire l’ASA avec une grammaire à attributs
– Ecrire des passes parcourant l’ASA
• Synthèse d’information
• Vérifications (déclarations, existance, typage…)
• Transformations préservant la sémantique
• …
– Approche plus modulaire, extensible… A privilégier…

203
 Overview du chapitre
• Vérification de portée
– Comment dire à quoi réfère un identifiant ?
– Comment stocke-t-on cette information ?

• Vérification de type
– Comment dire si des expressions ont le bon type ?
– Comment dire si les fonctions ont des paramètres
valides ?

204
Analyse sémantique

TABLE DES SYMBOLES

205
 Qu’est qu’un symbole ?
• Le même symbole dans un programme peut faire
référence à des choses totalement différentes.
– Ex en java:

public class A
{
char A;
A A(A A)
{
A.A = ‘A’
return A( (A) A ) ;
}
}

206
 Qu’est qu’un symbole ?
• Le même symbole dans un programme peut faire
référence à des choses totalement différentes.
– Ex en java:

public class A
{
char A;
A A(A A)
{
A.A = ‘A’
return A( (A) A ) ;
}
}

207
 Notion de portée
• La portée d’une entité est l’ensemble des endroits dans
un programme où le symbole associé à l’entité réfère à
cette entité

• L’introduction d’une nouvelle entité dans un contexte

peut cacher des entités préalablement visibles
– Ex : une variable locale peut cacher un paramètre de
fonction

• Comment savoir à tout instant ce qui est visible et à

quoi un symbole réfère ?
208
 Table des symboles
• La table des symboles est une association entre un
symbole et l’entité à laquelle il réfère

• En cours d’analyse sémantique la table des symboles

est continuellement mise à jour pour savoir ce qui est à
portée

• Questions :
– A quoi cela ressemble-t-il ?
– Quelle opération doit-elle définir ?
– Comment l’implémenter ?

209
 Table des symboles : intuition
01: int x = 137;
02: int z = 42;
03: int function(int x, int y)
04: {
05: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
06: {
07: int x, z;
08: z=y;
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

210
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y)
04: {
05: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
06: {
07: int x, z;
08: z=y;
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

211
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
06: {
07: int x, z;
08: z=y;
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

212
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
06: {
07: int x, z; x 03
08: z=y; y 03
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

213
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
06: {
07: int x, z; x 03
08: z=y; y 03
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

214
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z=y; y 03
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

215
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z=y; y 03
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

216
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z=y; y 03
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

217
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x=z;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

218
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

219
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

220
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: } y 11
19: }

221
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x<<", "<<y<<", "<<z<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: } y 11
19: }

222
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: } y 11
19: }

223
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; x 07
14: }
15: std::cout<<x<<", "<<y<<", "<<z<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: } y 11
19: }

224
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; x 07
14: }
15: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: } y 11
19: }

225
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; x 07
14: }
15: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; z 07
16: }
17: std::cout<<x<<", "<<y<<", "<<z<<std::endl;
18: }
19: }

226
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; x 07
14: }
15: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl; z 07
16: }
17: std::cout<<x@07<<", "<<y@03<<", "<<z@07<<std::endl;
18: }
19: }

227
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z; x 03
08: z@07=y@03; y 03
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl;
14: }
15: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl;
16: }
17: std::cout<<x@07<<", "<<y@03<<", "<<z@07<<std::endl;
18: }
19: }

228
 Table des symboles : intuition
Symbole Ligne
01: int x = 137;
02: int z = 42; x 01
03: int function(int x, int y) z 02
04: {
05: std::cout<<x@03<<", "<<y@03<<", "<<z@02<<std::endl;
06: {
07: int x, z;
08: z@07=y@03;
09: x@07=z@07;
10: {
11: int y=x@07;
12: {
13: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl;
14: }
15: std::cout<<x@07<<", "<<y@11<<", "<<z@07<<std::endl;
16: }
17: std::cout<<x@07<<", "<<y@03<<", "<<z@07<<std::endl;
18: }
19: }

229
 Remarque
• Dans l’exemple précédent
– La table contient les déclarations de variables
– Les numéros de ligne de déclaration

• De façon usuelle
– La table contient tous les symboles (variables,
fonctions…)
– Le type de l’entité associée au symbole
– D’autres informations utiles à la compilation…

230
 Implémentation 1 : pile
• Une implémentation typique : une pile le tables de correspondance

• Chaque table correspond à un contexte (bloc, fontion…)

• La pile permet de facilement gérer l’entrée et la sortie d’un contexte

• Les opérations :
– Entrée dans un contexte : push d’une nouvelle table
– Sortie d’un contexte : pop de la table en sommet de pile
– Insertion de symbole : ajout d’une entrée dans la table en sommet de pile
– Recherche d’un symbole : parcours des tables depuis le sommet de la pile (du
plus récent au plus ancien) pour rechercher la première occurrence du
symbole

231
Utilisation de la table des symboles
• Pour traiter une portion de programme qui crée un contexte (bloc,
déclaration de fonction, déclaration de classe…)
– Entrer dans un nouveau contexte
– Ajouter toutes les déclarations de variables dans la table
– Traiter le corps du block / de la fonction / de la classe
– Sortir du contexte

• Avec cette structure de données, la table n’est généralement pas

conservée mais construite/détruite en cours de parcours de l’ASA

• La plupart des analyses sémantiques sont définies comme une passe

récursive de ce type sur l’ASA

232
 Une autre vision
01: int x;
02: int y;
03: int function(int x, int y)
04: {
05: int w,z;
06: {
07: int y;
08: }
09: {
10: int w;
11: }
12: }

233
 Une autre vision
Global
01: int x;
x 01
02: int y;
03: int function(int x, int y) y 02
04: {
05: int w,z;
06: {
07: int y;
08: }
09: {
10: int w;
11: }
12: }

234
 Une autre vision
Global
01: int x;
x 01
02: int y;
03: int function(int x, int y) y 02
04: {
function
05: int w,z;
x 03
06: {
y 03
07: int y;
08: }
09: {
10: int w;
11: }
12: }

235
 Une autre vision
Global
01: int x;
x 01
02: int y;
03: int function(int x, int y) y 02
04: {
function
05: int w,z;
x 03
06: {
y 03
07: int y;
08: } Bloc 04-12
09: { w 05
10: int w;
z 05
11: }
12: }

236
 Une autre vision
Global
01: int x;
x 01
02: int y;
03: int function(int x, int y) y 02
04: {
function
05: int w,z;
x 03
06: {
y 03
07: int y;
08: } Bloc 04-12
09: { w 05
10: int w;
z 05
11: }
12: } Bloc 06-08
y 07

237
 Une autre vision
Global
01: int x;
x 01
02: int y;
03: int function(int x, int y) y 02
04: {
function
05: int w,z;
x 03
06: {
y 03
07: int y;
08: } Bloc 04-12
09: { w 05
10: int w;
z 05
11: }
12: } Bloc 06-08 Bloc 09-11
y 07 w 10

238
 Implémentation 2 : spaghetti stacks
• La table des symbole est un arbre de tables de
correspondances (associées à des contextes)

• Chaque contexte possède un pointeur sur le contexte

englobant

• En chaque point du programme, la table des symboles

apparait comme une pile
 Mêmes propriétés que la première implémentation

• Mais : peut être stockée et calculée une et une seule fois!

239
ANALYSE SEMANTIQUE

VERIFICATION DE TYPE

240
 Qu’est ce qu’un type ?
• Définition sujette à débat…

• Dénote d’un groupement de valeurs

• Et d’un ensemble d’opérations sur ces dernières

• Les erreurs de type arrivent quand les opérations

sont effectuées sur des valeurs ne les supportant
pas

241
 Types de vérification de type
• Vérification de type statique
– Analyse effectuée au moment de la compilation
– Prouve l’absence d’erreur avant l’exécution

• Vérification de type dynamique

– Vérification des opérations en cours d’exécution
– Plus précis que la vérification statique mais
souvent bien moins efficace

242
 Les systèmes de typage
• Les systèmes de typage forts
– N’autorisent jamais une erreur de typage
– Ex: Java, Python, ADA, Haskell…

• Les systèmes de typage faible

– Autorisent des erreurs de typage à l’exécution
– Ex: C
• Ex : manipulation des pointeurs, débordements, cast…

243
 La guerre des types
• Débat sans fin sur le meilleur système de typage

• Les systèmes de typage dynamique facilitent le

prototypage, les systèmes de typage statique ont
moins de bugs

• Les langages fortement typés sont souvent plus

robuste, les faiblement typés sont souvent plus
rapides…

244
 Ingrédients du typage
• Un langage de termes

• Un langage de types

• Un système de typage
– Quel type a quel terme ?

245
 Termes et types
• Les termes dénotent de valeurs
– On les évalue pour obtenir leur dénotation

• Les termes ont des types

• Evaluer ne change pas le type d’un terme

– Les types sont des invariants
 Vérification statique envisageable
246
 Langage de termes
• Les expressions élémentaires
– Constantes et variables
• "douze", "12", 12, 0x12, douze

• Les expressions composées

– Opérations, appels, accès structures, tableaux
• 0x12+12, douze(12), douze.XII, douze[12]

• Les fonctions, procédures

• Les programmes…
247
 Langage de types
• Pas forcément explicite dans le langage source
– Si explicite, on peut garder la syntaxe abstraite, sinon en
inventer une
– Situation intermédiaire possible

• Lisp, Scheme
– Complètement implicite
• ML, Javascript, Scala
– Explicite optionnel, tous les types ont une expression
• C, C++, Java
– Explicite obligatoire

248
 Langage de types

• Exemple avec des constructions classiques

– Langage procédural / fonctionnel

249
 Types atomiques
• bool, int, float, char…

• unit
– Type des termes avec une seule valeur possible
– Utile en fonctionnel pour des fonctions ne
renvoyant pas vraiment de valeur (void en C…).

• void
– Le type des termes avec valeur pas représentable
250
 Type tableau
• array(Ind, Val)
– Retourne un terme de type Val quand on l’indexe
avec un terme de type Ind

• Ex :
– en C, float t[12] dénote array(int, float)

251
 Le type fonction
• fun(From, To)
– Retourne un terme de type To
– Quand on l’appelle avec un terme de type From

• Ex : fun(float, int)
– En C : int f(float)
– En ML : int -> float

• Note : on pense à une fonction exécutable

– Pas nécessaire : mémoïsation
– Correspondance directe entre paramètre et résultat
(cache)

252
 Le type structure
• struct(A1:T1, …, Ai:Ti, …, An:Tn)
– Retourne un terme de type Ti
– Quand on lui applique le sélecteur Ai

• Ex: struct(i:int, f:float)

– En C : struct { int i; float f } ;

253
 Le type union
• union(A1:T1, …, Ai:Ti, …, An:Tn)
– Retourne un terme de type Ti
– Quand on lui applique le sélecteur Ai

• Différence avec structure ?

– Structure : tous les sélecteurs sont définis tout le temps
– Union : un seul sélecteur est défini à un moment donné

• Warning : un sélecteur mais lequel ???

– Ex : C++ : std::variant => union avec vérification de type à
l’exécution

254
 Le type pointeur
• ptr(A)
– Retourne un terme de type A
– Quand on le déréférence

• Ex : ptr(int)
– En C : int *

255
 Expressions de type
• En C
– struct list { char car ; struct list * suivant }
• Dénote
– list : struct(car:char, suivant:ptr(list))

• En ML
– (A->B)->(B->C)->(A->C)
• Dénote
– fun(fun(A,B), fun(fun(B,C), fun(A,C)))

256
 Curryfication
• fun(A, fun(B,C)) peut se lire fun(A,B,C)

• Il n’est pas nécessaire de prévoir un type de

fonction n-aire
– Ex : l’opérateur + sur les entiers : int X int -> int
• i.e. fun(int, int, int)
– Mais
• (A,B)->C A->(B->C)
– Donc + a le type fun(int, fun(int, int))

257
 Système de typage

• Un système logique reposant sur

– Des jugements
– Des axiomes
– Des règles de déduction

258
 Jugement de type
• t:T
– Le terme t a le type T

• Peut être manifestement vrai ou faux, ou

demander vérification
– 12.5 : int ?
– 12 : int ?
– f(12) : int ?

259
 Règles de déduction
• Forme générale d’une règle

 Si toutes les hypothèses sont vraies alors la conclusion l’est

• Axiome

 La conclusion est toujours vraie

260
 Notion d’arbre de preuve
• Arbre de preuve
– Nœuds : instances de règles de déduction
– Racine : un jugement à prouver

• Analogie avec l’arbre de dérivation

• Un arbre de preuve est une preuve ssi toutes ses

feuilles sont des axiomes

 Un système de déduction est une grammaire de preuve

261
 Système de typage

Système de typage
=
Règles de déduction dont les jugements sont
des types

262
 Axiomes
• Liés aux constantes

…
• Les variables

263
 Règles de déduction
• Tableau

• Fonction

LA règle de déduction de type

264
 Règles de déduction
• Structure

• Union

265
 Règles de déduction
• Pointeurs

266
 Quelques concepts
• Surcharge :

– Symboles de type différent mais de même nom

• + : fun(int, fun(int, int))
• + : fun(float, fun(float, float))
+, -, *, /, =, == sont des symboles très surchargés…

– Les langages acceptant la surcharge (java, c++

etc…) acceptent cela pour les fonctions définies
par l’utilisateur

267
 Quelque concepts
• Programme bien typé

– Un programme p est bien typé

si un jugement p : T peut être prouvé.

– Vérifier le bon typage d’un programme consiste à

chercher une preuve
• Dans les faits, c’est plus simple qu’il n’y parait (enfin…)

268
 Quelques concepts
• Vérification de type statique / dynamique

– Statique : la vérification de type est statique si elle est réalisée

sans exécuter le programme (i.e. par le compilateur)
• Ex : CAML, Scala

– Dynamique : la vérification se fait à l’exécution du programme

• Ex : Javascript

– Combinaison possible : une partie en statique, l’autre en

dynamique
• Ex : Java

269
 Quelques concepts
• Propriété du typage sain
– Un système de typage est dit sain (sound) si un
programme bien typé statiquement ne peut pas
causer d’erreur de type dynamique

Propriété recherchée mais rare

• Ex : CAML, ML, Scala

270
 Mise en œuvre
• En utilisant une grammaire attribuée
– Utiliser deux attributs
• Type : le type de l’expression
• Ok : vrai si pas d’erreur de typage, faux sinon
– Vérification en cours d’analyse syntaxique

• Sur un arbre de syntaxe abstraite

– Même principe, deux attributs associés aux nœuds de l’arbre
– Vérification après l’analyse syntaxique

• Attention : dans la « vraie » vie, il faut aussi pouvoir

émettre un message d’erreur pertinent… (avec numéro de
ligne…)

271
 Ex: mise en œuvre en GA (1/3)
• Attributs
– TS : table des symboles
• isFunction : permet de savoir si un symbole est une fonction
• type : retourne le type associé au symbole
– Ok : vrai si le typage est correct
– type : le type de l’expression

• Fonction utilisées
– to(FunctionType) => retourne ne type de retour de la
fonction
– from(FunctionType) => retourne le type du paramètre de
la fonction

272
 Ex: mise en œuvre en GA (2/3)
• expr -> Symbol ‘(‘ expr1 ‘)’
{
expr1.TS = expr.TS;
expr.ok = expr1.ok && expr.TS.isFunction(Symbol) &&
from(expr.TS.type(symbol))==expr1.type;
expr.type = to(expr.TS.type(symbol));
}

• expr -> var

{ var.TS=expr.TS; expr.type = var.type ; expr.ok = var.ok; }

• expr -> cstInt

{expr.type = cst.type; expr.ok = true; }

273
 Ex : mise en œuvre en GA (3/3)
• De manière schématique la partie droite de la
règle va apporter les hypothèses et la partie
gauche sera étiquetée avec la conclusion

– Si pas de règle de déduction applicable dans le

contexte

– Pas de jugement de type

Erreur de typage

274
 Pour aller plus loin…
• Dans certains langages
– Déclaration de type absentes en partie…
• Ex : fonction génériques / lambda fonctions en C++,
Java…
– …ou totalement
• Ex : CAML

Il faut reconstituer les déclarations en

analysant le programme : inférence de type
275
 Inférence de type
• Point de vue logique
– Polymorphisme
• Ex :
length est une fonction retournant la longueur d’une liste quel que
soit le type des éléments de cette liste
– Inférence
• f est utilisé dans f(x), on en déduit que

• Du point de vue opérationnel, on ajoute des variables

de type :
– où est une variable de type

276
 Retour sur l’exemple précédent
• expr -> Symbol ‘(‘ expr1 ‘)’
{
expr.ok = expr1.ok && expr.TS.isFunction(Symbol) ;
if (expr.ok
&& unifType(expr.TS.Type(Symbol),
makeFunction(Expr1.type, new varType)))
then {expr.type = varType}
else {expr.type=error; expr.ok=false}
}

277
 Procédure d’unification
• unifType( fun( int, int ), fun( int, var(A) ) )
– OK, var(A) <- int

• unifType( fun( int, int ), fun( var(V), var(A) ) )

– OK, var(V) <- int, var(A) <- int

• unifType( fun( int, float ), fun( var(A), var(A) ) )

– Not OK

• unifType( fun( var(X), var(X) ), fun( int, var(A) ) )

– OK, var(X) <- int, var(A) <- int

278
 Procédure d’unification
• unifType( fun(var(X), var(X)), fun(var(V), var(A)))
– OK, var(X) <- var(V), var(A) <- var(V)

• unifType( fun(var(X), var(Y)), fun(var(V), var(A)))

– OK, var(X) <- var(V), var(A) <- var(Y)

• unifType(fun(var(X), var(X)), fun(fun(var(A), var(A)), var(A)))

 L’unification dans le cas général est assez complexe à

réaliser

279
 Conclusion
• Le type est vu comme une propriété

• Typage bien modélisé par déduction logique

• Vérification = recherche de preuve

facile à réaliser en GA

• Inférence = recherche de témoin de preuve ( )

plus difficile, mais faisable

280
CODE INTERMÉDIAIRE

281
 La sortie du front-end
• Le programme lu appartient bien au langage
– Lexicalement
– Syntaxiquement
– Sémantiquement

• Il est représenté par un arbre de syntaxe abstraite

décoré
– Table des symboles
– Types
–…
282
 La production de code
• Etape 1 : produire du code intermédiaire pour une
large cible
– Viser des familles de machines cible
– Sans contrainte de ressources
• Registres sans limite
• Types de données sans restriction

• Etape 2 : traduire le code intermédiaire en code

exécutable pour une cible précise
– Registres en nombre limité
– Types de données : ceux de la cible
– Modes d’adressage spécifiques

283
Intérêt du code intermédiaire

3 frontend 3 frontend
4*3 optimiseurs 1 optimiseurs
4*3 générateurs de code 3 générateurs de code

284
Différents types de code intermédiaire
• Le code intermédiaire doit être facile à produire, facile à
transformer en code machine
– Une sorte d’assembleur universel
– Ne doit pas contenir de paramètres spécifiques à une machine / un
processeur

• La nature du code intermédiaire est souvent dépendante de

l’application
– AST, Quadruplets, triplets…

• Une forme communément utilisée : Static Single Assignment form

(SSA)
– Facilite la transformation de programme
– Ex : propagation de constantes…

285
Code intermédiaire

LE CODE 3 ADRESSES

286
 Code 3 adresses
• Les instructions sont très simples
• Il y a une cible, au plus deux sources et un opérateur
• Les sources peuvent être des variables, des registres ou des
constantes
• Les cibles sont des registres ou des variables

• Exemple : a+b*c-d/(b*c) se traduit en

t1 = b*c
t2 = a+t1
t3 = b*c
t4 = d/t3
t5 = t2-t4
287
 Représentations
Quadruplets Triplets
t1 = b*c op res arg1 arg2 op arg1 arg2
t2 = a+t1 * t1 b c 1 * b c
t3 = b*c
t4 = d/t3 + t1 a t1 2 + a (1)
t5 = t2-t4 * t3 b c 3 * b c
/ t4 d t3 4 / d (3)
- t5 t2 t4 5 - (2) (4)

- -

+ / + /

a d Graphe acyclique
a * d * orienté
b c b c *
Arbre de syntaxe abstraite b c
288
 Code 3 adresses : instructions
• Instructions avec assignation
– a=b
• Copie b dans a
– a = unop b
• applique l’opérateur unaire unop sur b et stocke le résultat dans a
• Ex : -, !, ~
– a = b biop c
• Applique l’opération biop avec b et c pour opérandes et stocke le résultat dans
a
• Ex : +, -, *, /, &, |, <, >
• Instructions de saut
– goto L : saut inconditionnel au label L
– if t goto L : si t est vrai sauter à L
– Note : sur le if, il peut y avoir beaucoup de variantes
• Ex : ifnz, ifz…

289
 Code 3 adresses : instructions
• Les fonctions
– func begin <name>
• Déclare le début de la fonction nommée <name>
– func end
• La fin de la fonction
– Return
• Retourne à la fonction appelante
– return a
• Retourne la valeur a à la fonction appelante
– param p
• Place la paramètre p sur la pile
– R = call <name> n
• Appelle la fonction <name> avec les n paramètres en sommet de pile

290
 Code 3 adresses : instructions
• Les tableaux
– a = b[i]
• Stocke la valeur de la ieme case du tableau b dans a
– b[i] = a
• Stocke la valeur de a dans la ieme case du tableau b

• Les pointeurs
– a = &b
• Stocke l’adresse de la variable b dans a
– (*a)=b
• Stocke la valeur de b à l’adresse désignée par a
– a = (*b)
• Stocke dans a la valeur à stockée l’adresse mémoire b

291
 Code 3 adresses : remarques
• Généralement les variables du code 3 adresses sont
– Les variables déclarées par l’utilisateur
– Eventuellement quelques variables ajoutées par une
transformation de code
 Toutes présentes dans la table des symboles

• Les résultats de calculs intermédiaires

– Stockés dans des registres
– Code 3 adresses : théoriquement une infinité de registres
– Généralement un registre stocke un seul résultat
• i.e. écrit une fois, lu n fois
 Facilite la transformations de code

292
Représentation intermédiaire

GÉNÉRATION DE CODE 3 ADRESSES

293
 Production de code 3A
• Entrée : un arbre de syntaxe abstraite
• Sortie : un code 3 adresses

+
R0 = x
R1 = 2
x * R2 = y
R3 = R1 * R2
2 y R4 = R0 +R3

294
 Stratégie générale
• Chaque nœud de l’arbre de syntaxe abstrait
– Produit des bribes de code selon un patron
prédéfini
• Sans avoir connaissance de ce que font les autres
nœuds
– Peut composer un nouveau code à partir des
codes des nœuds fils

• En utilisant une grammaire attribuée

– Code = attribut synthétisé
295
 Retour sur l’exemple
+

x *

2 y

296
 Retour sur l’exemple
+

x *
r0=x

2 y

297
 Retour sur l’exemple
+

x *
r0=x

2 y
r1=2

298
 Retour sur l’exemple
+

x *
r0=x

2 y
r1=2 r2=y

299
 Retour sur l’exemple
+

x *
r0=x r1=2
r2=y
r3=r1*r2

2 y
r1=2 r2=y

300
 Retour sur l’exemple
+
r0=x
r1=2
r2=y
r3=r1*r2
r4=r0+r3

x *
r0=x r1=2
r2=y
r3=r1*r2

2 y
r1=2 r2=y

301
Exemple de structure de contrôle
R0=a
if(a<b) R1=b
{ R2=R0<R1
ifz R2 goto false_label_0
b=3*a; R3=3
R4=a
} R5=R3*R4
b=R5
else goto end_if_label_1
{ false_label_0:
R6=3
a=3*b R7=b
R8=R6*R7
} a=R8
End_if_label_1:

302
 Remarques
• Le code généré est naïf
– Contient beaucoup de variables intermédiaires
(registres)
– Certains traitements sont « peu » utiles

• Des passes de transformation de code seront

utilisées pour réduire l’utilisation des registres
(entre autre)
– Propagation de copie, élimination de code mort…
– Algorithme d’allocation de registres

303
Code 3 adresses et runtime du langage
• Le langage source requiert des fonctionnalités
– Souvent codées directement dans le langage cible
– Lors de la production du code 3 adresses, utilisation de
fonctions au nom prédéfini
– Fonctions présentes dans la bibliothèque de runtime du langage

• Ex: l’opérateur new en C++

– Partie intégrante du langage
– Compilation en code 3 adresses
param size
R0 = call _new
– Le registre R0 contient l’adresse de la mémoire allouée

304
Transformation optimisantes

305
 Le challenge de l’optimisation
• Un bon optimiseur
– Ne doit pas changer le comportement observable du
programme
– Devrait produire un code intermédiaire aussi efficace que
possible
– Ne devrait pas prendre trop de temps de calcul

• Cependant
– Les optimiseurs ratent souvent des optimisations
« faciles » de part les limitations des algorithmes
– Presque toutes les optimisations intéressantes sont NP-
complètes voire indécidables…

306
 Que pouvons nous optimiser ?
• Temps d’exécution
– essayer de rendre le programme le plus rapide possible
– Souvent au détriment de la mémoire et de la consommation
énergétique

• L’occupation mémoire
– Essayer de minimiser l’occupation mémoire du code produit
– Souvent au détriment de la vitesse d’exécution et de la
consommation énergétique

• La consommation énergétique
– Essayer de réduire la consommation énergétique
– Souvent au détriment de la vitesse

307
Optimisation de code intermédiaire vs
optimisation de code
• La distinction n’est pas toujours claire…

• Typiquement:
– L’optimisation de code intermédiaire essaye de réaliser des
simplifications valables pour toutes les machines
– L’optimisation de code essaye d’améliorer les
performances en connaissant les spécificités de la machine
cible

• Parfois, des optimisations sont au milieu…

– Ex : remplacer x/2 par x*0.5

308
 Optimisations préservant la
sémantique
• Une optimisation conserve la sémantique si elle ne change
pas la sémantique du programme original

• Exemples
– Suppression de variables temporaires inutiles
– Calculer des valeurs qui sont connues au moment de la
compilation
• Ex : int a = 2*3 peut être remplacé par int a = 6
– Sortir des invariants de boucles

• Contre exemple
– Remplacer un tri à bulles par un quick sort…
• Ne préserve pas la sémantique du programme original

309
 Notion de bloc de base
• Un bloc de base est une séquence d’instructions
de code intermédiaire telle que
– Il y a exactement un point d’entrée à la séquence et
s’il y a un contrôle entrant dans la séquence, il entre
au début de cette dernière
– Il y a exactement un endroit où le contrôle quitte la
séquence et cet endroit est la fin de la séquence

 La séquence d’instruction s’exécute toujours en

groupe

310
 Graphe de flot de contrôle
• Un graphe de flot de contrôle est un graphe
contenant les blocs de base d’une fonction

• Un arc orienté signale que le contrôle peut

passer de la fin d’un bloc de base au début
d’un autre bloc de base

• Il y a un nœud dédié au début et à la fin de la

fonction
311
 Exemple : calcul de pgcd
R0 = call _readInt
a = R0
R1 = call _readInt
b = R1
loop:
R2 = a
R3 = b
R4 = R2 % R3
r = R4
ifz r goto end_if
R5 = a
b = R5
R6 = r
a = R6
goto loop
end_if:
param b
call _printInt

312
 Exemple : calcul de pgcd
Découpage en bloc de base
R0 = call _readInt
a = R0
R1 = call _readInt
b = R1
loop:
R2 = a
R3 = b
R4 = R2 % R3
r = R4
ifz r goto end_if
R5 = a
b = R5
R6 = r
a = R6
goto loop
end_if:
param b
call _printInt

313
 Exemple : calcul de pgcd
Graphe de flot de contrôle
R0 = call _readInt Start
a = R0 loop:
R1 = call _readInt R2 = a
b = R1 R3 = b
loop: R0 = call _readInt
a = R0 R4 = R2 % R3
R2 = a r = R4
R3 = b R1 = call _readInt
b = R1 ifz r goto end_if
R4 = R2 % R3
r = R4
ifz r goto end_if
R5 = a R5 = a
b = R5 b = R5
end_if:
R6 = r R6 = r
param b
a = R6 a = R6
call _printInt
goto loop goto loop
end_if:
param b
call _printInt End

314
 Les types d’optimisation
• Une optimisation est dite locale si elle travaille
sur un bloc de base

• Une optimisation est dite globale si elle travaille

sur le graphe de flot de contrôle

• Une optimisation est dite interprocedurale si elle

travaille sur les graphes de flot de contrôle de
plusieurs fonctions
– Non abordé dans ce cours…

315
Transformation optimisantes

OPTIMISATIONS LOCALES

316
 Un code exemple
o1 = i 4
b=a–d
a = t[o1] + d
o2 = i 4
c=a–d
t[o2] = c

317
 Elimination de sous expressions
communes
o1 = i 4 o1 = i 4
b=a–d b=a–d
a = t[o1] + d a = t[o1] + d
o2 = i 4 o2 = o1
c=a–d c=b
t[o2] = c t[o2] = c

Conditions d’application ?

318
 Elimination de sous expression
communes
• Remplacer la séquence suivante
– (1) t = a op b
– (2) …
– (3) … = a op b
• Par
– (1) t = a op b
– (2) …
– (3) … = t
• Si
– t, a et b ne sont pas modifiés dans la suite d’instructions (2)
– si (1) est toujours exécuté quand (3) l’est : toujours vrai dans un
bloc de base

319
 Propagation de copies
o1 = i 4 o1 = i 4
b=a–d b=a–d
a = t[o1] + d a = t[o1] + d
o2 = o1 o2 = o1
c=b c=b
t[o2] = c t[o1] = b

Conditions d’application ?

320
 Propagation de copies
• Remplacer la séquence suivante :
– (1) x = y
– (2) …
– (3) … x …
• Par
– (1) x = y
– (2) …
– (3) … y …
• Si
– x et y ne sont pas modifiés dans la suite d’instructions (2)
– si (1) est toujours exécuté quand (3) l’est : toujours vrai
dans un bloc de base

321
 Elimination de code mort
o1 = i 4 o1 = i 4
b=a–d b=a–d
a = t[o1] + d
o2 = o1
c=b
t[o1] = b t[o1] = b

Conditions d’application ?

322
 Elimination de code mort
• Remplacer
– (1) x = E
– (2) …
• Par
– (2) …
• Si x n’est pas utilisé dans (2)

• La valeur rangée dans x en un point (P) n’est pas lue après le point (P)
– On dit que x n’est pas vivante après ce point

• Attention : cet algorithme nécessite de connaitre les variables vivantes à la

fin d’un bloc de base
– La détermination des variables vivantes en fin d’un bloc de base nécessite
l’analyse du graphe de flot de contrôle
– Algorithme global…

323
Appliquer des optimisations locales
• Les optimisations précédentes prennent en
compte des petites optimisations
– La suppression des sous expressions communes
élimine des calculs inutiles
– La propagation de copies aide à identifier le code mort
– L’élimination de code mort supprime des affectations
inutiles

• Pour obtenir un effet maximum, il faut souvent

appliquer ces optimisations plusieurs fois

324
 Exemple
b=a*a b=a*a
c=a*a c=b
d=b+c d=b+c
e=b+b e=b+b

Elimination de sous expressions communes

325
 Exemple
b=a*a b=a*a
c=b c=b
d=b+c d=b+b
e=b+b e=b+b

Propagation de copies

326
 Exemple
b=a*a b=a*a
c=b c=b
d=b+b d=b+b
e=b+b e=d

Elimination de sous expressions communes

327
 Autres optimisations locales
• Simplification de sous expressions constantes
– Ex : x=4*5 peut se réécrire en x=20

• Simplification arithmétiques
–E 2 E+E shift-left1 E
–E 7 (shift-left3 E) – E
–E/4 shift-right2 E

328
 Implémentation de l’optimisation
locale
• Expressions disponibles
– L’élimination des expressions communes (CSE) et la
propagation de copie (CP) reposent sur les expressions
disponibles à un endroit dans le code
– Une expression est disponible si une variable contient
la valeur de cette expression
– Dans l’élimination des expressions communes on
remplace une expression par la variable contenant sa
valeur
– Dans la propagation de copie, on remplace une
variable par l’expression qui lui est associée

329
Recherche des expressions disponibles
• Initialement, aucune expression de disponible
• Quand une instruction du type a = b op c est
exécutée
– Toute expression utilisant a est invalidée
– L’expression a = b op c devient disponible
– (de même pour a = op b ou encore a = b)

• Algorithme : itérer sur le bloc de base depuis le

début vers la fin en calculant les expressions
disponibles
330
Exemple

a=b

c=b

d=a+b

e=a+b

d=b

f=a+b

331
Expressions disponibles
{}
a=b
{a=b}
c=b
{a=b, c=b}
d=a+b
{a=b, c=b, d=a+b}
e=a+b
{a=b, c=b, d=a+b, e=a+b}
d=b
{a=b, c=b, d=b, e=a+b}
f=a+b
{a=b, c=b, d=b, e=a+b, f=a+b}

332
Elimination des sous expressions
communes
{}
a=b
{a=b}
c = b -> c=a
{a=b, c=b}
d=a+b
{a=b, c=b, d=a+b}
e = a + b -> e = d
{a=b, c=b, d=a+b, e=a+b}
d = b -> d = a
{a=b, c=b, d=b, e=a+b}
f = a + b -> f = e
{a=b, c=b, d=b, e=a+b, f=a+b}

333
Elimination des sous expressions
communes
a=b

c=a

d=a+b

e=d

d=a

f=e

334
Expressions disponibles
{}
a=b
{a=b}
c=a
{a=b, c=a}
d=a+b
{a=b, c=a}
e=d
{a=b, c=a, e=d}
d=a
{a=b, c=a, d=a}
f=e
{a=b, c=a, d=a, f=e}

335
Propagation de copie
{}
a=b
{a=b}
c = a -> c = b
{a=b, c=a}
d = a + b -> d = b + b
{a=b, c=a}
e=d
{a=b, c=a, e=d}
d = a -> d = b
{a=b, c=a, d=a}
f=e
{a=b, c=a, d=a, f=e}

336
Propagation de copie

a=b

c=b

d=b+b

e=d

d=b

f=e

337
 Les variables vivantes
• L’analyse correspondant à l’élimination du code mort
repose sur la notion de variable vivante

• Une variable est dite vivante à un endroit du programme si

sa valeur est lue avant d’être réécrite

• L’élimination de code mort repose sur la collecte des

variables vivantes et la suppression des affectations
concernant les variables mortes

• Analyse s’effectuant depuis la fin du bloc vers le début de

ce dernier

338
 Calcul des variables vivantes
• Initialement seul un sous ensemble des variables
sont connues comme étant vivantes
– Ex : valeur de retour pour une fonction…

• Lorsque qu’une instruction du type a = b op c est

rencontrée
– Avant cette instruction a n’est pas vivante puisque sa
valeur va être réécrite
– Avant cette instruction b et c sont vivantes car leur
valeur est lue

339
Variables vivantes
{b}
a=b
{b}
c=b
{b}
d=b+b
{b,d}
e=d
{b,e}
d=b
{b,d,e}
f=e
{b, d}

340
Elimination de code mort
{b}
a=b
{b}
c=b
{b}
d=b+b
{b,d}
e=d
{b,e}
d=b
{b,d,e}
f=e
{b, d}

341
Elimination de code mort

d=b+b

e=d

d=b

342
Variables vivantes (2)

{b}
d=b+b
{b,d}
e=d
{b}
d=b
{b, d}

343
Elimination de code mort (2)

{b}
d=b+b
{b,d}
e=d
{b}
d=b
{b, d}

344
Elimination de code mort (2)

d=b+b

d=b

345
Variables vivantes (3)

{b}
d=b+b

{b}
d=b
{b, d}

346
Elimination de code mort (3)

{b}
d=b+b

{b}
d=b
{b, d}

347
Elimination de code mort (3)

d=b

348
Une autre vision de l’analyse locale

Vin

: propriétés avant l’exécution de la

commande
a=b+c : propriétés après l’exécution de la
commande
: fonction explicitant l’impact de
l’instruction s sur le contexte
Vout et retournant le contexte
modifié

349
 Formalisation de l’analyse locale
• Définition de l’analyse d’un bloc de base : quadruplet (D, V,
F, I)

– D : la direction de l’analyse (avant / arrière)

– V : un ensemble de valeurs / propriétés que le programme peut

avoir à un certain point

– F : famille de fonctions de transfert définissant le sens d’une

expression comme une fonction : F : V V

– I : L’information initiale au debut (analyse avant) ou à la fin

(analyse arrière) d’un bloc de base

350
 Expressions disponibles
• D : avant

• V : l’ensemble des expressions assignées à des variables

• F : Etant donné un ensemble d’assignations de variables V

et une expression de la forme où @ est une
opération :
– Supprimer de V toute expression contenant a comme sous
expression
– Ajouter dans V

• I : l’ensemble vide

351
 Variables vivantes
• D : arrière

• V : Ensemble de variables

• F : Etant donné un ensemble de variables et une expression

de la forme où @ est une opération
– Supprimer a de V (toutes le valeurs précédentes de a sont
mortes)
– Ajouter b et c à V (les valeurs de b et de c sont vivantes)
– Plus formellement :

• I : Les variables vivantes dans les blocs suivants

352
 Réaliser une analyse locale
• Etant donné une analyse (D,V,F,I) pour un bloc
basique
– Supposons que D est « avant » (si « arrière »,
parcourir les instructions en sens inverse)

• Initialement OUT[entrée] = I
• Pour chaque instruction s
– IN[s] = OUT[prev] avec prev l’instruction précédente
– OUT[s] = (IN[s]) avec la fonction de transfert
associée à s

353
Transformation optimisantes

OPTIMISATIONS GLOBALES

354
 Analyse globale
• Fonctionne sur le graphe de flot de contrôle
complet

• Plus puissant que l’analyse locale

– Prend en compte les structures de contrôle et donc les
branchements

• Plus compliqué que l’analyse locale

– Il existe plusieurs chemin dans le graphe de flot de
contrôle (tests, boucles etc…)
355
 Analyse locale vs globale
• Beaucoup des optimisations issues de
l’analyse locale peuvent être appliquées
globalement

• Certaines optimisations sont possibles en

global mais pas en local
– Ex : déplacement de code

356
 Suppression de code mort globale
• La suppression de code mort locale a besoin
de connaitre les variables vivantes en sortie de
bloc
Information uniquement calculable par analyse
globale

• Comment modifier l’analyse de variables

vivantes pour l’appliquer sur le graphe de flot
de contrôle ?

357
Graphe de flot de contrôle sans boucle
{a,c,d}
b=c+d
Entrée
e=c+d
{a,b,c,d}

{b,c,d} {a,b,c,d}
x=c+d y=a+b
a=b+c
{a,b,c,d} {a,b,c,d}

{a,b,c,d}
x=a+b {x, y}
y=c+d Sortie
{x, y}

358
Graphe de flot de contrôle sans boucle
{a,c,d}
b=c+d
Entrée
e=c+d
{a,b,c,d}

{b,c,d} {a,b,c,d}
x=c+d y=a+b
a=b+c
{a,b,c,d} {a,b,c,d}

{a,b,c,d}
x=a+b {x, y}
y=c+d Sortie
{x, y}

359
Graphe de flot de contrôle sans boucle
{a,c,d}
b=c+d
Entrée
{a,b,c,d}

{b,c,d} {a,b,c,d}

a=b+c
{a,b,c,d} {a,b,c,d}

{a,b,c,d}
x=a+b {x, y}
y=c+d Sortie
{x, y}

360
Graphe de flot de contrôle sans boucle
b=c+d
Entrée

a=b+c

x=a+b
y=c+d Sortie

361
 Différences avec analyse locale
• Analyse locale : chaque instruction a
exactement 1 prédécesseur / successeur

• Analyse globale : chaque instruction peut

avoir plusieurs prédécesseurs / successeurs

• Analyse globale : nécessité d’avoir une

manière de combiner les informations des
prédécesseurs / successeurs d’un bloc de base
362
 Différences avec l’analyse locale
• Analyse locale: il n’y a qu’un unique chemin
dans un bloc de base

• Analyse globale : il y a plusieurs chemin dans

le graphe de flot de contrôle
– Il se peut que les valeurs doivent être recalculées
plusieurs fois au fur et à mesure de l’acquisition
d’information
 Calcul de point fixe

363
Graphes de flot de contrôle avec
boucles
b=c+d
Entrée
c=c+d

a=b+c c=a+b
d=a+c

{a} a=a+b
Sortie d=b+c

364
 Différences avec l’analyse locale
• Dans l’analyse locale, il y a toujours une première
instruction bien définie pour commencer le
traitement

• Dans l’analyse globale avec des boucles, chaque

bloc de base peut dépendre des autres blocs de
bases

• Pour régler le problème, il faut assigner une

valeur initiale à tous les blocs du graphe de flot
de contrôle
365
Graphe de flot de contrôle avec
boucles
{}
b=c+d
Entrée
c=c+d

{} {}
a=b+c c=a+b
d=a+c

{}
{a} a=a+b
Sortie d=b+c

366
Graphe de flot de contrôle avec
boucles
{}
b=c+d
Entrée
c=c+d

{} {}
a=b+c c=a+b
d=a+c

{}
{a} a=a+b
Sortie d=b+c
{a}

367
Graphe de flot de contrôle avec
boucles
{}
b=c+d
Entrée
c=c+d

{} {}
a=b+c c=a+b
d=a+c

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a}

368
Graphe de flot de contrôle avec
boucles
{}
b=c+d
Entrée
c=c+d

{} {}
a=b+c c=a+b
d=a+c
{a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a}

369
Graphe de flot de contrôle avec
boucles
{}
b=c+d
Entrée
c=c+d

{b,c} {}
a=b+c c=a+b
d=a+c
{a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a}

370
Graphe de flot de contrôle avec
boucles
{}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {}
a=b+c c=a+b
d=a+c
{a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a}

371
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {}
a=b+c c=a+b
d=a+c
{a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a}

372
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a}

373
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a}

374
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

375
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

376
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

377
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

378
Graphe de flot de contrôle avec
boucles
{c,d}
b=c+d
Entrée
c=c+d
{a,b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

379
Graphe de flot de contrôle avec
boucles
{a,c,d}
b=c+d
Entrée
c=c+d
{a,b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

380
Graphe de flot de contrôle avec
boucles
{a,c,d}
b=c+d
Entrée
c=c+d
{a,b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

381
Graphe de flot de contrôle avec
boucles
{a,c,d}
b=c+d
Entrée
c=c+d
{a,b,c}

{b,c} {a,b}
a=b+c c=a+b
d=a+c
{a,b,c} {a,b,c}

{a,b,c}
{a} a=a+b
Sortie d=b+c
{a,c,d}

382
Graphe de flot de contrôle avec
boucles
b=c+d
Entrée
c=c+d

a=b+c c=a+b

a=a+b
Sortie d=b+c

383
 Autres optimisations
• Propagation de constante globale

• Extraction d’invariants de boucle

 Si un calcul fourni le même résultat à chaque itération d’une boucle,
mettre ce calcul avant la boucle

• Déroulage de boucles

• Inlining
 Supprimer l’appel d’une fonction en recopiant le corps de la fonction
dans l’appelant

• …

384
 Conclusion
• Attention : optimisation optimalité
– Pas de transformations optimisantes à proprement parler
– Plutôt des transformations améliorantes

• Tout devient compliqué avec les processeurs modernes

– Pipe-line, cache, multi-cœurs, exécution spéculative,
SIMD…

• Consommation mémoire vs consommation

énergétique vs rapidité d’exécution
– Compromis complexe à trouver…

385
GESTION MÉMOIRE

386
 Introduction
• Beaucoup de constructions dans les langages de
programmations ont besoin de mémoire

• Certaines nécessitent une quantité de mémoire fixée

– Ex : constantes de programme

• Certaines nécessitent une quantité de mémoire variable

– Tableaux, objets, variables locales, chaines de caractères…

 Le compilateur doit prévoir comment la mémoire va être

utilisée

387
 Gestion de la mémoire
1. De la mémoire est allouée à priori et est persistante durant
l’exécution
– Variables globales, table des fonction virtuelles, code exécutable…

2. De la mémoire est allouée sur la pile d’exécution

– Variables locales, paramètres, variables temporaires…

3. De la mémoire est allouée dans le tas

– Les objets, les tableaux…

• La gestion mémoire pour 1 et 2 est triviale

• Comment gérer la mémoire allouée dans le tas ?

388
Gestion mémoire

GESTION MANUELLE DE LA MÉMOIRE

389
 Gestion manuelle de la mémoire
• Le programmeur doit se charger de la gestion mémoire

• Approche utilisée en C et en C++ par exemple

• Avantages
– Le programmeur peut exercer un contrôle précis de
l’utilisation de la mémoire

• Inconvénients
– Le programmeur DOIT exercer un contrôle précis de
l’utilisation de la mémoire

390
 Force de la gestion manuelle
• Relativement facile à implémenter
– Requiert un gestionnaire de mémoire

• Permet aux programmeurs de faire des

optimisations de performances agressives
– Peut choisir des schémas d’allocation qui ont les
meilleures performances par rapport au domaine
applicatif

391
 Problèmes de la gestion manuelle
• Conduit facilement à des bugs

– Fuites mémoires : une mémoire allouée n’est jamais

libérée

– Double désallocation : la mémoire est désallouée deux fois

ou plus
• Peut faire bugger le gestionnaire de mémoire ou générer des bugs
aléatoires dans le programme…

– Utilisation après désallocation

• Peut faire bugger le gestionnaire de mémoire (écriture)
• Peut fournir des données incohérentes (lecture)

392
Gestion mémoire

GARBAGE COLLECTION

393
 Qu’est-ce qu’un objet « Garbage »
• A un point de l’exécution un objet est qualifié de « garbage » s’il ne sera
plus jamais utilisé par la suite

• En général, le problème est indécidable

– Besoin d’une approximation conservatrice

• Un objet est atteignable s’il peut encore être référencé par le programme
– Principe sur lequel beaucoup d’algorithmes de « garbage collection » reposent

• Attention : n’empêche pas complètement les fuites mémoires !

– Beaucoup d’objets atteignables ne seront pas utilisés dans le programme
– Il est facile d’avoir des fuites mémoire dans des langages avec « garbage
collector » (même Java ;) !!!)

394
 Hypothèses de travail
• Supposons que durant l’exécution, nous puissions trouver
toutes les références dans un programme
– Impossible de fabriquer une référence vers un objet ex nihilo
– Impossible de transformer un pointeur en entier et
réciproquement

• Exemples : Java, Python, C#, Javascript…

• Contre-exemples : C, C++…

• La connaissance des références permet d’analyser le

comportement programme lors de l’exécution

395
Les types de « garbage collectors »
• Incrémental vs stop-the-world
– Un GC incrémental fonctionne en parallèle du programme
– Un GC stop-the-world met l’exécution du programme en
pause

• Compacting vs non-compacting
– Un compacting GC déplace les objets en mémoire pour les
tasser et éviter la fragmentation de la mémoire
– Un non-compacting GC laisse les objets à leur
emplacement initial (peut générer de la fragmentation
mémoire)

396
Garbage collection

COMPTAGE DE RÉFÉRENCES

397
 Comptage de références
• Un framework simple
– Mais qui a de sérieux défauts !!!

• Idée : associer à chaque objet un compteur de références qui compte le

nombre de références vivantes désignant cet objet

• La création d’une référence vers l’objet incrémente le compteur

• La destruction d’une référence vers l’objet décrémente le compteur

• Un objet ayant un compteur de référence à zéro n’est plus atteignable et la

mémoire peut donc être libérée
– Note cela peut conduire à mettre d’autres compteurs de références à 0
– Destruction en cascade

398
 LE PROBLEME
les références cycliques
• Un cycle de références est créé par des objets qui se
références les uns les autres et forment un cycle

• Comme tous les objets sont référencés

– le compteur de référence ne tombe jamais à 0
– la mémoire ne peut jamais être libérée

• Problème : le compteur compte le nombre global de

références, pas le nombre de références atteignables

399
 Analyse
• Avantages
– Simple à implémenter
– Peut être implémenté dans une librarie au dessus de la
gestion manuelle de la mémoire
• Ex : C++ et std::shared_ptr<T>

• Désavantages
– Echoue dans la libération de la mémoire de tous les objets
non atteignables (problème des cycles)
– Peut être lent lorsque beaucoup d’objets sont libérés
– Ralenti les assignations de références (ou pointeurs) car
accède au compteur (pose des problèmes de cache)

400
Garbage collection

MARK AND SWEEP

401
 L’intuition
• Etant donné la connaissance de ce qui est
immédiatement accessible, trouver tous les objets
accessibles depuis le programme

• L’ensemble racine et l’ensemble des emplacements

mémoires connus pour être atteignables
• Un objet atteignable depuis l’ensemble racine est
atteignable
• Un objet non atteignable depuis l’ensemble racine n’est
pas atteignable
 Réaliser une recherche dans un graphe en partant de
l’ensemble racine
402
 L’algorithme
• Le mark-and-sweep fonctionne en deux passes

• Marking phase : trouver les objets atteignables

– Ajouter l’ensemble racine dans une liste de travail
– Tant le la liste n’est pas vide
• Piocher un objet dans la liste
• Si l’objet n’est pas marqué
– Le marquer
– Ajouter tous les objets atteignables depuis cet objet dans la
liste

• Sweeping phase : libérer la mémoire

– Pour chaque objet alloué
• Si l’objet n’est pas marqué, libérer la mémoire
• Si l’objet est marqué, supprimer le marqueur

403
 Exemple
Liste de travail
1

Ensemble
racine 1 2

3
4
5 6

404
 Exemple
Liste de travail
3

Ensemble
racine 1 2

3
4
5 6

405
 Exemple
Liste de travail
56

Ensemble
racine 1 2

3
4
5 6

406
 Exemple
Liste de travail
67

Ensemble
racine 1 2

3
4
5 6

407
 Exemple
Liste de travail
77

Ensemble
racine 1 2

3
4
5 6

408
 Exemple
Liste de travail
7

Ensemble
racine 1 2

3
4
5 6

409
 Exemple
Liste de travail

Ensemble
racine 1 2

3
4
5 6

410
 Exemple
Liste de travail

Ensemble
racine 1 2

3
4
5 6

411
 Exemple
Liste de travail

Ensemble
racine 1

5 6

412
 Implémentation du mark-and-sweep
• L’algorithme tel que présenté a deux problèmes
majeurs

• Le temps d’exécution est proportionnel au

nombre d’objets alloués
– La « sweep phase » visite tous les objets pour les
libérer ou supprimer les marques

• La liste de travail a besoin de beaucoup de

mémoire
– L’espace ne peut pas être pré-alloué
413
 L’idée clé
• Durant la collection chaque bloc mémoire doit être dans un de ces
4 états
– Marqué : L’objet est connu comme atteignable
– Exploration : L’objet est dans la liste de travail
– Inconnu : L’objet n’a pas encore été vu
– Désalloué : l’objet a été détruit

• Utiliser 2 bits dans le bloc mémoire pour stocker l’état

• Gestion de 4 listes doublement chainées contenant tous les objets

dans chaque état

• Les pointeurs sont ajoutés en début du bloc mémoire

– Fonctionne car chaque objet n’appartient qu’à une et une seule liste…

414
 L’algorithme de Baker
• Déplacer l’ensemble racine dans la liste d’exploration

• Tant que la liste d’exploration n’est pas vide

– Déplacer l’objet de la liste d’exploration à la liste des marqués
– Pour chaque objet référencé et dans l’état inconnu, l’ajouter dans la liste d’exploration

• A ce point, tout ce qui est atteignable est dans la liste marqué et ce qui n’est pas
atteignable dans la liste inconnu

• Concaténer la liste inconnu à la liste désalloué

– Se fait en O(1) car liste doublement chainée

• Déplacer la liste marqué dans la liste inconnu

– Se fait en O(1)
– Indique que les objets doivent être prouvé comme atteignables la prochaine fois

415
 Analyse
• Avantages
– Trouve précisément les objets atteignables
– Avec l’algorithme de Baker, le temps d’exécution est
proportionnel au nombre d’objets atteignables

• Désavantages
– Approche de type stop-the-world qui peut imposer de
gros temps de pose
– Les informations de double chainage et d’état dans
chaque bloc alloué utilisent beaucoup de mémoire par
objet

416
Garbage collection

STOP AND COPY

417
 Amélioration de performances
• Il y a beaucoup de manière d’augmenter les performances d’un
programme
• Certaines peuvent être améliorées par un bon garbage collector

• Augmenter la localité
– Caches mémoires : accélération de l’accès à des données adjacentes
en mémoire
– Placer les objets de manière consécutive en mémoire peut réduire les
fautes de cache

• Augmenter la vitesse d’allocation mémoire

– Beaucoup de langages allouent des objets fréquemment
– Augmenter les performances de l’allocation peut augmenter les
performances des programmes

418
 Augmenter la localité
• Idée : durant le processus de « garbage collection »,
déplacer les objets pour qu’ils soient adjacents en mémoire
– Compactage de la mémoire

• Idéalement, déplacer les objets qui se référencent les uns

les autres dans une mémoire contigüe
– Le garbage collector doit mettre à jour toutes les références

• Possible en Java ? Possible en C++ ?

– De grosses différences…
– Java possède un garbage collector nativement, pas C++
– Un pointeur C++ peut être converti en entier, puis de nouveau
en pointeur…

419
 Augmenter la vitesse d’allocation
• Les implémentations de malloc / free utilisent des
listes de blocs libres en mémoire

• L’allocation requière de suivre les pointeurs jusqu’à

trouver un emplacement mémoire adéquat
– Usuellement rapide mais necessite au moins 10 à 20
instructions assembleur
– Allocation sur la pile : 1 instruction

• Question : peut on effectuer une allocation dynamique

aussi rapidement qu’une allocation sur la pile ?
420
Principe du stop-and-copy
Mémoire adressable

421
 Principe du stop-and-copy
Mémoire adressable

• La mémoire est découpée en deux parties égales

• Facile, tout est une puissance de 2…

422
 Principe du stop-and-copy
Mémoire adressable

Nouvel espace Ancien espace

• La mémoire est découpée en deux parties égales
• Facile, tout est une puissance de 2…
• Ancien espace : espace contenant les instances avant la collection
• Espace libéré
• Nouvel espace : espace contenant les instances après la collection
• Espace utilisé pour les nouvelles allocations

423
 Principe du stop-and-copy

Début espace libre

424
 Principe du stop-and-copy

Début espace libre

• Allocation d’un objet

• Dans le nouvel espace
• En début d’espace libre

425
 Principe du stop-and-copy

Début espace libre

• Allocation d’un objet

• Dans le nouvel espace
• En début d’espace libre
• Après le dernier objet alloué
• Aucune recherche, aucun chainage…

426
Principe du stop-and-copy

Début espace libre

427
Principe du stop-and-copy

Début espace libre

428
Principe du stop-and-copy

Début espace libre

429
 Principe du stop-and-copy

Début espace libre

• Rq : création d’un cycle

430
 Principe du stop-and-copy

Ensemble racine

431
 Principe du stop-and-copy

Ensemble racine
• A partir de l’ensemble racine
• Recopier les objet accessibles
• Mettre à jour les références

432
 Principe du stop-and-copy

Début espace libre

• Echanger le nouvel et l’ancien espace

433
 Principe du stop-and-copy

Début espace libre

• La mémoire a été compactée

• L’adresse de la prochaine allocation
• Est connue
• Suit immédiatement le dernier objet alloué

434
 Principe du stop-and-copy

Début espace libre

• La mémoire a été compactée

• L’adresse de la prochaine allocation
• Est connue
• Suit immédiatement le dernier objet alloué

435
Principe du stop-and-copy

Ensemble racine Début espace libre

436
 Principe du stop-and-copy

Ensemble racine Début espace libre

• Les objets sont réordonnés suivant leur accessibilité

• Meilleure disposition pour le cache

437
 Principe du stop-and-copy

Début espace libre

• Les objets sont réordonnés suivant leur accessibilité

• Meilleure disposition pour le cache

438
 Stop-and-copy : l’algorithme
• Partitionner la mémoire en deux régions : l’ancien espace et le nouvel
espace
• Conserver un pointeur sur l’espace libre (situé à la fin de la mémoire
allouée)
• Pour allouer n octets
– S’il y a un espace de n octets
• l’adresse allouée est dans le pointeur sur l’espace libre
• Incrémenter le pointeur de n octets
– Sinon, effectuer une étape de copie
• Etape de copie
– Pour chaque objet dans l’ensemble racine
• Copier l’objet dans l’ancien espace
• Copier récursivement les objets accessibles dans l’ancien espace
– Mettre à jours les références dans l’ancien espace pour qu’ils désignent les
nouveaux emplacements
– Echanger le rôle de l’ancien espace et du nouvel espace

439
 Détail d’implémentation
• Le point important est de mettre correctement à jour les
références dans les objets copiés
• Idée : chaque objet contient un pointeur de réexpédition
sur sa copie
• Pour dupliquer un objet
1. Faire une copie bit à bit
• Toutes le références désignent encore les anciens emplacements
2. Mettre à jour le pointeur de réexpédition de l’objet original
pour qu’il désigne sa copie
• Après avoir dupliqué chaque objet :
– Suivre les références vers les objets désignés
– Remplacer les références par le pointeur de réexpédition de
l’objet désigné

440
 Mise à jour des références

• Les objets sont copiés bit à bit

• Les références sont conservées

441
 Mise à jour des références

• Les objets sont copiés bit à bit

• Les références sont conservées
• Les références sont mises à jour en utilisant les pointeurs de réexpédition

442
 Mise à jour des références

• Les objets sont copiés bit à bit

• Les références sont conservées
• Les références sont mises à jour en utilisant les pointeurs de réexpédition

443
 Mise à jour des références

• Les objets sont copiés bit à bit

• Les références sont conservées
• Les références sont mises à jour en utilisant les pointeurs de réexpédition

444
 Mise à jour des références

• Les objets sont copiés bit à bit

• Les références sont conservées
• Les références sont mises à jour en utilisant les pointeurs de réexpédition

445
 Mise à jour des références

• Les objets sont copiés bit à bit

• Les références sont conservées
• Les références sont mises à jour en utilisant les pointeurs de réexpédition

446
 Analyse
• Avantages
– Facile à implémenter
– Allocation mémoire très rapide
– Très bonne localité
• La copie en utilisant une exploration en profondeur d’abord
place les objets accessibles près les uns des autres

• Désavantages
– Seul 50% de la mémoire est utilisé
– Temps de collection proportionnel au nombre d’octets
utilisés par les objets accessibles

447
Garbage collection

APPROCHES HYBRIDES

448
 Le meilleur des deux mondes
• Les meilleurs garbage collectors sont basés sur
la combinaison de plus petits garbage
collectors

• Chaque garbage collector est en charge d’un

sous ensemble des objets

• Un garbage collector final gère tout le reste

449
 Les objets meurent jeunes
• La devise des garbages collectors : Les objets meurent
jeunes

• Beaucoup d’objets ont des durées de vie très courtes

– Objets alloués localement à une fonction
– Objets temporaires utilisés pour construire des objets plus
gros

• Idée : optimiser le garbage collector pour gérer

rapidement la collecte pour les objets jeunes et passer
moins de temps sur les objets plus vieux
450
 Les garbage collectors générationnels
• Partitionner la mémoire en plusieurs générations

• Les objets sont toujours alloués dans la première génération

• Quand la première génération est remplie exécuter le garbage collector sur cette
génération
– S’exécute rapidement, collecte de petites portions de mémoire

• Déplacer les objets survivant suffisamment longtemps dans la seconde génération

• Quand on ne trouve plus d’espace libre, lancer un garbage collector sur toute la
mémoire

• Le garbage collector lié à la jeune génération tourne fréquemment et ceux liés aux
plus vielles générations moins souvent
– Permet d’améliorer les performances

451
 Conclusion
• C++
– Mémoire gérée à la main ou comptage de
référence
• Appel du destructeur avec la libération de la mémoire
• Exécution synchrone

• Java
– Pas de destructeur
– Mais une méthode finalize()
• Pourquoi ne l’avez-vous jamais utilisée ?

452
 Conclusion
• Finalisation : action entreprise lors de la destruction
implicite d’un objet

– Impossible de connaitre l’ordre de finalisation

– Impossible de savoir si un objet sera finalisé

– Impossible de connaitre le délai entre perte d’utilité et

finalisation

• Ne rien mettre de fonctionnellement important dans la

finalisation !

453
 Conclusion
• Vous aimez les garbage collectors

• Mais ils ne sont pas exempts de défauts

– Gèrent la durée de vie des objets par rapport à leur accessibilité
– Pas par rapport à leur utilité
– Certains objets toujours référencés ne peuvent pas être libérés alors qu’ils
sont inutiles
• Fuite mémoire

• Ex : vous avez un tableau et vous gérez sa taille et sa capacité et souhaitez

supprimer le dernier élément du tableau
1. Vous décrémentez simplement la taille
• La case du tableau désigne toujours un objet !!!
• Il est inutile mais ne peut pas être supprimé par le garbage collector
2. Vous mettez la référence à null et décrémentez la taille
• Ici, le garbage collector peut faire son travail

454
CONCLUSION GLOBALE

455
 Ce qui a été abordé dans ce cours
• Théorie des langages
– Une approche très formalisée
– Permettant une automatisation
– Ex : ANTLR, Xtext…

• Grammaires attribuées
– Ajouter des traitements en cours d’analyse du langage
– Ex : construction d’un AST

• L’analyse sémantique
– Gestion des erreurs et avertissements
– Construction de la table des symboles

456
 Ce qui a été abordé dans ce cours
• Le typage
– Une approche formelle
– Basée sur les preuves
– Typage explicite ? Typage implicite ?
– Certains langages marient les deux
• Ex : C++

• Les représentations intermédiaires

– Arbre de syntaxe abstraite
• Outils fondamental pour toutes les passes d’analyse et de génération
– Code 3 adresses
• Code simple à manipuler
• Très proche de l’assembleur
• Permet de faire des optimisations indépendantes de la machine, du langage
source ou encore du langage cible !!!

457
 Ce qui a été abordé dans ce cours
• Génération de code intermédiaire et
transformations optimisantes
– Une approche très systématique
– Génération d’un code naïf
– Puis transformations pour le rendre plus efficace

• La gestion mémoire
– Tous les langages ont un modèle mémoire
– Rq : la gestion du garbage collector est très liée au
compilateur
• Besoin de connaitre toutes les références…

458
 Ce qui n’a pas été abordé
• Le backend : la génération de code
– Allocation de registres
– Ordonnancement d’instructions
• Joue avec la dépendance des données
• Possibilité d’entrelacer les instructions indépendantes
– La gestion des caches
• Réordonnancement des boucles
• Array of structures or structure of arrays ?
– La parallélisation
–…
459
 Conclusion
• Les compilateurs sont des outils complexes
– Grand nombre de technologies mises en jeu
– Modularité extrême

• Comprendre les compilateurs est un atout

– Compréhension des langages et des formats
– Connaissance d’outils de manipulation de texte
– Optimisation des programmes

• Parfois, créer un langage peut permettre de résoudre

des problèmes plus facilement…

460