Dossier complet — Compilation

L3 · S6 · Fondements de l’informatique

Dossier pédagogique original Matrice MI. Contenu d’entraînement non officiel; il ne remplace pas le support ou la maquette d’un établissement.

Objectifs d’apprentissage

• Décrire le pipeline d’un compilateur, de la source à l’exécutable, en distinguant analyse, représentation et synthèse.

• Construire un flux de lexèmes et spécifier les erreurs lexicales courantes avec des diagnostics précis.

• Utiliser une grammaire hors contexte pour analyser une expression et produire un arbre syntaxique abstrait correct.

• Traduire un AST en représentation intermédiaire puis justifier une optimisation locale sans changer la sémantique.

• Évaluer les limites d’un mini-compilateur : ambiguïtés, portée des noms, types, diagnostics et dépendance à la cible.

Prérequis

• Programmation impérative : variables, fonctions, structures de contrôle et manipulation de chaînes.

• Notions de structures arborescentes, récursivité et complexité asymptotique au niveau licence.

• Bases de langages formels : alphabet, mots, grammaire et distinction entre syntaxe et sémantique.

Cours

1. Analyse lexicale

Transformer des caractères en unités

L’analyseur lexical lit le flux de caractères et le regroupe en lexèmes : identifiants, entiers, mots-clés, opérateurs et séparateurs. Il ignore généralement les espaces et commentaires, tout en conservant la position de chaque lexème pour les diagnostics. Une spécification de tokens est souvent réalisée par expressions régulières, puis compilée en automate fini. La règle « plus long lexème » évite de lire <= comme < puis = ; les priorités départagent ensuite les règles de même longueur.

Exemple guidé. Pour x = 12 + 3, on obtient ID(x) ASSIGN INT(12) PLUS INT(3). Un curseur avance : il consomme x, saute l’espace, reconnaît =, puis lit chaque suite de chiffres. Si le langage interdit les identifiants commençant par un chiffre, 12x doit être signalé plutôt que découpé silencieusement en 12 et x.

Erreur fréquente : oublier les caractères illégaux ou confondre valeur textuelle et valeur numérique.

Point de contrôle : proposer le flux de tokens de total<=10 et justifier le choix de <=.

Points-clés

• Un lexème est une occurrence concrète d’un type de token.
• Le principe du plus long lexème stabilise les opérateurs composés.
• Les positions source sont indispensables aux messages d’erreur exploitables.

2. Syntaxe et arbre abstrait

Donner une structure au flux

Une grammaire hors contexte décrit les phrases valides par des productions. Pour les expressions, une grammaire stratifiée encode la priorité : E -> E + T | T, T -> T * F | F, F -> INT | ( E ). Le parseur consomme les tokens et construit un arbre syntaxique ; l’AST retire les détails comme les parenthèses tout en conservant les opérateurs et leurs opérandes. Une grammaire récursive gauche convient à certains parseurs LR, mais provoque une boucle dans une descente récursive naïve : il faut alors la factoriser.

Exemple guidé. Pour 2 + 3 * 4, E prend T, T reconnaît 2, puis + déclenche un second T. Ce T reconnaît 3 * 4, donc l’arbre est Add(Int(2), Mul(Int(3),Int(4))), évalué à 14.

Erreur fréquente : produire Mul(Add(2,3),4) en traitant les opérateurs dans l’ordre de lecture.

Point de contrôle : dessiner l’AST de (2 + 3) * 4 et expliquer pourquoi il diffère.

Points-clés

• La grammaire exprime la forme ; l’AST conserve la structure utile.
• Priorité et associativité sont des choix syntaxiques explicites.
• La stratégie de parsing doit être compatible avec la forme de la grammaire.

3. Code intermédiaire et génération

Produire un code correct et raisonnable

La génération de code traduit l’IR vers une machine cible, un bytecode ou une autre forme portable. Avant cela, des optimisations sûres exploitent les dépendances : propagation de constantes, élimination d’une copie inutile et calcul constant. Une transformation n’est correcte que si elle conserve le comportement observable, notamment les exceptions, les entrées-sorties et les effets de bord. La génération finale affecte registres ou emplacements mémoire et doit respecter la convention d’appel.

Exemple guidé. L’IR t1 = 2 + 3; t2 = t1 * 4; x = t2 devient, par calcul constant, t1 = 5; t2 = 20; x = 20, puis x = 20 si les temporaires n’ont aucune autre utilisation. En revanche, remplacer lire() + lire() par 2*lire() serait faux : les appels ont des effets observables.

Erreur fréquente : confondre une valeur inutilisée avec une instruction sans effet ; un appel ou une écriture mémoire peut rester nécessaire.

Point de contrôle : marquer les transformations sûres dans un bloc contenant une affectation pure et un appel d’entrée.

Points-clés

• Une optimisation doit préserver la sémantique observable.
• Les graphes de flot et d’usage aident à décider quoi supprimer.
• La cible impose registres, mémoire, conventions d’appel et coûts.

4. Du texte source à l’exécutable

Idée directrice

Un compilateur transforme un programme source en une forme exécutable en plusieurs passes. Une chaîne classique est : prétraitement, analyse lexicale, analyse syntaxique, analyse sémantique, génération d’une représentation intermédiaire, optimisation, génération de code puis édition de liens. Chaque étape produit une structure vérifiable et signale ses erreurs au plus près de leur origine. La compilation n’est donc pas une simple traduction mot à mot : elle préserve une sémantique tout en changeant de représentation.

Méthode. Pour une expression 2 + 3 * 4, le lexer produit INT PLUS INT STAR INT, le parseur impose * avant +, puis l’AST devient Add(2, Mul(3,4)). Une génération naïve donne t1 = 3 * 4; t2 = 2 + t1.

Limite fréquente : confondre compilation et édition de liens, ou optimiser avant d’avoir validé les effets de bord.

Point de contrôle : expliquer quelle passe connaît les lexèmes, laquelle connaît la structure et laquelle choisit les instructions cibles.

Points-clés

• Les passes séparent reconnaissance, vérification et production de code.
• Une représentation intermédiaire rend les optimisations plus portables.
• Un diagnostic utile associe étape, position, cause et correction possible.

5. Analyse sémantique et représentation intermédiaire

Vérifier le sens avant de traduire

Après le parsing, l’analyse sémantique vérifie ce que la syntaxe ne peut pas exprimer seule : déclaration préalable, portée, compatibilité des types, nombre d’arguments et règles de retour. Une table des symboles associe un nom à ses attributs et respecte les blocs imbriqués. L’AST peut ensuite être traduit en code trois-adresses, où chaque instruction possède au plus une opération et des temporaires.

Exemple guidé. Pour a = 2 + 3, si a est déclaré entier, on vérifie les deux opérandes, calcule le type entier, puis émet t1 = 2 + 3 et a = t1. Pour a = vrai + 3, la syntaxe est valide mais le typage refuse l’addition. Dans un bloc interne, une nouvelle déclaration de a masque temporairement l’ancienne ; elle ne doit pas la supprimer de la table externe.

Erreur fréquente : accepter un identifiant inconnu parce que son texte a été reconnu lexicalement.

Point de contrôle : indiquer quelles entrées de table sont visibles dans deux blocs imbriqués et quel diagnostic donner pour f(1,2) si f attend un argument.

Points-clés

• La table des symboles encode portée, type et nature des identifiants.
• La validité syntaxique n’implique pas la validité sémantique.
• Le code trois-adresses rend dépendances et temporaires explicites.

Exercices corrigés

Exercice 1 · Fondamental

Pour l’expression total <= 10 + 2, donnez la suite ordonnée de lexèmes en distinguant les valeurs des tokens, puis indiquez l’ordre de lecture des caractères.

Correction détaillée

1. Lire total : c’est ID(total). 2. Ignorer l’espace. 3. Tester l’opérateur composé et reconnaître <= comme LE, plutôt que < puis =. 4. Lire 10 : INT(10). 5. Reconnaître + : PLUS. 6. Lire 2 : INT(2). La suite est donc ID(total), LE, INT(10), PLUS, INT(2). Les espaces ne produisent pas de token. Le choix de LE applique le plus long lexème : à la position de <, deux caractères forment un opérateur valide, donc on ne s’arrête pas au premier.

Exercice 2 · Fondamental

Construisez l’AST de 2 + 3 * 4 avec les nœuds Add, Mul et Int, puis calculez la valeur de l’expression.

Correction détaillée

La multiplication est prioritaire. Le sous-arbre droit de l’addition est donc Mul(Int(3), Int(4)). L’AST complet est Add(Int(2), Mul(Int(3), Int(4))). Évaluation étape par étape : Int(3) vaut 3 et Int(4) vaut 4 ; Mul vaut 3 * 4 = 12 ; Int(2) vaut 2 ; enfin Add vaut 2 + 12 = 14. L’arbre incorrect Mul(Add(Int(2),Int(3)),Int(4)) donnerait 20 et révèle que la priorité n’a pas été respectée.

Exercice 3 · Intermédiaire

Traduisez x = (2 + 3) * (y - 4) en code trois-adresses, en supposant x et y déjà déclarés entiers.

Correction détaillée

On traite d’abord chaque sous-expression parenthésée. 1. Émettre t1 = 2 + 3. 2. Émettre t2 = y - 4. 3. Combiner les résultats avec t3 = t1 * t2. 4. Affecter au nom déclaré : x = t3. Le bloc final est donc : t1 = 2 + 3; t2 = y - 4; t3 = t1 * t2; x = t3. Le typage est valide car les littéraux et y sont entiers, et chaque opérateur reçoit deux entiers. Une génération qui calcule 2 + 3 en avance pourra remplacer la première instruction par t1 = 5, mais cette optimisation n’est pas nécessaire pour satisfaire l’exercice.

Exercice 4 · Intermédiaire

Une fonction f attend un entier. Dans un bloc externe, a est un entier ; dans un bloc interne, a est une chaîne. Analysez sémantiquement f(a) dans chacun des deux blocs et expliquez la portée.

Correction détaillée

La table externe contient a : entier et f : entier -> .... Dans le bloc interne, l’insertion de a : chaîne masque l’entrée externe sans la détruire. Ainsi, dans le bloc externe, la résolution de a donne un entier : f(a) est bien typé. Dans le bloc interne, la résolution s’arrête sur a : chaîne ; l’argument ne correspond pas à l’entier attendu et le compilateur émet une erreur de type à la position de a. En quittant le bloc interne, la table externe redevient visible et a retrouve le type entier. Il faut donc chercher d’abord dans la portée courante, puis remonter les environnements parents.

Exercice 5 · Avancé

Concevez une grammaire et un pseudo-parseur de descente récursive pour des entiers, +, * et parenthèses, avec * prioritaire et les opérateurs associatifs à gauche. Donnez aussi l’AST produit pour 1 + 2 * (3 + 4).

Correction détaillée

On évite la récursion gauche avec : expr -> terme (PLUS terme)*, terme -> facteur (STAR facteur)*, facteur -> INT | LPAREN expr RPAREN. Le parseur expr lit un terme, puis boucle tant que le prochain token est PLUS, en replaçant l’accumulateur dans Add. terme fait de même avec STAR et Mul; facteur consomme un entier ou les deux parenthèses autour d’un appel récursif à expr. Pour 1 + 2 * (3 + 4), expr crée Add(Int(1), ...); le second terme crée Mul(Int(2), Add(Int(3),Int(4))). L’AST est donc Add(Int(1), Mul(Int(2), Add(Int(3), Int(4)))), de valeur 15. Toute parenthèse fermante inattendue doit être signalée au point de lecture, et un token restant après expr constitue une erreur de syntaxe.

Quiz d’autoévaluation

Question 1

Quelle passe transforme prioritairement des caractères en tokens ?

✓ Analyse lexicale • Analyse sémantique • Édition de liens • Allocation de registres

Explication : Le lexer regroupe les caractères en lexèmes et leur attribue un type de token. Les autres passes interviennent plus tard ou sur une autre représentation.

Question 2

Pourquoi 2 + 3 * 4 vaut-il 14 dans la grammaire proposée ?

• Parce que l’addition est évaluée deux fois ✓ Parce que * appartient au niveau terme, prioritaire sur + • Parce que le lexer réordonne les tokens • Parce que les parenthèses sont implicites autour de toute expression

Explication : La séparation entre expr et terme place la multiplication dans le sous-arbre de droite avant la construction de l’addition.

Question 3

Quel objet associe un identifiant à son type et à sa portée ?

• Le tampon de caractères ✓ La table des symboles • Le registre d’instructions • Le fichier objet

Explication : La table des symboles mémorise les déclarations et permet la résolution selon les environnements imbriqués.

Question 4

Quel exemple est une erreur sémantique plutôt que lexicale ?

• Un caractère @ interdit par le langage ✓ Un identifiant non déclaré utilisé dans une addition • Un token PLUS reconnu • Un espace entre deux tokens

Explication : Le nom peut être lexicalement valide, mais son absence de déclaration rend son usage sémantiquement invalide.

Question 5

Quelle représentation expose explicitement les temporaires d’une traduction ?

✓ Code trois-adresses • Image de l’écran • Commentaire source • Nom du fichier

Explication : Le code trois-adresses décompose les opérations en instructions simples et introduit des temporaires nommés.

Question 6

Quelle optimisation est sûre pour une expression pure 2 + 3 ?

✓ La remplacer par 5 • La remplacer par un appel d’entrée • La supprimer même si elle déclenche une exception • La remplacer par une valeur aléatoire

Explication : Le calcul constant conserve la valeur d’une expression littérale pure. Une instruction avec effet de bord ne pourrait pas être supprimée de la même manière.

Question 7

Que signifie le principe du plus long lexème ?

• Toujours choisir le token le plus ancien ✓ Choisir la séquence valide de caractères la plus longue • Trier les tokens par taille après le parsing • Lire uniquement les identifiants longs

Explication : Il permet notamment de reconnaître <= comme un seul opérateur au lieu de deux tokens plus courts.

Question 8

Quelle condition est nécessaire pour supprimer une instruction par élimination de code mort ?

• Elle doit produire un effet observable ✓ Sa valeur et ses effets doivent être inutilisés • Elle doit contenir une parenthèse • Elle doit être dans le lexer

Explication : On ne supprime une instruction que si aucun usage ni effet observable ne dépend de son exécution.

Glossaire

• AST — Arbre syntaxique abstrait représentant la structure utile d’un programme sans conserver tous les détails de notation.
• Lexème — Suite de caractères reconnue comme une occurrence d’un type de token, avec une position dans le source.
• Token — Catégorie produite par l’analyse lexicale, comme identifiant, entier, opérateur ou mot-clé.
• Grammaire hors contexte — Ensemble de productions qui décrit comment des non-terminaux engendrent des phrases valides.
• Table des symboles — Structure qui enregistre noms déclarés, types, natures et environnements de portée.
• Code trois-adresses — Représentation intermédiaire où une instruction comporte au plus une opération et des opérandes explicites.
• Portée — Région du programme dans laquelle une déclaration de nom est visible et résoluble.
• Édition de liens — Étape qui assemble fichiers objets et bibliothèques afin de produire une image exécutable cohérente.

TP · Mini-compilateur d’expressions arithmétiques

Vous devez traiter un petit langage d’affectations entières contenant des identifiants, des littéraux, +, *, des parenthèses et des espaces. Le programme doit transformer une ligne source en tokens, AST puis code trois-adresses, sans prétendre remplacer un compilateur industriel.

Objectifs

• Implémenter un lexer avec positions et erreur sur caractère inconnu.

• Écrire un parseur qui respecte priorité et associativité.

• Afficher un AST lisible puis générer du code trois-adresses.

• Tester les cas valides, invalides et limites explicitement.

Étapes

1. Définir les types de tokens et une fonction next_token appliquant le plus long lexème.

2. Coder parse_expr, parse_term et parse_factor selon la grammaire sans récursion gauche.

3. Définir les nœuds AST et vérifier les invariants : opérateur avec deux enfants, parenthèses consommées.

4. Parcourir l’AST en postordre pour émettre des temporaires et une affectation finale.

5. Écrire au moins six tests, dont 2+3*4, (2+3)*4, une affectation et deux erreurs.

Livrables attendus

• Un dépôt ou dossier contenant le code source et un README d’exécution.

• Un tableau de tests avec entrée, tokens ou résultat attendu, sortie observée et statut.

• Une note d’une page présentant une limite du mini-compilateur et une amélioration possible.

Critères d’évaluation

• Lexer : 25 %, tokens corrects, positions et diagnostics.

• Parser/AST : 30 %, priorité, parenthèses et erreurs de syntaxe.

• Génération IR : 25 %, temporaires cohérents et ordre d’évaluation.

• Tests et documentation : 20 %, couverture, reproductibilité et limites explicites.

Piste de résolution

Une solution sépare quatre modules : lexer, parser, AST et générateur IR. Le lexer utilise une boucle sur l’entrée et teste d’abord <= si cet opérateur est ajouté ; le parser applique la grammaire expr/terme/facteur ; le générateur retourne le nom d’un temporaire pour chaque sous-arbre et émet l’opération après ses enfants. Pour x = 2 + 3 * 4, la sortie attendue peut être t1 = 3 * 4, t2 = 2 + t1, x = t2. Les tests doivent montrer que (2+3)*4 produit une racine Mul et qu’un caractère inattendu arrête proprement le traitement.

Sujets originaux d’entraînement (non officiels)

Sujet original de préparation — Compilation, session normale

Sujet d’entraînement original non officiel : il ne s’agit jamais d’une épreuve d’années passées ni d’un document institutionnel. Toute grammaire et toute convention nécessaires sont données dans l’énoncé.

Exercice 1

Pour a = 2 + 3 * 4, donnez les tokens puis l’AST en utilisant Assign, Add, Mul et Int. Justifiez la priorité.

Correction : Les tokens sont ID(a), ASSIGN, INT(2), PLUS, INT(3), STAR, INT(4). La grammaire place STAR au niveau des termes : le sous-arbre droit de Add est Mul(Int(3),Int(4)). L’AST est Assign(a, Add(Int(2), Mul(Int(3),Int(4)))). Le calcul donne 14, mais l’AST est la réponse structurelle principale.

Exercice 2

Détectez et expliquez les erreurs sur les lignes suivantes : x = 12y et z = q + 1 lorsque les identifiants doivent commencer par une lettre et que q n’est pas déclaré.

Correction : Dans x = 12y, le lexer lit INT(12) puis rencontre y immédiatement. Comme un identifiant ne peut pas commencer par un chiffre et qu’aucune règle ne valide la juxtaposition, il émet une erreur lexicale à la position de y ou signale le lexème mal formé selon la spécification. Dans z = q + 1, q peut être reconnu comme ID(q) ; l’erreur survient ensuite en analyse sémantique, car la recherche dans la table des symboles échoue. Les deux erreurs ne doivent donc pas être confondues.

Exercice 3

Traduisez x = (2 + 3) * y en code trois-adresses puis appliquez uniquement le calcul constant sûr.

Correction : La traduction directe est t1 = 2 + 3, t2 = t1 * y, x = t2. Comme 2 + 3 est une expression pure constante, on la réduit à 5 : t1 = 5, t2 = t1 * y, x = t2. On peut aussi propager t1 pour obtenir t2 = 5 * y, x = t2, mais il faut conserver l’ordre et les éventuels effets de y si sa lecture n’est pas une simple variable.

Sujet original de préparation — Compilation, session de rattrapage

Sujet d’entraînement original non officiel : il ne s’agit jamais d’une épreuve d’années passées ni d’un document institutionnel. Il propose un autre jeu de questions pour réviser les mêmes compétences.

Exercice 1

Avec expr -> terme (PLUS terme)*, terme -> facteur (STAR facteur)*, construisez l’AST de 1 * (2 + 3) + 4 et calculez sa valeur.

Correction : Le premier terme est Mul(Int(1), Add(Int(2),Int(3))), car les parenthèses forcent l’addition dans le facteur droit. La boucle de expr rencontre ensuite + et ajoute Int(4). L’AST est Add(Mul(Int(1), Add(Int(2),Int(3))), Int(4)). Évaluation : l’addition parenthésée vaut 5 ; le produit vaut 1 ; l’addition finale vaut 1 + 4 = 5.

Exercice 2

Dans une portée externe, n est entier. Une portée interne déclare n réel et contient n + 1. Expliquez la résolution et le diagnostic si + n’accepte que deux entiers.

Correction : La portée interne est consultée en premier : n est donc le réel local, qui masque l’entier externe. Le littéral 1 est entier. La résolution produit l’expression réel + entier ; si l’opérateur n’accepte que deux entiers, l’analyse sémantique signale une incompatibilité de types sur +. Elle ne doit pas reprendre automatiquement l’ancienne déclaration externe. Après la sortie du bloc, la déclaration entière redevient visible.

Exercice 3

Donnez une optimisation valide et une transformation invalide pour t1 = 2 + 3; t2 = lire(); x = t1 + t2, en justifiant les effets de bord.

Correction : Optimisation valide : remplacer t1 = 2 + 3 par t1 = 5, car l’expression est constante et pure. On peut ensuite produire x = 5 + t2 après lecture, sans déplacer ni supprimer t2 = lire(). Transformation invalide : remplacer l’ensemble par x = 5 + 1 ou supprimer lire(), car l’appel fournit une entrée observable. Une autre transformation invalide serait de déplacer un appel au-delà d’une écriture dont il dépend sans preuve d’absence d’effet.

Parcours de révision sur quatre semaines

Semaine 1 · Pipeline et analyse lexicale

Faire une fiche des passes, puis tokeniser à la main dix expressions et coder trois tests de caractères invalides. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 2 · Grammaires, priorité et AST

Réécrire une grammaire sans récursion gauche, dessiner huit AST et vérifier les valeurs avec des parenthèses. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 3 · Portée, types et code intermédiaire

Résoudre des noms dans trois niveaux de blocs et traduire cinq AST en code trois-adresses. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 4 · Optimisation, génération et synthèse

Corriger le mini-cas, justifier quatre optimisations sûres et faire un sujet original chronométré en relisant les diagnostics. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.