PandaCodeur · Cours 1 / 5
Compilation : 1. Langages et chaîne de compilation
Comprendre les mots, les langages et le rôle de chaque phase.
Objectifs et prérequis
Prérequis : ensembles, fonctions et lecture de pseudocode. À la fin du chapitre, vous saurez distinguer un alphabet, un mot et un langage, puis localiser une erreur dans la chaîne de compilation. Comptez 35 minutes et faites le mini-exercice avant d’ouvrir sa correction.
Alphabet, mot et langage
Un alphabet Σ est un ensemble fini de symboles. Un mot est une suite finie de symboles de Σ ; ε désigne le mot vide et |w| sa longueur. Σ* contient tous les mots finis, dont ε ; Σ+ contient les mots de longueur au moins un. Un langage L est un sous-ensemble de Σ*.
| Notation | Sens | Exemple |
|---|---|---|
| uv | Concaténation de mots | 01 · 10 = 0110 |
| L ∪ K | Union | {a} ∪ {b} = {a,b} |
| LK | Concaténation de langages | {a,b}{c} = {ac,bc} |
| L* | Zéro ou plusieurs concaténations | {ab}* = {ε,ab,abab,…} |
| Σ* \ L | Complément sur un alphabet fixé | Tous les mots de Σ* hors de L |
Compilation et interprétation
Un compilateur traduit une représentation source vers une représentation cible, par exemple du code machine ou du bytecode. Un interpréteur exécute une représentation du programme. Une implémentation peut combiner compilation et interprétation, et compiler certaines parties pendant l’exécution. Le mode d’exécution dépend de l’implémentation, pas d’une propriété absolue du langage.
Le préprocesseur transforme le texte ; l’assembleur traduit l’assembleur ; l’éditeur de liens rassemble les modules et bibliothèques ; le chargeur prépare l’exécution.
De la source au code cible
Le lexer reconnaît des lexèmes et produit des tokens. Le parseur organise ces tokens selon la grammaire. L’analyse sémantique contrôle notamment les déclarations et les types. La génération de code intermédiaire, l’optimisation et la génération de code cible poursuivent la traduction. La table des symboles et les diagnostics accompagnent plusieurs phases.
Source : total = prix + quantite * 2;
Tokens : ID ASSIGN ID PLUS ID STAR INT SEMI
Intermédiaire : t1 = quantite * 2
t2 = prix + t1
total = t2Identifier les erreurs
| Exemple dans un mini-langage | Phase | Justification |
|---|---|---|
| x = 2 § 3; | Lexicale | § ne correspond à aucun token autorisé |
| x = (2 + ); | Syntaxique | Opérande absent |
| x = inconnu + 1; | Sémantique | Identificateur non déclaré |
La faute « fi » au lieu de « if » peut produire un token identificateur valide : elle devient alors une erreur syntaxique dans le contexte d’une instruction conditionnelle. Il faut préciser les règles lexicales et la position de l’erreur.
Mini-exercice : calculer et classer
Sur Σ = {a,b}, donner |abba|, {a,b}{ε,a} et la différence entre ε et {ε}. Pour x = y + 2;, y non déclaré, quelle phase peut signaler l’erreur ?
Afficher la correction expliquée
|abba| = 4 ; le produit vaut {a,aa,b,ba}. ε est un mot ; {ε} est un langage. Le lexer et le parseur peuvent accepter la forme de l’affectation ; la recherche de y dans la table des symboles révèle une erreur sémantique.