COMPILATION

De l’algorithme à la porte logique

Télécom SudParis
CSC4536
Pascal Hennequin

12/10/2022 1 / 127
 Sommaire (1/2)

Introduction
0) Prolégomènes 4
Analyse Lexicale et Syntaxique
1) Analyse Lexicale 18
2) Automate Fini 31
3) Grammaire Algébrique 48
4) Analyse Syntaxique 63

12/10/2022 2 / 127
 Sommaire (2/2)

Compilation
6) Arbre de Syntaxe Abstraite 81
7) Analyse Sémantique 95
8) Représentation Intermédiaire 109
9) Génération de code 120

12/10/2022 3 / 127
 Chapitre 0

0) Prolégomènes
Compilation 5
Interprétation 6
Méli-mélo 7
Traduction 8
Phases de Compilation 9
Objectif du cours 14
Bibliographie 16

12/10/2022 4 / 127
 Compilation
De l’algorithme à la porte logique

Entrée : un algorithme implanté sous forme d’un programme dans un

langage de programmation «évolué »

COMPILATEUR

Sortie : un programme équivalent exécutable par un processeur

Exemple : C avec gcc

12/10/2022 5 / 127
 Interprétation
Autre possibilité

Entrée : un algorithme implanté sous forme d’un programme dans un

langage de programmation «évolué »

INTERPRÉTEUR

Sortie : exécution directe

Exemple : Bash, Python

12/10/2022 6 / 127
 Méli-mélo
On peut mélanger
Entrée : un algorithme implanté sous forme d’ un programme dans
un langage de programmation «évolué »
COMPILATEUR

Forme intermédiaire : un programme équivalent dans un autre

langage «moins évolué »
INTERPRÉTEUR

Sortie : exécution de la forme intermédiaire par un programme

interpréteur ou machine virtuelle

Exemple : Java
12/10/2022 7 / 127
 Traduction
De façon plus large

Entrée : un fichier définissant des objets informatiques (exécution,

données, …) en utilisant un format ou syntaxe ou langage

TRADUCTEUR

Sortie : un fichier équivalent (ou pas) utilisant un autre langage

Exemples : Traitement de texte, Conversion d’images, Impression de

documents, …, …, PrettyPrint, ...

12/10/2022 8 / 127
 Phases de Compilation (1/4)
I) Analyse Lexicale
Reconnaître les mots du langage en entrée

πR2=alpha+1 πR2 = alpha + 1

IDENT AFF IDENT OPBIN ENTIER
II) Analyse Syntaxique
Reconnaître les phrases en entrée : construire et valider la structure
grammaticale
Grammaire :
R1 : ENTIER → exp R3 ( R4 ( R2 , R1 ) )
R2 : IDENT → exp
=> phrase correcte
R3 : IDENT AFF exp → phrase
R4 : exp OPBIN exp → exp

12/10/2022 9 / 127
 Phases de Compilation (2/4)
III) Analyse Sémantique
Établir la signification du fichier en entrée
Construire les éléments de contexte :
●
liaison entre les définitions et les utilisations des variables ou fonctions
●
vérification des contraintes de typage, gestion du transtypage
●
analyse des chemins d’exécutions, i.e code mort, return absent
●
...
πR2=alpha+1

int alpha Addition entière Résultat entier

?
ou transtypage avant affectation
double alpha Addition flottante Transtypage (double) 1 , ...
Concaténation Transtypage [Link]() ,
String alpha chaines Méthode [Link](), ...

12/10/2022 10 / 127
 Phases de Compilation (3/4)
IV) Code Intermédiaire
Traduction de l’entrée dans un langage intermédiaire qui se veut :
●
Indépendant du langage en entrée et plus simple
●
Indépendant du langage en sortie ou du traitement à suivre
Interface entre partie avant et partie arrière du compilateur

πR2=alpha+1 int πR2;

void F(int alpha) { πR2=alpha+1; }

Code à 3 adresses : bytecode Java :

t2:=alpha PLUS 1 1 iload_1 [arg0]
πR2:=t2 2 iconst_1
3 iadd
4 putfield Test2.πR2 : int [2]

12/10/2022 11 / 127
 Phases de Compilation (3 bonus/4)

πR2=alpha+1 String πR2;

void F(String alpha) { πR2=alpha+1; }

bytecode Java (cas String)

1 new [Link] [2]
4 dup
5 invokespecial [Link]() [3]
8 aload_1 [arg0]
9 invokevirtual [Link]([Link]) : [Link] [4]
12 iconst_1
13 invokevirtual [Link](int) : [Link] [5]
16 invokevirtual [Link]() : [Link] [6]
19 putfield Test2.πR2 : [Link] [7]

12/10/2022 12 / 127
 Phases de Compilation (4/4)
V) Génération de code
Optimisation du code intermédiaire
Génération du code cible
Optimisation du code cible
Production de l’exécutable et édition de liens

MIPS : ELF (gcc) :

move $t2, $a1 4004f7: mov %rsp,%rbp
li $v1, 1 4004fa: mov -0x4(%rbp),%eax
add $t2, $t2, $v1 4004fd: add $0x1,%eax
sw $t2, 0($a0) 400500: mov %eax,0x200b2a(%rip)

V bis) Interprétation
Exécution directe du code intermédiaire
12/10/2022 13 / 127
 Objectif du Cours (1/2)
Écrire un compilateur pour un sous-ensemble du langage Java
vers le langage assembleur MIPS
– Comprendre par la pratique les enjeux et les techniques des
différentes phases de la compilation
Trois objectifs sous-jacents
– Analyse lexicale et syntaxique : maitriser les concepts théoriques et
leurs mises en œuvre dans les outils « compiler’s compiler »
– Architecture des processeurs : instructions, registres, structures
algorithmiques, appel de fonction, gestion mémoire ...
– Algorithmique et programmation :
●
Dans l’écriture du compilateur (algorithmique d’arbre,...)
●
Dans la compréhension de la chaîne de compilation et de la façon dont
les paradigmes usuels de programmation sont implantés pour l’exécution

12/10/2022 14 / 127
 Objectif du Cours (2/2)
Ne fait pas partie du cours
– Analyse sémantique dynamique et analyse de flux
– Aspects théoriques de l’analyse sémantique
– Optimisation du code généré et transformation d’arbre
– Optimisation du code du compilateur
– Compilation séparée et édition de lien

12/10/2022 15 / 127
 Bibliographie (1/2)
Mots clés
Compilation, théorie des langages, expressions régulières, automates
finis, grammaires algébriques (context-free), compilateur de compilateur
(compiler’s compiler), analyse syntaxique ascendante (LR)

Bibles
●
Gödel, Escher, Bach: an Eternal Golden Braid, aka "GEB", Douglas
Hofstadter, 1979, Basic Books
●
Compilers: Principles, Techniques, and Tools, aka «dragon book», A.
Aho, M. Lam, R. Sethi, J Ullman. 2nd ed., 2006, Pearson Education, Inc.
●
Modern Compiler Design in Java, 2nd edition - A.W. Appel -
Cambridge, 2002
●
Compilateurs, D. Grune, H.E. Bal, C.J.H. Jacobs, K.G. Langendoen,
Dunod 2002.

12/10/2022 16 / 127
 Bibliographie (2/2)
Références
●
Introduction to Automata Theory, Langages and Computation, John
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. 3ieme ed.2013,
Pearson Education.
●
Langages Formels, Calculabilité et Complexité, Olivier Carton, 1er ed.
2012. Vuibert
●
[Link]
●
Learning Perl, [Link], T. Christiansen, 1997, O’Reilly.
●
Mastering Regular Expressions, Jeffrey Friedl, 3ieme ed.. 2006,
O’Reilly.

12/10/2022 17 / 127
 Chapitre 1

1) Analyse Lexicale
De la théorie 19
Et en pratique 21
Lexicale versus Syntaxique 22
Analyse Lexicale 24
Spécification du vocabulaire 27
Expression Régulière 28

12/10/2022 18 / 127
 De la théorie (1/2)
Théorie des Langages, Théorie de la Calculabilité
Que peut on calculer automatiquement ?
Que peut on calculer efficacement ?
Systèmes et grammaires formels

Hiérarchie de CHOMSKY-SCHÜTZENBERGER

Type Langage / Grammaire Machine

0 Récursivement énumérable Machine de Turing
1 Contextuel (context-sensitive) Automate à ressources bornées
2 Algébrique (context-free) Automate à pile
3 Rationnel (regular) Automate fini

12/10/2022 19 / 127
 De la théorie (2/2)
Machine de Turing et Calculabilité
BANDE : infinie 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 ...
TÊTE : Lecture / Écriture 0 ou 1
Déplacement Droite ou Gauche
CONTRÔLE : un état (« variable entière »),
des instructions (« table d’automate ») :
[état courant, symbole lu, nouvel état, action=0/1/D/G]

Machine la plus simple pour les calculs les plus généraux

– Thèse de Church-Turing : tout ce qui est calculable automatiquement
est calculable avec une machine de Turing
– Il existe des fonctions non calculables
– L’arrêt de la machine de Turing est indécidable
– Théorème de Rice : toute propriété non triviale est indécidable

12/10/2022 20 / 127
 Et en Pratique
Langage de type 3 = Expressions Régulières
– Reconnues par automates à états finis
– ∃ outils pour reconnaître les expressions régulières en temps O(n)
●
Générateurs d’analyseur lexical : lex, flex, JFlex …
●
Aussi : commande grep, langage Perl, éditeurs de texte, …, ...

Langage de type 2 = Grammaires Algébriques

– Reconnues par automates à Pile
– Couvre l’ensemble des langages informatiques
– ∃ outils pour faire l’analyse syntaxique en temps O(n)
●
yacc (Yet Another Compiler’s Compiler), Bison, CUP, ...
●
ANTLR, JavaCC, ...

12/10/2022 21 / 127
 Lexicale versus Syntaxique (1/2)
Séparation usuelle dans les langages naturels
– Les mots et leur catégorie (nom, verbe, adjectif,..) définis par un
dictionnaire
– Les phrases définies par des règles de construction (grammaire)

Séparation théorique dans la hiérarchie de Chomsky

– Expressions Régulières versus Grammaire algébrique
Vocabulaire = Unité lexicale = Lexème
– Les mots autorisés dans le langage
Catégorie Lexicale = Symbole terminal = Token
– Ensemble de mots ayant le même comportement dans la grammaire
Grammaire
– Ensemble de règles définissant les séquences de Token valides

12/10/2022 22 / 127
 Lexicale versus Syntaxique (2/2)
Exemple : langage naturel élémentaire
– Lexique POINT = .
ARTICLE = un | le
VERBE = mange | tue
NOM_C = lapin | chasseur | gnou
NOM_P = Bart | Jeannot | Obi-Wan
– Syntaxe
<Phrase> := <SujetVerbeCompl> POINT ;
<SujetVerbeCompl>:= <GroupeNom> VERBE <GroupeNom> ;
<GoupeNom> := NOM_P | ARTICLE NOM_C ;
– Des phrases valides :
●
Obi-Wan mange un gnou.
●
le lapin tue un chasseur.
12/10/2022 23 / 127
 Analyse lexicale (1/3)
Reconnaître
– Les mots du langage, ou unités lexicales ou lexème
– Leur catégorie lexicale ou token

Qui est lexème ?

– Une chaîne de caractères dont la signification n’est pas construite à
partir de ces composants.
– Exemples : Mots clés (for while if) , Identificateur (ma_variable
forif), Opérateurs (+ = ++ +=), Ponctuation (; , .), Commentaire (/*
coucou */)
– Contre-exemple : une constante entière est en général un lexème
même si conceptuellement la numération est un processus syntaxique

12/10/2022 24 / 127
 Analyse lexicale (2/3)
Qui est catégorie lexicale ?
– Ensemble de lexèmes non différentiés dans les règles de grammaire
– Dépend de l’écriture de la grammaire
●
OpBin={+ , - , * , / } ou OpPlus, OpMoins, OpMult, OpDiv ?

Token
– Entier identifiant la catégorie lexicale reconnue (type énuméré)
– De façon optionnelle :
●
Valeur du lexème dans la catégorie pour les traitements après l’analyse
syntaxique
●
Position du lexème dans le fichier source
●
...

12/10/2022 25 / 127
 Analyse lexicale (3/3)
Analyseur Lexical (lexer, tokenizer)
– Entrée : Texte ASCII, ou Unicode, ou éventuellement binaire

– Sortie : une séquence de symboles terminaux (tokens) qui servira

d’entrée à un analyseur syntaxique.

Exemple
– Entrée : Alpha += 32 * bêta + 2 /* comment*/

– Sortie : 132414 2

Catégories={ Ident., Littéral, Affect., OpBin}

– Ignore : blancs, commentaires, ...
12/10/2022 26 / 127
 Spécification du Vocabulaire
Par énumération
– Vocabulaire fini <Séparateur> : ',' | '.' | ':' | ';' ;
– Structure de dictionnaire <Opérateur> : '+' | '-' | '*' | '/' ;

Par règle de production récursive <Entier> := <Chiffre>

– Vocabulaire infini | <Entier > <Chiffre> ;
– Reconnaissance complexe
<Nom> := <Lettre>
|| <Nom > <Lettre> ;
– Ex : BNF
<Chiffre> := '0' | '1' | … | '9' ;
<Lettre> := 'a' | 'b' | … ;
Par expression régulière
– Vocabulaire infini <Entier> = [0-9]+
– Formalisme simple <Nom> = [a-zA-Z][_a-zA-Z]*
– Reconnaissance automatisable et efficace
12/10/2022 27 / 127
 Expression Régulière (1/3)
Définition
ε Mot vide
Constantes
Caractère Singleton
r1 | r2 Alternative ou Union
3 Opérateurs r1 r2 Concaténation (implicite)
r* Fermeture de Kleene : répété N ≥ 0 fois
Parenthèses () Gestion des priorités

Exemple
a* a (b | c)* a* sur ∑ = { a, b, c}
Mots commençant par au moins un a, suivi de b ou c en nombre
quelconque, et éventuellement terminé par des a
a, aa, ab, ac, aaa, aab, aac, aba, abb, abc,, abba, ...
12/10/2022 28 / 127
 Expression Régulière (2/3)
Classes de caractères : Reconnaît 1 symbole parmi un ensemble
. Un caractère quelconque sauf fin de ligne
[xyzT] Un caractère de l’énumération == x|y|z|T
[ … A-F … ] Idem avec intervalle
[^…] Un caractère hors de l’énumération

Répétitions
r? r répétée 0 ou 1 fois == r | ε
r+ r répétée n>0 fois == r r*
r {k} r répétée k fois
r {k,l} r répétée entre k et l fois

Délimiteurs de contexte
^r r en début de ligne
r$ r en fin de ligne
12/10/2022 29 / 127
 Expression Régulière (3/3)
Exemples

[aeiouy] Une voyelle

[A-Za-z]+ Un mot alphabétique non vide
^[ \t]+$ Une ligne blanche
//.* Un commentaire C++
\"[^"]*\" Une constante chaîne
[0-9]+ (\.[0-9]*)? ([eE][+-]?[0-9]+)? Une constante flottante
0 | [1-9] ( [0-9_]* [0-9] )? Une constante entière décimale Java

12/10/2022 30 / 127
 Chapitre 2

2) Automate Fini
Abrégé de la théorie des langages 32
Automate Fini 34
Reconnaissance par un automate 37
Reconnaissance par des outils 38
Déterministe versus Indéterministe 39
Langage Rationnel et Automate Fini 40
Petit commentaire 42
Illustrations 43

12/10/2022 31 / 127
 Abrégé de la théorie des langages (1/2)
Définitions
Alphabet ∑ : ensemble fini de lettres
Mot w sur ∑ : suite finie de lettres de ∑
∑* : ensemble de tous les mots = monoïde libre
Langage L : ensemble de mots inclus dans ∑*
Mot vide ε, Langage vide ∅ ≠ {ε}
Opérations
Alternative (union) , Concaténation (produit),
Fermeture de Kleene (étoile) : L*= {ε} ∪ L ∪ LL ∪ LLL
Aussi Intersection, Complémentaire, Quotient, …
Questions
w ∈ L ? , L = ∅ ?, L fini ?, L1=L2 ?, ...
décidable, calculable, facilement calculable ?

12/10/2022 32 / 127
 Abrégé de la théorie des langages (2/2)
Langage Rationnel Algébrique Algébrique Contextuel Récursif Récursivement
déterministe énumérable
Machine Automate Automate à pile Automate borné Turing qui Machine de
fini s’arrête Turing
Spécification Expression Grammaire context-free Grammaire Grammaire générale ou
régulière context-sensitive phrase-structure
Exemples a n bn Palindrome Papou diag(CSL) diag(TM)
abcd
n n p p
anbncp ∪ abc,abcd
n n n n p n p
Ackermann pas diag(TM)
ap et p Dyck ([]()) a p bn c n a et p premier
p

paire ap et p carré
Déterministe == OUI NON, mais Décidable ; Problème ouvert OUI OUI
Non Déterministe Ambiguïté Indécidable.
w∈L O(n) O(n) O(n3) PSPACE EXPSPACE Indécidable
L rationnel OUI Décidable Indécidable Indécidable Indécidable Indécidable
L= ∅ Décidable PTIME PTIME Indécidable Indécidable Indécidable
L = ∑* Décidable Décidable Indécidable Indécidable Indécidable Indécidable
L1 = L2, L1 ⊂ L2 Décidable Décidable Indécidable Indécidable Indécidable Indécidable
Union,concat,étoile Fermé Non clos Fermé Fermé Fermé Fermé
Intersection Fermé Non clos Non clos Fermé Fermé Fermé
Complémentaire Fermé Fermé Non clos Fermé Fermé Non clos
12/10/2022 33 / 127
 Automate fini (1/3)
Principe int état =0 ;
tant que pas_fini {
lire un caractère c
selon état et c
changer état
}
Automate Fini (Finite State Automaton)

A = ( ∑, Q, q0, QT, δ ) avec

∑={c0 , … , cm-1}, alphabet d’entrée (ou événements)
Q={q0 , … , q n-1}, ensemble fini d’états
q0 état initial
QT ⊂ Q, ensemble des états terminaux (ou accepteurs)
δ : Q×∑ → Q, fonction de transition
q = δ(p , c) : transition de p à q sur lecture de c

12/10/2022 34 / 127
 Automate fini (2/3)
Exemple c∉N N = [0-9]
0 c∉ A
A = [a-zA-Z] 0
c∈N c∈A
AN= A ∪ N
n=val(c) s=c
2 1 2 1
c∉N n=10*n+val(c) s=sc
c∉AN
c∈N c∈AN
a) reconnaître un entier b) reconnaître un identificateur

i=j=0 c∉AN
c∈ A 0 c∈N
si = c i++ j++ nj = val(c)
eof
c∉AN c∉N
s i = si c 1 3 2 nj = 10*nj + val(c)
eof eof
c∈AN c∈N
c) Reconnaître tous les identificateurs et tous les entiers
12/10/2022 35 / 127
 Automate fini (3/3)
Représentations d’un automate
– Diagramme d’état

0 initial événement
États Transitions action
n final

– Table états/transitions

car. lu c∈A c∈N c∉AN c=EOF

état
0 1 2 0 3
1 1 2 0 3
2 0 2 0 3

12/10/2022 36 / 127
 Reconnaissance par un automate
Langage reconnu par un automate
Les mots dont la séquence de caractères mène l’automate de l’état
initial q0 à un état terminal q∈QT
Exemple
Sur l’alphabet ∑ ={a, b}, reconnaître une chaîne
●
contenant une seule chaîne d’au moins deux b consécutifs
●
éventuellement précédée d’un ou plusieurs a
●
et obligatoirement suivie d’au moins un a

a b
b b a a
0 1 2 3
a b a, eof eof
a eof eof b
0 b 1 b 2 a 3 5
4
Erreur Fin ok
12/10/2022 37 / 127
 Reconnaissance par des outils
Reconnaissance multiple de chaînes valides dans un texte
– Glouton versus Récalcitrant
– retourner la forme la plus étendue (glouton, greedy) ou la plus courte
(récalcitrant, reluctant, lazy)
– [0-9]+ sur « 1234 » ?
– < .* > sur « <b>bold</b> » ?
– Avec ou sans recouvrement ( aussi : avec ou sans trou)
– a*bb+a+ sur « abbaabba » ?
●
« abbaa » et « aabba » ou sans recouvrement : « abbaa » et « bba »
– Plusieurs automates simultanément
– [0-9]+ et [a-zA-z]+ en même temps

Il existe des algorithmes pour outiller l’automate de base afin

d’avoir les différents comportements
12/10/2022 38 / 127
 Déterministe versus Non Déterministe
Machine non déterministe
Déterministe Non déterministe
∀ couple (p,c), - Plusieurs transitions possibles
∃! transition p -c-> q p -c-> q1, p -c-> q2
- ou des ε-transitions (sans caractère lu)
p --> q
Exécution linéaire Exécution par exploration de toutes les
possibilités. Un mot est reconnu si il existe
un chemin vers un état terminal.

Théorème
Pour tout automate fini non déterministe (NFA), il existe un automate
fini déterministe (DFA) reconnaissant le même langage

12/10/2022 39 / 127
 Langage Rationnel et Automate Fini (1/2)
Théorème de Kleene (1956)
Expressions Régulières <==> Automates Finis

Preuve : cyclique et constructive

1) Regexp → NFA avec ε-transition
Traduction concaténation/union/étoile sur les automates
2) NFA avec ε-transition → NFA sans ε-transition
Algorithme de fermeture transitive
3) NFA sans ε-transition → DFA
« construction par sous-ensemble »
états du DFA = ensemble des parties des états du NFA.
4)DFA → Regexp
Récurrence à 3 indices (McNaughtom & Yamada)
12/10/2022 40 / 127
 Langage Rationnel et Automate Fini (2/2)
Théorème de minimisation
Il existe des algorithmes (Nérode, Hopcroft, …) pour construire des
automates déterministes de taille minimale
=> 3bis) DFA → DFA minimal

Corolaire pratique
Outils de reconnaissance par expressions régulières = 1 + 2 + 3 + 3bis

Théorèmes faciles
1. Le complémentaire d’un langage rationnel est rationnel
2. L’intersection de 2 langages rationnels est rationnel
Preuve ?

12/10/2022 41 / 127
 Petit commentaire
Supprimer les commentaires /* … */
out(c)
– Expression régulière 0 c≠'/'
●
"/*" .* "*/" !!!
out('/')
"/*" tout_sauf("*/") "*/" ??? c='/'
●
out(c)
c≠'*' 1
– Plus facile : Automate
c='*'

– Outils lex, flex, JFlex offrent 2

aussi une vision automate : c≠'*'
c≠'/' c='*'
Start-Condition, Super-état
c≠'*' c='/'
3
c='*'

12/10/2022 42 / 127
 Illustrations (1/5)
LuBuChu
une rivière, une barque, un fermier,
un loup, un bouc, un chou

. .B . .|LBC
LB|C. .BC|L C|LB. .C|LB
.C .C .L .C .

.B . . .B
.LBC| LC|B. .LC|B B|LC. .B|LC |LBC.

. .L .L
.L .C
BC|L. . .LB|C L|BC. . .L|BC
LBC|. .B

12/10/2022 43 / 127
 Illustrations (2/5)
L’ arbre de vie.
10 Sephiroth et 22 sentiers
Azriel de gérone XIIIe siècle

12/10/2022 44 / 127
 Illustrations (3/5)
Langage fini A
E
Structure de données L S
E
pour dictionnaire 0 D U
N E
U

1 2 3
Ascenseur 0 1 2 3
0 1 2

0 a 1
a
Parité 0 1 b b
a a
2 3

12/10/2022 45 / 127
 Illustrations (4/5)
Numération et Modulo e1
e0 e0
1 0 0 1
0 1 e2
0 1 2 e0= 0|3|6|9
e2 e2
1 0 e1 e1 e1= 1|4|7
Bin-Mod3 Dec-Mod3 e2= 2|5|8
2
e0
Déterminisme
a b c c
0 ε 1 ε 2 b
a c
Non déterministe avec ε 1 b 2 c 3

a b c a b c
0 a,b 1 b,c 2 0

a,b,c Déterministe
Non déterministe sans ε
12/10/2022 46 / 127
 Illustrations (5/5)
Négation de « .*aba.* »
Exercice TP ABBA-3 : preuve du corrigé
a,b a,b
Non déterministe 0 a 1 b 2 a 3

b a a,b
Déterministe b
complet 0 a 0,1 0,2 a 0,3

b
Négation :
états finaux = 0, {0,1}, {0,2}
Re (0->0) = b*(aa*bbb*)* = b*(a+bb+)*
Re (0->{0,1}) = Re (0->0)aa*
Re (0->{0,2}) = Re (0->0)aa*b
Re (0->final) = b*(a+bb+)* (ε | aa* | aa*b)
=> Not ( .*aba.*) == b*(a+bb+)*(a*|a+b)
aussi = b*(a+bb+)*a*b?
12/10/2022 47 / 127
 Chapitre 3

3) Grammaire Algébrique
Grammaire 49
Arbre de Syntaxe 52
Où est l’étoile ? 53
Exemple 55
Grammaire régulière 56
Grammaire ambiguë 59
Spécification avec BNF 61

12/10/2022 48 / 127
 Grammaire (1/3)
(rappel) Exemple de langage naturel élémentaire
– Lexique POINT = .
ARTICLE = un | le
VERBE = mange | tue
NOM_C = lapin | chasseur | gnou
NOM_P = Bart | Jeannot | Obi-Wan
– Syntaxe
<Phrase> := <SujetVerbeCompl> POINT ;
<SujetVerbeCompl>:= <GroupeNom> VERBE <GroupeNom> ;
<GoupeNom> := NOM_P | ARTICLE NOM_C ;
– Des phrases valides :
●
Obi-Wan mange un gnou.
●
le lapin tue un chasseur.
12/10/2022 49 / 127
 Grammaire (2/3)
Grammaire algébrique (context free)
G = ( VT , VN , S , P ) avec
VT , ensemble des symboles terminaux ou constantes ou tokens
VN , ensemble des symboles non-terminaux ou variables
VT et VN sont finis et disjoints
S ∈ VN , symbole de départ ou axiome.
P ⊂ VN× (VT ∪ VN)*, ensemble des règles de production :
v := s1 s2 …sn ;
– Le membre gauche v est un symbole non-terminal, le membre droit
est une concaténation de symboles si terminaux ou non-terminaux
– Les productions peuvent être regroupées en utilisant l’alternative :
v := s1 s2 …sn ; v := s1 s2 …sn
v := s'1 s'2 …s'p ; | s'1 s'2 …s'p ;
12/10/2022 50 / 127
 Grammaire (3/3)
Utilisations
– En production
●
en partant de l’axiome, substitutions d’un membre gauche d’une
production par un membre droit.
●
on génère l’ensemble des phrases valides pour la grammaire
●
Ex :
<Phrase> => <SujetVerbeComp> POINT
=> <GroupeNom> VERBE <GroupeNom> POINT
=> NOM_P VERBE ARTICLE NOM_C POINT
=> Bart tue un lapin .
– En reconnaissance, parsing
●
Réductions d’une phrase en remplaçant des membres droits par les
membre gauches
●
La phrase est valide si les réductions terminent sur l’axiome
12/10/2022 51 / 127
 Arbre Syntaxique
Décrit la reconnaissance d’une phrase donnée conformément à
une grammaire
Arbre étiqueté :
– Feuilles = tokens = mots de VT
– Nœud = membre gauche de production = symbole de VN
– Fils = membres droits de la production
– Racine = axiome
<Phrase>
< SujetVerbeCompl >

<GroupeNom> <GroupeNom>

Tokens : Nom_P VERBE ARTICLE NOM_C POINT

Texte en entrée : Obi-wan mange un gnou .

12/10/2022 52 / 127
 Où est l’étoile ?
Problème !
– Les grammaires algébriques contiennent la concaténation et
l’alternative mais pas la fermeture de Kleene
– Selon Chomsky, les langages rationnels sont algébriques
– Comment réaliser l’étoile avec une grammaire algébrique ?

Exercice
– Soit L un langage décrit par le symbole L, comment définir le langage
L* avec une grammaire algébrique ?
●
N.B. : si L est rationnel, L* est rationnel et doit donc être algébrique

12/10/2022 53 / 127
 Où est l’étoile ? (soluces)
Solution(s)
« La récursivité contient l’étoile »

Récursif Droit Récursif Gauche

Lstar := ε Lstar := ε
| L Lstar | Lstar L
; ;

N.B. : dans les outils, le mot vide ε pourra s’écrire /* mot vide */

12/10/2022 54 / 127
 Exemple
Ébauche d’un langage informatique
– Vocabulaire terminal TYPE = int | char | float
IDENT = [a-zA-Z] [a-zA-Z0-9]*
INT = -? [0-9]+
FLOAT = -? [0-9]+ ( \. [0-9] *) ?
– Règles de productions Program := Definitions Functions ;
Definitions := TypeVar
| Definitions TypeVar ;
TypeVar := TYPE VarList ';' ;
VarList := Var
| VarList ',' Var ;
– Exemple de production Var := ScalarVar | ArrayVar ;
ScalarVar := IDENT
int i, j, i42=-1 ; | IDENT '=' Number ;
int a[-42], b[3][1][4] ; ArrayVar := IDENT '[' INT ']'
float pi=3 ; | ArrayVar '[' INT ']' ;
int yy=0.3 ; Number := INT | FLOAT ;

12/10/2022 55 / 127
 Grammaire Régulière (1/2)
Une grammaire algébrique peut décrire un langage rationnel
– Indécidable dans le cas général (non-déterministe)
– Mais certaines productions simples génèrent des langages rationnels

Grammaire Linéaire Gauche (resp. Droite)

– Toute production contient au plus un symbole non-terminal en
membre droit
– Ce symbole non-terminal est le premier (resp. dernier) symbole en
membre droit
Linéaire Gauche Linéaire Droit
vi := vj t1 t2...tn ; vi := t1 t2...tn vj ;

Les grammaires linéaires gauches (resp. droite) engendrent les

langages rationnels
12/10/2022 56 / 127
 Grammaire Régulière (2/2)
Exemples
1) VN={S,A} , VT={a,b} S := b A | a S ;
A := b A | a ;
Expressions régulières pour A et S ?

2) VN={S} , VT={LETTRE, CHIFFRE} S := LETTRE

| S LETTRE
LETTRE=[a-z][A-Z], CHIFFRE=[0-9] | S CHIFFRE ;
Expression régulière pour S ?

3) VN={S}, VT={a,b}
S := a b
Linéaire ? Régulier ? | aSb ;
Expression régulière pour S ?

12/10/2022 57 / 127
 Grammaire Régulière (2/2 soluce)
Solutions
1) A = b* a S := b A | a S ;
A := b A | a ;
S = a* b A = a* b+ a
L(S) = {ba, aba, aaba, abba, aaaba ...}

2) S = [a-zA-Z] [a-zA-Z0-9]* S := LETTRE

| S LETTRE
| S CHIFFRE ;

3) Linéaire « milieu », ni droite ni gauche

Non régulier,
L(S) = {anbn, n>0} S := a b
| aSb ;
Linéaire « et droite et gauche » : SS := ab;
:= a T ;
T := S b ;
12/10/2022 58 / 127
 Grammaire Ambiguë (1/2)
Plusieurs arbres de syntaxe possibles pour une entrée
– Ambiguë => indéterminisme dans l’analyse syntaxique
– En général , arbres différents => sémantiques différentes

Exemple : Instruction IF
(R0) Inst := Inst_if | ... ;
(R1) Inst_if := "if" "(" Condition ")" Inst
(R2) | "if" "(" Condition ")" Inst "else" Inst ;

R1
R0
R2
Entrée : if ( cond1 ) if ( cond2 ) inst1 else inst2
R1
R0
R2
12/10/2022 59 / 127
 Grammaire Ambiguë (2/2)
Grammaire d’opérateur (pas de mot vide, pas de non-terminaux voisins)
Généralement ambiguë Expr := Expr '+' Expr
2+3+4 = (2+3)+4 ou 2+(3+4) ? | Expr '-' Expr
| Expr '*' Exp
a=1; a + ++a + ++a = ? | '-' Expr
2-3-4 = (2-3)-4 ou 2-(3-4) ? | '(' Expr ')'
2+3*4 = (2+3)*4 ou 2+(3*4) ? | INT
| SYMBOL ;

Solutions /* Version non ambiguë gauche */

Expr := Term
●
Réécriture de la grammaire | Expr '+' Term ;
en ajoutant des non-terminaux | Expr '-' Term;
Term := Facteur
| Term '*' Facteur ;
●
Gestion de priorités sur les règles Facteur:= '-' Expr
dans l’analyse syntaxique | '(' Expr ')'
| INT
| SYMBOL ;
12/10/2022 60 / 127
 Spécification avec BNF (1/2)
Syntaxes Multiples : BNF, EBNF, ABNF
Regroupe grammaire algébrique et expression régulière
Terminaux = chaînes de caractères constantes
Répétitions et groupages dans les règles de production
Éléments de syntaxe
Définition avec = ou ::= et éventuellement ; en fin
Non-Terminaux entre <> ou pas. Terminaux entre " " ou ' ' ou pas
Groupage avec ( )
Répétition Kleene entre { } , ou *terme
Répétition numérique n*terme, n*mterme, …
Optionnel (répétition 0 ou 1) entre [ ]
Alternative avec | ou / ,, Concaténation avec , ou pas
Commentaires (* … *) ou ; ...
12/10/2022 61 / 127
 Spécification avec BNF (2/2)
Exemples <Expression > ::= <Terme> { ( + | - ) <Terme> } ;
Expressions <Terme > ::= <Facteur> { ( * | / ) <Facteur> } ;
Arithmétiques <Facteur> ::= <Nombre> | <Variable> | "(" <Expression> ")" ;
en BNF/EBNF <Nombre> ::= [-] <Chiffre> {<Chiffre>} ;
<Chiffre> ::= 0 | 1 | ..... | 9 ;
<Variable> ::= <Lettre> { <Lettre> | <Chiffre> | - } ;
<Lettre> ::= a | b | ..... | Z ;

date-time = [ day "," ] date time

ABNF day = "Mon" / "Tue" / "Wed" / "Thu" / "Fri" / "Sat" / "Sun"
RFC822 date = 1*2DIGIT month 2DIGIT ; dd mm yy
month = "Jan" / "Feb" / "Mar" / "Apr" / "May" / "Jun"
/ "Jul" / "Aug" / "Sep" / "Oct" / "Nov" / "Dec"
time = hour zone ; hh:mm:ss zzz
hour = 2DIGIT ":" 2DIGIT [":" 2DIGIT]
zone = "GMT" / ....... / ( ("+" / "-") 4DIGIT )
DIGIT = <any ASCII decimal digit> ; ( decimal 48.- 57.)
12/10/2022 62 / 127
 Chapitre 4

4) Analyse Syntaxique
Analyse syntaxique : trois stratégies 64
Analyse descendante 65
Analyse ascendante « Shift/Reduce » 68
Automate LR 73

12/10/2022 63 / 127
 Analyse syntaxique : trois stratégies
Résolution générale
– Applicable aux langages algébriques non déterministes
– Complexité O(n3) ; Algorithmes : Earley, CYK,Valiant, …

Analyse descendante ou « LL »
– Applicable à « beaucoup » de langages algébriques déterministes
– Algorithme plus intuitif, mais contraignant sur l’écriture de la
grammaire
– Complexité linéaire O(n) ; Outils : « à la main », javacc, ANTLR, …

Analyse ascendante ou « LR » ou Shift/Reduce

– Applicable à « énormément » de langages algébriques déterministes
– Applicabilité fonction du langage et pas de la grammaire
– Complexité linéaire O(n) ; Outils : yacc, bison, CUP, GOLD, ...

12/10/2022 64 / 127
 Analyse descendante (1/3)
Principe
– Construction de l’arbre de syntaxe de haut en bas
– Utilisation de la grammaire en production
– Arbre de décision ET/OU
●
Nœud OU : pour remplacer un symbole non-terminal, on a le choix entre
les différentes productions (ou alternatives) avec ce symbole en membre
gauche
●
Nœud ET : pour une production, il faut reconnaître la séquence des
symboles en membre droit
(v1) v := s1 s2 …sn ;
(v2) v := s'1 s'2 …s'p ;
– Exploration de l’arbre
V
●
En profondeur avec retour arrière /---\
●
En « parallèle » ... / OU \
V1 V2
●
Rendre prédictible les choix OU ? / | \ / | \
s1 .. sn s'1 .. s'p
12/10/2022 65 / 127
 Analyse descendante (2/3)
Exemple langage naturel élémentaire
<Phrase>

<SujetVerbeCompl>

<GroupeNom> <GroupeNom>

GN1 GN2 GN1 GN2

NOM_P ARTICLE NOM_C VERBE NOM_P ARTICLE NOM_C POINT

Parcours en profondeur : « Obi-Wan mange un gnou. » ?

– Choix GN1, Obi-wan=NOM_P ? ok, mange=VERBE ? ok,
●
Choix GN1, un=NOM_P ? echec, retour dernier choix,
●
Choix GN2, un=ARTICLE ? ok, gnou=NOM_C ? ok, .=POINT ? ok
– Fini, Accepte.
12/10/2022 66 / 127
 Analyse descendante (3/3)
Descente récursive : Mise en œuvre simple et intuitive
Pour chaque symbole X, une fonction reco_X()
●
Si X est terminal reco_X() lit le token X en entrée, ou échec
●
Si X est non-terminal, reco_X() choisit une production de X et appelle
successivement reco_Si() pour les symboles en membre droit
Contraintes sur l’écriture de la grammaire
Pas de récursivité gauche dans les productions !!!
directement L := L a | a ; ou indirectement L := M … ; M :=L... ;
D’autres contraintes : factorisation gauche de la grammaire, ….
Rendre prédictible (déterministe)
Utilisation du Lookahead, calcul de fonctions first(),next()
Principe : une production n’est applicable que si récursivement elle
peut générer le prochain token en entrée
12/10/2022 67 / 127
 Analyse ascendante « Shift/Reduce » (1/4)
Principe
– Construire l’arbre syntaxique de bas en haut
– Utilisation de la grammaire en reconnaissance
●
Réduction = remplacement membre droit par membre gauche
– Utilisation d’une pile
●
Shift = empiler le token suivant
●
Tester les réductions possibles en tête de pile
●
Reduce = dépiler n symboles d’un membre droit, empiler le symbole
non-terminal du membre gauche
Indéterminisme
– « reduce/reduce » plusieurs réductions possibles au même moment
– « shift/reduce » réduction possible, mais décalage préférable
NB : Si il existe une production vide, il y a toujours une réduction possible
même avec une pile vide !
12/10/2022 68 / 127
 Analyse ascendante « Shift/Reduce » (2/4)
Entrée = « Obi-Wan mange un gnou. »
Opération Pile
décalage NOM_P
réduction <GroupNom>
décalage <GroupNom> VERBE
décalage <GroupNom> VERBE ARTICLE
décalage <GroupNom> VERBE ARTICLE NOM_C
réduction <GroupNom> VERBE <GroupNom>
réduction <SujetVerbeCompl>
décalage <SujetVerbeCompl> POINT
réduction <Phrase>
Succès

N.B. Succès = règle conventionnelle « $START = <Phrase> EOF »

12/10/2022 69 / 127
 Analyse ascendante « Shift/Reduce » (3/4)
Entrée = « alpha + bêta + 666 »
Expr := Expr '+' Expr
Opération Pile | INT
décalage SYMBOL | SYMBOL ;
réduction Expr
décalage Expr '+'
décalage Expr '+' SYMBOL
Ambiguïté
réduction Expr '+' Expr
Conflit shift/reduce
réduction Expr décalage Expr '+' Expr '+'
décalage Expr '+' décalage Expr '+' Expr '+' INT
décalage Expr '+' INT réduction Expr '+' Expr '+' Expr
réduction Expr '+' Expr réduction Expr '+' Expr
réduction Expr réduction Expr
succès succès
(alpha+bêta)+666 alpha+(bêta+666)
12/10/2022 70 / 127
 Analyse ascendante « Shift/Reduce » (4/4)
Input = « 42 666 »

(R0) Liste := /* mot vide */ (R0) Liste := /* mot vide */

(R1) | Liste INT ; (R1) | INT Liste ;

Opération Pile Opération Pile

– Quand fait-on la réduction R0 ?

– Dans quel ordre sont réduits les entiers de la liste ?

12/10/2022 71 / 127
 Analyse ascendante « Shift/Reduce » (4/4 soluce)
Input = « 42 666 »

(R0) Liste := /* mot vide */ (R0) Liste := /* mot vide */

(R1) | Liste INT ; (R1) | INT Liste ;

Opération Pile Opération Pile

Réduction R0 Liste décalage INT
décalage Liste INT décalage INT INT
Réduction R1(42) Liste Réduction R0 INT INT Liste
décalage Liste INT Réduction R1(666) INT Liste
réduction R1(666) Liste Réduction R1(42) Liste

Récursivités droites ou gauches valides

Récursivité gauche préférée par analyseur LR

12/10/2022 72 / 127
 Automate LR (1/3)
Analyse LR : Automate à pile pour décider des shift/reduce
États de l’automate
– états viables du sommet de pile ( séquence de n symboles)
– viable = le sommet de pile pourra être réduit à terme
– sommet de pile = préfixe de membre droit de production

Pile
– A chaque Push, l’état de l’automate est empilé avec le symbole
Transitions
– Shift : transition « simple » avec Push d’un token
– Reduce : transition avec remplacement (Pop* + Push) et retour à
l’état stocké dans la pile (dernier Pop)
– En général, les transitions reduce ne sont pas représentées

12/10/2022 73 / 127
 Automate LR (2/3)
Exemple LALR(1) avec « cup -dump »

terminal TOK; ---- ACTION_TABLE ----

nonterminal list; From state #0
=== Viable Prefix Recognizer === [term 0:REDUCE prod 0]
list ::= /* vide */ [term 2:REDUCE prod 0]
–--lalr_state [0]:
| list TOK [list ::= (*) list TOK , {EOF TOK }] From state #1
; [$START ::= (*) list EOF , {EOF }] [term 0:SHIFT to state 2]
[list ::= (*) , {EOF TOK }] [term 2:SHIFT to state 3]
transition on list to state [1] From state #2
== Terminals == [term 0:REDUCE prod 1]
[0]EOF –--lalr_state [1]:
[list ::= list (*) TOK , {EOF TOK }] From state #3
[1]error [term 0:REDUCE prod 2]
[2]TOK [$START ::= list (*) EOF , {EOF }]
transition on TOK to state [3] [term 2:REDUCE prod 2]
=== Non terminals = –-- REDUCE_TABLE ----
[0]list transition on EOF to state [2]
–--lalr_state [2]: From state #0
=== Productions = [non term 0->state 1]
[0] list ::= [$START ::= list EOF (*) , {EOF }]
–--lalr_state [3]: From state #1
[1] $START ::= list EOF From state #2
[2] list ::= list TOK [list ::= list TOK (*) , {EOF TOK }]
From state #3

12/10/2022 74 / 127
 Automate LR (3/3)
(using CUP eclipse plugin)

R1 R2

lalr_state [2]: lalr_state [3]:

[$START ::= list EOF (*) , {EOF }] [list ::= list TOK (*) , {EOF TOK }]}

EOF TOK

lalr_state [1]:
[list ::= list (*) TOK , {EOF TOK }]
[$START ::= list (*) EOF , {EOF }]
list

lalr_state [0]:
[list ::= (*) list TOK , {EOF TOK }]
R0
[$START ::= (*) list EOF , {EOF }]
[list ::= (*) , {EOF TOK }]

12/10/2022 75 / 127
 Chapitre 5

5) Outils JFlex et CUP (annexe )

Utilisation JFlex et CUP 77
Format des spécifications 78
Automate LALR et Conflit 79

12/10/2022 76 / 127
 Utilisation JFlex et CUP
[Link]
[Link] [Link]
[Link] [Link]
Spécification JFlex Spécification CUP
Options,main() main()
Règles lexicales Règles syntaxiques

java -jar [Link] [Link] java -jar java_cup.jar [Link]

[Link] [Link] [Link]

int next_token() Énumération Symbol parse()
Symbol next_token() des tokens

javac [Link] javac -cp java_cup.[Link] *.java

Analyseur Analyseur
Lexical Syntaxique
java Yylex <data java -cp java_cup.[Link] CupParse <data

12/10/2022 77 / 127
 Format des spécifications
Jflex Cup
package [Link] package [Link]
import [Link] import [Link].*
%% parser code {: /* … */ :}
%include [Link] action code {: int i ; :};
%include [Link] init with {: i=0; :}
%{ terminal int TOK ;
%} terminal TIK, TAK ;
%init{ nonterminal int sym, var;
%init} precedence left TIK;
%eof{ precedence right TAK ;
%eof} start with sym,;
ANY = [^] sym ::= sym:s TOK:n {: RESULT=s+n; :}
BLANC = [ \t] | var:v {: RESULT=v; :}
%% ;
[a-zA-Z] [a-zA-Z0-9]* { ECHO("ID"); } var ::= /* vide */ {: RESULT=0; :}
[ \t] | {NL} { ECHO(); } | TIK {: RESULT=42 ; i++; :}
{ANY} { WARN("Invalid char"); } ;

12/10/2022 78 / 127
 Automate LALR et Conflit (1/2)
« cup -dump » : ===== Viable Prefix Recognizer ===
–--lalr_state [0]:
===== Terminals ===== [list ::= (*) TOK , {EOF TOK }]
terminal TOK; [0]EOF [1]error [2]TOK [$START ::= (*) list EOF , {EOF }]
nonterminal list; ===== Non terminals == [list ::= (*) list TOK , {EOF TOK }]
[0]list [list ::= (*) , {EOF TOK }]
list ::= /* vide */
===== Productions === transition on TOK to state [2]
| TOK [0] list ::=
| list TOK transition on list to state [1]
[1] $START ::= list EOF ---lalr_state [1]:
; [2] list ::= TOK [$START ::= list (*) EOF , {EOF }]
[3] list ::= list TOK [list ::= list (*) TOK , {EOF TOK }]
transition on TOK to state [4]
transition on EOF to state [3]
---lalr_state [2]:
Warning : *** Shift/Reduce conflict [list ::= TOK (*) , {EOF TOK }]
found in state #0 ---lalr_state [3]:
between list ::= (*) [$START ::= list EOF (*) , {EOF }]
and list ::= (*) TOK ---lalr_state [4]:
under symbol TOK [list ::= list TOK (*) , {EOF TOK }]

12/10/2022 79 / 127
 Automate LALR et Conflit (2/2)
(using CUP eclipse plugin)
R1 R3

lalr_state [3]: lalr_state [4]:

[$START ::= list EOF (*) , {EOF }] [list ::= list TOK (*) , {EOF TOK }

EOF TOK
R2

lalr_state [1]:
lalr_state [2]: [$START ::= list (*) EOF , {EOF }]
[list ::= TOK (*) , {EOF [list ::= list (*) TOK , {EOF TOK }]
TOK }]]
list
Conflit TOK
shift/reduce lalr_state [0]:
[list ::= (*) TOK , {EOF TOK }]
R0 [$START ::= (*) list EOF , {EOF }]
[list ::= (*) list TOK , {EOF TOK }]
[list ::= (*) , {EOF TOK }]

12/10/2022 80 / 127
 Chapitre 6

6) Arbre de Syntaxe Abstraite

Arbre Syntaxique 82
CST vs AST 84
Arbre et Analyse LR 86
Arbre et Typage Objet 87
Visiteur 88
Classes Java du cours 90
(Bonus) Retour au source 94

12/10/2022 81 / 127
 Arbre Syntaxique
L’Arbre Syntaxique est :
– La preuve de la validité syntaxique de l’entrée
– Le support d’une part importante de la sémantique de l’entrée
– La structure de données transmise dans les deux phases suivantes de
la compilation : analyse sémantique et génération de code
intermédiaire
Rappel :
– Nœud=règle de production
<Phrase>
– feuille=token
< SujetVerbeCompl >

<GroupeNom> <GtoupeNom>

Tokens : Nom_P VERBE ARTICLE NOM_C POINT

Texte en entrée : Obi-wan mange un gnou .

12/10/2022 82 / 127
 ...

Syntaxique Sémantique Bon pour génération

12/10/2022 83 / 127
 CST vs AST (1/2)
Concrete Syntax Tree (CST) :
– Forme adaptée pour la validation syntaxique
– Pas de valeurs sémantiques pour les tokens
– Les nœuds respectent strictement les règles de grammaire
– Construction automatique avec les outils d’analyse syntaxique

Abstract Syntax Tree (AST) :

– Forme porteuse de la sémantique
– Intègre les valeurs sémantiques des tokens
– Supprime les tokens inutiles (séparateurs, parenthèses,…)
– Se libère du « tyran algébrique »
●
OPBIN vs {PLUS,MOINS,…}
●
Liste « 1 2 3 » vs List ( List ( List (List(ε), 1) , 2) , 3)

12/10/2022 84 / 127
 CST vs AST (2/2)
Exemples : « F(a, b+3, 1) »
CST AST

Call Call("F")

IDENT ( args ) ExpList

args , ExprLit Var("a") OpBin(+) Int(1)

args , ExprPlus ENTIER Var("b") Int(3)

ExprVar ExprVar + ExprLit

IDENT IDENT ENTIER

12/10/2022 85 / 127
 Arbre et Analyse LR
Analyse LR
– Construction ascendante de l’arbre
– Action sémantique = nouvel arbre à partir des fils déjà existants

/* Exemple dans une spécification CUP */

nonterminal Arbre v, s1, s2 , … ;
v ::= s1: x1 s2: x2 … /* RegleN */
{: RESULT= new Arbre (« RegleN », x1, x2, …) ; :}
;
/* Cas des feuilles */
temninal [type] Tj , … ;
v ::= …Tj ... /* RegleM */
{: RESULT= new Arbre (« RegleM », .. , new Arbre(« Tj »), ..) ; :}
;

12/10/2022 86 / 127
 Arbre et Typage Objet
Utilisation d’un langage objet :
– Typage des nœuds
●
new ArbreRegleN (x1,…) vs new Arbre(« RegleN »,x1,...).
– Héritage et productions alternatives dans la grammaire
●
ArbreV = classe abstraite pour ArbreRegleV1, ArbreRegleV2,...
– Surdéfinition (overriding) et liaison dynamique
●
ArbreV T = new ArbreRegleVi() ;
[Link]() ; /* méthode xxx de la classe concrète de T (ArbreRegleVi) */
Réalisation d’une fonction sur l’arbre
– Méthodes d’objets dans les nœuds et parcours récursifs
– Variante : patron de conception « Visiteur » (Visitor Pattern)
But : obtenir le même résultat mais avec le code des méthodes d’objets
de chaque nœud regroupé dans une seule classe.

12/10/2022 87 / 127
 Visiteur (1/2)
Ajouter une fonction à une hiérarchie de classes (classes visitées)
– Non pas en utilisant le schéma naturel OO des méthodes d’instance
dans chaque classe (héritage, surdéfinition)
– Mais en utilisant une classe externe (classe visiteuse).

Utilité
– Regrouper l’algorithme de la fonction dans une même classe
– Ne pas modifier les classes visitées pour chaque nouvelle fonction

Problème de liaison dynamique : comment connaître dans la

classe visiteuse, la classe concrète des objets visités ?
– Solution « pas très classe » : Imbrications de if ( x instanceof X1)
– Solution « plus classe » : définir une méthode dans les classes visitées
qui sert uniquement à connaître la classe concrète.

12/10/2022 88 / 127
 Visiteur(2/2)
« Accept et Visit sont dans un bateau »

class Visiteuse extends Visitor class VisitéeA extends Visitées

public void accept(Visitor v) {
public void visit ( VisitéeA o) { [Link](this) ;
/* maFonction cas A */ } }
/* public void maFonction() */
public void visit ( VisitéeB o) {
/* maFonction cas B */ } class VisitéeB extends Visitées
… public void accept(Visitor v) {
[Link](this) ;
void maFonction ( Visitées o) { }
[Link](this) ; /* public void maFonction() */
}
(Solution « plus classe » !?)

12/10/2022 89 / 127
 Classes du cours (1/4)
AstNode : Classe abstraite ancêtre des « visitées »
/** Patron Visiteur */
public abstract void accept(AstVisitor v);

/** Constructeur varargs */

public AstNode( AstNode ... fils )

/** Itérable avec for(AstNode f : node) {} */

public Iterator<AstNode> iterator()
public int size()

/** Impression d’un nœud */

public String toString()

/** Impression Arbre */

public String toPrint()
12/10/2022 90 / 127
 Classes du cours (2/4)
AstList<R> : fils homogènes et construction itérative
class AstList<R extends AstNode> extends AstNode {
public void accept(AstVisitor v) { [Link](this); }
/** Construction itérative avec ajout en fin de liste */
public void add(R node)
}
Ast : Classe concrète de base (pour tests ou CST)
class Ast extends AstNode {
public void accept(AstVisitor v) { [Link](this); }

public final String label;

public Ast(String label, AstNode... f) { super(f); [Link] = label; }
public String toString() { return label; }
}

12/10/2022 91 / 127
 Classes du cours (3/4)
AstVisitor : Interface des classes « Visiteuses »
– Méthodes abstraites visit() pour chaque classe visitable de l’AST

interface AstVisitor {

<T extends AstNode> void visit(AstList<T> n);

void visit(Ast n);

/* … idem pour chaque classe visitable. */

12/10/2022 92 / 127
 Classes du cours (4/4)
AstVisitorDefault : Visiteur générique de l’AST
– Classe mère pour des Visiteurs qui font des calculs par parcours en
profondeur de l’arbre.
– Les méthodes visit() sont alors à surdéfinir (override). Ou pas !

class AstVisitorDefault implements AstVisitor {

public void defaultVisit(AstNode n) {
for (AstNode f : n) [Link](this);
}

public <T extends AstNode> void visit(AstList<T> n) { defaultVisit(n); }

public void visit(Ast n) { defaultVisit(n); }
/* … idem pour chaque classe visitable. */
}

12/10/2022 93 / 127
 (Bonus) Retour au source
Propager les informations de positions dans le fichier source
– JFlex vers CUP : transparent avec [Link]
●
ComplexSymbolFactory et TOKEN()
– CUP vers AST :
●
Option « -locations » de CUP requise (Makefile ou [Link])
●
Méthode addPosition() de AstNode :
v ::= s1: aa … sn:zz
{: RESULT= new Arbre ( aa, …,zz) ;
[Link](aaxleft, zzxright) ; :}
;

●
Exemple : [Link]() -> RopBin[16/10/293-16/21/304](+)

12/10/2022 94 / 127
 Chapitre 7

7) Analyse Sémantique
Où en est-on ? 96
Analyse sémantique 99
Attributs sémantiques 101
Analyse statique ou dynamique 102
Des fonctions sémantiques 103
Table des symboles 106
Contrôle de type 107

12/10/2022 95 / 127
 Où en est-on ? (1/3)
Retour : Phases de Compilation
Texte Tokens AST Sémantique
Lexicale Syntaxe

java_cup.[Link] syntax,[Link] Arbre Sémantique =

AST +
Attributs +
Optimisation, Table Symbole
Assemblage,
Allocation [Link] :
Édition de liens [Link] +
mémoire/registre
[Link]
[Link] + [Link].
MIPS
Représentation
Génération Intermédiaire
Intermédiaire
de code [Link]

12/10/2022 96 / 127
 Où en est-on ? (2/3)
Compilation Classique versus Moderne
– « Dragon Book » Aho, Ullman 1977
– « Modern Compiler » Appel 2000 , ...

Identique pour l’analyse lexicale et syntaxique

Différences importantes sur l’analyse sémantique et la

génération de la forme intermédiaire

Différences sur les solutions techniques et aussi sur le problème

à résoudre

12/10/2022 97 / 127
 Où en est-on ? (3/3)
Compilation Multi-passe ou Mono-passe ?
– Exécution en séquence vs chainage (pipeline) des phases
– Mono-passe : contraignant sur l’algorithmique du compilateur, mais
économe sur les performances en temps, en espace, en entrée-sortie
– Multi-passe : plus souple dans la programmation et l’indépendance
des phases de compilation
Historiquement : Mono-passe était un enjeu vital
– Contrainte sur le langage : Tout ce qui est nécessaire pour analyser
une portion de programme doit exister « avant » dans le source.
– Algorithmique lourde pour tout résoudre en une fois

Aujourd’hui : Multi-passe encouragé

– Contraintes plus faibles sur les performances
– Langages plus «libéraux» (i.e. Java)

12/10/2022 98 / 127
 Analyse sémantique (1/2)
Objectifs :
– Valider les règles du langage non gérables au niveau syntaxique

– Établir la signification du programme et sa sémantique d’exécution

– Construire les éléments de contexte : Informations nécessaires pour

l’exécution mais non explicites dans l’arbre de syntaxe, ou explicites
dans une autre partie de l’arbre

– Vérifier ou Inférer des propriétés de l’algorithme : Invariants

●
Terminaison, validité de l’algorithme, non débordement, …
●
N.B. : Théorème de Rice => problèmes indécidables

12/10/2022 99 / 127
 Analyse sémantique (2/2)
De la théorie :
– « Haute » : Lambda-calcul, Théorèmes du point fixe, Preuve de
programmes
– « Basse » : Grammaires Attribuées, Traduction dirigée par la syntaxe

Mais en pratique ?
– Trop théorique, et peu de résultats pour de « vrais » programmes
– Trop orientée sur la contrainte « compilation mono-passe »

Conclusion : Approche pragmatique

– Des fonctions sémantiques réalisées de façons modulaires et en
passes successives

12/10/2022 100 / 127

 Attributs sémantiques
Analyse Sémantique = Décoration de l’AST
– Calcul d’attributs associés aux différents nœuds de l’arbre de syntaxe
●
Visibilité des identificateurs
●
Type de données
●
Chemins d’exécution
●
…
Attribut Synthétisé vs Attribut Hérité
– Hérité : la valeur est construite à partir de la valeur du père.
– Synthétisé : la valeur est construite à partir des valeurs des fils.
– Mixte ? Essayer de décomposer en Hérité + Synthétisé
– N.B. Analyse syntaxique LR => synthétisé facile, hérité difficile

Algorithmie : Parcours récursif en profondeur d’Arbre

– cf. Mémento du projet Minijava pour la réalisation.
12/10/2022 101 / 127
 Analyse statique ou dynamique
Statique
– Les attributs sémantiques sont calculés sur la structure statique de
l’AST.

Dynamique
– On ajoute à l’AST, les chemins d’exécutions du programme pour
calculer des attributs qui vont hériter de nœuds traversés « avant » ou
« après » à l’exécution.
– Algorithmique :
●
« Couture d’arbre »
●
Interprétation symbolique
●
Équations de flots de données
●
Analyse de vivacité

12/10/2022 102 / 127

 Des fonctions sémantiques (1/3)
Liaison des identificateurs
– Table des symboles
– Détections : « Non défini », « déjà défini », « initialisation »
– Consistance des définitions : détection de boucle (héritage Java,
définitions régulières JFlex, …), …
– Paradigmes Objets : héritage, redéfinition (override), polymorphisme,
liaison dynamique, héritage multiple .
Contrôle de Type
– Typage des expressions, contraintes d’affectation et d’appel
– Surcharge des opérateurs
– Transtypage (cast) implicite, équivalence des types
– Héritage Objet

12/10/2022 103 / 127

 Des fonctions sémantiques (2/3)
Propagation de constantes
– Évaluation «immediate» de l’assembleur, optimisation d’expressions
– Calcul d’intervalles : réduction des contrôles à l’exécution,
optimisation de boucle, ..
– Élimination de code

Analyse de vie, Analyse de dernière définition

– Optimisation mémoire : registre / sauvegarde de registre / pile /tas
– Variable unused, i.e. paramètre d’appel
– Garbage Collect

Optimisation appels de fonctions

– Fonction vs recopie/insertion de code
– Détection / Optimisation de récursivité

12/10/2022 104 / 127

 Des fonctions sémantiques (3/3)
Vivacité, Analyse de flot de données/contrôle
– Code mort
– Existence « return » dans toutes les exécutions d’une méthode
–…

Signalement de sémantiques douteuses : Compromis entre

optimisation silencieuse et détection d’erreurs de
programmation
– Boucles infinies, code mort, ...
– Transtypages « étranges »
– Expressions à valeurs triviales

12/10/2022 105 / 127

 Table des Symboles
Liaison entre déclarations et utilisation des identificateurs
– Et mise en œuvre de la surcharge, polymorphisme, …
Attribut « mixte »
– Une déclaration est synthétisée pour trouver sa portée (scope)
– La visibilité est héritée, et éventuellement surchargée dans l’AST

=> Structure spécifique : « Table des symboles »

– Regroupe l’ensemble des déclarations d’identificateurs, leurs portées
et leurs visibilités depuis chaque nœud de l’arbre
– Propagée dans la suite de la compilation (y compris l’exécutable)

Dans le cas d’un langage OO

– la visibilité est aussi hérité en suivant l’arbre d’héritage des classes
qui est indépendant de l’AST. (information de contexte)
– Et aussi liaison dynamique, ..

12/10/2022 106 / 127

 Contrôle de type (1/2)
Langage compilé <-> Langage fortement typé
Typage
– Partie importante en volume de la définition d’un langage
– Mais beaucoup de règles rapides à vérifier, bien que difficilement
gérables au niveau syntaxique.
Valider les contraintes de typage du langage
– Conformité des opérateurs
– Affectations
– Appel de fonctions

Fixer les contraintes pour l’implantation des variables :

– Type => taille mémoire, type de registre, …
– Construction d’un attribut synthétisé

12/10/2022 107 / 127

 Contrôle de type (2/2)
Valider et réaliser les transtypages implicites ou explicites:
– Équivalence de types, héritage,
– Fonctions de conversion

Calcul de la sémantique des expressions

– Surcharge des opérateurs

Gérer les mécanismes de construction de type du langage

– Références, tableaux, enregistrements/structures, énumérations,
ensembles, …
– Héritage multiple

12/10/2022 108 / 127

 Chapitre 8

8) Représentation Intermédiaire
Objectif 110
Principe 111
Code à trois adresses 113
Représentation pour Minijava 114
Traduction AST vers IR 116

12/10/2022 109 / 127

 Objectif
Objectif génie logiciel
– Modularité du compilateur => Interface entre :
●
Partie Avant dépendante du langage source
●
Partie Arrière dépendante de la machine cible (assembleurs ou autres)

Objectif programmation
– Étape intermédiaire pour la phase « Génération »
– Génération = traduction de l’AST vers code machine
●
Linéarisation du code
●
Génération de l’assembleur
●
Allocation mémoire
●
Optimisations : allocations des registres, évaluation des expressions, ...

12/10/2022 110 / 127

 Principe (1/2)
Génération de la représentation intermédiaire
– Convertir les nœuds de l’AST en utilisant un nombre réduit
d’ « instructions »
– Utiliser des instructions « intermédiaires » entre le langage source et
le langage cible
– Linéarisation (canonisation) :
●
Traduire la sémantique d’exécution sous forme de séquence
d’instructions
●
Traduire en particulier les structures algorithmiques et les appels de
fonction sous forme de code séquentiel avec des sauts
●
Les expressions peuvent être complètement linéarisées (« classique ») ou
conserver la structure d’arbre (« moderne » )
●
N.B. : On fait implicitement de la « couture d’AST » et donc possibilités
de faire de l’analyse sémantique dynamique après la forme intermédiaire

12/10/2022 111 / 127

 Principe (2/2)
Représentation Intermédiaire
– Instructions
●
Affectations ou Copy
●
Labels pour sauts et appels de fonction
●
Sauts inconditionnels et conditionnels
●
Expressions (arbres ou linéarisées)
●
Gestion des Appels : ...
– Variables
●
Héritées de l’AST
●
Ajoutées pour la forme intermédiaire : évaluation des expressions,
gestion d’appels,, ...
– Informations administratives
●
Définition des symboles IR : variables, labels, constantes/immediate
●
...
12/10/2022 112 / 127
 Code à trois adresses
Programme
– Séquence d’instructions
– Linéarisation complète des expressions

Instruction
[ OP , X , Y, Z]
– Une opération et zéro à trois « adresses »
– « adresses » ou variables intermédiaires « Z = X OP Y »
●
Variables du programme source (ou nom de fonction, ou … )
●
Variables temporaires pour évaluation des expressions
●
Labels pour des sauts
●
Valeurs constantes
Exemple : [ * , 2, x, t1 ] t1 = 2 * x
A = 2*x +1 [ + , t1, 1, t2 ] t2 = t1+1
[ = , t2, , A ] A = t2

12/10/2022 113 / 127

 Représentation pour Minijava (1/2)
Représentation Intermédiaire : classe [Link]
– Programme = séquence de IRquadruple
●
Construction itérative par ajout de IRquadruple
– Création de variables intermédiaires :
●
IRvariable newTemp(String method), IRvariable newConst(int value),
●
IRvariable newLabel(), IRvariable newLabel(String label)

Instructions : package [Link].*

– abstract IRquadruple = [ op, arg1, arg2, result ]
– [Link] op : opérateur, uniquement nœuds *Assign*
– IRvariable result, arg1, arg2 : variables intermédiaires
– Les variables de l’AST ([Link]) implémentent
IRvariable
12/10/2022 114 / 127
 Représentation Minijava (2/2)
Instructions (suite) :
– Affectation : QCopy
– Labels
●
QLabel et QLabelMeth
– Sauts
●
QJump : inconditionnel
●
QJumpCond : conditionnel
– Gestion d’appel
●
QCall, QCallStatic, QParam, QReturn ( et QlabelMeth)
– Expressions
●
QAssign, QAssignUnary, QNew
– Expressions avec Tableau
●
QAssignArrayFrom, QAssignArrayTo, QNewArray, QLength

12/10/2022 115 / 127

 Traduction AST vers IR (1/4)
Génération de la représentation intermédiaire
– Classe [Link]
– Visite récursive en profondeur de l’AST
– Utilisation d’un attribut synthétisé de type IRvariable
●
Requis pour les nœuds expressions de l’AST (Expr*) ,
●
Contient la variable (temporaire ou constante ou AST) utilisée dans la
représentation intermédiaire pour stocker le résultat de l’expression
●
Les méthodes setVar() et getVar() affecte et retourne l’attribut IRvariable
associé à chaque nœud de l’AST
– Traduction et linéarisation
●
Concerne l’ensemble des nœuds de l’AST, à l’exception de quelques
nœuds uniquement déclaratifs (Klass, Formal,…)

12/10/2022 116 / 127

 Traduction AST vers IR (2/4)
Schémas de traduction
– Expressions
●
N.B. : toutes les « traduction(exp) » exécute un setVar(exp,...)

/* ExprLiteralInt */ setVar node, newConst(666))

666

/* ExprLiteralBool */ setVar node, newConst(0)

false /* ou 1 pour true */

/* ExprOpBin */ traduction(exp1)
exp1 + exp2 traduction(exp2)
setVar node, newTemp()
… QAssign +, getVar(exp1), getVar(exp2), getVar(node)

12/10/2022 117 / 127

 Traduction AST vers IR (3/4)
Schémas de traduction(suite)
– Déclaration et Appel de méthode
/* Method */ QLabelMeth newLabel(«xxx»)
xxx(….) { traduction(contenu)
contenu traduction(exp)
Return exp } QReturn getVar(exp)

/* ExprCall */ traduction(exp)
[Link](arg1,arg2,..) traduction(arg1)
/* … args suivants */
QParam getVar(exp) // this
QParam getVar(arg1)
/* … args suivants */
QCall newLabel(«xxx»), newConst(nb_args)

12/10/2022 118 / 127

 Traduction AST vers IR (4/4)
Schémas de traduction (fin)
– Instructions
/* StmtPrint */ traduction(exp)
[Link](exp) QParam getVar(exp)
QCallStatic newLabel(«_system_out_println»), «1»

/* StmtAssign */ traduction(exp)
X = exp setVar(node, lookup(« X »))
QCopy getvar(exp), getvar(node)

QLabel L1 L1 = newLabel()
/* StmtWhile */ traduction(exp) L2 = newLabel()
while (exp) inst QJumpCond L2, getVar(exp)
traduction(inst)
… QJump L1
QLabel L2
12/10/2022 119 / 127
 Chapitre 9

9) Génération de code
Différentes fonctions 121
Mémoire et Variables 124
Cadre d’appel 125
Convention d’appel 126
Fin de Compilation ! 127

overflow -128

12/10/2022 120 / 127

 Différentes fonctions (1/3)
Optimisation de la représentation intermédiaire
– Réduire le nombre de variables temporaires nécessaires
– Optimiser le calcul des expressions : ordre d’évaluation, recopies
– Optimiser les séquences d’instructions et les recopies
●
Graphes de flot de contrôle
Allocation Mémoire et Registre
– Définir les « adresses » pour implanter les variables (ou les méthodes
avec liaison dynamique)
– Identifier la vivacité des variables :
●
Utilisation des registres ?
●
Localité et besoin de save/restore pour les appels de fonctions ? ..
– Optimisation des registres
●
Algorithmes de coloriage de graphe

12/10/2022 121 / 127

 Différentes fonctions (2/3)
Exemple d’optimisation d’expression
traduction(exp1)
traduction(exp2)
QAssign OP, getVar(exp1), getVar(exp2), getVar(n)

traduction(exp2) /* ershow(exp2)>ershow(exp1) */
/* ExprOpBin */ traduction(exp1)
exp1 OP exp2 ?? QAssign OP, getVar(exp1), getVar(exp2), getVar(n)

traduction(exp1)
« Qassign »
« QJumpCond L0» En java :
traduction(exp2) (f==null) || (f.x==0)
« Qassign » (f!=null) && (f.x==0)
QLabel L0

12/10/2022 122 / 127

 Différentes fonctions (3/3)
Traduction de la Représentation Intermédiaire vers le langage
machine
– Réalisation d’un schéma d’appel pour les fonctions :
●
Passage d’argument, valeur de retour, adresse de retour
●
Sauvegarde de registres
●
Convention d’appel entre appelant et appelé
●
Utilisation de la pile et/ou des registres
– Sélection des instructions assembleur
– Génération, assemblage, édition de liens

Optimisation de code assembleur

– Remplacement de séquences d’instructions
●
Optimisation à lucarne

12/10/2022 123 / 127

 Mémoire et Variables
Variables
Pile ($sp) Locales
+ ...
Variables
Globales
Dynamiques
Tas (malloc/sbrk) Variables
Globales
Statiques
Statique (.data, $gp)
Constantes
(immediate)
Code (.text)
Labels
12/10/2022 124 / 127
 Cadre d’appel
Cadre d’appel = Bloc d’activation = Frame
– Utilisation de la pile pour les Arguments
appels de fonctions
– Des choix possibles :
Valeur de retour
(liens d’accès, de contrôle)
●
Pile ou Registre (args, …)
Sauvegarde état
●
Définition de l’état (quels registres ?)
Adresse retour, registres
– Séquence d’appel
●
Allocation dans la pile Variables locales
●
Remplissage de champs
– Séquence de retour Variables temporaires
●
Restauration état (pile et registres) (Variables dynamiques)
– => Convention d’appel
●
Définition détaillée du cadre et Répartition entre appelant et appelé

12/10/2022 125 / 127

 Convention d’appel MIPS/Minijava
(0) début de l’appel par l’appelant,
(1) fin de l’appel chez l’appelant == début de l’appel chez l’appelé
(2) fin de l’appel chez l’appelé

$sp (0)
$sp = stack pointer $fp
$fp = frame pointer $a0,… $a3

Appelant
$t0,… $t9, $v0, $v1 si besoin.
ArgN
Arguments 0 à 3 $fp ..
$a0,... $a3 Arg4
$sp (1)
$ra

Appelé
Frame $s0,… $s7 si besoin
Valeur de retour
size Variables locales
$v0
(et temporaires)
$sp (2)

12/10/2022 126 / 127

 Fin de Compilation !

12/10/2022 127 / 127