Abonnez-vous à DeepL Pro pour traduire des fichiers plus volumineux.

Visitez [Link]/pro pour en savoir plus.

Compilateur : Théories,
techniques et outils
Georges Edouard KOUAMOU École
nationale supérieure d'ingénieurs
Objectifs
• Introduire les étudiants aux principes de la compilation.
• Les idées et les techniques développées dans ce domaine sont si générales
et fondamentales qu'un informaticien (et même un non-informaticien) les
utilisera très souvent au cours de sa carrière (traitement des données,
moteurs de recherche, etc.).
• Étudier les algorithmes et les structures de données
inhérents à la mise en œuvre des compilateurs : analyse
lexicale, analyse syntaxique, analyse sémantique, génération
de code.
• Comprendre comment un compilateur est écrit pour permettre
aux étudiants de mieux comprendre les "contraintes" imposées
par les différents langages lorsqu'ils écrivent un programme dans
un langage de haut niveau.
Conception de compilateurs : 2
Théorie, outils
Contenu
• Introduction
• Analyse lexicale
• Machine à états finis
• Expressions régulières
• Jetons lexicaux
• Parsing (analyse syntaxique)
• Grammaires
• Analyse descendante
• Analyse ascendante
• Grammaires attribuées (ajout d'une sémantique à une grammaire sans contexte)
• Mise en œuvre avec SableCC

Conception de compilateurs : 3
Théorie, outils
Références
• Seth D. Bergmann. Conception de compilateurs : Theory, Tools,
and Examples, février 2016, Notes de cours
• Andrew W. Appel. Modern Compiler implementation in Java.
2nd Edition, Cambridge University Press, 2004
• Donald Knuth. Sémantique des langages contextuels libres.
MATHEMATICAL SYSTEMS THEORY, Vol. 2, No. 2, Publié par
Springer-Verlag, New York Inc.

Conception de compilateurs : 4
Théorie, outils
Introduction

Conception de compilateurs : 5
Théorie, outils
Définition (Compilateur)
• L'unité centrale de l'ordinateur est capable d'exécuter des tâches très simples et
primitives.
opérations = langage machine (ou langage d'assemblage)
1. additionner deux nombres stockés en mémoire
2. déplacer des nombres d'un emplacement de la mémoire à un autre
3. déplacer des informations entre l'unité centrale et la mémoire
-𝑏± 𝑏2-4𝑎𝑐
• Comment l'ordinateur exécute-t-il une instruction complexe :
2𝑎
• Utilisation d'un traducteur
logiciel
• Un compilateur accepte des énoncés (complexes) et les traduit en
séquences d'opérations en langage machine.
• Un interprète est un logiciel dont la fonction est très similaire à celle d'un
compilateur. Il exécute les calculs spécifiés dans le programme source.
Conception de compilateurs : 6
Théorie, outils
La structure d'un compilateur
1. Analyse lexicale
2. Analyse
3. Analyse sémantique
4. Optimisation
5. Génération de codes
• Les trois premiers, au moins, peuvent être compris par analogie avec la
façon dont les humains
comprendre les langues naturelles (français, anglais, ...)

Conception de compilateurs : 7
Théorie, outils
Structure d'un compilateur
• input : chaîne de caractères
• Analyse lexicale ou Scanner : diviser la chaîne de caractères en mots connus sous le nom
de "token".
ou lexème
• Exemples : mots-clés, opérateurs, constantes, identifiants
• Analyse syntaxique ou analyseur syntaxique : vérifie la syntaxe correcte et construit
l'arbre syntaxique.
• La structure sous-jacente du programme source
• De nombreux compilateurs incluent également une phase d'analyse sémantique
• Les types de données sont vérifiés et des conversions de type sont effectuées si nécessaire.
• Phase d'ajout : l'optimisation est utilisée pour produire un code objet efficace.
• Génération de code : le compilateur produit
Conception de compilateurs : 8
Théorie, outils
• une forme intermédiaire, connue sous le nom de byte code. Le cas du compilateur Java ou .Net
• Ou un code natif pour une machine particulière (code binaire exécutable)

Conception de compilateurs : 9
Théorie, outils
Techniques de mise en œuvre
• Un compilateur est un logiciel aussi
• Il doit être rédigé dans un langage
• amorçage
• un petit sous-ensemble du langage source est mis en œuvre et utilisé pour
compiler un compilateur pour le langage source complet, écrit dans le
langage source lui-même.
• Compilation croisée
• un compilateur existant peut être utilisé pour mettre en œuvre un compilateur pour un
nouvel ordinateur.
• La forme intermédiaire permet de réduire la charge de travail de l'auteur du
compilateur.
• un langage intermédiaire entre le langage de haut niveau de la source et la machine
langue
Conception de compilateurs : 10
Théorie, outils
• il suffit d'un seul traducteur pour chaque langue de haut niveau vers la forme
intermédiaire et d'un seul traducteur (ou interprète) pour la forme intermédiaire
sur chaque ordinateur

Conception de compilateurs : 11
Théorie, outils
Quelques applications des techniques de
compilation
• Internet
• Navigateur web : traduire le texte HTML en objets graphiques
• Interprète PHP
• Systèmes de gestion de bases de données (SGBD)
• Interprétation et exécution des instructions SQL
• Recherche
• Recherche avancée dans les éditeurs de texte, les logiciels de bureautique, etc.
• Cadre XML/JSON
• Encodage/décodage d'un flux de texte en structure XML
• Traduire un message SOAP en une invocation d'objet
• Réseau, Capteurs
Conception de compilateurs : 12
Théorie, outils
• Décodage du flux de données

Conception de compilateurs : 13
Théorie, outils
Analyse lexicale
la décomposition de l'entrée en mots individuels ou "jetons"
Le langage formel et la théorie des automates comme outils de conception des scanners

Conception de compilateurs : 14
Théorie, outils
Analyse lexicale
• Que voulons-nous faire
? Exemple :
si (i == j)
Z=0;
autre
Z=1;
• L'entrée est une simple chaîne de caractères :
\Nsi (i == j)\Nt\tz = 0;\Ntelse\Nt\Nt\Ntz = 1 ;
• Objectif : diviser la chaîne d'entrée en sous-chaînes
✓ - Lorsque les sous-chaînes sont des jetons
Conception de compilateurs : 15
Théorie, outils
Jeton (définition et spécification)
• Définition : Une catégorie syntaxique
• En français ou en anglais : • Classer les sous-chaînes de programme en fonction
de leur rôle
• nom, verbe, adjectif, ... • Le résultat de l'analyse lexicale est un flux de tokens
• Dans un langage de programmation : ...
• Identificateur, Entier, Mot-clé, Espace blanc, ... • . . qui est l'entrée de l'analyseur syntaxique
• L'analyseur s'appuie sur les distinctions de jetons
• Spécification : Les jetons correspondent -àUndes ensembles
identificateur est traitéde chaînesd'un
différemment demot
clé
caractères.
• Identifiant : chaînes de lettres ou de chiffres commençant par une lettre.
• Entier : une chaîne de chiffres non vide
• Mot-clé : "else" ou "if" ou "begin" ou ...
• Espace blanc : une séquence non vide de blancs, de nouvelles lignes et de
Conception de compilateurs : 16
Théorie, outils
tabulations.

Conception de compilateurs : 17
Théorie, outils
 Conception d'un scanner
• Définir un ensemble fini de jetons
✓ - Les jetons décrivent tous les éléments d'intérêt
✓ - Le choix des jetons dépend de la langue et de la conception de l'analyseur
syntaxique.
• Exemple
• \Nsi (i == j)\Nt\tz = 0;\Ntelse\Nt\Nt\Ntz = 1 ;
• Jetons utiles pour cette expression : Entier, Mot-clé, Relation,
Identifiant, Espace blanc, (, ), =, ;
• Remarque : ( ) = ; sont des jetons et non des caractères.
• Décrire les chaînes de caractères qui
appartiennent à chaque jeton
Conception de compilateurs : 18
Théorie, outils
Mise en œuvre du scanner
• Une mise en œuvre doit faire deux choses :
1. Reconnaître les sous-chaînes correspondant aux tokens
2. Retourne la valeur ou le lexème du jeton
✓ Le lexème est la chaîne de caractères
• Le lexateur se débarrasse généralement des jetons "inintéressants" qui ne
contribuent pas à l'amélioration de la qualité de l'information.
l'analyse syntaxique.
• Exemples : Espace blanc, commentaires
Nous avons encore besoin de ❑ Il existe plusieurs formalismes pour spécifier les jetons
✓ Une façon de décrire les lexèmes de chaque ❑ Les langues régulières sont les plus populaires
jeton – Une théorie simple et utile
✓ Une façon de résoudre les ambiguïtés – Facile à comprendre
-Si deux variables i et f ? – Des mises en œuvre efficaces
-Est == deux signes égaux = = ? Conception de compilateurs :
Théorie, outils
19
 Langage formel Exemples de langues de l'alphabet {0, 1}
L1={0,10,1011}
L2= { } ou ∅
• Un alphabet Σ est un ensemble de symboles
L3 = {ε, 0,00,000,0000,00000,... }
L4 : L'ensemble de toutes les chaînes de zéros et de
• Exemple : alphabet binaire ={0, 1} uns ayant
un nombre pair de 1 (ensemble infini)
• Une chaîne de caractères est une liste de caractères
issus d'un alphabet donné.
• l'ordre dans lequel les caractères sont énumérés est important
• Exemple : "101" est différent de "110"
• ε désigne la chaîne nulle (chaîne de 0 caractère)
• Un langage (formel) est un ensemble de chaînes de caractères issues d'un
alphabet donné
• Problème : Comment pouvons-nous spécifier les chaînes de caractères dans
Conception de compilateurs : 20
Théorie, outils
un système infini (ou très grand) ?
langue ?

Conception de compilateurs : 21
Théorie, outils
Langues régulières
• Les langues sont des ensembles de chaînes de caractères.
• Nécessité d'une notation pour spécifier les ensembles souhaités
• La notation standard pour les langages réguliers est l'expression régulière.

Exemple
Alphabet = caractères anglais/français Langue
= phrases anglaises/françaises
Toute chaîne de caractères anglais (resp. français) n'est pas forcément une
phrase anglaise (resp. française).
Conception de compilateurs : 22
Théorie, outils
 Expressions
régulières • Définition Les expressions
régulières sur Σ sont le
• Expressions régulières atomiques plus petit ensemble
• Caractère unique "c" ={"c"} d'expressions comprenant
• Epsilon ε = {""} :
• Expressions régulières • ε
composées • c" où c∈ Σ
• 𝐴 + 𝐵 où A, B sont des rexp sur Σ
• Union : 𝐴 + 𝐵 = 𝑠| 𝑠 ∈ 𝐴 𝑜𝑟 𝑠 ∈ 𝐵
• 𝐴𝐵 où A, B sont des rexp sur Σ
• Concaténation : 𝐴𝐵 = 𝑎𝑏| 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵
• Itération : 𝐴∗ = ‫≥𝑖ڂ‬0 𝐴 • ∗
𝐴où A est un rexp sur Σ
Sémantiq - 𝐿 𝐴𝐵 = 𝐿 𝐴 . 𝐿 𝐵 = 𝑢𝑣|𝑢 ∈ 𝐴 𝑎𝑛𝑑 𝑣 ∈ 𝐵
ue
- L 𝜀 = "" - 𝐿 𝐴∗ = ‫≥𝑖ڂ‬0 𝐿(𝐴 )𝑖
- L ′c′ ={"c"}
- L𝐴+𝐵 =𝐿𝐴 ∪𝐿𝐵
Exemples
• Entier : une chaîne de chiffres non vide
• 𝑑𝑖𝑔𝑖𝑡 =′ 0′ +′ 1′ +′ 2′ +′ 3′ +′ 4′ +′ 5′ +′ 6′ +′ 7′ +′ 8′ +′ 9′
• 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 = 𝑑𝑖𝑔𝑖𝑡 𝑑𝑖𝑔𝑖𝑡∗
• Abréviation : 𝐴+ = 𝐴 +𝐴∗
• Identifiant : chaîne de lettres ou de chiffres commençant par une lettre.
• lettre = 'A' + . . . + 'Z' + 'a' + . . . +'z'
• identifiant = lettre (lettre + chiffre)*
• Est-ce que (lettre* + chiffre*) est la même chose ?
• Adresses électroniques
• Σ = 𝑙𝑒𝑡𝑡𝑒𝑟𝑠 ∪ . , @
• n𝑎𝑚𝑒 = 𝑙𝑒𝑡𝑡𝑒𝑟+
• 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = nom′′name′.′name′.′name
Conception de compilateurs : 19
Théorie, outils
Notation
• La notation des expressions régulières varie
• Union : A | B≡ A + B
• Option : A + ε≡ A ?
• Portée : 'a'+'b'+...+'z '≡ [a-z]
• Gamme exclue :
• complément de [a-z ]≡ [^a-z]

Conception de compilateurs : 20
Théorie, outils
Notation des expressions régulières
• un caractère ordinaire se suffit à lui-même
•𝜖 la chaîne vide
• 𝑀|𝑁 alternance, en choisissant parmi M ou N
• 𝑀 ∙ 𝑁 (ou 𝑀𝑁 ) concaténation, un M suivi d'un N
•∗ 𝑀répétition zéro ou plusieurs fois
•+ 𝑀répétition une ou plusieurs fois
•? 𝑀facultatif, zéro ou une occurrence de M
• Alternance de jeux de caractères [a-zA-Z]
• Un point représente n'importe quel caractère de signe, à
l'exception de la nouvelle ligne.
Conception de compilateurs : 21
Théorie, outils
Ambiguïté des expressions régulières
• Ces règles sont quelque peu ambiguës.
• Est-ce que if8 correspond à un identifiant unique ou aux deux jetons if et 8 ?
• Correspondance la plus longue : La sous-chaîne initiale la plus
longue de l'entrée qui peut correspondre à une expression
régulière est prise comme élément suivant.
• Priorité de la règle : Pour une sous-chaîne initiale particulière la plus
longue, la première
l'expression régulière qui peut correspondre détermine son type de jeton
• L'ordre dans lequel les règles d'expression régulière sont écrites est important

Conception de compilateurs : 22
Théorie, outils
Mise en œuvre des expressions régulières
• Spécification de la structure lexicale à l'aide d'expressions régulières
• Les expressions régulières décrivent de nombreux langages utiles
Etant donné une chaîne de
• Les langages réguliers sont une spécification linguistique caractères s et un rexp R, est
• Nous avons encore besoin d'une implémentation
s∈
• Mise en œuvre des expressions régulières = Automates finis
L(R) ?
• - Automates finis déterministes (AFD)
• - Automates finis non déterministes (AFN)

RegExp NFA DFA Tables

Conception de compilateurs : Théorie, outils 23
Machines à états finis (FSM)
• L'étude des machines à états finis (théoriques) est appelée théorie des automates.
• automate n'est qu'un autre mot pour machine
• Un automate 𝐴 = Σ, 𝑄, 𝑑, 𝐹, 𝛿 où
• Σ 𝑖𝑠 𝑡ℎ𝑒 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡
• 𝑄 𝑖𝑠 𝑡ℎ𝑒 𝑓𝑖𝑛𝑖𝑡𝑒 𝑠𝑒𝑡 𝑜𝑓
𝑠𝑡𝑎𝑡𝑒𝑠
• 𝑑 ∈ 𝑄 𝑖𝑠 𝑡ℎ𝑒 𝑖𝑛𝑖𝑡𝑖𝑎𝑙 𝑜𝑟 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒
• 𝐹 ⊆ 𝑄 𝑖𝑠 𝑡ℎ𝑒 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑜𝑟 𝑎𝑐𝑐𝑒𝑝𝑡𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑒𝑠
• 𝛿 : 𝑄 × Σ → 𝑄 𝑖𝑠 𝑡ℎ𝑒 𝑠𝑡𝑎𝑡𝑒 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛
• une chaîne est acceptée lorsque l'automate atteint un état final après que
toute la chaîne d'entrée a été lue.
• Le langage reconnu par un automate est l'ensemble des chaînes de caractères qu'il
accepte.
Conception de compilateurs : 24
Théorie, outils
• 𝐿 𝐴 = 𝑢 ∈ Σ∗ |∃𝑞 ∈ 𝐹, 𝛿 ∗ 𝑑, 𝑢= 𝑞

Conception de compilateurs : 25
Théorie, outils
Graphes d'état des automates finis et exemples
Un automate fini qui n'accepte que des "1"

Un état 1

L'état initial Automate fini acceptant un nombre

quelconque de 1 suivis d'un seul 0.
• Alphabet : {0,1}

Un état 1
d'acceptation
0
a

Une transition
Conception de compilateurs : 26
Théorie, outils
 Représentations

Représentation par diagramme d'état Représentation du tableau

0 1
q0 q0 q1
q1 q1 q0
• Chaque état de la machine est représenté par un cercle
Exemple : Vérificateur de parité paire • La fonction de transition est représentée par des arcs
étiquetés par
Cette machine accepte toute chaîne de les symboles d'entrée menant d'un état à un autre.
zéros et de uns qui contient un nombre • Les états acceptants sont des doubles cercles
pair de uns (ce qui inclut la chaîne • L'état de départ est indiqué par un arc sans état à son
nulle). extrémité source (queue)
CoConception de compilateurs 26
: Théorie, outils
Exercices
• Présenter un automate à états finis, sous forme de graphe d'états ou de
tableau, pour
chacune des langues suivantes (dans chaque cas, l'alphabet d'entrée est
{0,1}) :
1. Chaînes de caractères contenant un nombre impair de zéros
2. Chaînes de caractères contenant trois "1" consécutifs
3. Chaînes contenant exactement trois zéros
4. Chaînes de caractères contenant un nombre impair de zéros et
un nombre pair de uns.

Conception de compilateurs : 27
Théorie, outils
Solutions

Conception de compilateurs : 28
Théorie, outils
Automates finis
• Un automate fini non déterministe (AFN) est un automate qui
dispose d'un choix d'arêtes - étiquetées avec le même symbole - à
suivre à partir d'un état.
• Il peut y avoir plusieurs transitions pour une entrée dans un état donné.
• Peut avoir des mouvements ε
• Dans un automate fini déterministe (AFD), deux arêtes partant du
même état ne sont pas étiquetées avec le même symbole
• Une transition par entrée et par état
• Pas de mouvements ε
• D'après la représentation du tableau, il est plus facile de s'assurer que la machine
est
complètement spécifié et déterministe
• Il doit y avoir exactement une entrée dans chaque cellule du tableau.
• Les automates finis sont utilisés pour mettre en œuvre le jeton lexical
Conception de compilateurs : 29
Théorie, outils
sous la forme d'un programme informatique

Conception de compilateurs : 30
Théorie, outils
NFA vs. DFA
• Pour un langage donné, la NFA peut être plus simple que la DFA.
• Les NFAs et les DFAs reconnaissent le même ensemble de
langages (langages réguliers)
• Les DFA sont plus rapides à exécuter
• Il n'y a pas de choix à faire Un automate fini acceptant tout
• L'AFD peut être exponentiellement plus grande que l'AFN.
nombre binaire multiple de 4
• Alphabet : {0,1}
1 1
0
0 0 0 0
A B C A B C
1
1
0 NFA DFAE
Conception de compilateurs : 31
Théorie, outils
Expressions régulières et automates finis
NFA
Pour chaque type de rexp, définir une NFA
- Notation : NFA pour rexp M
Régulière DFAE
expression

Lexique Mise en œuvre

spécification de la DFA à l'aide d'un M
tableau

Conception de compilateurs : 32
Théorie, outils
 Expressions régulières vers NFA (1)
Pour l'entrée a Pour l'entrée A+B

a ε A ε

ε B ε
Pour ε

ε ou
Pour l'entrée A*

ε
Pour l'entrée AB
ε ε
ε A
A B

ε
Conception de compilateurs : 33
Théorie, outils
Exemple de conversion RegExp -> NFA
Considérons l'expression régulière (1+0)*1
(1+0)*1
(1+0)*

1
(1+0) Conception de compilateurs : Théorie, outils 33
Transformation d'une AFN en AFD
• Définition (𝜖-closure)
• Soit S un ensemble d'états. La fermeture ( S ) est l'ensemble des états qui peuvent être atteints à
partir d'un état dans S
sans consommer aucune entrée, c'est-à-dire en passant uniquement par les arêtes 𝜖
• 𝐜𝐥𝐨𝐬𝐮𝐫𝐞 𝑆 est le plus petit ensemble T tel que 𝑇 = 𝑠∈𝑇 𝑆 ∪‫𝑠 𝐞𝐠𝐝𝐞 ڂ‬,
• Calcul de T
• 𝑇←𝑆
• 𝐫𝐞𝐩𝐞𝐚𝐭 𝑇 ′ ← 𝑇
• 𝑇 = 𝑇′ ∪ ‫𝑇∈𝑠ڂ‬′ 𝐞𝐝𝐠𝐞 𝑠,
• 𝐮𝐧𝐭𝐢𝐥 𝑇 = 𝑇′
• Algorithme de conversion de la NFA en DFA
• État initial : closure({d}) où d est l'état initial de la NFA
• La transition de S avec un symbole c : δ 𝑆, 𝑐 = ‫𝑠(𝛿 𝑒𝑟𝑢𝑠𝑜𝑙𝑐 ∈𝑠ڂ‬, 𝑐)
• S est un état final si S ∩ 𝐹 ≠ ∅
Conception de compilateurs : 34
Théorie, outils
Exemple de conversion NFA -> DFA
Considérons l'expression régulière (1+0)*1

1
1
0 1

0
0

Conception de compilateurs : 35
Théorie, outils
Exemple
• ID
• NUM (nombre entier ou décimal)
• VRAI
• SI

Écrivez l'expression régulière

pour chaque token, puis
dessinez la NFA
correspondante.

Conception de compilateurs : 36
Théorie, outils
Exercices
• Dans le livre "De l'appel", pages 34-35
• Exercice 2.1 : écrire une expression régulière
• De la DFA à l'expression régulière
• Exercice 2.4 : convertir une expression régulière en NFA
• Exercice 2.5 : conversion de l'AFN en AFD
• Exercice 2.6 : algorithme de minimisation d'un DFA

Conception de compilateurs : 37
Théorie, outils
Analyse syntaxique
Syntaxe : la façon dont les mots sont assemblés pour former des expressions, des
clauses ou des phrases.
Pour l'analyse syntaxique, les chaînes sont des programmes source, les symboles sont des
jetons lexicaux, et les symboles
alphabet est l'ensemble des types de jetons renvoyés par l'analyseur lexical
Conception de compilateurs : 38
Théorie, outils
Grammaires sans contexte
• Nous avons déjà vu deux façons de spécifier formellement un langage : les
langages réguliers et les langages de base.
les expressions et les machines à états finis.
• Nous allons maintenant définir une troisième façon de spécifier les langues en
utilisant une grammaire
• Une grammaire est une liste de règles qui peuvent être utilisées pour
produire ou générer toutes les chaînes de caractères d'un langage, et
qui ne génèrent pas de chaînes de caractères qui ne font pas partie du
langage.
• Définition formelle : Une grammaire sans où
contexte 𝐺 = Σ, 𝑉, 𝑅, 𝑆
• Σ est l'alphabet d'entrée, un ensemble fini de caractères, les symboles d'entrée.
• V est un ensemble fini de symboles, distincts des symboles terminaux, appelés non
terminaux.
Conception de compilateurs : 39
Théorie, outils
 symboles
• 𝑆 ∈ 𝑉 est le nonterminal de départ ou Axiome.
• 𝑅 ⊆ 𝑉 × Σ ∪ 𝑉 ∗ Une liste finie de règles de réécriture, également appelées productions,
qui définissent
comment les chaînes de caractères du langage peuvent être générées. Chacune de ces règles
de réécriture est de type
forme 𝐴 → 𝛽, où 𝐴 ∈ 𝑉, 𝛽 ∈ Σ ∪ 𝑉 ∗.

Conception de compilateurs : 40
Théorie, outils
Dérivations et arbres d'analyse
• Une dérivation est la substitution d'un non-terminal par le côté droit (RHS)
d'une production.
• Une dérivation la plus à gauche est une dérivation dans laquelle le symbole non
terminal le plus à gauche est toujours celui qui est développé.
• une dérivation la plus à droite est une dérivation dans laquelle le nonterminal
le plus à droite est toujours le prochain à être développé
• Le langage spécifié par la grammaire G est L(G) défini comme suit :
• 𝐿 𝐺 = 𝑢 ∈ Σ ∗ | 𝑆 ⟹∗ 𝑢
• Un arbre d'analyse est créé en connectant chaque symbole d'une dérivation à celui de
l'arbre d'analyse.
dont il est issu
• Une grammaire est ambiguë si elle peut dériver une phrase avec deux arbres d'analyse
différents
Conception de compilateurs : 41
Théorie, outils
• L'ambiguïté peut généralement être éliminée en transformant la grammaire.

Conception de compilateurs : 42
Théorie, outils
 S

Exemples
0 S 0

0 S 0
Grammaire Exemple de dérivation
1 S 1
𝑆 → 0𝑆0 1𝑆1 0|1 𝑆 ⇒ 0𝑆0 ⟹ 00𝑆00 ⟹ 001𝑆100 ⟹ 0010100 0010100 ∈ 𝐿(𝐺)
0
𝑆 → 𝐴𝑆𝐵
𝑆 ⇒ 𝐴𝑆𝐵 ⟹ 𝐴𝐴𝑆𝐵𝐵 ⇒ 𝑎𝐴𝑆𝐵𝐵 ⇒ 𝑎𝑎𝑆𝐵𝐵 ⇒ 𝑎𝑎𝐵𝐵 ⇒ 𝑎𝑎𝑏𝐵 ⟹ 𝑎𝑎𝑏𝑏 𝑎𝑎𝑏𝑏 ∈ 𝐿(𝐺2)
𝑆→𝜖
𝐴→𝑎 𝐿 𝐺2 = 𝑛𝑎𝑏 𝑛 , 𝑛 ∈
𝐵→𝑏 ℕ

Étant donné la grammaire

𝐸→𝐸+𝐸 1. Montrer que le mot 1-2-3 est dans le langage généré par cette grammaire.
𝐸→𝐸-𝐸 2. Dessinez deux arbres d'analyse différents pour le mot donné. Concluez que cette grammaire est
𝐸→𝐸∗𝐸 ambiguë.
𝐸 → 𝐸/𝐸 3. Faites le même exercice avec le mot 1+2*3
𝐸 → 𝑛𝑢𝑚
𝐸 → 𝑖𝑑

Conception de compilateurs : 43
Théorie, outils
𝐸→𝐸+𝐸 Dérivation gauche
𝐸→𝐸-𝐸
𝐸→𝐸∗𝐸 E=> E-E=> num-E=> num-E-E=> num-num-E=> num-num-num
𝐸→𝐸/𝐸
𝐸→𝑛𝑢𝑚 Dérivation droite
𝐸→𝑖𝑑
E=> E-E=> E-num=> E-E-num=> E-num-num=> num-num-num

E E
E - E E - E

Num E - E E - ENumérique
ériqu (3)
e
(1)
Numé Numérique Numé Num
Classes de grammaires
• La classification de Noam Chomsky (linguiste, 1959) propose des classes de grammaires en
fonction de leur complexité.
0. Sans restriction : Une grammaire non restreinte est une grammaire dans laquelle il n'y a pas de
restrictions sur les règles de réécriture.
1. Sensible au contexte : Une grammaire sensible au contexte est une grammaire dans laquelle chaque règle
doit être de la forme
𝛼𝐴𝛾 → 𝛼𝛽𝛾
où chaque α, β, γ est une chaîne quelconque de terminaux et de non terminaux,
et A représente un non terminal
2. Sans contexte : Une grammaire sans contexte est une grammaire dans laquelle chaque règle doit être de
la forme : A → α
3. Linéaire droite : Une grammaire linéaire droite est une grammaire dans laquelle chaque règle est de la
forme :
𝐴 → 𝑎𝐵|𝜀 où A et B représentent des non-terminaux, et a représente un terminal.
Avis
Conception de compilateurs : 43
Théorie, outils
• Les grammaires linéaires droites peuvent être utilisées pour définir des éléments lexicaux tels que des identificateurs,
des constantes et des mots-clés.
• 𝑐𝑙𝑎𝑠𝑠(3) ⊂ 𝑐𝑙𝑎𝑠𝑠(2) ⊂ 𝑐𝑙𝑎𝑠𝑠(1) ⊂ 𝑐𝑙𝑎𝑠𝑠(0)

Conception de compilateurs : 44
Théorie, outils
Exercices
• Ecrire une grammaire non ambiguë qui engendre les
langages suivants :
• (a). Parenthèses et crochets équilibrés. Exemple : ([[](()[()][])])
• (b). les palindromes sur l'alphabet {a,b}
• Montrer que l'image miroir d'un langage algébrique est algébrique.
• Montrer que la famille des langages algébriques est close par
les opérations rationnelles (union, concaténation et itération).
• Remarque : Elle n'est par contre pas close par intersection, ni par passage au
complémentaire.
• Montrer que la grammaire S→SS + aSb + 1 est ambiguë, et construire
une grammaire non ambiguë qui reconnait le même langage.
Conception de compilateurs : 45
Théorie, outils
Exercices
• Écrivez une grammaire non ambiguë pour chacune des langues suivantes.
a. Palindromes sur l'alphabet {a, b} (chaînes de caractères
identiques à l'envers et à l'endroit).
b. Les chaînes de caractères qui correspondent à l'expression régulière a∗b∗
c. Les chaînes de caractères qui correspondent à l'expression
régulière a∗b∗ et qui ont plus de a que de b.
d. Parenthèses et crochets équilibrés. Exemple : ([[](()[()][])])
• Montrez que la grammaire 𝑆 → 𝑆𝑆|𝑎𝑆𝑏|𝜀 est ambiguë.
Construisez ensuite une grammaire non ambiguë qui reconnaisse
la même langue.
Conception de compilateurs : 46
Théorie, outils
Exercices
• Objectif : convertir un automate non fini (ANF) en une
grammaire sans contexte.
• Donnez une grammaire linéaire droite pour chacun des langages
de l'exemple de problème.
1. Chaînes de caractères contenant un nombre impair de zéros
2. Chaînes de caractères contenant trois "1" consécutifs
3. Chaînes contenant exactement trois zéros
4. Chaînes de caractères contenant un nombre impair de zéros et
un nombre pair de uns.

Conception de compilateurs : 47
Théorie, outils
Réponse : Algorithme général
• Algorithme de conversion d'une DFA en une grammaire linéaire droite
1. Associer une variable 𝑋𝑖 à chaque état i
𝑎
2. Pour chaque transition 𝑖 → 𝑗, ajouter une nouvelle production 𝑋𝑖 → 𝑎𝑋𝑗 à
l'ensemble
de règles
3. Pour chaque état final k, ajouter 𝑋𝑘 → 𝜀 à l'ensemble des règles de
production.
4. le non terminal associé à l'état initial est le symbole de départ
(axiome)
Conception de compilateurs : 48
Théorie, outils
Problème d'analyse
• Étant donné une grammaire et une chaîne d'entrée, déterminer si la
chaîne est dans le langage de la grammaire et, le cas échéant,
déterminer sa structure.
• Classification des algorithmes d'analyse syntaxique
• fait référence à la séquence dans laquelle un arbre de dérivation est construit ou
parcouru
• Deux approches : soit descendante, soit ascendante
• algorithme d'analyse descendante, les règles de grammaire sont
appliquées dans un ordre qui correspond à une direction générale
descendante dans l'arbre de dérivation
• L'algorithme d'analyse ascendante part du bas de l'arbre de
Conception de compilateurs : 49
Théorie, outils
dérivation et applique les règles de grammaire (en sens
inverse).

Conception de compilateurs : 50
Théorie, outils
Analyse descendante

Conception de compilateurs : 51
Théorie, outils
Présentation
• Marqueur de fin de dossier
• Les analyseurs doivent lire non seulement les symboles terminaux, mais aussi le
marqueur de fin de fichier.
• Le symbole $ est généralement utilisé pour représenter la fin d'un fichier.
• La grammaire donnée est augmentée d'un nouveau symbole de début S' et d'un
nouveau symbole de fin S'.
production 𝑆′ → 𝑆$
• Calculer les ensembles FIRST et FOLLOW pour chaque non-terminal.
• FIRST (γ ) est l'ensemble des terminaux qui peuvent commencer les chaînes dérivées
de γ
• FOLLOW ( X ) est l'ensemble des terminaux qui peuvent suivre immédiatement X
Conception de compilateurs : 52
Théorie, outils
• Construire la table d'analyse

Conception de compilateurs : 53
Théorie, outils
Calcul itératif de FIRST
• si X est un symbole terminal, FIRST(X)={X}
• Si 𝑋 → 𝜖 est une production, 𝑋 ⊇ {𝜖}
𝐹𝐼𝑅𝑆𝑇
• Si 𝑋 → 𝑌1 𝑌 2 𝑌 3 ... 𝑌𝑛 est une
production,
• 𝐹𝐼𝑅𝑆𝑇 𝑋 = 𝐹𝐼𝑅𝑆𝑇 𝑌1
• ∪ 𝐹𝐼𝑅𝑆𝑇 𝑌2 𝑖𝑓 𝜖 ∈ 𝐹𝐼𝑅𝑆𝑇 𝑌1
• ∪ 𝐹𝐼𝑅𝑆𝑇 𝑌3 𝑖𝑓 𝜖 ∈ 𝐹𝐼𝑅𝑆𝑇𝑌2
• ....
• ∪𝐹𝐼𝑅𝑆𝑇 𝑌𝑛 𝑖𝑓 𝜖 ∈ 𝐹𝐼𝑅𝑆𝑇 𝑌𝑛-1
• ∪ 𝜖 𝑖𝑓𝜖 ∈ 𝐹𝐼𝑅𝑆𝑇
Conception de compilateurs : 54
Théorie, outils
 𝑌𝑛

• trouver l'union des ensembles First(x) pour chaque symbole du côté droit d'une
règle,
mais s'arrête lorsqu'il atteint un symbole non annulable

Conception de compilateurs : 55
Théorie, outils
Calcul des ensembles FOLLOW
• Ajouter le marqueur EOF $ dans FOLLOW(S) où S est l'axiome
• 𝑖𝑓 𝐴 → 𝛼𝐵𝛽 est une production où 𝐴, 𝐵 ∈ 𝑉 𝑎𝑛𝑑 𝛼, 𝛽 ∈ (𝑉 ∪ Σ)∗
alors 𝐵 𝐹𝑂𝐿𝐿𝑂𝑊⊇ 𝛽 𝐹𝐼𝑅𝑆𝑇-
𝜖
• 𝑖𝑓 𝐴 → 𝛼 𝐵 est une production où 𝐴, 𝐵 ∈ 𝑉 𝑎𝑛𝑑 𝛼 ∈ (𝑉 ∪ Σ)∗ alors
𝐹𝑂𝐿𝐿𝑂𝑊⊇ 𝐵 𝐹𝑂𝐿𝐿𝑂𝑊 𝐴
• 𝑖𝑓 𝐴 → 𝛼𝐵𝛽 et 𝐹𝐼𝑅𝑆𝑇 𝛽 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝜖 alors 𝐹𝑂𝐿𝐿𝑂𝑊𝐵 ⊇
𝐹𝑂𝐿𝐿𝑂𝑊 𝐴

Conception de compilateurs : 56
Théorie, outils
Construction du tableau d'analyse syntaxique
• Le tableau d'analyse prédictive est un tableau à deux dimensions dans lequel
• Les lignes sont indexées par des nonterminaux
• Les colonnes sont indexées par les terminaux
• Les cellules contiennent des règles de production
• Les tables d'analyse syntaxique codent les informations nécessaires à la
mise en œuvre d'une analyse syntaxique prédictive
• Algorithme (Comment remplir le tableau)
• Inscrire la production X → γ à la ligne X, colonne T du tableau pour chaque T ∈ FIRST(γ)
• si γ est nullable, inscrire la production à la ligne X, colonne T pour chaque T ∈ FOLLOW(X) .
• Une grammaire est LL(1) si sa table d'analyse prédictive ne contient
pas d'entrées dupliquées.
• LL(1) est l'abréviation de left-to-right parse, leftmost-derivation, 1-symbol lookahead (analyse
syntaxique de gauche à droite, dérivation la plus à gauche).

Conception de compilateurs : 57
Théorie, outils
 Exemple
S → ABc 1. First(ABc) = First(A) U First(B) = {b,c} (car A est
nullable)
A → bA 2. Premier(bA) = {b}
A→ε 3. Premier(ε) = {ε}
B→c 4. Premier(c) = {c}

Premier(S) = {b,c} 1. Follow(S)={$}

Premier(A) = {b, ε} 2. Suivre(A) =Premier(B)={c}
Premier(B) = {c} 3. Suivre(B)=Premier(c) ={c}
Premier(b) = {b} b c $
First(c) = {c} S S → ABc S → ABc
A A → bA A→
𝐿𝐺 = {𝑏 𝑐 , 𝑛 ≥ 1}
𝑛 2
B B→c
Conception de compilateurs : 58
Théorie, outils
 Exercice : construire la table d'analyse LL(1)
⎧S → Ab a AA
⎪
⎨ A → Sa Ac B
⎪
⎩ B → Sd

Conception de compilateurs : 59
Théorie, outils
Récursion à gauche
• Considérons les deux productions E → E + T et E → T
• La règle 1st se présente sous la forme suivante : A → Aa
• Cette propriété est connue sous le nom de récursivité gauche
• Théorème : Les grammaires avec récursion à gauche ne peuvent pas être LL(1)
• Éliminer la récursivité gauche
ቊ𝐴 → 𝐴𝛼
• La règle incriminée peut se présenter sous la forme suivante :
𝐴→𝛽
• dans laquelle nous supposons que β est une chaîne de terminaux et de non terminaux qui
ne commence pas par un A
• Éliminez la récursion gauche en introduisant un nouveau nonterminal, R, et en réécrivant le
𝐴 → 𝛽𝑅
règles comme :
ቊ𝑅 → 𝛼𝑅|𝜀
• Théorème : Les règles résultantes dérivent les mêmes chaînes de
caractères que les productions originales.
Conception de compilateurs : 60
Théorie, outils
Récursion à gauche
• Définition : Une grammaire est récursive à gauche si elle contient un non-
terminal A tel qu'il existe une dérivation 𝐴 →+ 𝐴𝛼 où 𝛼 est une chaîne
quelconque.
𝑆 → 𝐴𝑎|𝑏
• Exemple ቊ
𝐴 → 𝐴𝑐|𝑆𝑑|𝜀
• Le non terminal S est récursif à gauche puisque 𝑆 → 𝐴𝑎 → 𝑆𝑑𝑎
• Élimination de la récursivité gauche

Conception de compilateurs : 61
Théorie, outils
Ordonner les non terminaux 𝐴1, 𝐴2, ... , 𝐴𝑛
Pour i=1 à n
pour j=1 à i-1
remplacer chaque production 𝐴𝑖 → 𝐴𝑗𝛼 𝑤ℎ𝑒𝑟𝑒 𝐴𝑗 → 𝛽1| ... |𝛽𝑝 par 𝐴𝑖 → 𝛽1𝛼| ...
|𝛽𝑝𝛼
fin pour
éliminer la récursion immédiate à gauche sur les productions 𝐴𝑖
Fin de la période

Conception de compilateurs : 62
Théorie, outils
Exemple
• Commande S, A ቊ𝐴′ →
𝑐𝐴|𝑎𝑑𝐴|𝜀′
• i=1 pas de récursion immédiate à gauche
dans 𝑆 →
𝐴𝑎|𝑏
• i=2 et j=1 remplacer
𝑆 𝑏𝑦 𝑟𝑒𝑠𝑝𝑒𝑐𝑡𝑖𝑣𝑒𝑙𝑦 𝐴𝑎 𝑎𝑛𝑑 𝑑 𝑖𝑛 𝐴 → 𝑆𝑑,
nous obtenons 𝐴 → 𝐴𝑐 𝐴𝑎𝑑 𝑏𝑑|𝜀
• Éliminer la récursion immédiate à
gauche
𝐴 → 𝑏𝑑𝐴′ |𝐴′
Conception de compilateurs : 63
Théorie, outils
• La grammaire résultante est
𝑆 → 𝐴𝑎|𝑏
൞𝐴 → 𝑏𝑑𝐴 |𝐴′′
′ 𝐴→ 𝑐𝐴 |𝑎𝑑𝐴 |𝜀′′

Conception de compilateurs : 64
Théorie, outils
Affacturage à gauche
• Une grammaire n'est pas facteur de gauche lorsque les mêmes
nonterminaux commencent par les mêmes symboles.
• Théorème : une grammaire qui n'est pas à facteur gauche ne peut pas être
LL(1)
• Facteur gauche une grammaire
• Prenez les terminaisons autorisées et créez un nouveau non terminal pour les
représenter
• Remplacer la production 𝐴 → 𝛼𝛽1 ... 𝛼𝛽𝑛 𝛾1 ... |𝛾𝑝 où
𝛼 ≠ 𝜖 𝑎𝑛𝑑 𝛾𝑖 ne commence pas 𝑤𝑖𝑡ℎ 𝛼, avec les deux règles :
• 𝐴 → 𝛼𝐴′ 𝛾1 ... |𝛾𝑝
• 𝐴′ → 𝛽1 ... 𝛽𝑛
• Exemple
Conception de compilateurs : Théorie, outils 59
Exercices
• Montrez comment éliminer la récursivité gauche de chacune des
grammaires présentées ci-dessous :
• A → Abc|ab
• ParmList → ParmList, Parm|Parm

Conception de compilateurs : 60
Théorie, outils
Analyse ascendante

Conception de compilateurs : 61
Théorie, outils
Motivation et présentation
• La faiblesse des techniques d'analyse syntaxique LL(k)
• Prédiction de la production à utiliser, en n'ayant vu que les k premiers jetons du côté droit
• Les situations dans lesquelles il n'est pas facile d'utiliser une grammaire LL(k)
• Grammaires récursives
• Pas de facteur de gauche grammaire
• Les techniques ascendantes d'analyse LR(k) sont plus puissantes
• Reporter la décision jusqu'à ce qu'elle ait vu les jetons d'entrée correspondant à
l'ensemble du côté droit d'une production.
• Les règles de grammaire sont appliquées à l'envers
• Les arbres de dérivation sont construits, ou parcourus, de bas en haut
• LR(k) signifie left-to-right parse, rightmost-derivation, k-token lookahead.
• L indique que nous lisons les données à partir de la gauche
• R indique que nous trouvons une dérivation la plus à droite

Conception de compilateurs : 62
Théorie, outils
Moteur d'analyse LR
• L'analyseur LR effectue deux types d'actions
• Shift : Déplace le jeton d'entrée au sommet de la pile.
• Réduire : Choisissez une règle de grammaire 𝑋 → 𝛼1𝛼2 ... 𝛼𝑘 ;
• faire sortir 𝛼𝑘, ... 𝛼1 du sommet de la pile
• pousser X sur la pile.
• L'analyseur syntaxique LR utilise un DFA (automate fini déterministe).
• La DFA est appliquée à la pile
• Les arêtes de l'AFD sont étiquetées par les symboles (terminaux et non terminaux).
• Quatre types d'actions étiquettent la table de transition
• snShift into state n ;
• gnGoto état n ;
• rkRéduire par la règle k ;
• a Accepter ;

Conception de compilateurs : 63
Théorie, outils
Construction d'un DFA
• Augmenter la grammaire avec 𝑆′ → 𝑆$.
• S' est une nouvelle variable avec le symbole de départ dérivé
• Explication : l'entrée sera une phrase S complète suivie de $.
• $ est le marqueur EOF
• Un item est une règle de grammaire, combinée avec le point qui indique
une position dans son côté droit
• Exemple : 𝑆 ′ →. 𝑆$
• Un état est un ensemble d'éléments
• Les opérations de base que nous avons effectuées sur les états
consistent à considérer que I est un ensemble d'éléments et que X est
un symbole grammatical (terminal ou variable).
• 𝐶𝑙𝑜𝑠𝑢𝑟𝑒(𝐼) ajoute des éléments à un ensemble d'éléments lorsqu'il y a un point
à gauche d'un non terminal.
• 𝑔𝑜𝑡𝑜(𝐼, 𝑋) fait passer le point devant le symbole X dans tous les éléments.
Conception de compilateurs : 64
Théorie, outils
Calcul de la fermeture ′ 𝑆→ 𝑆$
𝐂𝐥𝐨𝐬𝐮𝐫𝐞 ( 𝐼 ) = 𝑆→ 𝐿
𝐫𝐞𝐩𝐞𝐚𝐭 𝑆→𝑥
𝐟𝐨𝐫 𝑎𝑛𝑦 𝑖𝑡𝑒𝑚 𝐴 → 𝛼. 𝑋 𝛽 𝑖𝑛 𝐼 𝐿→𝑆
𝐟𝐨𝐫 𝑎𝑛𝑦 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑋 → 𝛾 𝐿 → 𝐿, 𝑆
Exemples de fermeture
𝐼←𝐼∪ 𝑋→.𝛾
𝐮𝐧𝐭𝐢𝐥 𝐼 𝑑𝑜𝑒𝑠 𝑛𝑜𝑡 𝑐ℎ𝑎𝑛𝑔𝑒 𝑆→ .𝐿 𝑆 →. 𝑥
𝐫𝐞𝐭𝐮𝐫𝐧 𝐼 𝑳 →. 𝑺
𝐿 →. 𝐿, 𝑆
𝑆 →. 𝑥
𝑆 →. 𝐿
Conception de compilateurs : 65
Théorie, outils
Exécution de Goto
Exemples de goto
𝐆𝐨𝐭𝐨 ( 𝐼 , 𝑋 ) =
𝑠𝑒𝑡 𝐽 𝑡𝑜 𝑡ℎ𝑒 𝑒𝑚𝑝𝑡𝑦 𝑠𝑒𝑡 𝑆 →. 𝑥 x 𝑆 → 𝑥.
𝐟𝐨𝐫 𝑎𝑛𝑦 𝑖𝑡𝑒𝑚 𝐴 → 𝛼. 𝑋 𝛽 𝑖𝑛
𝐼
𝑎𝑑𝑑 𝐴 → 𝛼 𝑋 . 𝛽 𝑡𝑜 𝐽
𝐫𝐞𝐭𝐮𝐫𝐧 𝐶𝑙𝑜𝑠𝑢𝑟𝑒 𝐽 S 𝐿→
𝑆→ .𝐿 𝑆.
𝑳 →. 𝑺 𝑆 → 𝐿.
𝐿 →. 𝐿, 𝑆
L
𝐿 → 𝐿. , 𝑆
𝑆 →. 𝑥
𝑆 →. 𝐿
Conception de compilateurs : 66
Théorie, outils
DFA de la construction des items
1. Augmenter la grammaire avec une production auxiliaire de départ 𝑆′ → 𝑆$.
2. Soit T l'ensemble des états observés jusqu'à présent,
3. Soit E l'ensemble des arêtes (shift ou goto) trouvées jusqu'à présent.

𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑖𝑧𝑒 𝑡𝑜 𝑒𝑚𝑝𝑡𝑦
𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑖𝑧𝑒 𝑇 𝑡𝑜 { 𝑪𝒍𝒐𝒔𝒖𝒓𝒆 ({ 𝑆′ → . 𝑆$ }) }
𝒓𝒆𝒑𝒆𝒂𝒕
𝒇𝒐𝒓 𝑒𝑎𝑐ℎ 𝑠𝑡𝑎𝑡𝑒 𝐼 𝑖𝑛 𝑇
𝒇𝒐𝒓 𝑒𝑎𝑐ℎ 𝑖𝑡𝑒𝑚 𝐴 → 𝛼. 𝑋 𝛽 𝑖𝑛 𝐼
𝐥𝐞𝐭 𝐽 𝑏𝑒 𝑮𝒐𝒕𝒐 𝐼 , 𝑋
𝑇←𝑇∪ 𝐽
𝑋
𝐸←𝐸 ∪𝐼 → 𝐽
𝒖𝒏𝒕𝒊𝒍 𝐸 𝑎𝑛𝑑 𝑇 𝑑𝑖𝑑 𝑛𝑜𝑡 𝑐ℎ𝑎𝑛𝑔𝑒 𝑖𝑛 𝑡ℎ𝑖𝑠 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛
Conception de compilateurs : 67
Théorie, outils
Construction du tableau d'analyse syntaxique
• Le tableau d'analyse LR est un tableau à deux dimensions dans lequel
• Les lignes sont indexées par les états de la DFA
• Les colonnes sont indexées par les terminaux et les non terminaux
• Et les cellules contiennent l'action (shift, reduce, accept, goto)
𝑋
• Pour chaque bord 𝐼 → 𝐽
• Si X est un terminal, placer le décalage d'action J à la position (I,X) du tableau.
• si X est un non-terminal, on met goto J à la position (I,X)
• Pour chaque état I contenant un élément 𝑆 ′ → 𝑆. $
• Placez une action d'acceptation à (𝐼, $)
• Pour un état contenant un élément 𝐴 → 𝛾. (production n avec le point à la fin)
• Cas de LR(0) : mettre une action de réduction n à (𝐼, 𝑌) pour chaque jeton Y
• Cas de SLR(1) : mettre une action de réduction n à (𝐼, 𝑌) pour chaque jeton Y dans FOLLOW(A)

Conception de compilateurs : 68
Théorie, outils
Exemple
0. 𝑆′ → 𝑆$
1. 𝑆 → 𝐿 Analyse SLR(1)
2. 𝑆 → 𝑥 Tableau
3. 𝐿 → 𝑆
4. 𝐿 → 𝐿, 𝑆 ( ) X , $ S L ( ) X , $ S L
1 S3 S2 g4 1 S3 S2 g4
2 r2 r2 r2 r2 r2 2 r2 r2 r2
3 s3 s2 g7 g5 3 S3 S2 g7 g5
4 Acc Follow(S)={$ ) ,} 4 Acc
Analyse LR(0) 5 s6 s8 Follow(L)={) ,}
5 s6 s8
Tableau 6 r1 r1 r1 r1 r1 6 r1 r1 r1
7 r3 r3 r3 r3 r3 7 r3 r3
8 s3 s2 g9 8 S3 S2 g9
9 r4 r4 r4 r4 r4 Cocompi Conception : Théorie, 9 r4 r4 69
lateur outils
 Analyse d'un mot

Nous considérons le mot u= (x,x)

CoConception de 70
compilateurs : Théorie,
Limites des grammaires contextuelles
• Impossible de représenter la sémantique
• Par exemple, "toute variable utilisée dans une instruction doit être
déclarée plus tôt dans le code" ; ou "l'utilisation d'une variable doit être
conforme à son type" (vérification du type).
• Nécessité de n'autoriser que les programmes qui satisfont à certaines conditions contextuelles
• Ne peut être utilisé pour générer d'autres choses que des arbres d'analyse.
• Par exemple, que se passe-t-il si nous voulons générer un code d'assemblage pour le
programme donné ?

Conception de compilateurs : 71
Théorie, outils
Grammaires attribuées
Sémantique des langages sans contexte
Ajouter un contexte à la grammaire sans
contexte

Conception de compilateurs : 72
Théorie, outils
Vue d'ensemble
• Les grammaires d'attributs ont été développées pour la première fois par
Donald Knuth en 1968
• Un moyen de formaliser la sémantique d'un langage sans contexte.
• Leur application principale a été l'écriture de compilateurs, ils sont un outil
principalement utilisé par les implémenteurs de langages de
programmation.
• Les grammaires d'attributs peuvent remplir plusieurs fonctions utiles
pour spécifier la syntaxe et la sémantique d'un langage de
programmation.
• Une grammaire d'attributs peut être utilisée pour spécifier les
aspects contextuels de la syntaxe d'un langage, tels que la
Conception de compilateurs : 73
Théorie, outils
vérification qu'un élément a été déclaré et que l'utilisation de
l'élément est cohérente avec sa déclaration.

Conception de compilateurs : 74
Théorie, outils
Actions sémantiques
• Un compilateur doit faire plus que reconnaître si une phrase appartient
au langage d'une grammaire
• il doit faire quelque chose d'utile avec cette phrase.
• Les actions sémantiques d'un analyseur syntaxique peuvent faire des choses
utiles avec les phrases analysées.
• Les actions sémantiques sont des fragments de code de programme, écrits dans un langage
de programmation.
langage (Java, C, ...), attaché à des productions grammaticales
• Les grammaires sont étendues en introduisant des grammaires attribuées
• Chacun des terminaux et des non-terminaux peut avoir zéro ou plusieurs attributs
• zéro ou plusieurs règles de calcul des attributs sont associées à chaque règle de grammaire
• Exemples
• l'attribut d'un symbole d'entrée (un jeton lexical) peut être la partie valeur du jeton
• Gérer le type de chaque identifiant

Conception de compilateurs : 75
Théorie, outils
Syntaxe Définition dirigée
• Une définition syntaxique (SDD) relie un ensemble de règles
sémantiques à la production.
• Les terminaux et les non-terminaux ont des attributs
• Formellement, un SDD=(G, Attr, R) où
• G est une grammaire sans contexte
• Attr est un ensemble d'attributs
• R est un ensemble de règles sémantiques
• X.a désigne l'attribut a attaché au symbole X (terminal ou non
terminal)
• Si X apparaît plusieurs fois dans une production
• X0 .a est le LHS
• X1 ,..., Xn sont les RHS

Conception de compilateurs : 76
Théorie, outils
Exemple
• Considérons la grammaire G : Productions Règles sémantiques
𝑆 → 𝑎𝑆𝑏 𝑎𝑆 𝑐𝑆𝑎𝑐𝑆|𝜖 0
𝑆. 𝑛𝑏𝑎 = 𝑆 1 . 𝑛𝑏𝑎 +1
𝑆 → 𝑎𝑆𝑏
• Ecrivez les règles pour calculer 0
𝑆. 𝑛𝑏𝑐 = 𝑆 1 . 𝑛𝑏𝑐
le nombre de a et de c dans un 0
𝑆. 𝑛𝑏𝑎 = 𝑆 1 . 𝑛𝑏𝑎 +1
𝑆 → 𝑎𝑆
mot 𝑢 ∈ 0
𝑆. 𝑛𝑏𝑐 = 𝑆 1 . 𝑛𝑏𝑐
𝐿
𝐺
0
𝑆. 𝑛𝑏𝑎 = 𝑆 1 . 𝑛𝑏𝑎 + 𝑆 2 . 𝑛𝑏𝑎 +1
𝑆 → 𝑐𝑆𝑎𝑐𝑆
• Solution 0
𝑆. 𝑛𝑏𝑐 = 𝑆 1 . 𝑛𝑏𝑐 + 𝑆 2 . 𝑛𝑏𝑐 +
• Définir deux attributs 2
• nba qui contient le numéro d'un 𝑆. 𝑛𝑏𝑎 = 0
𝑆→𝜖
• nbc qui détient le nomber de c 𝑆. 𝑛𝑏𝑐 = 0

Conception de compilateurs : 77
Théorie, outils
Construire un arbre décoré

Arbre de dérivationArbre de dérivation notée (attribuée)

Conception de compilateurs : 78
Théorie, outils
Catégories d'attributs
• Soit 𝑋0 → 𝑋1 ... 𝑋𝑛 une production.
• Si la règle de calcul de l'attribut de 𝑋0 est de la forme 𝐴(𝑋0 ) =
𝑓(𝐴 𝑋1 , ... , 𝐴𝑋𝑛 )
• Attribut synthétisé
• Si la règle de calcul de l'attribut de 𝑋𝑗 est de la forme 𝐴(𝑋𝑗) =
𝑓(𝐴 𝑋0 , ... , 𝑋𝑖 , ... )
• Attribut hérité
• Les terminaux ont des attributs intrinsèques
• Valeurs lexicales fournies par l'analyseur lexical

Conception de compilateurs : 79
Théorie, outils
 Exemple d'attributs hérités
calcul du niveau d'imbrication de) dans un système de
parenthèses bien formé

Productions Règles sémantiques

𝑆′ → 𝑆 𝑆. 𝑛𝑏 = 0
1
𝑆. 𝑛𝑏 = 𝑆 0 . 𝑛𝑏 +1
𝑆 →𝑆 𝑆 2
𝑆. 𝑛𝑏 = 𝑆 0 . 𝑛𝑏
𝑆→𝜖 𝑒𝑐𝑟𝑖𝑟𝑒 𝑆. 𝑛𝑏

Conception de compilateurs : 80
Théorie, outils
Exercice
• Concevoir une grammaire attribuée pour évaluer les expressions
arithmétiques

Conception de compilateurs : 81
Théorie, outils
Productions Règles sémantiques 1. Implémentez votre
𝐸→𝐸+𝑇 0
𝐸. 𝑣𝑎𝑙 = 𝐸1 . 𝑣𝑎𝑙 + 𝑇. 𝑣𝑎𝑙 solution dans SableCC
𝐸→𝐸-𝑇 0
𝐸. 𝑣𝑎𝑙 = 𝐸1 . 𝑣𝑎𝑙 - 𝑇. 𝑣𝑎𝑙 2. Exigences supplémentaires
𝐸→𝑇 𝐸. 𝑣𝑎𝑙 = 𝑇. 𝑣𝑎𝑙
Ajoutez le jeton d'identification
(ID) à votre grammaire afin que
𝑇→𝑇∗𝐹 0
𝑇. 𝑣𝑎𝑙 = 𝑇 1 . 𝑣𝑎𝑙 ∗ 𝐹. 𝑣𝑎𝑙
votre calculatrice puisse
𝑇 → 𝑇/𝐹 0
𝑇. 𝑣𝑎𝑙 = 𝑇 1 . 𝑣𝑎𝑙/𝐹. 𝑣𝑎𝑙 accepter les expressions avec
𝑇→𝐹 𝑇. 𝑣𝑎𝑙 = 𝐹. 𝑣𝑎𝑙 contient des variables telles que :
𝐹 → 𝑛𝑢𝑚𝑏𝑒𝑟 𝐹. 𝑣𝑎𝑙 = 𝑛𝑢𝑚𝑏𝑒𝑟. 𝑣𝑎𝑙 3+x-y/(6*z) Lorsque l'évaluateur
𝐹 → (𝐸) 𝐹. 𝑣𝑎𝑙 = 𝐸. 𝑣𝑎𝑙 rencontre un ID, il demande à
l'utilisateur de saisir la valeur.

Conception de compilateurs : 82
Théorie, outils
Attributs synthétisés ou hérités
• attributs synthétisés
• Les attributs prennent leurs valeurs dans les attributs des nœuds inférieurs de
l'arbre.
• Ce type d'attributs peut être rempli dans une analyse ascendante.
• Attributs hérités
• Les attributs prennent leurs valeurs dans les attributs des nœuds supérieurs de
l'arbre.
et les frères et sœurs
• L'analyse descendante est indiquée pour remplir ces attributs si et
seulement si les valeurs proviennent des nœuds supérieurs
• Dans le cas où une grammaire contient des attributs synthétisés et hérités,
l'attribut
Conception de compilateurs : 83
Théorie, outils
le processus de remplissage des valeurs d'attributs n'est pas simple
• Graphes de dépendance

Conception de compilateurs : 84
Théorie, outils
Graphiques de dépendance
• Les règles sémantiques établissent des dépendances entre les
attributs qui peuvent être représentées par un graphe de
dépendance.
• Ce graphe de dépendance détermine comment les attributs
peuvent être évalués dans les arbres d'analyse.
• Pour chaque symbole X, le graphe de dépendance comporte
un nœud pour chaque attribut associé à X
• Une arête reliant le nœud A au nœud B signifie que l'attribut
de A est nécessaire pour calculer l'attribut de B
• Comment différencier les attributs synthétisés des attributs hérités ?
Conception de compilateurs : 85
Théorie, outils
Exemple 1
Productions Règles sémantiques
D 🡪T L [Link] = [Link]
L 🡪 L,id
L 🡪 id
T 🡪 int [Link] = entier
T 🡪 réel [Link] = réel

Conception de compilateurs : 86
Théorie, outils
Exemple 2

production action sémantique

E.h:=2*E.s+1
S.r:=E.t
E(0).s:=E(1).s+E(2).s
E(0).t:=3*E(1).t-E(2).t
E(1).h:=E(0).h
E(2).h:=E(0).h+4
E 🡪nombre E.s:= nombre
E.t:=E.h +1
Conception de compilateurs : 87
Théorie, outils
Graphique de dépendance pour les productions

Conception de compilateurs : 88
Théorie, outils
Graphe de dépendance pour un arbre syntaxique

Conception de compilateurs : 89
Théorie, outils