INFO 2108

Syntaxe et sémantique des

langages de programmation

Pierre-Yves Schobbens

Bureau 409
081/72 49 90
rue Grandgagnage 21
5000 Namur
[email protected]
 Plan

0. Introduction
1. Analyse lexicale : Langages réguliers
2. Analyse syntaxique : Langages non contextuels
3. Analyse statique (p.ex. typage): Grammaires attribuées
4. Eléments de génération de code
5. Sémantique
 Références
• Grune, Bal, Jacobs, Langendoen « Compilateurs »,
Dunod, 2002.
• Aho, Sethi, Ullman : « Compilateurs : principes,
techniques et outils », InterEditions, 1998, BUMP
# 1 412/037
• R. Wilhem, D. Maurer : « Les compilateurs :
théorie, construction, génération », Masson, 1994,
BUMP # 1 412/030
Chapitre 0. Introduction
 Types de langages
• Les techniques de ce cours s’appliquent à:
– des langages de programmation : Pascal, Ada, …
– des langages de commande : JCL, Sh, Csh, …
– des langages de description de données: SQL (DDL), XML, ...
– des langages de spécification : VDM, Z, Albert, ...
– des langages de formulaires : EDIFACT, CGI (WWW), ...
– des formats de messages (réseaux)
– des langages de documents : EQN, HTML,
Paradigmes de langages de programmation
1. impératifs : Algol, Pascal, Ada, Fortran, Cobol, Modula, C
axés sur l’affectation

2. fonctionnels : Lisp, ML, Hope, Miranda, Haskell, FP

basés sur l’évaluation des expressions

3. logiques : Prolog, Gödel

basés sur la preuve de formules

4. orientés objet : Simula, Smalltalk, C++, Eiffel, CLOS, Java

basés sur l’héritage

N.B. : Les paradigmes ne sont pas mutuellement exclusifs.

 Exécution des langages

2 extrêmes

1. Les interpréteurs
- lisent le programme au fur et à mesure
les programmes peuvent être créés dynamiquement

2. Les compilateurs
- traduisent l’ensemble du programme
soit - en langage d’une machine concrète 486, P6, Power
ou - en langage d’une machine abstraite SECD, WAM, JVM,
P-MACHINE
 Rôle d’un compilateur
Code source compilateur Code cible

Code machine du compilateur

compilateur
d’implémentation
Code d’implémentation du compilateur
Générateur de
compilateur
(Flex, Bison)
Spécification
D25

Structure d’un compilateur

1. analyse lexicale
reconnaître les « mots »
2. crible
avant

3. analyse syntaxique reconnaître les « phrases »

4. analyse sémantique vérifier les types, etc.
5. optimisations élimination de code inutile, etc.
6. allocation mémoire choisir la place des variables
arrière

7. génération de code instructions machine

8. optimisations propres à la cible séquence plus efficaces
G6

Ex. compilateurs GNU

C Ada
Front-ends (1-4) C++ Pascal
ANSI 95
partie avant

Middle-end (5)
Partie centrale

Back-ends (6-9) 68000 Pentium Power

partie arrière
D17

Outils pour les langages

• Editeurs structurels : édition intelligente
• Analyseurs : p.ex. pour la rétro-ingénierie,
Y2K
• Paragrapheurs : mettent en page
Chapitre 1 : Analyse Lexicale

Rôle : retrouver les mots qui

composent le texte
D104-108

Place de l’analyse lexicale

Texte source Analyseur « mots »

= caractères lexical = lexèmes

Automate fini

générateur
d’analyseur
lexical

Expressions régulières
 Plan
1. Langages et expressions régulières

2. automates finis : Kleene

2.1 non-déterministe
2.2 déterministe
2.3 minimal

3. Régulier ou pas?
D112

Définitions

: alphabet, ensemble de caractères (donné, fini)

ex. : ASCII, EBCDIC, ISO-Latin-1, UniCode, ...

texte, mot, phrase : suite de caractères

Langage : ensemble de phrases

Note : convient pour les langages séquentiels (parlé, écrit) mais pas
pour des langages graphiques

 : phrase vide

. : concaténation (parfois le . est omis)
D113

Propriétés

• x.=x=.x neutre
• x . (y. z) = (x . y) . z associativité
• Ces propriétés sont complètes
 D113

Ordres
• X est un préfixe de Y : Y commence par X
– « 12 » est un préfixe de « 1234 »
• X est un suffixe de Y : Y finit par X
– « 34 » est un suffixe de « 1234 »
• X est une sous-chaîne de Y : X s’obtient par
suppression d’un suffixe et d’un préfixe
– « 23 » est une sous-chaîne de « 1234 »
D114

Opérations sur les langages

Notation Définition Nom
L1 ∪ L2 = {p ⎜p ∈ L1 ou ∈ pL2} union

L1 . L ⎜ ∈ L1
2 = {x . y x et ∈ yL2} concaténation

C(L) = {x ⎜x est une phrase∑sur

et x∉ L} complément
n
L = L . L . L . … . L exponentielle
0
L = { ε} ou puissance
*
Ln
étoile de Kleene

L = ∪
n≥0
a= { " a " } singleton

∅= { } ≠ε( !) langage vide

ε= {ε} mot vide
D117

Propriétés
 D115

Expressions régulières
= les expressions écrites avec

aussi noté ou +
souvent omis

Langage régulier = langage décrit par une expression régulière

 Exemples
d’expressions régulières

1. < constante décimale > = 0 | (1| 2 | 3 | 4 | 6 | 7 | 8 | 9) . (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)*

une constante décimale de C est, soit un 0 seul, soit un chiffre significatif suivi d’autant

0 1 n’est pas une constante décimale en C, mais octale.

1 0 est une constante décimale.

2. < multiples-de-2-en-binaire > = (0 | 1)* . 0

3. < identificateur > = (a | b | ... | z). (a | b | ... | z | 0 | ... | 1)*

 Abréviations

Ln = L. L. ... L
} où n est un naturel  n

n fois

L+ = L L*

[a - z] = tous les caractères entre a et z dans le code ASCII =

les lettres = a b ... z

L? = L 
[n-m] n n+1 m
L = L L ... L
D135

2. Automates finis
caractère courant
bae mot à reconnaître

q0 b q1 a q2 b q3  q4
a
état initial état courant
c état final
ou accepteur
D136

Définition

Un automate fini (non-déterministe avec transitions vides) se compose de :

D137

Fonctionnement
• Un automate accepte un mot m si on peut trouver un
chemin c:
– Qui commence dans l’état initial
– Qui finit dans un état final
– Qui suit des transitions
– La concaténation des étiquettes des transitions donne m
• Les mots acceptés forment le langage de l’automate L(A)
Exemple: constante naturelle décimale de C

[1-9]
[0-9]
Exemple : multiples de 2 en notation binaire

0
1

Multiples de 2 en notation binaire :

Ils se terminent toujours par 0.
Ceci est facile à représenter par un
automate non-déterministe
Exemple : identificateurs de Pascal

a
[a-z 0-9]
a z
[a-z]
z notation :
0
9
 Exemple : Multiples de 7

a
r s

Principe: r est le reste par 7 du nombre lu (n)

m = n * 10 + a donc s = (r * 10 + a) mod 7
 Théorème de Kleene

Un langage est régulier

ssi

c’est le langage d’un automate fini

Preuve : La preuve est donnée par 2 algorithmes

1. qui construit un automate pour chaque expression régulière

2. qui construit une expression régulière pour chaque automate fini

en gardant le même langage.

Expression  automate
cas de base
début

(a) Automate pour

début 

(b) Automate pour .

début a

(c) Automate pour le caractère "a".

Expression  automate:
union
Pour R1
 
début

 
Pour R2

(a) Construction de l’automate d’union pour deux expressions régulières

 Expression  automate:
concaténation

début 
Pour R1 Pour R2

(b) Construction de l’automate de concaténation pour deux expressions régulières

Expression  automate:
répétition

début  
Pour R1


(c) Construction de l’automate de fermeture pour deux expressions régulières
Exemple : constante décimale de C
0
1 2

0 F

9 9
4
3
5 ...
0
1
 Problèmes
• 1. L’automate contient des -transitions
• 2. Il n’est pas déterministe: moins efficace
• 3. Il y a beaucoup trop d’états (80 dans l’exemple)
D138

Automate déterministe
• Un automate fini est déterministe, intuitivement
s’il ne peut se comporter que d’une façon pour un
mot donné :
– Il n’a pas de transition-
– Étant donné un état de départ et un caractère lu, il y a au plus 1
état d’arrivée
• Il est complet si, étant donné un état de départ et un
caractère lu, il y a au moins un état d’arrivée
 Idée de la déterminisation
début 1 2 ... k
S1

1 2 ... k
S2

... début 1 2 ... k

S1, S2 ,..., Sk

1 2 ... k Dans l’automate déterministe:

Sn Un seul chemin vers un état qui représente
tous ceux où une copie peut être.
Dans l’automate non déterministe:
Plusieurs chemins étiquetés 
D140

Déterminisation

On construit un nouvel automate A’

- De même alphabet
- nouvel état = ensemble d’anciens états
-état initial = succs({q0}) = états accessibles de q0 par des transitions vides
- état final = état contenant un ancien état final
- transition = ensemble des états où une copie peut arriver
S,a) = succs( {q | p  q,ap S} )

Note : on peut diminuer le nombre d’états en ne considérant que les

états accessibles.
Notation : puisque  est fonctionnelle pour les automates déterministes,
on emploie une notation fonctionnelle
Exemple : constantes décimales de C
Quelques ensembles fermés par 
0
1 2 F

9 9
4
3
5 ...
0
1

État initial
Constantes décimales de C déterminisé

0 0

9
0

0
9 9

9
 Exemple
Reconnaître une suite de 1, 2, 3 où le dernier chiffre est apparu précédemment.
Expression régulière : * (1 * 1 | 2 * 2 | 3 * 3), où 

1,2,3

1
1,2,3 1 1
1,2,3
2 2
Automate : 0 2 4

1,2,3
3 3
3
 Exemple : déterminisation
1

0,1,4
3 1/2
1 0,1
2 1/2
2,4

0,1 2
0,1,2 3 3
1 3 2 0,1 1/2/3 1/2/3
1 2,3
0,1,3 0,1
2 0,2 1 1/3 2,3,4
0 2
1/3
0,2,4 1 0,1 2
3 3 1 3,4
1 3 1
2
0,3 0,2,3
2/3 2/3
3 2 0,2
3,4
0,3,4

Intuition : Les états marqués 1 (ou 2, 3) signifient «on a rencontré un 1 (ou 2,3)».
L’état 4 signifie : on a rencontré un 2° caractère identique, donc
on peut terminer.
 Algorithme de minimisation
retirer les états non accessibles
compléter l’automate
Idée : On met les états dans des classes différentes quand on voit qu’ils ont
un comportement différent.
 : partition courante les états sont groupés en classes
 := {F, Q \ F} au départ, on crée deux classes: les finaux et les non-finaux

répéter
pour chaque K,
K’ 
 := (  \ {K})  {{Ki}}

où {Ki} est la partition de K la plus grosse

tous les états de Ki arrivent dans la même classe pour chaque caractère

jusqu’à ce que  ne change pas

Fusionner les états d ’une même classe
Retirer l’état mort
 Exemple de minimisation
« Constante décimale de C » Minimisation du nombre d’états

Non finaux

0 Finaux

0 0

9
0

0
9 9

9
 : partition des états
 Exemple de minimisation
« Constante décimale de C » Fusion d’états

1 0

9
9

 : partition des états

 Kleene (2)
automate fini  expression régulière (1)
1° étape : automate fini  jeu d’équations
a
pour chaque état S3 S4
b

S5

on crée une équation : S3 = a . S4 b . S5 

si S3 est final

S3 représente l’ensemble des chaînes qu’on peut lire en

partant de S3.

Note: ces équations ont plusieurs solutions, c'est la plus petite qui nous intéresse.
automate fini  expression régulière (2)

2° étape : résolution des équations

S3 = x  y . S 3 ~> S 3 = y* x

où S3 n’apparaît pas dans les expressions x, y.

 Exemple
0
S0 S1
1-9

S2 0-9

1° étape: l ’automate est équivalent aux équations

S0 = 0 . S1 | (1 | 2 | … | 9) . S2

S1 = 

S2 =  | (0 | 1 | ... | 9) . S2
 Exemple (2)
2° étape : résolution par triangulation
1) éliminer S1 :

S0 = 0 | [1-9] . S2

S2 =  | [0-9] . S2

2) résoudre S2 :

S2 = [0-9]* . 

3) éliminer S2 :
 Complémentation
• On calcule un automate qui accepte le complément de A.
• Algorithme:
1. Déterminiser A;
2. Le compléter:
1. Ajouter un état mort;
2. Ajouter des transitions vers cet état (si car. manque).
3. Propriété: chaque chaîne amène dans un seul état.
3. Inverser les états finaux et non-finaux.
 Exemple de complémentation
complété : il y a une flèche pour
chaque caractère de  = [0-9]
Automate déterministe
[0-9]
0 [0-9]
S0 S1
[1-9]
[0-9]
S2

Négation : on intervertit les états finaux

[0-9]
0 [0-9]
S0 S1 S3
[1-9]
[0-9]
S2
D119

Langages non réguliers

• Un langage est régulier ssi un programme peut le
lire (de gauche à droite) en ne mémorisant qu’une
information finie.
• Lemme de pompage: Une chaîne plus longue que
le nombre d’états de l’automate contient une
boucle qu’on peut répéter.
x
y

z
si k est le nombre d’états
une chaîne plus longue
doit faire une boucle.
 Exemple
• Le langage {0n 1n } n’est pas régulier :
– Il faut retenir le nombre de 0, qui peut être grand : l’information
n’est pas finie.
– S’il était régulier, on aurait un automate; Soit k son nombre
d’états. 0k 1k doit passer par une boucle :
• Si la boucle ne contient que des 0, on accepte des chaînes avec plus
de 0 que de 1.
• Si la boucle ne contient que des 1, on accepte des chaînes avec plus
de 1 que de 0.
• Si la boucle contient des 0 et 1, alors on accepte des chaînes où 0 suit
1.
Chapitre 2 : Analyse Syntaxique
Rôle : L’analyseur syntaxique retrouve la structure (arbre)
grammaticale du programme.
Grammaire non contextuelle

une grammaire a 4 éléments:

• l’ensemble des symboles terminaux VT
finis
• l’ensemble des non-terminaux VN
• l’ensemble des productions P
• le symbole de départ S (non-terminal)
 BNF : Exemple : Pascal
Exemple

Pour Pascal, on reprend :

VT = les symboles reconnus lors de l’analyse lexicale :

mots-clés. Ex. if, identificateurs. Ex. x, ...

VN = les catégories syntaxiques :

Ex. : < programme >, < instructions >, < expr >

P = les productions de la grammaire

Ex. : < instruction > : : = if < expr >
then < instruction >
else < instruction >

S = la catégorie des textes complets : < programme >

Pour le langage C la catégorie < programme > n’existe pas, le symbole de départ
(ce qu’on peut compiler) est <déclarations>.
D192 W254

Notations
• Terminaux: les minuscules, chiffres, symboles
d’opérateurs, symboles en gras
• Non-terminaux: majuscules: A,B,C,S ; entre
<crochets>
• Symboles: X, Y, Z
• Chaînes de terminaux: u,v,w
• Chaînes de symboles: 
 Historique
- Pourquoi « non contextuel » ? (context-free)

Chomsky (en 1956) a choisi ce nom

par contraste avec ses « grammaires contextuelles » (type 1)
où on peut mettre des conditions pour l’application d’une règle.

- BNF signifie « Backus Naur form », du nom de ses inventeurs

(utilisé pour la définition d ’Algol 60, vers 1958).
 Emploi d’une grammaire
• Partir du symbole de départ (ou axiome) S;
• répéter :
– employer une règle : remplacer le côté gauche
par le côté droit
• jusqu’à ce qu’il n’y ait plus que des
symboles terminaux dans le texte.
 Langage
• Chaque chaîne qu’on peut obtenir ainsi est une
phrase de G.
• L’ensemble des phrases est le langage de G noté
L(G).
• Les étapes intermédiaires sont des proto-phrases
de G.
 Dérivations
• Une dérivation est une suite de pas de
l ’algorithme précédent:
S 1 2 3 w
• Si l ’algorithme peut passer de  à  en
zéro, une ou plusieurs étapes, on dit que 
produit , noté  * 
 Exemple
produit directement

 : program tutu  : program tutu

< déclarations >
⇒ < déclarations >
Comp
< instr. composée >. begin < suite d’instructions >
end.

Comp : < instr. composée > : : = begin < suite d’instructions > end

produit
< programme > ⇒ * program tutu
begin
end.
 Simplifications
• Un non-terminal est inaccessible s’il ne fait
partie d’aucune proto-phrase.
• Il est improductif s’il ne produit aucune
chaîne de terminaux.
• On peut retirer ces non-terminaux de la
grammaire sans changer le langage : ils ne
servent à rien.
 Algorithme: Productif

Algorithme qui donne les non-terminaux productifs.

Au départ: aucun non-terminal n’est marqué productif

tous les terminaux sont productifs
répéter
parcourir les productions A ::= 
si tous les symboles du côté droit  sont marqués productifs
alors marquer le côté gauche A comme productif
jusqu’à ce qu’un parcours ne marque rien de plus

On enlève les non-terminaux improductifs et les productions où ils apparaissent .

 Algorithme: Accessible
Algorithme qui donne les non-terminaux accessibles.

Au départ: seul le symbole de départ S est marqué accessible

répéter
parcourir les productions A ::= 
si le côté gauche A est marqué accessible
alors marquer tous les non-terminaux du côté droit  comme accessibles
jusqu’à ce qu’un parcours ne marque rien de plus

On enlève les non-terminaux inaccessibles et leurs règles.

Exercice: Réécrivez ces deux algorithmes avec un temps d'exécution

optimal (linéaire plutôt que quadratique).
 Arbre de dérivation
• Idée : pour une phrase, il y a beaucoup de dérivations essentiellement
identiques

• Déf. : Un arbre de dérivation pour u dans G est un arbre ordonné :

– Dont les nœuds sont étiquetés par des non-terminaux

– Dont les feuilles sont étiquetées par des terminaux (ou )

– Dont la racine est étiquetées par le symbole de départ
– Chaque nœud correspond à une règle de production
 Exemple d’arbre
S : : = p id R ; D C. (1)
D::= (2)
Grammaire R : : = (F) |  (3 | 4)
S: programme
R: paramètres du programme
F ::= id | id, F (5 | 6)
D: déclarations
C ::= b I e (7) C: instruction composée
I ::=  (8)
Dérivations
• gauche: S  p id R ; D C.  p id ; D C.  p id ; C.  p id ; b I e.  p id ; b e.
(1) (4) (2) (7) (8)
• droite: S  p id R ; D C.  p id R ; D b I e.  p id R ; D b e.  p id R ; b e.  p id ; b e.
(1) (7) (8) (2) (4)

Arbre de dérivation : S
p id R ; D C .
  bIe

 Ambiguité
Déf. : une grammaire est ambiguë s’il y a une phrase qui a plusieurs arbres de dérivation.
A éviter quand on veut générer un analyseur.
Peut être utile comme grammaire abstraite.

Exemple d’ambiguïté : les « else pendants » du Pascal

< instruction > : : = if < expr > then < instruction > else < instruction>
| if < expr > then < instruction >

if b then if c then x : = 5 else x : = 3

Autre exemple: la grammaire précédente est ambigüe

 Ambiguité : exemple : expressions
La grammaire suivante des expressions de Pascal avec +,* :
E ::= E+E | E*E | (E) | id
est ambiguë: par exemple, x+y+z a deux arbres d'analyse:
E E
E E E E
E E E E
x + y + z x + y +z
On notera ces arbres (x+y)+z et x+(y+z).
 Résolution des ambigüités
Une ambigüité (x+y)+z vs. x+(y+z) est
appellée une ambigüité d'associativité:
on la résoud en choisissant le coté récursif
(coté gauche en Pascal)
E ::= E+F | F
F ::= id | (E)
 Résolution des ambigüités
Une ambigüité (x+y)*z vs. x+(y*z) est
appellée une ambigüité de précédence:
on la résoud en ajoutant un nouveau non-
terminal par niveau de précédence.
Ici, terme T et facteur F:
E ::= E+T | T
T ::= T*F | F
F ::= id | (E)
 Résolution des ambigüités
L'ambigüité du if then else peut aussi se résoudre en introduisant des
non-terminaux:
<instruction close>: qui a tous ses else
<instruction non close>: sinon.

<instruction> ::= <instruction close> | <instruction non close>

<instruction close> ::= if <expr> then <instruction close> else <instruction close>
<instruction non close> ::= if <expr> then <instruction>
| if <expr> then <instruction close> else <instruction non close>
 Automate à pile
caractère courant

a
fenêtre de lecture (avance d’un caractère)

a sommet
= état courant

l’état définit le sommet

de la pile .
.
pile
.
.
 Automates à pile
Définition

Un automate à pile se compose de :

•V l’alphabet d’entrée (fini)

T
•Q les états (fini)
• q0 l’état initial
Q +états
• FΔ fini ⊆ les ( VT ∪
x finaux ou {accepteurs
ε}) x Q *

•
états à caractère à états à empiler
dépiler du trouver dans sur la pile
sommet de la fenêtre
la pile
 Fonctionnement

• L’automate démarre avec une pile vide,

dans l’état initial.
• Il suit les transitions (d, a, e) :
– lire le caractère.
– dépiler/empiler les éléments indiqués de la pile.
• Il accepte le texte s’il arrive dans un état
accepteur (final).
 Déterminisme
Un automate à pile est déterministe si :
– il n’a pas de transitions .
– si deux transitions lisent le même caractère, elle
ne peuvent pas s’appliquer sur la même pile :
la pile consultée de l’une ne peut pas être un préfixe
de la pile consultée de l’autre.
 BNF  Automates à piles
• Les états sont des items, càd des règles avec un « point de
lecture • » inséré.
• On utilise 3 types de transitions :
– Expansions (expand) : si l’état a le point devant un non-terminal B:
A::= … • B … on empile une règle pour celui-ci: B ::= • … avec le
point au début.
– Réductions (reduce): si l’état a le point en fin: B ::= …•, on le dépile
et on avance le point: A::= … B• …
– Lectures ou décalages (shift): si l’état a le point devant un terminal:
A::= … • a … , on le lit et on avance le point A::= …a • … .
 BNF: état initial/final
• On ajoute un nouveau symbole de départ S’
• l’état de départ est S’ ::= • S
• l’état final est S’ ::= S •
 BNF = Automates à pile
• Il y a aussi une transformation des
automates à pile vers les BNF.
• Un langage est donc non-contextuel ssi
c’est le langage d’un automate à pile non-
déterministe.
 Non-déterminisme
• L’automate obtenu est non-déterministe :
plusieurs expansions sont possibles, laquelle
choisir ?
– Regarder les k symboles en entrée pour choisir la bonne production:
analyseur descendants gauche LL(k)

– Postposer la décision (comme pour les automates finis)

analyseur ascendant droit (ex. yacc) LR(k)
 Analyse descendante LL(k)

• Grammaire LL(k) : Le choix de la bonne

expansion doit pouvoir se faire sur base des
k prochains symboles à lire.
 Cas simple

Si pour chaque non-terminal chacune des productions

commence par un symbole terminal différent
alors la grammaire est simplement LL(1)
Exemple

< instr > : : = if < expr > then < instr > else < instr > fi
while < expr > do < instr > od
begin < instr > end

le premier terminal permet de

faire le bon choix.
 LL(k): définition
Pour chaque choix d'une production pour A,
on peut faire ce choix sur base des k premiers caractères non encore lus:

G est LL(k) ssi

pour tout choix A ::= , A::=  de G () ,

PREMIER( )  PREMIER( ) = 

pour tout  qui peut suivre A dans une dérivation gauche: S g* wA
 Algorithme : PREMIER
PREMIER(A) donne les possibilités de début de A,
tronqués à k caractères.
Pour chaque non-terminal A, le tableau P[A] contient
un sous-ensemble de PREMIER(A), initialement vide.

tant que P change:

pour chaque règle A ::=  ajouter PREMIER() à P[A]

PREMIER(X1…Xn) est la concaténation tronquée à k de

PREMIER(X1) … PREMIER(Xn)

PREMIER(X) = {X} si X est terminal

PREMIER(X) = P[X] si X est non-terminal
 Exemple : sommes
Une somme est une expression Pascal du genre :
x+y+z+w
en Pascal, les opérations se regroupent de gauche à droite :
((x+y)+z)+w
La grammaire des sommes est donc:
S ::= S+id | id | (S) où id est le terminal pour les identificateurs
P[S] =  après la 1ère production
= {id} après la 2ème production
= {id, ( } après la 3ème production, qui est la valeur finale.
Donc cette grammaire n’est pas LL(1).
En général, une grammaire récursive à gauche n’est pas LL(k)
Comment rendre une grammaire LL(1) ?

• éliminer la récursivité gauche

• factoriser les parties communes
D201

Éliminer la récursivité gauche

• Une grammaire est récursive à gauche si un
non-terminal A se dérive strictement en une
proto-phrase commençant par A: A+A
• Une grammaire récursive à gauche n’est
jamais LL(k).
• A ::= Adevient A’ ,
A’ ::=A’|
 Algorithme
• pre : G sans cycle AA, sans vide A
• post : G sans récursivité à gauche
• invariant :  (Ak ::= Al), si k<i alors l>k :
les règles déjà traitées commencent par des grands terminaux

pour i := 1..n
pour j := 1..i-1
remplacer Aj par sa définition dans Ai ::= Aj 
remplacer Ai ::= Ai par Ai ::=Ai’ , Ai’ ::=Ai’|
 D202
Exemple
Élimination de la récursivité gauche
Grammaire d’expressions: Résultat
i=1 Ai::=Ai | 
E ::= E + T | T E ::= T E’
i=2 Ai::=Ai |  E’ ::= +T E’ | 
T ::= T * F | F T ::= F T ’
T’ ::= * F T’ | 
F ::= ( E ) | id F ::= ( E ) | id

Ordre: 1: E, 2: T, 3: F
 D203
Exemple 2
Élimination de la récursivité gauche
Grammaire : calcul : Résultat

A ::= B b | C e A ::= B b | C e
i=2 Ai::=Aj  Ai::=Ai |
B ::= A a | d B ::= B b a | C e a | d B::= CeaB’|dB’
B’::=baB’| 
C ::= A c | d C ::= B b c | C e c | d C ::= dB’bcC’|dC’
C ::= CeaB’bc|dB’bc|Cec|d C’::=eaB ’bcC’|ecC’|
Ordre: 1: A, 2: B, 3: C
 Factorisation
• Idée : postposer le choix en regroupant les
parties communes (facteurs)
• Exemple: I ::= if E then I | if E then I else I
devient I ::= if E then I C
C::= | else I
 Exemple : PREMIER
Pour la grammaire des expressions sans récursivité gauche:
0 : S ::= E 3 : E’ ::= + E 6 : T’ ::= * T
1 : E ::= T E’ 4 : T ::= F T’ 7 : F ::= (E)
2 : E’ ::=  5 : T’ ::=  8 : F ::= id
k vaut 1. Les itérations de PREMIER sont listées en colonnes. On visite les productions en
commençant par le fin (de 8 à 1). Par exemple, on peut lire dans la deuxième entrée de la
première colonne, qu’après la visite des productions 8 puis 7, l’ensemble P du non-terminal
F contient les symboles id et (.

8 : P[F] = {id} 5 : P[T’] = {*, } 2 : P[E’] = {+, }

7 : P[F] = {id, ( } 4 : P[T] = {id, ( } 1 : P[E] = {id, ( }
6 : P[T’] = {*} 3 : P[E’] = {+} 0 : P[S] = {id, ( }

P ne donne pas le début des productions 5 et 2: il faut connaître le début de ce qui est
derrière E’ et T’, calculé par SUIVANT.
 Suivant
• Quand PREMIER() est trop court, on regarde derrière
avec SUIVANT(A) : ce qui peut suivre A.
• Algorithme :
Le tableau des suivants est initialisé à vide
SUIVANT[S] := {$} /* le marqueur de fin */
tant que SUIVANT change
pour chaque règle A ::= B
ajouter PREMIER() . SUIVANT[A](tronqué à k) à SUIVANT[B]
Si ceci élimine les conflits, on dit que la grammaire est fortement LL(k).
Une grammaire LL(1) est fortement LL(1).
 Exemple : SUIVANT
Pour la grammaire des expressions sans récursivité gauche:
0 : S ::= E 3 : E’ ::= + E 6 : T’ ::= * T
1 : E ::= T E’ 4 : T ::= F T’ 7 : F ::= (E)
2 : E’ ::=  5 : T’ ::=  8 : F ::= id
PREMIER ne suffit pas pour E’, T’
On calcule SUIVANT:
S: {$}
0: E: {$}
1: T: {+,$} E’:{$}
4: F: {*,+,$} T’:{+,$}
7: E: { ),$}
1: T: {+,),$} E’:{ ),$}
4: F: {*,+,),$} T’:{+,),$}
 Analyseur descendant à pile
• Si la grammaire est LL(k) : à partir du non-terminal à
développer (derrière le • en sommet de pile) et des k
caractères d’entrée, on sait quelle règle appliquer. On le
met dans une table.
• L’analyseur fait :
– une lecture si le • est devant un terminal:
On avance la fenêtre et le point dans l'item.
– une réduction si le • est en fin de d'item:
On dépile l'item.
– une expansion si le • est devant un non-terminal:
On empile l'item d’après la table.
D215 Exemple
table LL(1) pour expressions
( ) + * id #
E (E → TE') erreur erreur erreur (E → TE') erreur
E' erreur (E'→ ε) (E'→ + E) erreur erreur (E'→ ε)
T (T → FT') erreur erreur erreur (T → FT') erreur
T' erreur (T'→ ε) (T'→ ε) (T'→ * T') erreur (T'→ ε)
F (F → (E)) erreur erreur erreur (F → id) erreur
S (S → E) erreur erreur erreur (S → E) erreur
D216 Trace de l’analyse LL(1) d’une expression
Contenu de la pile Chaîne d'entrée
$ [S  •E] id * id $
$ [S  •E] [E  •TE'] id * id $
$ [S  •E] [E  •TE'] [T  •FT'] id * id $
$ [S  •E] [E  •TE'] [T  •FT'] [F  •id] id * id $
$ [S  •E] [E  •TE'] [T  •FT'] [F  id•] * id $
$ [S  •E] [E  •TE'] [T  F•T'] * id $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  •*T] * id $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *•T] id $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *•T] [T  •FT'] id $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *•T] [T  •FT'] [F  •id] id $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *•T] [T  •FT'] [F  id•] $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *•T] [T  F•T'] $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *•T] [T  F•T'] [T' •] $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *•T] [T  FT'•] $
$ [S  •E] [E  •TE'] [T  F•T'] [T'  *T•] $
$ [S  •E] [E  •TE'] [T  FT'•] $
$ [S  •E] [E  T•E'] $
$ [S  •E] [E  T•E'] [E' •] $
$ [S  •E] [E  TE'•] $
$ [S  E•] $
$ $
D215

Gestion de la pile
On peut représenter les items en mettant les non-terminaux
non encore lus en ordre inverse sur la pile.
L’analyseur fait :
– une lecture si le sommet est un terminal:
On avance la fenêtre et on dépile.
– une expansion si le sommet est un non-terminal:
On empile en ordre inverse la partie droite de la règle trouvée
d’après la table.
– les réductions deviennent implicites.
 Analyseur récursif prédictif
• On peut employer la pile implicite de
récursion :
– le non-terminal de gauche = procédure appelée
– règles = corps de la procédure
– prédiction = test du fichier d’entrée
– point = adresse de retour
 Exemple : expression

procedure expr; E ::= T E’

begin
if input^ in [ ‘(‘ , ‘id’ ] choix par table LL(1)
then begin
term; T
exprend; E’
end
else erreur
end;
 Exemple: suite
E’ ::= +TE ’ | 
procedure exprend; E’
begin
if input^ = ‘+’
then begin
get; +
term; T
exprend; E’
end
else if eof or input^ = ‘)’ 
then
else erreur
end
 Actions
• On peut insérer du code dans les règles de
syntaxe, appelé « action »
• Ce code est exécuté lorsque l'analyseur
exécute cette partie de la règle
• Souvent ces actions construisent un arbre
d’analyse abstrait
 Arbre abstrait : exemple
E

T E’

F T’ E
+
T E’
x y

F T’

id  + id  
x + y

Arbre syntaxique concret de x + y, Arbre abstrait

pour la grammaire des expressions
sans récursion à gauche.
D222

2.3 Analyse syntaxique ascendante

• Idée : On choisit la règle à appliquer après avoir lu le

texte correspondant
– l’arbre d’analyse est construit de bas (feuilles) en haut (racine)
– la dérivation correspondante est droite : le non-terminal le plus à
droite est actif.
– Le programme remonte dans la dérivation.
• Problème : comment garder trace des règles possibles ?
 Exemple : Texte Ada

if x + 1 > y then x := 1 else x := 2 end if ;

<expr>
<expr> <instr> <instr>
> := :=
+ y x 1 x 2

x 1

*
if < expr > then < instr > else < var > := < expr > end if
manche

if < expr > then < instr > else < instr > end if
...

< instr >

 Automate fini caractéristique
• Décrit le comportement du sommet de pile
• Sa déterminisation donne des ensembles de
règles possibles
• Ses états finaux sont les réductions
 Automate fini caractéristique
Déf. : L’automate fini caractéristique est donné par
états = items(G)
alphabet = les symboles (terminaux ou non)
état initial = l’item de départ: [S’ ::= •S]
états finaux = les états où on réduit: [A ::= • ]
transitions = lecture : on déplace le point après le symbole lu
([A ::= • XX, [A ::= • Xoù X VN VT
expansion: si le point est devant un non-terminal, on choisit une de ses productions:
([A ::= • B•
 Exemple : expression
E
[S → .E] → [S → E.]

  
E + T
 [E → .E + T] → [E → E. + T] → [E → E + .T] → [E → E + T. ]

  S1
T
[E → .T] → [E → T. ]

  
T * F
 [T → .T * F] → [T → T. * F] → [T → T * .F] → [T → T * F. ]

  S2
F
[T → .F] → [T → F. ]
S3
 
( E )
 [F → .(E)] → [F → (.E)] → [F → (E.)] → [F → (E).]


id
[F → .id] → [F → id.]
S5
S
 Préfixe viable

• = la partie déjà analysée du texte

• = l’état de la pile d’un analyseur ascendant
(avant le point)
• def: un préfixe d’une proto-phrase droite
qui ne s’étend pas au-delà du manche le
plus à droite
 Item valide
• Intuitivement, un item valide donne un état possible de
l’analyseur quand il a lu un préfixe.

Def. : A::=  •  est valide pour le préfixe viable 

ssi

il y a une dérivation droite S d*  A w d*    w

 Déterminisation de l’automate fini
caractéristique
• En appliquant la déterminisation, on obtient un automate déterministe
où l’état atteint en suivant un préfixe viable est l’ensemble de ses
items valides.
• Cet état peut être impropre ou conflictuel, s'il contient:
– Une lecture (shift), càd un item où le point est devant un terminal
– Et une réduction, càd un item où le point est en fin
ou
- deux réductions (conflit R/R)
Dans ce cas, l’automate à pile associé est non déterministe, et la grammaire
n'est pas LR(0).
D252 W342
Construction directe
• On peut spécialiser la déterminisation pour
l’automate caractéristique de façon à ne pas le
construire: on fait les deux étapes ensemble.
D252 W342
Fermeture

fonction Fermeture (s : ensemble d’items) : ensemble d’items ;

(* fermeture par les  successeurs, ici les expansions *)

var q : ensemble d’items ;

début
q := s ;
tant que  [X •Y]  q et Y  P et [Y •] q
/* il y a une expansion qui n'est pas encore dans q
*/
ajouter [Y •] à q
retourne (q)
fin ;

s est appelé le noyau de q; il détermine q.

D253 W343
Successeurs
Le noyau du successeur par une transition étiquetée Y contient
les items de l’état de départ qui avaient le point devant Y, où
on a avancé le point.

fonction Transition(s : ensemble d’items, Y : VN  VN ) : ensemble d’items;

(* donne le noyau de l’état atteint par la lecture de Y *)
retourne ( {[X Y•] | [X •Y]  s } )
D253 W343

Construction des états

Q := { Fermeture({[S' ::= • S]})} /* l'ensemble des états part de l'item initial */

 :=  /* les transitions sont initialement vides */
pour chaque état q de Q, symbole X apparaissant derrière le point dans q faire
q’ := Fermeture(Transition(q,X)) ;
si q' non vide
alors
si q’ n'est pas dans Q
alors on l'ajoute à Q
on ajoute la transition de q vers q' lisant X dans 
D254 W339

Exemple : expressions
L’automate LR(0) donne :

+ T
S1 S6 S9 Les états S1, S2, S9 sont impropres :
id
ils contiennent des conflits LR(0) :
F
E
S5
cette grammaire n’est pas LR(0).
( +
id
F id *
S0 S3
id
( F
E )
T ( S4 S8 S11
T (

* F
S2 S7 S10
Exemple : expressions : états LR(0)
S0 = { [S → .E], S5 = {[F → id.]}
[E → .E + T],
[E → .T], S6 = {[E → E + .T],
[T → .T * F], [T → .T * F],
[T → .F], [T → .F],
[F → .(E)], [F → .(E)],
[F → .id] } [F → .id] }
S1 = { [S → E.], S7 = {[T → T * .F],
[E → E. + T] [F → .(E)],
[F → .id] }
S2 = { [E → T.], S8 = {[F → (E.)],
[T → T. * F] } [E → E. + T] }
S3 = { [T → F.] } S9 = {[E → E + T.],
[T → T. * F] }
S4 = { [F → (.E)] { →
S10 = [T T * F.] }
[E → .E + T],
[E → .T], { → (E).]
S11 = [F }
[T → .T * F],
[T → .F],
[F → .(E)], Les états S1, S2, S9 sont impropres :
[F → .id] }
ils contiennent des conflits LR(0) :
cette grammaire n’est pas LR(0).
 Exemple C q5
q1
a
b D
q2
La grammaire:
S ::= C | D
b e q7
C ::= a C | b
q0 e q3
D ::= a D | e
C
n’est pas LL(k) : on ne peut pas choisir entre C et D q4
car il peut y avoir des a d’abord dans les deux cas.
Elle est LR(0) car on peut choisir après lecture. S D
q6
Son automate déterministe caractéristique q8
ne contient pas de conflits LR(0).
q0 = {[S’ ::= •S], [S::= •C], [C::= •aC], [C::= •b], [S::= •D], [D::= •aD], [D::= •e]}
q1 = {[C::= a•C], [C::= •aC], [C::= •b], [D::= a•D], [D::= •aD], [D::= •e]}
q2 = {[C::= b•]}
q3 = {[D::= e•]}
q4 = {[S::= C•]}
q5 = {[C::= aC•]}
q6 = {[S::= D•]}
q7 = {[D::= aD•]}
q7 = {[S’::= S•]}
D256 W352

SLR
• Pour résoudre les conflits LR(0), on regarde
SUIVANT(A), où A est le côté gauche de la
règle à réduire.
D237 W353

Exemple : expressions SLR(1)

Les états conflictuels LR(0)
S1: le conflit entre réduire S, SUIVANT(S) = { $ }
et lire +, est résolu.
S2 : le conflit entre réduire E, SUIVANT(E) = { $, +, ) }
et lire *, est résolu.
S9 : idem.

Cette grammaire est donc SLR(1).

D257

Exemple : Affectations en C

S::=L=R| R
L : : = *R | id
R::=L

L = partie gauche (donne l’adresse)

R : expression ; une expression est une instruction en C
* : déréférenciation (prendre le contenu de l’adresse)
D258

Exemple : Affectations en C :
automate SLR(1)
S [S’  S • ]
[S’  • S]
[S  • L = R]
[S  • R] S3
[L  • * R] R [S  R • ]
[L  • id]
[R  • L] *
id S4
S2 L *
S5 [L  * • R]
[S  L • = R] id [R  • L]
[R  L • ] [L  id • ]
[L  • *R]
[L  • id]
S6 = id *
L R
[S  L = • R] S8 S7
[R  • L] [R  L • ] [L  *R • ]
[L  • * = R] L
[L  • id]

S9 R S2 est
conflictuel : SUIVANT(R) contient =.
[S  L = R • ] Cette grammaire n’est pas SLR(1).
D260 W350

Items LR(k) canonique

• On ajoute aux items une chaîne de longueur  k (la
prévision de l’item), qui indique le texte qui peut suivre cet
item: [A•, u]
• La prévision est propagée par les transitions.
• Une nouvelle prévision est calculée avec PREMIER pour
les expansions.
• On crée plus d’états qu’avec les autres techniques (LR(0),
SLR(1), LALR(1) ).
D261 W350

Fermeture
fonction Fermeture(I);
répéter
pour chaque item LR(k) [A•B, u] de I
et chaque chaîne v de PREMIER(u)
pour chaque règle B 
 ajouter [B •, v] à I
jusqu’à stabilisation
 Exemple : expressions : états LR(1)
+ T
S14 S20
id +
+ T id
S1 S6 S9
id S12
(
F
E *
S5 id
F S18
id F id
F
F ( *
S0 S3 E )
id ( S15 S13 S19
( (
T
E )
S11 F
S4 S8 *
T T S17 S16 S21
(

* F
S2 S7 S10

L’automate LR(0) est doublé : prévision avec $ (fin) ou avec )

 Exemple : expressions : états LR(1)
S0 = Fermeture(Début) S6 = Fermeture(S1, +))
= { [S  • E ,{$}] { [E  E + • T, {$, +} ],
[E  • E+T,{$, +}], [T  • T * F, {$, +, *} ],
[E  • T, {$, +} ], [T  • F, {$, +, *} ],
[T  • T * F, {$, +, *} ], [F  • (E), {$, +, *} ],
[T  F, {$, +, *}], [F  • id, {$, +, *} ] }
[F  • (E), {$, +, *}],
[F  • id, {$, +, *} ] } S9 = Fermeture(Succ(S6, T))
{ [E  E + T • , {$, +}],
S1 = Fermeture(Succ(S0,E)) [T  T • * F, {$, +, *}] }
= { [S  E • , {$}], S4 = { [F  ( • E), {$, +, *}],
[E  E • + T, {$, +}] } [E  • E+T,{), +}],
[E  • T, {), +} ],
S2 = Fermeture(Succ(S1,T)) [T  • T * F, {), +, *}
= { [E  T • , {$, +}], [T  F, {), +, *}],
[T  T • * F, {$, +, *}] } [F  • (E), {), +, *}],
[F  • id, {), +, *} ] }

Notation: Les prévisions des items LR(1) qui ont le même item sans prévision sont regroupés.
D270 W

LALR
• on garde les états LR(0)
• les prévisions sont la fusion des prévisions LR
ayant le même cœur (état LR(0) )
• Pour calculer les prévisions de [B •] :
– trouver les origines de la règle : expansions [B •]
– trouver les sources de l’expansion [A•B, u]
– calculer ce qui se trouve derrière B: PREMIER( u)
– faire l’union
– en cas de boucle: répéter jusqu’à stabilisation
Exemple : affectations en C
S0
S [S’  S • ]
[S’  • S , {$} ]
[S  • L = R]
[S  • R , {$} ] S3
[L  • * R] R [S  R • ]
[L  • id]
[R  • L , {$} ] *
id S4
S2 L *
S5 [L  * • R]
[S  L • = R] id [R  • L]
[R  L •, {$} ] [L  id • ]
[L  • *R]
[L  • id]
S6 = id *
L R
[S  L = • R] S8 S7
[R  • L] [R  L • ] [L  *R • ]
[L  • * = R] L
[L  • id]

S9 R Le conflit en S2 est résolu

[S  L = R • ] Cette grammaire est LALR(1).
 Exemple : expressions
S0 = { [S → .E], {$} S5 = {[F → id.]}
[E → .E + T],{$, +}
[E → .T], {$, +} S6 = {[E → E + .T],{), +, $}
[T → .T * F], [T → .T * F],
[T → .F], [T → .F],
[F → .(E)], [F → .(E)],
[F → .id] } [F → .id] }
(conflit décaler/réduire)

[S → S7 = {[T →
( S1 = { E.], {$} T * .F],
Etats impropres

[E → E. + T] {$, } +} [F → .(E)],
[F → .id] }
S2 = { [E → T.], {$, +, ) } S8 = {[F → (E.)],{), +}
( [T → T. * F] } [E → E. + T] }
S3 = { [T → F.] } S9 = {[E → E + T.],{$, +, )}
( [T → T. * F] }
S4 = { [F → (.E)] { →
S10 = [T T * F.] }
[E → .E + T],{ ), +}
[E → .T], { ), +} { → (E).] }
S11 = [F
[T → .T * F],
[T → .F],
[F → .(E)], Tous les conflits sont :résolus
[F → .id] } la grammaire est LALR(1).

Derrière, en mauve: les ensembles de prévision LALR(1)

D277 W368

Grammaires ambiguës
• Une grammaire ambiguë peut être plus
naturelle
• Elle provoque toujours des conflits
• Les conflits peuvent être résolus par des
règles de précédence et d’associativité, sans
augmenter le nombre d’états
 Exemple : expressions
La grammaire la plus naturelle est :
E ::= E + E | E * E | ( E ) | id
qui est ambiguë, mais peut servir de grammaire abstraite.

En donnant des règles d’associativité:

%left ‘ + ’
%left ‘ * ’
et de précédence données par l’ordre d’écriture,
on résout les conflits Shift/Reduce:
• Si le dernier terminal de la règle à réduire est plus fort que celui la
fenêtre, on réduit; sinon on lit.
• Si c’est le même, on emploie l’associativité: on réduit pour %left
• Enfin, Yacc et Bison décalent de préférence.
Pour les conflits réduire/réduire, ils préfèrent la règle écrite en premier.
 Exemple : if then else

En Pascal, on a :
<conditionnelle > ::= if E then I else I | if E then I
cette grammaire est ambiguë, mais sera analysée correctement
grâce à la préférence au décalage.
 Langages contextuels
• Certains langages ne peuvent pas être traités avec
les grammaires non-contextuelles.
• Méthodes:
– 1. un langage est non-contextuel ssi il peut être reconnu
par un programme dont la seule structure de données
infinie est une pile.
 Lemme de pompage
– 2. Si un langage est non-contextuel, alors il a une longueur k :
toute chaîne plus longue que k se décompose en 5 parties u v w
x y, et les parties v et x peuvent être répétées le même nombre de
fois: u vn w xn y fait aussi partie du langage. Les parties v w x
ensemble ont une longueur de k au plus.
• En pratique on l’emploie dans l’autre sens : on trouve une série de
phrases (une pour chaque k) dans le langage et, quelle que soit la
S décomposition, le lemme nous obligerait à inclure aussi des phrases
incorrectes : on sait alors que le langage ne peut être décrit par une
grammaire BNF.
A
A
u v w x y
 Exemple

{an bn cn} n’est pas non-contextuel:

on peut empiler pour chaque a, puis dépiler pour chaque b
mais alors on ne sait plus compter les c.
 Exemple

{an bn cn} n’est pas non-contextuel: si l'était,

ak bk ck se décomposerait en u v w x y
v w x est de longueur k au plus

donc il ne peut contenir à la fois des a, des b, et des c

donc en répétant v et x, on n'a plus assez du caractère manquant:
impossible.
D Ch.5-6 W Ch. 9

Sémantique statique
Rôle :

Vérifier les propriétés contextuelles statiques, principalement la

cohérence des types
 Syntaxe abstraite
La sémantique statique travaille sur les arbres de syntaxe abstraite.

if2

grt

plus assign assign

id iconst id id iconst id iconst

(x) (1) (y) (z) (1) (z) (2)

Exemple : Arbre de syntaxe abstraite

 Ifstat

Cond Stat Stat

E E Ass Ass

E E T E E E E

T F F T T

F F F

if id + iconst compop id then id := iconst else id := iconst fi

(x) (1) (>) (y) (z) (1) (z) (2)

Arbre de syntaxe concrète pour le même exemple

 Sémantique statique
• 1. un exemple : le typage
• 2. une technique de spécification : les
grammaires attribuées
D Ch. 6 W388

1. Typage
• Portée
• Systèmes de types
– équivalence
– coercition
– polymorphisme
– surcharge
 Portée
• Les types se déduisent des déclarations
• Les déclarations sont valides dans leur portée
• Elles peuvent être cachées par d’autres
déclarations
• Chaque langage a ses règles de portée / visibilité.
 Portée : exemple de Pascal
• En Pascal, la portée d’une déclaration est le bloc
dans lequel elle se trouve
• Il ne peut y avoir qu’une déclaration de ce nom
dans un bloc
• Une nouvelle déclaration du même nom dans un
bloc imbriqué cache la déclaration extérieure
• Les paramètres sont traités comme des variables
locales
 Portée : exemple d’Ada
• La portée d’une déclaration commence à la
déclaration et se termine à la fin du bloc
• Si le bloc est un package, elle comprend de
plus les packages qui importent celui-ci
• Une nouvelle déclaration ne cache un nom
que si le type est le même
 Portée : implémentation
• Pour chaque bloc on crée une table de symboles
• Chaque table a un lien vers le bloc englobant
• Chaque déclaration ajoute une entrée dans le bloc
(souvent avec des infos: type, taille, déplacement
dans le bloc d’activation, etc.)
• Chaque occurrence d’identificateur est recherchée
dans la liste des blocs en appliquant les règles du
langage.
D381

Expressions de types
• expressions de type : typiquement :
– des types de base :
• booléen, entier, réel, …
– des noms de types
– des constructeurs de type :
• tableaux
• records (structures, enregistrement)
• fonctions
• pointeurs
D383

Règles de typage
• Chaque langage a ses règles
• Parfois les règles demandent une
vérification dynamique (à l’exécution)
• Un système de typage est sain si toutes les
valeurs utilisées à l’exécution sont du type
calculé statiquement
• Un langage est typé si le typage impose des
conditions sur les programmes.
 Exemple : Pascal
• le typage de Pascal n’est pas sain :
– on n’est pas obligé de vérifier que les indices de
tableaux restent dans les bornes prévues
– les variants peuvent être modifiés sans contrôle
– les valeurs initiales ne sont pas nécessairement
du bon type
 Exemple de règles
• Si a est un tableau, alors dans indexation sur
a, les expressions des indices doivent avoir
le même type de base que le type d’indices
apparaissant dans la déclaration de a.
– exemple:
var a : array[1..10] of integer;
i : -10.. 0 ;
i := a[i] (* correct car le type de base est integer , mais pas recommand
D389

Equivalence des types

Quand 2 types sont ils égaux ?

2 grandes familles :
• équivalence par nom : ils doivent avoir la
même déclaration (Pascal, Ada)
• équivalence structurelle : on calcule s’ils se
ramènent à la même structure (C, Algol68,
ML)
 Equivalence par nom
ex. : Pascal, Ada
1) var x : record a, b : integer end
y : record a, b : integer end
les types de x, y sont différents (dépend de l’implémentation en Pascal74)

2) type r = record a, b : integer end

var x:r;
y:r;
les types de x, y sont équivalents

3) var x, y : record a, b : integer end

les types de x, y sont équivalents en Pascal, mais différents en Ada
D390

Equivalence structurelle
• deux types sont équivalents si leur structure
est la même (intuitivement, s’ils admettent
les mêmes valeurs)
• vérification en parcourant la structure des
types
• si cycles possibles, attention à la
terminaison
 Algorithme
structure globale : partition des nœuds du graphe,
notée t1 == t2 (les types déjà prouvés équivalents)

equiv(t1, t2)
si t1 == t2 alors renvoyer vrai
sinon si constructeur(t1) <> constructeur(t2)
alors renvoyer faux
sinon si pour tout i, equiv (fils(i,t1),fils(i,t2)))
alors union(t1, t2); renvoyer vrai
 Particularités de typage
• surcharge
• coercition
• polymorphisme
Surcharge (ou « polymorphisme ad hoc »)

Un identificateur est surchargé s’il peut avoir des significations différentes

suivant son type.

Exemple en Pascal, en ML, …

+: real x real  real

+: int x int  int

en Ada : l’utilisateur peut surcharger lui-même, par exemple :

function "*" (x, y : Matrix) return Matrix ;

 D400 W390

Résolution de la surcharge
Soit vis(k) l’ensemble des définitions de k visibles, avec leurs types

Ex. : vis(« + ») = { int x int  int,

real x real  real }

L’algorithme élimine les types d’abord en montant dans l’arbre puis en descendant.
La contrainte est que les arguments doivent avoir le type attendu par la fonction.

Ex. : vis(« p ») = {int, real}

vis(« f ») = {real  real, int  int, char  char}

3 + f(p) + int x int int

real x real real

int 3 f real real

int int
char  char
p  real
 int

A la fin de l’algorithme, chaque fonction doit avoir un seul type

sinon : ambiguïté de type
D396

Coercition
Def : Conversion implicite entre types (insérée par le compilateur)

Exemple : En Pascal, un entier peut être employé à la place d’un réel

dans une expression mais PAS à gauche de :=
ex. : var r : real ;
i : integer ;
begin
r := √i
i := r x interdit

Notation : typedest note une coercition vers typedest (notation

Ada)

Exemple : Dans tous les langages à objets :

une variable peut être « coercée » vers tous les types
dont son type statique hérite.
Les coercitions introduisent de nombreuses ambiguïtés,
surtout combinées aux surcharges :

Exemple : coercition integer  real notée real

/ : integer x integer  integer ;
/ : real x real  real ;

r := 3/2 peut se comprendre :

r := real (3/2) valeur 1.
ou r := real (3) / real (2) valeur 1.5

en Pascal : on utilise 2 noms pour la division: / et

div.
 Résolution de la coercition

• Pour résoudre les ambiguïtés de coercition, on se

donne des règles de préférence, p.ex.:
– préférer une coercition unique à une suite de coercitions
– préférer les coercitions le plus haut dans l’arbre

• S’il n’y a pas de surcharge: insérer des coercitions

lorsque nécessaire
• Avec surcharge : on étend l’ensemble des typages
avec un ordre partiel de préférence
• Pour Pascal, une passe ascendante suffit.
 Exemple : Pascal
• si les 2 opérandes sont entiers : résultat
entier
• si les 2 opérandes sont réels : résultat réel
• si un opérande est entier, le coercer en réel.
• exemple:
3+2+5*4.1 = real(3+2) +( real(5) * 4.1 )
D402 W391

Polymorphisme (paramétrique)
Une définition est polymorphique si elle peut s’appliquer de la même
façon à tout type.

Exemple en ML
head : ‘a list  ‘a renvoie le 1er élément d’une liste
où ‘a est une variable qui représente n'importe quel type
en Pascal :
nil :  ‘a

Différence par rapport à la surcharge

• l’opérateur a une seule définition :
son comportement est uniforme
• l’ensemble des types est potentiellement infini.
D409 W394

Résolution du polymorphisme
• Pour chaque occurrence d’une fonction polymorphe, on introduit une
copie de son type avec de nouvelles variables de type
• Pour chaque variable (de type inconnu), on introduit une nouvelle
variable de type. La portée des variables est locale à une ligne.
• Les variables de type peuvent recevoir des valeurs particulières dans
une substitution
• On résout les contraintes par unification, en calculant la substitution
qui permet de les satisfaire. Il y a un résultat le plus général, le type
principal.
D412

Exemple 1 (en ML)

On peut écrire une fonction « longueur » qui marche sur des listes de n’importe
quel type (impossible en Pascal)
fun longueur( [] )= 0
| longueur (x :: l) = longueur(l) +1
où: [] est la liste vide, de type ‘a list : liste de n’importe quel type.
: : est le constructeur de liste: (x :: l) est la liste obtenue en mettant x devant l.
Il est de type ‘b x ‘b list  ‘b list, càd que x doit avoir le même type que les
éléments de l.
Les types de longueur, x, l sont inconnus a priori. On introduit donc de
nouvelles variables ‘to, ‘tx, ‘tl pour leur type.
Les contraintes sont:
‘to = (‘a list)  int pour la 1ère ligne
‘to = (‘b list)  int pour la 2ème ligne. On en déduit ‘a = ‘b par unification.
W395

Exemple 2 (ML)
‘ta ‘a list‘tl2 ‘tl2
fun append ( [ ] ) (l2) = l2

append (x :: r) (l2) = x :: (append r l2)

‘tx ‘tr ‘tl3 !
Contraintes :

‘ta = ‘a list (‘tl2 ‘e1)

‘tl2 = ‘e1
:: : ‘b x ‘b list ‘b list
‘tr = ‘b list
‘tx = ‘b ‘tx list
‘ta = ‘b list (‘tl3 ‘e2 )
‘tx = ‘c
‘ta = ‘tr (‘tl3 ‘c list)
‘e2 = ‘c list
‘ta = ‘a list (‘a list ‘a list)
 2. Grammaires attribuées
• basées sur une grammaire BNF
• on ajoute à chaque nœud de l’arbre des attributs
(p.ex. : type, table de symboles, code, valeur). Ce
sont des champs supplémentaires
• les attributs sont calculés par des règles
d’attribution associées aux règles de la grammaire
 Attributs synthétisés et hérités
• Attribut synthétisé : remonte dans l’arbre
(calculé d’après les attributs de ses fils)
• Attribut hérité : descend dans l’arbre
(calculé d’après les attributs de son père
et/ou de ses frères)
• Attributs lexicaux (synthétisés) : pour les
terminaux, calculés par l’analyseur lexical
(p.ex. la valeur d’une constante)
 Exemple : calculatrice
Règle de grammaire Règle d’attribution
S ::= E val : attribut synthétisé de E, T, F, nombre
E ::= E1 +T E.val = E1.val + T.val
E ::= T E.val = T.val
T ::= T1 *F T.val = T1.val * F.val
T ::= F T.val = F.val
F ::= ( E ) F.val = E.val
F ::= nombre F.val = nombre.val
Pour l ’exemple suivant, il nous faut un type abstrait « table de symboles » :

ajout (table, id, def) : table - crée une erreur si id est déjà dans table
- dans cet exemple, def est le type de la variable ;
on peut mettre d ’autres infos dans la table (le déplacement, etc.)

t1 + t2 : table les défs de t2 écrasent les défs de t1

vide : table

rech(table, id) : def retrouve la déf courante de id.

La table sera synthétisée par les déclarations et héritées par les instructions.
D316
Exemple : types dans les
déclarations
typeh: attribut hérité de L
tab: attribut synthétisé de L: table de symboles (nom, type)

Règles de grammaire Règles d'attribution

D ::= L : Type L.typeh = Type
L ::= id, L1 L1.typeh = L.typeh
L.tab = ajout(L1.tab , id.entrée, L.typeh)
| id L.tab = ajout(vide, id.entrée, L.typeh)
 Graphe de dépendances
• Sur un arbre attribué, on ajoute une flèche si
un attribut est employé pour calculer un
autre
• Les flèches changent au max. d’1 niveau
• L’ordre du calcul doit suivre les flèches
• S’il y a un cycle, le calcul n’est pas possible
 Exemple : Graphe de
dépendances
D

typeh L tab : T

id , typeh L tab bool

id , typeh L tab

id

x, y, z : bool;
 Exemple : typage Pascal
Calcul du type d’une expression numérique en Pascal
(avec surcharge à la place de coercition) dans la grammaire abstraite

type : attribut synthétisé de E : {int, real}

Règles de grammaire Règles d’attribution

E0 ::= E1 op E2 op peut être +, -, *
E0.type = if E1.type = int

and E2.type = int

then int
else real
| (E1)
E0 . type = E1 . type
 Exemple : arbre abstrait
Les grammaires attribuées peuvent aussi servir à calculer
l’arbre abstrait comme attribut de l’arbre concret.
cons(e,g,d) construit un nœud d’arbre à 2 fils, g et d.
a est un attribut synthétisé représentant l'arbre abstrait
Règles de grammaire Règles d’attribution
E ::= E1 +T E.a = cons(+, E1 .a , T.a)
E ::= T E.a = T.a
T ::= ( E ) T.a = E.a
T ::= id T.a = id
Pour un DAG, cons renvoie le nœud (si) existant
Ordres d’évaluation des attributs
• ordre fixe : donné a priori (p.ex. suit la méthode
d’analyse syntaxique : LL ou LR)
• ordre statique : d’après la grammaire attribuée, on
précalcule un ordre
• ordre dynamique : le graphe de dépendance est
construit avec l’arbre; les attributs sont évalués
dans un ordre compatible avec le graphe
D326
Ordre fixe : grammaire S-
attribuées
• Une grammaire est S-attribuée si elle ne
contient que des attributs synthétisés
• Implémenté dans les analyseurs ascendants
(Yacc, Bison, …)
• Syntaxe: ex: E : E '+' E { $$ = $1 + $3 } ;
– l’évaluation de l’attribut synthétisé $$ se fait
dans l’action de réduction
– $i désigne l’attribut du ième symbole
D328
Grammaires S-attribuées :
Implémentation
• L’analyseur LR conserve une pile des non-
terminaux déjà réduits
• Il leur associe leur attribut synthétisé
• Lors de la réduction, les $i sont trouvés en
sommet de pile, utilisés pour calculer $$, et
remplacés par $$.
 Exemple : calculatrice
Règle de grammaire Action
d’attribution(Yacc)
S:E;
E : E ‘+’ E { $$ = $1+$3 }
| E ‘*’ E { $$ = $1*$3 }
| ‘ (‘ E ‘ ) ’ { $$ = $2} ;
F : nombre { $$ = $1} ;
D329

Exemple : calculatrice - pile

• Dans cet exemple, la pile des attributs se
comporte comme une pile d’évaluation
postfixe.
D330 W434
Ordre fixe : grammaires L-
attribuées
• Une grammaire est L-attribuée si on peut évaluer
les attributs lors d'un parcours en profondeur de
gauche à droite de l’arbre d’analyse
• càd: un attribut hérité ne dépend que d’attribut
hérités plus à gauche ou du père
• peut s’implémenter dans LL(1), LALR(1), etc.
 Exemple : expression LL(1)
val : attribut synthétisé
h : attribut hérité de E': valeur de l'expression à gauche

Règles BNF Attribution

E ::= T E' E'.h = T.val
E.val = E'.val
E' ::= - T E'1 E'1.h = E'.h - T.val
E'.val = E'1.val
| E'.val = E'.h
T ::= nb T.val = nb.val
Ex d’évaluation d’une expression
E.val=1

T.val = 9 E’.h = 9 val

=1

nb.val = 9 T.val = 5 E’.h = 4 val

=1
val =1
nb.val = 5 T.val = 3 E’.h = 1

nb.val = 3

arbre attribué pour l’expression 9 - 5 - 3

D340

L-Attributs dans LL(1) récursif

• On ajoute les attributs hérités comme
paramètres d'entrée de la procédure du non-
terminal, les attributs synthétisés comme
paramètres de sortie
• On ajoute des variables locales pour les
attributs apparaissant dans une règle du
non-terminal
 Exemple : expressions LL(1)
procedure reste(h: integer; var val: integer); Règle LL(1) attribution
var tval, e1val : integer; E' ::=
begin
if eof
then val := h
else if input^ = ‘ - ’  E'.val = E'.h
then
begin
get; (* lit ‘ - ‘ *)
terme(h, tval); | - T E'1 E'1.h = E'.h - T.val
reste(h-tval, e1val); E'.val = E'1.val
val := e1val
end
else error
end
D342

L-attributs dans LR
• On ajoute des actions à l’endroit où les attributs
doivent être calculés
• les actions dans un règle (mais pas à la fin) seront
traduites par des marqueurs : des non-terminaux à
définition vide, avec une action en fin.
• On accède aux attributs des non-terminaux
précédents en remontant la pile ($0, $-1, etc.)
 Exemple : marqueur
Une règle
S : {$$ = 5} B ;
est traduite par
S : M B;
M : {$$ = 5};
Dans B la valeur de M est accessible comme $0
(c’est l’élément précédent sur la pile).
D344

Ex: table de symboles pour C

D : déclaration
L : liste d’identificateurs
T : type (se place avant en C)

BNF Attribution insérée dans la règle BNF

D ::= T { L.typeh = T.type }

L
T ::= int { T.type = entier }
L ::= {L1.typeh = L.typeh }
L1, id {L.tab = Ajout(id.nom, L.typeh, L1.tab) }
| id {L.tab = Ajout(id.nom, L.typeh, L1.tab) }
 Ex: Table de symboles (Bison)
Dans cet exemple l’action {$$=$1}n’est pas nécessaire:
On peut utiliser l’attribut synthétisé type pour l’attribut hérité typeh

D: T {$$=$1} L {$$ = $3 };
T : int {$$ = integer() };
L: L ',' id {$$ = add($3, $<ty>0, $1)}
| id {$$ = add($1, $<ty>0,
empty() ) };
D23, D333, D347

Ex: mise en page de formule

• EQN est un programme de mise en page de
formules mathématiques (dites "boîtes")
• les indices doivent être plus bas et dans une fonte
plus petite.
• P.ex. le texte d’entrée E sub 1 .a est mis en page
comme E1.a . Les boîtes servent à l'espacement.
• sub s'associe à droite: E sub i sub j = E sub (i sub j)
D334

Ex: mise en page de formule

• tc: attribut hérité: taille des caractères
• ht: attribut synthétisé: hauteur totale de la boîte

S ::= B B.tc = 10 au départ, taille 10 points

S.ht = B.ht
B ::= B1 B2 B1.tc = B.tc
B2.tc = B.tc
B.ht = max(B1.ht, B2.ht)
B ::= B1 sub B2 B .tc = B.tc
1
B2.tc = Rétrécir(B.tc) plus petit pour l'indice
B.ht = Déplacer(B1.ht, B2.ht) p.ex B1.ht + B2.ht/2
B ::= texte
 Même exemple en Bison

%left ' '

%right sub S.ht B.ht
%% B.tc
S : {$$ = 10 } B {$$ = $2};
B : B ' '{$$ = $0} B {$$ = max($1, $4)}
| B sub {$$ = Rétrécir($0)} B {$$ = Déplacer($1,$4)}
| texte {$$ = $1 * $0};
Avant chaque B, une action met tc dans $$ pour qu'il soit disponible dans
B comme $0.
On peut omettre {$$=$0} avant le premier B d'une règle pour B.
D350

Utiliser les attributs synthétisés

Ex: types dans les déclarations (Pascal)
• La règle D ::= L ‘ : ’ T fait que le type n’est pas
disponible dans L ::= id, L
• Solution (peu naturelle): mettre le type dans la
liste: D
R
D ::= id R R
R ::= , id R | : T T
id , id : integer
T ::= integer | ...
 Ex: types dans les déclarations
(Pascal)
D ::= id L D.tab = Ajout(id.nom, L.type, L.tab)

L ::= , id L1 L.type = L1.type

L.tab = Ajout(id.nom, L1.type, L1.tab)

L::= : T L.type = T.type

L.tab = vide

Tous les attributs sont synthétisés.

 Ordre statique
• Pour certaines grammaires attribuées (l-
ordonnées, fortement non-circulaires) on
peut calculer un ordre de visite de l’arbre à
partir de la grammaire.
• Utilisé dans les systèmes FNC-2, GAG, etc.
 Ordre dynamique
• Si les conditions précédentes ne sont pas
vérifiées, on peut toujours construire l’arbre
d’analyse, son graphe de dépendances, et le
trier pour faire le parcours.
• En pratique, cette technique est coûteuse.
• Utilisé p.ex. dans le système Elegant
 Génération de Code
pour langages impératifs
Chap. 2 et 7 à 10 du Dragon ’s book
 Plan
• Expressions
• Instructions
• Allocation mémoire
– procédures imbriquées
 1. Expressions
• sans partage : Pile
– Allocation de registres
– Réordonnancement
• avec partage : DAG
– utilisation avec pipelines
 Pile d’expressions
Les expressions peuvent se calculer avec une pile en notation
postfixe (appelée aussi Polonaise inversée)
(p. ex. calculette Hewlett-Packard)

Exemple : ((3 * 5) + (7 * 4)) / (3 + 5)

Postfixe : 3 5 * 7 4 * + 3 5 + /

Parenthèses inutiles

chiffres empiler
opération prendre les données sur la pile
les remplacer par le résultat

4 5
} 28 } 8
5
}* 7 *
15
}+ 3 * }
43 / 5
3 15 43
Ce principe est employé dans les langages à pile PostScript et FORTH,
et dans les machines abstraites: P-machine (Pascal), JVM (Java)
 Registres

Types de registres courants:

•universels
•spécialisés:
• réels flottants
•données
•adresses
•base
•index
•PC: program counter (prochaine instruction)
•CC: codes de conditions

Les processeurs RISC ont de nombreux registres universels

D613 W565

Allocation de registres
Technique simplifiée pour les arbres :
1. réorganisation des calculs
2. allocation des registres par simulation de pile
 Réordonnancement
Idée : on évalue d’abord l’expression qui emploie le plus de regist
car 1 registre sert pour le résultat.
+
Exemple :
t1 t2
4 reg 3 reg

R4
R3
R2 RES 2
R1 RES 1 RES 1 RES 1 }+ RES
calcul de t1 ; calcul de t2 ; addition
Calcul du meilleur ordre

calculer récursivement le nombre de registres optimal :

r ( t1 op t2) =
{ max (r1, r2) si r1  r2

r1 + 1 si r1 = r2

où r1 = r(t1)

r2 = r(t2)

Le cas de base dépend du type d’instructions de la machine.

Pour une architecture load/store, il faut 1 registre.
 Exemple

_ 3

+ 2 _ 2

a b c + 2
1 1 1

d e
1 1

(a + b) - (c - (d + e)) requiert 3 registres sur une machine load/store

 type abstrait Pile
• empiler(P, E) ajoute E sur P
• dépiler(P) enlève le sommet de P et le renvoie
• échanger(P) échange le sommet et celui en dessous
• sommet(P) renvoie le sommet sans changer la pile
• sommet2(P) renvoie l’élément en dessous du sommet
 Algorithme d’allocation
• pilereg : pile statique de registres libres
• pilereg n’est jamais vide
• Le sommet de pilereg contiendra le résultat
• pilereg doit être remis dans l’état initial
• Une pile de temporaires est employée
lorsqu ’il n ’y a plus assez de registres (> r)
D617

Algorithme : cas de base

la variable est chargée dans le registre :
ProdCode(n) :
si n est une feuille (une variable d’adresse var):
émettre( lw sommet(pilereg) , 0(var) )

Note: diffère de D617 car prévu pour une machine load/store (p.ex.
MIPS)
 Algorithme : cas 3
• s’il est plus avantageux de respecter
l’ordre : r1r2, r>r2
ProdCode(n1);
R := dépiler(pilereg);
ProdCode(n2);
émettre(op, R, R, sommet(pilereg)) ;
empiler(pilereg, R);
 Algorithme : cas 2
s’il est plus avantageux d’inverser l’ordre
càd si r2r1, r>r1:
ProdCode(n2);
R := dépiler(pilereg);
ProdCode(n1);
émettre( op, R, sommet(pilereg), R);
empiler(pilereg, R);
 Algorithme : cas 4
si les deux sous-termes utilisent plus de registres qu’il n’y en
a: r1, r2 r
ProdCode(n1);
T := dépiler(piletemp);
émettre(sw sommet(pilereg), T ); // stocke le résultat en T
ProdCode(n2);
émettre(lw sommet2(pilereg), T ) ; // charge T
émettre(op sommet(pilereg), sommet2(pilereg), sommet(pilereg) );
empiler(piletemp, T)
 Exemple
pour (a + b) - (c - (d + e)) avec 2 registres :
lw R1 , a
lw R2, b _ 3
add R1, R1, R2
sw R1,T // T := a+b _
+ 2 2
lw R1, d
lw R2, e
a b c + 2
add R1,R1,R2 // R1 = d+e 1 1 1
lw R2, c
sub R1, R2, R1 // R1 = c-(d+e) d e
1 1
lw R2, T
sub R1, R2, R1 // R1 = (a+b)-(c-(d+e))
D579 W563

Bloc de base
• le graphe de flot de contrôle (ou ordinogramme) donne les
successions possibles d’instructions

ex: while B do S B

S
• un bloc de base est une suite d’instructions sans
branchements entrants ni sortants.
D598 W575

Partage de calculs : DAG

• représente les calculs d’un bloc de base
• les sous-expressions communes sont
partagées
• forme: graphe acyclique :
– les feuilles sont des variables ou des constantes
– les nœuds sont des opérateurs
– les nœuds sont étiquetés par les variables
affectées
 Exemple : DAG
c := a[i]+1;
b := 1-a[i];
b c
- +

1 [] 1

a i
D619

Registres pour DAG

• En cas de partage, la technique en pile n’est
pas toujours optimale
• On divise le DAG en arbres en coupant aux
nœuds partagés
b c
- + t b c
[] - +
1 [] 1
a i 1 t t 1
a i
W580

Pipelines
• Dans les processeurs à pipeline, le résultat n’est
disponible qu’après un délai
• Il faut insérer des instructions indépendantes
• Algorithme glouton:
– tri topologique du DAG
– choix d’une instruction parmi les minimales
– calcul des collisions
• Augmente l’emploi des registres
 Algorithme pour pipelines
Simplification : le délai est 1 cycle.

Candidats := minimaux(DAG);
Collisions := {instruction précédente };
répéter
b := ChoixHeuristique(Candidat \ enCollision(Candidats, Collisions );
si b = erreur alors insérer NOP; Collisions := vide;
sinon enlever b de Candidats; Collisions := {b};
ajouter dans candidats les nœuds dont b était le seul prédécesseur
jusqu’à Candidats vide
 2. Instructions

• 2.1 conditionnelles
• 2.2 boucles
• 2.3 case
 Instructions conditionnelles

La plupart des machines ont un jeu d’instructions qui contient :

exemple : MIPS

un goto absolu jq: goto q

un goto conditionnel beq $rs $rt q : if $rs = $rt then goto PC+q
un goto calculé jr $r : goto $r

change le PC (program counter), le registre qui contient l ’adresse de la prochaine

instruction.
 Instructions conditionnelles
if if
e codeD(e)
beq $r, $zero codeD(e) e
then
then
st1 code(st1) beq $r, $zero st
j
else code(st)
st2 code(st2)

(a) deux branches (b) une seule branche

Instructions traduisant les instructions conditionnelles
 Boucles

while repeat
e codeD(e) code(st) st
beq $r, $zero until
do
codeD(e) e
st code(st)
j beq $r, $zero
(a) boucle while (b) boucle repeat

Génération de code pour les boucles

 Instruction case
Laisse la valeur du sélecteur
codeD e  dans un registre $re
... Branchement indexé vers la fin de la
jr $t1
case e of L0: Table des branchements
codeD st0 
0 : st0 ; j exit Branchement vers la fin de l’instruction
1 : st1 ; codeD st1 
. j exit
.
. .
.
k : stk .
end Lk :
codeD stk 
j Lk
j
.
.
. Table des branchements
j L2
q: j L1
exit :
 3. Allocation de mémoire
• les variables ont deux emplois différents :
– à gauche de « := », c’est une adresse
– à droite de « := », c’est la valeur stockée à cette adresse
• le langage source admet-il:
– la récursivité ? si oui: nouvelles variables à créer
– l’imbrication de procédures ? si oui : retrouver les liens
 Allocation
• La mémoire est habituellement divisée en:
– code : lecture seule
– constantes : lecture seule
– variables globales : adresse statique
– pile : pour les variables locales de procédures
récursives
– tas : pour les autres variables dynamiques
 Tableaux
• En Pascal les dimensions d’un tableau sont statiques
• Les extensions de Pascal ont des tableaux
Algol-68
Ada
C
} taille dynamique

var < nom > : array [l1 .. u1, ..., lk .. uk] of < type >

Rangement
la ième dimension di = ui - li + 1 (si ui > li)

• par ligne:
le dernier indice varie d’abord: a[1,1] a[1,2] a[1,3] a[2,1] a[2,2] a[2,3]

• par colonne

le premier indice varie d’abord: a[1,1] a[2,1] a[1,2] a[2,2] a[1,3] a[2,3]
 Tableaux : indices
• Pour accéder à un élément a[e,f,g] on
calcule l’adresse a+ (e-l1)* d2 *d3 + (f-l2)*d3
+ (g-l3)
• en Pascal seuls e,f,g sont dynamiques
• on peut précalculer la partie statique
• Le schéma de Horner limite les
multiplications : e* d2 *d3 + f *d3 + g = (e*
d2 + f) *d3 + g
 Records
En Pascal tous les types ont une taille statique
pour chaque champ on a un déplacement relatif
Ex. record p.ex.
a : array [1 .. 5, 1 .. 5] of boolean 1 byte par bool.0
x : integer 1 byte par int. 25
y : real 1 byte par real26
end 27
Les machines ont souvent des contraintes d’alignement :
p.ex. un réel doit avoir une adresse multiple de 4
on doit laisser du remplissage
ou réordonner les champs

Traduction d ’un accès à un champ

codeG (v.ci) = codeG (v) ; # laisse l ’adresse de v dans un registre $t

add $t, (ci), $t #laisse l ’adresse du champ dans $t.
# (ci) est le déplacement de ci
D438 W25

Pointeurs
Les cases créées par new ne peuvent pas être allouées sur la pile car
elles vivent plus longtemps que la procédure qui les a créées.
On réserve une zone spéciale, le TAS.

PILE TAS
SP
La gestion du tas

- comment récupérer la place lors d’un dispose ?

- risque de fragmenter la mémoire si plusieurs tailles

p.ex. : organisation en pools où toutes les cases ont la même taille.

 Procédures récursives
• Chaque appel à une procédure récursive
doit avoir de nouvelles variables locales
• L’allocation est LIFO, donc en pile
• Les instances de procédures sont donc
stockées dans une pile.
• Souvent un registre SP pointe vers le
sommet de la pile.
D433

Pile de contrôle

L ’exécution des procédures (récursives) est imbriquée  représentable par une pile
Le contenu de la pile représente une branche de l ’arbre d ’activation.
La pile contient des blocs d ’activation.
Le registre FP (frame pointer) point sur le bloc courant, sommet de la pile.

Chaque bloc contient:

• des temporaires (pour l ’évaluation d ’expressions).
• les variables locales;
• l ’état des registres à restaurer, en particulier:
• l ’adresse de retour est la valeur du PC (program counter)
• le lien d ’accès ou prédécesseur statique (si imbrication)
• le lien de contrôle ou prédécesseur statique (valeur du FP) pointe vers le bloc appelant
• les arguments
• la valeur de retour (pour une fonction)
D446-449
Protocole d ’appel

Répartit les rôles de l ’appelant et de l ’appelé.

Par exemple:
1. l ’appelant crée le bloc d ’activation
2. l ’appelant évalue les arguments et les met dans les registres ($a) ou dans le bloc
3. l ’appelant calcule le lien d ’accès en suivant le sien.
3. l ’appelant sauve le PC et saute au début de l ’appelé
4. l ’appelé alloue et initialise les variables locales
5. l ’appelé commence son exécution (qui calcule la valeur de retour)
Au retour:
1. l ’appelé restaure les registres, en dernier le PC (saut de retour)
D453

Accès aux noms non locaux

• Algol, Pascal, Ada, ont des procédures imbriquées
• Ils emploient la portée statique : les variables sont
recherchées dans le texte englobant
• la portée d’une variable est le sous-programme où
elle est déclarée
• On emploie la déclaration la plus locale
Procédures
Distinguer l’imbrication
• statique du texte des procédures
• dynamique des appels de procédure

une variable a une distance d’imbrication statique :

procédure p
var x : integer
procedure q 1 niveau d’imbrication statique

... x ...
end

L ’imbrication de procédures n ’existe pas en C, FORTRAN, Java, ...

proc p(a)
var b;
var c
proc q
var a
var q Les flèches montrent pour
proc r chaque utilisation de
var b variable, la définition
b 0
1 associée
a
c 2
. Les nombres indiquent la
. distance d’imbrication des
.
occurrences de variables.
a 0
b 1
q 0
proc s
var a
.
. 0
.
a 1
q
a
q
 Prédécesseurs statiques
• Le lien d’accès (ou prédécesseur statique) pointe vers l’activation la
plus récente de la procédure englobante

program h ;
h
var i : integer ;
proc p
var a p p
proc r
var i : real p r
i := i/2 ; a := 5
if i > 0 p s
then i := i - 1 ; p i en cès
L ac
else r r d’
fi
i := 2 ;
p;
p
end.

Figure : Un programme et son arbre d ’activation (ou d’appels).

Les crochets donnent l ’imbrication des procédures.
D461

Accès non local

• Chaque occurrence de variable est identifiée par sa
différence d’imbrication d et son déplacement o
• Pour trouver son adresse, on suit d liens d’accès
(donne le bloc d’activation de sa déclaration) et on
ajoute o.
 Mise à jour
• Lors d’un appel, le nouveau lien d’accès est
obtenu en suivant d liens d’accès de
l’appelant.
 Exemples
proc p proc r proc r
proc q proc p proc q
q proc p
q proc q q
p
p q

* *
p r r
MP
* *
p q
q SP
MP
*
p
q SP

d=0 d=1 d=2

(a) (b) (c)
D467

Passage de paramètres
• Diffère d’un langage à l’autre
• Principaux types :
– par valeur
– par référence (ou par variable)
– par copie (in out)
– par nom
 Passage par valeur
• Le paramètre est comme une variable locale
• L’appelant évalue la valeur de l’argument et
le place comme valeur initiale du paramètre
 Passage par référence
• L’adresse de l’argument est passée.
• En Pascal: noté par var
 Exemple
procedure Troquer(var x, y : integer);
var t : integer;
begin
t := x;
x := y;
y := t
end;
N’aurait aucun effet en passage par valeur !
D470

Passage par copie

• Utilisé p.ex. en Ada (mode in out)
• La valeur de l’argument est copiée dans le
paramètre ; au retour la valeur du paramètre
est copiée dans l’argument
• Même effet que le passage par référence
sauf en cas de synonymie.
D471

Exemple
program ValeurResultat(output);
var a : integer;
procedure Hasardeuse(var x:integer);
begin x:=2 ; a := 0 end;
begin
a:=1; Hasardeuse(a) ; writeln(a)
end.
a=0 si passage par référence, a=2 si passage par copie.
D471

Passage par nom

• Remplacement textuel du paramètre par
l’argument (comme pour une macro)
• Utilisé seulement en Algol-60.
 Exemple
procedure Troquer(x,y:integer);
var t:integer;
begin
t := x;
x := y;
y := t
end;
Troquer(i, t[i] ) met i dans t[t[i]] !
 Passage de fonctions en
paramètre
• Pour les langages à portée statique (p.ex. Pascal):
On doit passer l’adresse de début du code et le lien
d’accès
Exemple : fonction en paramètre
Program HP
HP HP
proc p(fune h)

h
q q
proc q
func f
p p
p(g)

p(f)
f f
func g

q
(b) p (c)
situation de la pile
situation de la pile
(a) après appel de p(f)
après appel de p(g)
Un programme avec et (en pointillé)
g et (en pointillé)
fonction en paramètre après appel de h
après appel de h
 Sémantique dénotationnelle

Idée :

Le sens d’un programme est un objet mathématique

(souvent, une fonction)
 Qu’est-ce que c’est ?
• La sémantique donne le sens d’un langage
• Pour un langage de programmation, elle
permet de prévoir le comportement du
programme
• Pour un langage séquentiel, on suppose que
le seul comportement observable est le
résultat final.
 A quoi ca sert ?
La sémantique permet de:
– décider ce que doit faire un programme dans
des cas complexes
– calculer si des programmes sont équivalents, ce
qui permet à un compilateur de remplacer l’un
par l’autre.
– dériver la plupart des analyses de programmes
– construire des compilateurs fiables
 Types de sémantique
• Sémantique opérationnelle : décrit
comment un programme peut s’exécuter
• Sémantique dénotationnelle : donne un
objet (p.ex. une fonction des données vers
les résultats) comme sens d’un programme
• Sémantique axiomatique : donne des règles
pour raisonner sur les programmes
 Liens entre types de sémantique
les 3 types de sémantique ont leur utilité:
– la sémantique opérationnelle facilite la
construction de compilateurs
– la sémantique dénotationnelle donne les concepts
du langage
– la sémantique axiomatique est la plus utile pour les
programmeurs
On peut passer de l’une à l’autre en démontrant leur équivalence.
 Notation lambda ()
But : une notation pour les fonctions

Ex. : la fonction qui met au carré (sqr en Pascal)

 x. x * x

 est une déclaration de paramètre qui suit les règles de visibilité :

 x . x + sqr ((x. x + x) (x + 2))

On peut simplifier grâce aux règles :

 : ( x . E) (A) se simplifie en E [A x]

E où toutes les occurrences libres de x sont
remplacées par A
 : ( x . E(x)) se simplifie en E, si E n’a aucune occurrence libre de x
Exemple de simplification
x. x + sqr ((x . x + x) (x + 2)) def.
1 2
portée : x. x + ( x. x * x) (( x. x + x) (x + 2))

Il y a deux endroit où  s’applique : 1 , 2

3 4
1  x. x + ((x. x + x) (x + 2)) * (x. x + x) (x + 2)
4
3  x. x + ((x + 2) + (x + 2)) * (x. x + x) (x + 2))
4  x. x + (((x+ 2) + (x + 2)) * ((x + 2) + (x + 2)))

=  x. 4x2 + 9x + 16
si on emploie les simplifications arithmétiques.

On pourrait aussi appliquer les règles dans un autre ordre : on arrive au

même résultat (Théorème de Church-Rosser)

1
Ex. : 2  x. x + (x. x * x) (x+2 + x+2)
1  x. x + (x+2 + x+2) * (x+2 + x+2)
 Domaines sémantiques
Quel objet mathématique représente le sens d’un programme ?

Ceci dépend du langage considéré, et du sens qu’on lui accorde.

Ex. : Pour Pascal, on convient habituellement que :

- il devrait être déterministe

(OK si on évite les effets de bord dans les fonctions)

- on ne considère que les états initiaux et finaux des fichiers

le sens est une fonction des états initiaux vers les états finaux.

Ex. : Pour les langages concurrents (Ada, LOTOS, CSP, CCS,...) les opérations
intermédiaires visibles comptent aussi :
le sens est un objet plus compliqué (p.ex. des arbres)
 Compositionnalité
On veut donner un sens à chaque partie de façon à ce que le sens d’un
composé se déduise du sens de ses composants.

Avantages :

• Si deux composants ont le même sens, on peut toujours remplacer

l’un par l’autre (p.ex. compilateur optimisant)

• La définition de la sémantique suivra la structure de la syntaxe.

 Exemple : séquence en Pascal
• Le sens d'une instruction S, noté [[ S ]], est une fonction de l'état initial
vers l'état final
• Alors le sens d'une séquence est la composition fonctionnelle du sens
de ses composants:

• [[ S1 ; S2 ]] =  x. [[S2]] ([[ S1]] (x)) = [[ S2 ]] ° [[ S1 ]]

 Non-terminaison
Certains programmes bouclent pour certaines données

Ex. : la fonction factorielle pour les nombres négatifs

pour représenter cela, on ajoute une valeur spéciale

 « bouclage » ou « bottom »

à l’ensemble des résultats.

Comme ce résultat peut être l’argument d’un autre appel, il faut aussi l’ajouter
dans les données.
 Strict
Si un paramètre est nécessaire pour évaluer
une fonction, dès que l'évaluation du
paramètre ne termine pas, l'appel de
fonction ne termine pas non plus.
Def. : une fonction F est stricte dans son ième argument
si F(x1, , …, xi-1, , xi+1, ...) = 
 Exemple: Pascal
Presque toutes les fonctions de la sémantique
de Pascal sont strictes, parce qu'on évalue
tous les paramètres avant un appel.
Exception: les instructions de contrôle
p.ex. if ne nécessite pas d'évaluer une des
deux parties.
 Etat
• On représente ici l'état d'un programme par une
fonction des variables vers leur valeur
• Pour Pascal, il faudrait aussi représenter les
instances actives de procédures et leur variables
locales
 Sémantique des instructions Pascal
• [[ S1 ; S2 ]] = [[ S2 ]] ° [[ S1 ]]

• [[ skip ]] =  x. x

• [[ if E then S1 else S2 ]] = x.

if ([[ E ]] (x) = true) then [[ S 1 ]] (x)

else [[ S2 ]] (x)

• [[ V := E ]] = x. i. if i = V then [[ E ]] (x) else x(i)

• [[ while E do S ]] = x. if ([[ E ]] (x) = true)
then [[while E do S]] ° [[ S ]](x)

else x
 Récursivité
• la définition du while est récursive, mais pas bien fondée.
• Comment calculer son sens ?
• Ce doit être une solution de:
W = x. if [[ E ]] (x) then W ° [[ S ]](x) else x.
• Cette équation peut avoir plusieurs solutions, mais une
seule est intuitive.
• Les solutions sont appellées points fixes de:
F = W. x. if [[ E ]] (x) then W ° [[ S ]](x) else x.
 Ordre d’information
• Pour comparer les solutions et choisir la
plus naturelle, on définit un ordre partiel 
• X Y se lit
« Y contient au moins l’info de X »
ou
« X approxime Y »
 Bouclage
Considérons le programme f(x) = f(x)+1
Cette équation n’a pas de solution dans les nombres
Le programme boucle à l’exécution
On ajoute une valeur spéciale  qui représente le fait qu’un
programme boucle.
 = +1 est alors la seule solution.
 Ordre partiel
Un ordre partiel est une relation:
• Réflexive: X X
• Transitive: X Y et YZ implique X Z
• Antisymétrique: XY et YX implique X=Y
 Supremum
• Un majorant de Y est un élément b plus grand
que tous ceux d'Y:
bMaj(Y) = yY, yb
• Un majorant plus petit que les autres est le
supremum de Y
s=sup(Y)
ssi
s Maj(Y) et m Maj(Y), sm
 Chaîne
Une chaîne est une suite croissante
(xi)i N telle que xixi+1
 Domaine
Un domaine ou ordre partiel complet (CPO)
est un ensemble X muni d'un ordre partiel 
• X contient un minorant 
• Toute chaîne de X a un supremum
Intuition:
• Un programme qui boucle ne fournit aucune info: X
• On peut représenter l’info accumulée par un programme
par le supremum de ses calculs partiels
 CPO plat

Pour les valeurs classiques, on ajoute juste  en dessous:

x y ssi x =  ou x =y
Par exemple: les entiers avec , noté Z, est obtenu ainsi.
-4 -3 -2 -1 0 1 2 3
4


Exercice: est-ce bien un CPO?
 CPO Union disjointe
Si on a deux CPOs A, B on forme le type
union disjointe de A et B en rajoutant
encore un  en-dessous:

A B

A B Indique une valeur inconnue de B

A+B Indique une valeur inconnue de A+B

 Ordre ponctuel
Pour les fonctions, on emploie l’ordre ponctuel:
f DC g ssi xD, f(x) Cg(x)
L’élément minimum est la fonction qui
renvoie toujours :
DC =  x. C
 Fonction monotone
• Une application entre CPOs est monotone
si elle préserve l'ordre :
Si x  y alors f(x) f(y)
 Théorème de Tarski
Si F est une application monotone d’un CPO
dans lui-même, elle a un plus petit point
fixe, noté fix(F).
 Continuité pour l’ordre
Une fonction f est continue si elle préserve
les suprémums:
Pour toute chaîne C: f(sup (C) ) =sup(f (C))

Attention cette continuité n’est pas celle de la

topologie usuelle sur les nombres rééls!
Avec cette déf, toute fonction continue est
monotone.
 Théorème de Scott
Si f est une application continue d’un CPO
dans lui-même, son plus petit point fixe
peut se calculer en itérant f à partir de 
, f(), f(f()), f(f(f())), …
et en prenant le supremum
fix(f) = supi(fi())
où fi(x) note f(f(…f(x)))
 Preuve
1. Ce supremum est un point fixe
 = f0()  f() puisque CPO
fi()  fi+1() par monotonie
(fi()) i N est une chaîne, donc a un supremum s =
supi(fi())
f(s) =f(supi(fi())) = supi(f(fi())) = s
 Preuve (2)
Il est le plus petit: Soit v un autre point fixe
  v puisque CPO
fi()  fi(v) = v par monotonie càd v
majorant
s  v def. supremum
 Continuité
Pour appliquer le théorème de Scott, il faut que la fonction
soit « continue »
En pratique: toute fonction écrite en ML, Pascal, … est
continue.
Schéma de preuve:
• Les fonctions de base sont continues
• La composition préserve la continuité
• Un point fixe d’une fonctionnelle continue est continu.
 Exemple
Quel est le sens de la fonction récursive ML:
fun f(b) = if b then 3 else 2*f(b)
f : bool  int
C’est le plus petit point fixe de H:
H f b = if b then 3 else 2*f(b)
On le calcule par la chaîne:

H  =  b. if b then 3 else 
H(H ) =  b. if b then 3 else 
Donc,  i>0, Hi  =  b. if b then 3 else  = fix H = [[f]]
 Règles de simplification
Si f est stricte:
f(if b then T else E) = if b then f(T) else f(E)
 Exemple de point fixe
Quel est le sens de
f n = n+(if n=0 then 0 else f(f(n-1))
R: le plus petit point fixe de
H f n = n+(if n=0 then 0 else f(f(n-1))
H0  = 
H1  n = n+(if n=0 then 0 else )
= if n=0 then 0 else 
H2  n = n+(if n=0 then 0 else H1  (if n-1=0 then 0 else ))
= n+(if n=0 then 0 else if n=1 then 0 else )
= if n=0 then 0 else if n=1 then 1 else 
…
 Exemple de point fixe
H3  n = H(H2 ) n
= n+(if n=0 then 0 else H2 (H2 (n-1))
= n+(if n=0 then 0 else H2 (if n-1=0 then 0 else if n-1=1
then 1 else ))
= if n=0 then n+0 else if n=1 then n+ H2  0 else if n=2 then
n+ H2  1 else 
= if n=0 then 0 else if n=1 then 1 else if n=2 then 2+ H 2  1
else 
= if n=0 then 0 else if n=1 then 1 else if n=2 then 3 else 
 Exemple de point fixe
H4  n = H(H3 ) n
= n+(if n=0 then 0 else H3 (H3 (n-1))
= n+(if n=0 then 0 else H3  (if n-1=0 then 0 else if n-1=1
then 1 else if n-1=2 then 3 else ))
= if n=0 then 0 else if n=1 then n+ H3  0 else if n=2 then n+
H3  1 else if n=3 then n+ H3  3 else 
= if n=0 then 0 else if n=1 then 1 else if n=2 then 3 else if
n=3 then  else 
= if n=0 then 0 else if n=1 then 1 else if n=2 then 3 else 
= H3  n : le point fixe est atteint
 Exemple de point fixe limite
H h n = if n=1 then 1 else h(n-1)+1
H  = n. if n=1 then 1 else 
H2  = n. if n=1 then 1 else if n=2 then 2 else 
Hi  = n. if 0<n  i then n else 
Preuve par induction:
cas 0: Hi  = n. 
cas i+1: H(Hi )
= n. if n =1 then 1 else if 0<n-1  i then (n-1)+1 else 
 n. if 0<n  i+1 then n else 
Limite: sup Hi  = n. if 0<n then n else 
W447

Interprétation Abstraite
L’interprétation abstraite est une technique pour calculer des propriétés
d’un programme.
En principe ces propriétés se déduisent de la sémantique du programme,
mais celle-ci est trop coûteuse à calculer.
On ne calcule donc que les propriétés qui nous intéressent;
Le plus souvent ceci amène à faire des approximations.
La sémantique sert à trouver et prouver ces approximations.
 W470

Interprétation Abstraite: cadre

1. Une sémantique dénotationnelle compositionnelle

[[ . ]] : programme  Domaine standard A

Chaque construction f du langage a sa sémantique fA

2. On veut construire une sémantique abstraite compositionnelle qui retient les propriétés à calculer

Abs : programme  Domaine abstrait B

avec une relation  «est représenté par » entre les deux domaines :

- compatible : si a  b , alors fA(a)  fB(b)

- continue : si supi(ai) = a, supi(bi) = b, iN ai  bi, alors a  b

 Exemple: Signe
On veut que le compilateur calcule, si possible, le signe des
expressions entières
Domaine standard = Z
n 0 p
Domaine abstrait = {0, p, n, ?}
0 représente 0: 0  ?
p représente les nombres positifs: z  p ssiz>0
n représente les nombres négatifs: z  n ssi z<0
? représente tout le domaine abstrait: z 
 Exemple: Signe: fonctions abstraites
On construit les meilleures approximations des 4 opérations:

+ p 0 n ?  p 0 n ? * p 0 n ? / p 0 n ?
p p p ? ? p ? p p ? p p 0 n ? p p err n ?
0 p 0 n ? 0 n 0 p ? 0 0 0 0 0 0 0 err 0 0
nn n ? nn n ? ? nn 0 p ? nn err p ?
? ? ? ? ? ? ? ? ? ? ? ? 0 ? ? ? ? err ? ?

est continue (les chaînes sont finies).

 Exemple: Signe: point fixe
i := 1;
f := 1; Le compilateur utilise des états abstraits
while i<v do begin Si v est positif à l’entrée de ce programme,
f := i*f; il calcule que f et v seront positifs à la
i := i+1; sortie.
end i f v
Avant la boucle:
p p p
i f v
Après la boucle, par point fixe:
p p p
 D’autres applications de
l’interprétation abstraite
L’interprétation abstraite permet au compilateur de calculer des réponses
approchées à des questions comme:
• Des variables sont-elles synonymes ?
• Des structures de pointeurs ont-elles des cellules
partagées ?
• Une fonction est-elle stricte ?
• Une fonction a-t-elle des effets de bord ?
• Une variable a-t-elle un effet sur une autre ?
• Combien de temps prend un programme ?
• Calculs sur les grammaires (voir plus loin)
 Sémantique des grammaires non contextuelles

Le sens d’un non-terminal X dans une grammaire G = (S, VN, VT, P)

est l’ensemble des textes corrects pour X, càd {w  VT* | X * w }.

Les règles d'une grammaire sont récursives: la théorie du point fixe convient donc pour leur donner un
sens.
Si on suppose qu'on a donné un sens à chaque non-terminal (càd on a une fonction de VN  P(VT*) ) alors

on peut l'utiliser dans les règles de la grammaire pour calculer un nouveau sens. Le plus petit point
fixe donne la sémantique de chaque non-terminal. La sémantique du symbole initial donne le
langage de la grammaire. L'ordre utilisé est l'ordre sur les vecteurs d'ensembles:

A1 (X)  A2 (X) ssi  X  VN, A1 (X)  A2 (X)

 Continuité
Toutes les grammaires définissent une fonction "continue" pour l'inclusion. En
effet, le supremum pour l'inclusion est simplement l'union (infinie).
Les grammaires BNF sont écrites avec les 4 opérateurs:
union, . suivi de, a symbole terminal, chaîne vide.
On peut montrer qu'ils sont continus, p.ex.: Donc
(i Li ).M = {x.y | i. xLi et yM} = i ( Li .M)
Donc le langage peut se calculer par point fixe.
 Exemple
La grammaire P  = {A=, B=, C=}
A ::= a A c | B [[P]]  = {A=, B=, C=}
B ::= b B | C [[P]]2  = {A=, B= , C= }
[[P]]3  = {A= , B= {,b}, C= }
C ::=  | C
[[P]]4  = {A= {ac,,b}, B= {,b,bb}, C= }
On généralise:
[[P]]n  = { A = {ai bj ci | i+j  n-3},
B = { bj | j  n-2},
C= si n=0, C=  sinon }
On fait la preuve par induction
Puis le passage à la limite:
fix [[P]] = { A = {ai bj ci }, B = { bj }, C=  }
 Interprétation abstraite de grammaires

Le calcul des k premiers symboles terminaux (voir chap.2)

est une interprétation abstraite.
L'opérateur . (suivi de) est donc abstrait en une concaténation
bornée à k symboles. Les autres sont inchangés.
Le domaine abstrait des langages bornés à k caractères a des
chaînes finies, donc le calcul du point fixe converge
finiment.
 Sémantique opérationnelle
Sémantique opérationnelle = on donne le sens du programme en donnant
un ensemble d’exécutions possibles.

+ Avantages :

+ intuition claire
+ facilité de construire un interpréteur
+ traitement du non-déterminisme

 Inconvénients fréquents :

 non compositionnel : on ne peut pas donner de sens à

certaines parties

 peu abstrait : difficile de prouver que 2 programmes sont

équivalents.
difficile de construire un compilateur optimisant.
Sémantique Opérationnelle Structurée

• On évite les inconvients habituels en ajoutant:

– Compositionalité : On donne des règles d’inférences
qui donnent les exécutions possibles en fonction de
celles des composants.
– Abstraction : On ajoute des règles de similarités disant
quelles exécutions sont équivalentes.
 Système de déduction

Une règle d’inférence est de la forme :

F1 ... Fn prémisses
F0 conclusion

« Si on a prouvé F1 ... Fn on peut déduire F0 ».

(Ici les Fi décriront des exécutions possibles)

S’il n’y a pas de prémisses, on l’appelle un axiome.

Une règle peut contenir des méta-variables càd des variables qui
représentent n’importe quel texte d’une catégorie syntaxique donnée.
On l’appelle alors un schéma de règle.

Une preuve est un arbre fini composé de règles d’inférences ; elle a

une conclusion à la racine, appelée théorème.

La théorie d’un système de déduction est l’ensemble des théorèmes.

 Exemple : un système de déduction pour la
syntaxe

• Les formules sont de la forme T : VN (le texte T dérive de VN).

• Chaque règle non contextuelle, par exemple

S ::= if E then S1 else S2

peut se traduire en une règle d’inférence :

E : expression S1 : instruction S2 : instruction

if E then S1 else S2 : instruction

 Exemple : déduction syntaxique
Une preuve dans ce système est un arbre syntaxique :
5 : constante x : variable x : variable 3 : constante
5 : expression x : expression x : l - expr 3 : expression
5 = x : expression x := 3 : instruction ...
if 5 = x then x := 3 else x := 4 : instruction
Les règles d’inférences peuvent aussi
vérifier des conditions de contexte, p.ex. les types :

E1 : expr(entier) E2 : expr(réel)
E1 + E1 : expr(réel)
X : variable(T) E : expr(T)
X := E : instruction
 Sémantique Opérationnelle Structurée :
Définition

Les formules qui nous intéressent:

e1  e2
« dans l’état e1 par un pas d’exécution on
arrive dans l’état e2 »
 Etats
Les états doivent contenir l’information
nécessaire à l’exécution :
– la valeur des variables
– le point d’exécution dans le programme (ici, on
le représente par la partie du programme restant
à exécuter)
– l’état de la pile de récursion
– etc.
 Exemple : expressions Pascal
• on ne traite d’abord que des expressions
sans variables et sans effet de bord, donc la
mémoire n’est pas (encore) nécessaire.
 Règles

• de congruence : on peut simplifier n ’importe quelle sous-expression en

Pascal :
e→e'
i i
f (e ,.., e ,.., e ) → f (e ,.., e ' ,.., e )
1 i m 1 i m
où f est un opérateur ou un appel de fonction
• de calcul : pour chaque opérateur Pascal, on donne des règles pour calculer la
valeur du résultat à partir de la valeur des arguments
– par exemple :

not true  false

not false  true

 Exemple
• 7 + (4 * 5)  7 + 20  27
• le premier pas est la règle de congruence pour le 2ème
argument; sa prémisse est justifiée par la règle de calcul
pour *.
• le second pas est le calcul de +.
 Expressions avec mémoire
Un état a maintenant 2 composantes:
– l’expression à évaluer;
– l’état de la mémoire : une fonction Identificateur  Valeur
• de congruence : on peut simplifier une sous-expression

'
(ei , m) → (ei , m' )
'
• e
de calcul :( f ( 1 ,.., ei ,.., en), m) → ( f (e1 ,.., ei ,.., e ), m' )
n

(not true, m)  (false, m)

(not false, m)  (true, m)
• de recherche de valeur en mémoire: (id, m)  (m(id) , m)
 Exemple : expression
recherche
(x, m) → (5, m)
(4 * x, m ) → (4 * 5, m)
congruence
((4 * x) + (5 * y), m ) → ((4 * 5) + (5 * y), m) congruence

calcul *
(4 * 5, m) → (4 * 20, m)
congruence
((4 * 5) + (5* y), m) → (20 + (5* y), m)

recherche
(y, m) → (2, m)
(5 * y, m ) → (5 * 2, m) congruence
(20 + (5 * y), m ) → (20 + (5 * 2), m) congruence

(5* 2, m) → (10, m) calcul *

( 20 + (5* 2), m) → (20 + 10, m) congruence

calcul +
(20 + 10, m) → (30, m)
 Instructions
• affectation :
– d’abord évaluer l’expression
– ensuite modifier l’état pour la variable avec la constante ainsi calculée
• conditionnelle :
– d’abord évaluer l’expression
– ensuite évaluer la branche choisie (2 cas)
• boucle :
– créer une copie de l’expression
– l’évaluer (en gardant l ’expression du while pour les itérations)
• séquence :
– évaluer la première instruction
– lorsqu’elle se termine exécuter la 2ème instruction
 Instructions
Affectation : 1. (e, m) (e’, m ’)
e : expr congruence
(id := e, m) (id := e’, m ’)
id : identificateur calcul :=
n : const
2. (id := n, m) (skip, update (id, n, m))
instruction vide
Conditionnelle : 1. (e, m) (e’, m’)

(if e then S1 else S2m) (if e’ then S2 else S2m’)

2.1 (if true then S1 else S2, m) (S1, m)

2.2 (if false then S1 else S2, m) (S2, m)

abréviation
(if e then S1, m) (if e then S1 else skip, m)

Boucle : (while e do S, m)  (if e then begin S ; while e do S end, m)

Séquence : (S1, m)  (S’ , m’)1

(S1 ; S , m)  (S’ ; S , m’)

2 1 2
 Système de transitions
• Les règles de la SOS définissent une
machine à états infinis, qu’on appelle aussi
un système de transitions.
• On peut aussi la voir comme un graphe.
 Questions importantes

• 1. Il y a-t-il plusieurs suites de flèches partant d’un même état ?

(déterminisme)
• 2. Certaines de ces suites sont-elles infinies ? (terminaison)
• 3. Aboutissent-elles toutes au même état ? (confluence)
• 4. Quelle forme ont les états finals ? Les état finals corrects ?

Déf. : C final = il n’y a pas de C’ : C  C’ (forme normale)

• 5. Les flèches préservent-elles les types ?
 Equivalence sémantique

• La SOS détaille les calculs, donc peu de programmes sont équivalents

• Deux programmes P,Q sont équivalents ssi:
– ils mènent aux mêmes états finaux
– ils bouclent dans les mêmes circonstances :

• p*q signifie qu’un chemin d’exécution mène de p à q.

• p signifie qu’un chemin d’exécution infini part de p.

 Exemple
if e then S1 else S2 if not(e) then S2 else S1

1. Si (e, m) * (true, m’)

alors 1) (if e then S1 else S2, m)

congruence
* (if true then S1 else S2, m’) 2.1
(S1, m’)

2) (e, m) * (true, m’) congruence

(not(e), m) * (not(true), m’) calcul not
* (false, m’)

(if not(e) then S2 else S1, m) congruence

2.2.
(if false then S2 else S1, m’)

(S1, m’)

2. si (e, m) * (false, m’) : preuve symétrique

 Sémantique dénotationnelle
• Donne pour chaque partie de programme, un objet qui est
son sens: p.ex. un programme déterministe séquentiel
dénote une fonction
• Compositionnelle si le sens d’un programme dépend du
sens de ses parties mais pas de leur forme.
• Abstraite si le sens ne conserve que l’information qu’on
peut observer.
 Compositionalité
• Si S1, S2 sont deux instructions dont le sens
de chacune est une fonction des états de
mémoire (de départ) vers les états de
mémoire d’arrivée : f1, f2, alors la sequence
S1; S2 a comme sens la fonction f1(f2(i))
pour tout état de départ i.
 Sémantique axiomatique
• Donne des règles pour construire des programmes
• Les règles peuvent être démontrées à partir d ’une autre
sémantique (p.ex. opérationnelle)
• Notation : {pre} P {post} signifie que si P démarre dans un
état de mémoire satisfaisant pre, alors il se termine dans un
état de mémoire satisfaisant post.

pre post
 Exemple de règles
• règle pour l’affectation:
{ post [e/x] } x := e {post }
la règle est valide si x ne peut être accédée que par ce nom
(pas de synonymie)
• règle pour le if:
{ pre et b} t {post }
{ pre et non b} e {post }
{ pre } if b then t else e {post }