L'analyse syntaxique a produit un arbre bien formé. Mais bien formé ne veut pas dire correct : x = y + 1 respecte la grammaire même si y n'a jamais été déclarée, ou si y est hors de portée à cet endroit. Donner un sens à l'arbre est le rôle de l'analyse sémantique — et son socle est la table des symboles, ce service transversal annoncé au chapitre 1.

Ce chapitre construit la table et, surtout, le mécanisme qui fait toute sa subtilité : les portées. Savoir à quelle déclaration se rapporte un nom, dans un programme truffé de blocs imbriqués, est une question moins évidente qu'il n'y paraît — et sa réponse conditionne toute la suite.

Ce que la table retient

La table des symboles associe à chaque identificateur du programme ce que le compilateur en sait :

• son nom ;
• son type (chapitre 7) ;
• sa portée — la région du programme où il est visible ;
• son emplacement mémoire — le décalage qui donnera son adresse à l'exécution (chapitre 10).

Elle est remplie au fil des déclarations (pendant l'analyse) et consultée à chaque usage d'un identificateur, jusqu'à la génération de code. C'est la mémoire partagée du compilateur : le pont entre « ce nom est déclaré ici » et « ce nom vaut cela, à cette adresse, plus loin ».

Portées et blocs imbriqués

Un programme n'a pas un espace de noms unique. Chaque bloc — le corps d'une fonction, l'intérieur d'un if, une paire d'accolades — ouvre une portée : une région où des noms peuvent être déclarés, qui masquent éventuellement des noms de même orthographe déclarés plus à l'extérieur.

1int x;              // (0) x global2{3    int y;          // (1) y local au bloc4    x = y;          //     ici x = le global, y = le local5    {6        int x;      // (2) un NOUVEAU x, qui MASQUE le global7        x = 1;      //     ici x = le local du bloc interne8    }9    x = 2;          //     de retour : x redevient le global10}

Le même identificateur x désigne deux variables différentes selon l'endroit. La question centrale du chapitre est : à quelle déclaration un usage se rapporte-t-il ?

Organiser et implémenter : une pile de portées

L'implémentation qui suit naturellement la structure en blocs est une pile de portées. Chaque portée est une table locale (nom → information) ; on empile/dépile au rythme des blocs :

• entrer dans un bloc : empiler une portée vide ;
• déclarer un identificateur : l'insérer dans la portée du sommet (la portée courante) ;
• sortir du bloc : dépiler la portée — et tout ce qu'elle contenait disparaît d'un coup, ce qui est exactement le cycle de vie des variables locales ;
• résoudre un identificateur : le chercher du sommet vers la base, et prendre la première occurrence trouvée — la déclaration la plus interne.

C'est cette recherche « de l'intérieur vers l'extérieur » qui réalise le masquage : le x interne est trouvé avant le x global, sans l'effacer ; à la sortie du bloc, le global réapparaît intact. L'exercice de ce chapitre construit exactement cette pile.

D'autres organisations existent (une table unique avec un numéro de portée, des tables de hachage chaînées), avec le même comportement observable. Le choix relève de la performance ; le modèle mental, lui, reste la pile.

Déclaration et résolution des identificateurs

Deux opérations, deux règles à ne pas confondre.

Déclarer insère un nom dans la portée courante. Y insérer un nom déjà présent dans cette même portée est une erreur de redéclaration — on ne peut pas déclarer deux fois x dans le même bloc. En revanche, déclarer x alors qu'un x existe dans une portée englobante est parfaitement légal : c'est du masquage.

Résoudre cherche la déclaration active d'un nom à un point donné. Si la recherche du sommet vers la base n'aboutit pas, l'identificateur est non déclaré — l'erreur sémantique la plus courante, celle qui manquait à l'analyse syntaxique du chapitre 1.

Ces deux vérifications — pas de redéclaration, pas d'usage non déclaré — sont les premières que l'analyse sémantique effectue, avant même de parler de types.

Portée statique et portée dynamique

Reste une question de principe, qui distingue deux familles de langages.

En portée statique (ou lexicale), le nom auquel se rapporte un usage se détermine par la structure du texte — les blocs qui entourent physiquement l'usage. C'est décidable à la compilation, en lisant le programme. C'est le modèle de la pile ci-dessus, et celui de la quasi-totalité des langages modernes.

En portée dynamique, un nom se rapporte à la dernière déclaration active dans la chaîne des appels à l'exécution — ce qui dépend de qui a appelé qui, donc n'est pas connu à la compilation. Bien plus difficile à raisonner et source de bugs subtils, elle a été presque partout abandonnée (on la retrouve dans quelques langages anciens, ou pour des variables spéciales).

La conséquence pratique est nette : parce que la portée est statique, le compilateur peut, dès l'analyse, associer chaque usage à sa déclaration et détecter les erreurs — c'est ce qui rend l'analyse sémantique possible en amont de toute exécution.

À vous

L'exercice construit le service transversal du compilateur : une table des symboles à portées imbriquées. Vous implémentez la pile de portées, la déclaration (avec l'erreur de redéclaration) et la résolution de l'intérieur vers l'extérieur, puis vous observez le masquage d'une variable globale par une locale — et le retour du global à la sortie du bloc.

C'est la mémoire partagée qui servira jusqu'au bout : le chapitre 7 y lira les types, et le chapitre 10 y ajoutera les adresses.

// La table des symboles suit les DÉCLARATIONS et les PORTÉES. Un bloc { ... }
// ouvre une portée ; on la ferme en sortant. Chercher un identifiant, c'est
// remonter de la portée courante vers les englobantes (portée STATIQUE).
//
// On modélise la table par une PILE de portées (chacune un dictionnaire).

function nouvelleTable() {
  return { portees: [ {} ] };   // au départ : la portée globale
}
function entrerBloc(t) { t.portees.push({}); }        // ouvre une portée
function sortirBloc(t) { t.portees.pop(); }           // ferme la portée courante

// ── À VOUS : declarer et resoudre ───────────────────────────────────────────
// declarer : ajoute (nom -> info) dans la portée COURANTE (la dernière).
//   Redéclarer dans la MÊME portée est une erreur ; masquer une variable
//   d'une portée ENGLOBANTE est autorisé.
function declarer(t, nom, type) {
  const courante = t.portees[t.portees.length - 1];
  // à compléter : si 'nom' est déjà dans 'courante' -> renvoyer "ERREUR redéclaration"
  //               sinon courante[nom] = { type, niveau: t.portees.length - 1 }; renvoyer "ok"
  return "?";
}
// resoudre : cherche 'nom' de la portée COURANTE vers la GLOBALE ; renvoie
// l'info trouvée (la plus interne), ou "non déclaré".
function resoudre(t, nom) {
  // à compléter : parcourir t.portees de la fin vers le début
  return "non déclaré";
}

// ── Scénario : imite l'analyse d'un programme ───────────────────────────────
//   int x;            // global
//   { int y; x = y;   // bloc 1
//     { int x; x = 1; // bloc 2 : ce x MASQUE le global
//     }
//     x = 2;          // de retour au bloc 1 : x redevient le global
//   }
const t = nouvelleTable();
console.log("global   declarer x :", declarer(t, "x", "int"));
entrerBloc(t);
console.log("bloc1    declarer y :", declarer(t, "y", "int"));
console.log("bloc1    resoudre x :", JSON.stringify(resoudre(t, "x")));   // le global (niveau 0)
entrerBloc(t);
console.log("bloc2    declarer x :", declarer(t, "x", "int"));           // masque le global
console.log("bloc2    resoudre x :", JSON.stringify(resoudre(t, "x")));   // le x local (niveau 2)
sortirBloc(t);
console.log("bloc1    resoudre x :", JSON.stringify(resoudre(t, "x")));   // à nouveau le global
console.log("bloc1    resoudre z :", JSON.stringify(resoudre(t, "z")));   // jamais déclaré
console.log("bloc1    redeclarer y :", declarer(t, "y", "int"));         // ERREUR (même portée)

function declarer(t, nom, type) {
  const courante = t.portees[t.portees.length - 1];
  if (Object.prototype.hasOwnProperty.call(courante, nom)) return "ERREUR redéclaration";
  courante[nom] = { type, niveau: t.portees.length - 1 };
  return "ok";
}
function resoudre(t, nom) {
  for (let i = t.portees.length - 1; i >= 0; i--) {   // de la plus interne vers la globale
    if (Object.prototype.hasOwnProperty.call(t.portees[i], nom)) return t.portees[i][nom];
  }
  return "non déclaré";
}

// ── Trace attendue ──────────────────────────────────────────────────────────
//  global declarer x : ok
//  bloc1  declarer y : ok
//  bloc1  resoudre x : {"type":"int","niveau":0}   <- le global
//  bloc2  declarer x : ok                            <- masque le global
//  bloc2  resoudre x : {"type":"int","niveau":2}   <- le x LOCAL
//  bloc1  resoudre x : {"type":"int","niveau":0}   <- le global de nouveau
//  bloc1  resoudre z : "non déclaré"
//  bloc1  redeclarer y : ERREUR redéclaration
//
// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. La table est une PILE de portées. Entrer dans un bloc empile une portée
//    vide ; en sortir la dépile — et tout ce qu'elle contenait disparaît
//    d'un coup. C'est exactement le cycle de vie des variables locales.
//
// 2. La RÉSOLUTION va de l'intérieur vers l'extérieur : on prend la
//    déclaration la plus PROCHE. C'est ce qui réalise le MASQUAGE — le « x »
//    du bloc 2 cache le « x » global, sans l'effacer : à la sortie du bloc,
//    le global réapparaît intact.
//
// 3. C'est la PORTÉE STATIQUE (ou lexicale) : la variable désignée par un nom
//    se détermine par la STRUCTURE du texte (les blocs qui entourent l'usage),
//    connue à la COMPILATION. La portée DYNAMIQUE, plus rare, choisirait selon
//    la chaîne des APPELS à l'exécution — bien plus difficile à raisonner, et
//    abandonnée par presque tous les langages modernes.
//
// 4. Redéclarer dans la MÊME portée est une erreur ; masquer depuis une portée
//    englobante ne l'est pas. La table est le service transversal du
//    chapitre 1 : remplie ici, elle servira jusqu'à la génération de code
//    (où « niveau » et un décalage donneront l'adresse de la variable).

Ce que la suite en fait

La table des symboles répond à « ce nom existe-t-il, et où ? ». Reste la seconde moitié de l'analyse sémantique : « cet usage a-t-il un sens ? ». Additionner un entier et une chaîne, appeler une fonction avec le mauvais nombre d'arguments, affecter un flottant à un booléen — tout cela est bien formé et bien porté, mais mal typé.

Le chapitre 7 s'attaque à la vérification de types, en s'appuyant sur la table des symboles (pour connaître le type de chaque identificateur) et sur les grammaires attribuées — la manière propre de faire remonter et redescendre de l'information dans l'arbre syntaxique.

À retenir

La table des symboles (chapitre 6) répond à « ce nom existe-t-il ? ». Il reste la seconde moitié de l'analyse sémantique, celle qui traque les erreurs de sens : additionner un entier et un booléen, affecter un flottant à un entier sans le dire, comparer des choses incomparables. C'est la vérification de types — et c'est elle qui rattrape enfin les erreurs sémantiques du chapitre 1, invisibles à toutes les phases précédentes.

Ce chapitre introduit aussi l'outil qui structure toute l'analyse sémantique et la génération de code : les grammaires attribuées et les schémas de traduction dirigés par la syntaxe, c'est-à-dire la manière de faire circuler de l'information dans l'arbre.

Systèmes de types

Un type classe les valeurs et restreint les opérations qu'on peut leur appliquer : on additionne des entiers, on concatène des chaînes, on ne fait ni l'un avec l'autre. Un système de types est l'ensemble des règles qui, pour chaque construction du langage, disent quels types sont admis et quel type produit le résultat.

Sa promesse est forte : un programme qui passe la vérification de types ne commettra pas, à l'exécution, une faute de type — pas d'addition entre un entier et une fonction, pas d'appel d'un nombre comme s'il était une fonction. Le vérificateur transforme une classe entière d'erreurs d'exécution en erreurs de compilation, détectées une fois pour toutes.

Expressions de types et équivalence

Les types ne sont pas que des étiquettes : ce sont des expressions. Les types de base (int, float, bool) se combinent en types construits : tableau de int, pointeur vers float, fonction (int, int) → bool, structure { … }. Un type est un arbre, comme une expression.

D'où une question centrale : quand deux types sont-ils équivalents — quand « vont-ils ensemble » ? Deux réponses classiques :

• l'équivalence structurelle : deux types sont équivalents s'ils ont la même structure, quel que soit leur nom. tableau de int et tableau de int sont équivalents, même définis séparément.
• l'équivalence par nom : deux types ne sont équivalents que s'ils portent le même nom de type. Deux structures identiques mais nommées différemment sont alors distinctes.

Le choix a des conséquences réelles sur ce que le langage accepte ; C mêle les deux selon les cas. Pour un mini-langage, l'équivalence structurelle sur des types simples suffit.

Vérification et conversions implicites

Vérifier une expression, c'est calculer son type en appliquant les règles du système, et échouer si aucune ne s'applique. Pour une opération arithmétique :

1int  op int   → int2float op float → float3int  op float  → float      (l'entier est converti)4float op int   → float      (l'entier est converti)5bool op nombre → ERREUR

Le cas int op float introduit la conversion implicite (ou coercion) : plutôt que de refuser l'opération, le compilateur convertit automatiquement l'entier en flottant, parce que cette conversion ne perd aucune information — tout entier est un flottant exact. L'inverse, float → int, serait une troncature (perte de la partie décimale) : on ne le fait jamais implicitement ; il faut une conversion explicite. La règle générale des conversions implicites sûres est l'élargissement sans perte.

Un point à ne pas manquer : le type du résultat n'est pas toujours celui des opérandes. Une comparaison x < y entre deux nombres produit un bool, pas un nombre. C'est le vérificateur qui en décide.

Grammaires attribuées

Comment le vérificateur calcule-t-il le type de chaque nœud ? En attachant de l'information aux nœuds de l'arbre et en la faisant circuler selon des règles. C'est une grammaire attribuée : à chaque règle de grammaire, on associe des attributs (ici, le type) et des équations qui les calculent.

Il y a deux sens de circulation, et la distinction est fondamentale :

• un attribut synthétisé remonte : la valeur d'un nœud se calcule à partir de celles de ses enfants. Le type d'une expression est synthétisé — on type les feuilles, puis chaque parent en déduit son type. C'est le cas le plus courant.
• un attribut hérité descend : la valeur d'un nœud se calcule à partir de son parent ou de ses frères. Exemple : le type attendu d'une expression, imposé par le contexte (le type de la variable à gauche d'une affectation) et transmis vers le bas.

La plupart des vérifications de types se font avec des attributs synthétisés — c'est ce que construit l'exercice, où le type remonte des constantes et variables vers la racine de l'expression.

Schémas de traduction dirigés par la syntaxe

Quand on greffe des actions sur les règles de la grammaire — calculer un attribut, vérifier une compatibilité, émettre du code — on parle de traduction dirigée par la syntaxe : la structure syntaxique pilote le traitement. À chaque réduction (ou à chaque appel de fonction, en descente récursive), on exécute l'action associée.

C'est le mécanisme unificateur de tout ce qui suit l'analyse syntaxique. Vous l'avez déjà employé sans le nommer au chapitre 4 : l'analyseur descendant qui évaluait l'expression en même temps qu'il l'analysait faisait de la traduction dirigée par la syntaxe, avec un attribut synthétisé (la valeur). Le même schéma servira au chapitre 8 pour engendrer du code — on remplacera simplement l'attribut « valeur » par un attribut « code ». Bison permet d'ailleurs d'attacher directement ces actions aux règles.

À vous

L'exercice construit le vérificateur de types du compilateur du TP, sur un AST d'expression. Le type y est un attribut synthétisé qui remonte des feuilles : vous typez les constantes et variables (via la table des symboles du chapitre 6), puis chaque opérateur en déduit son type. Vous gérez l'équivalence, la conversion implicite int → float, le type bool d'une comparaison, et vous détectez les erreurs sémantiques — int + bool, identifiant non déclaré — celles-là mêmes que le chapitre 1 attribuait à cette phase.

C'est le dernier maillon du front-end : après lui, l'arbre est vérifié et typé, prêt à être traduit.

// L'AST d'une expression. Chaque nœud : { op, ... }.
//   { op: "nb",  type: "int"|"float" }        une constante
//   { op: "var", nom }                         un identifiant (type dans la table)
//   { op: "+"|"-"|"*"|"/", g, d }              une opération binaire
//   { op: "<", g, d }                          une comparaison -> bool
//
// La table des symboles (chapitre 6), déjà remplie :
const TABLE = { x: "int", y: "float", drapeau: "bool" };

// Règles de typage d'une opération arithmétique :
//   int  op int   -> int
//   float op float -> float
//   int  op float  ou float op int -> float  (CONVERSION IMPLICITE de l'int)
//   toute autre combinaison (ex. bool) -> ERREUR
function typeArith(tg, td) {
  if (tg === "int" && td === "int") return "int";
  if ((tg === "int" || tg === "float") && (tg === "float" || td === "float") &&
      (td === "int" || td === "float")) return "float";
  return "ERREUR";
}

// ── À VOUS : typer() calcule le type d'un nœud (attribut synthétisé) ─────────
// Le type REMONTE : on type d'abord les fils, puis on en déduit le type du
// parent. Renvoyer le type, ou lever une erreur explicite.
function typer(n) {
  if (n.op === "nb")  return n.type;
  if (n.op === "var") {
    // à compléter : chercher n.nom dans TABLE ; s'il est absent -> throw
    return "?";
  }
  if (n.op === "<") {
    // à compléter : typer les deux fils (ils doivent être numériques),
    // puis renvoyer "bool". Comparer un bool -> erreur.
    return "?";
  }
  // opérations arithmétiques + - * /
  const tg = typer(n.g), td = typer(n.d);
  const r = typeArith(tg, td);
  if (r === "ERREUR") throw new Error("types incompatibles : " + tg + " " + n.op + " " + td);
  return r;
}

// ── Vérification ────────────────────────────────────────────────────────────
const cas = [
  { desc: "x + 1",         ast: { op: "+", g: { op: "var", nom: "x" }, d: { op: "nb", type: "int" } } },
  { desc: "x + y (int+float)", ast: { op: "+", g: { op: "var", nom: "x" }, d: { op: "var", nom: "y" } } },
  { desc: "x < y",         ast: { op: "<", g: { op: "var", nom: "x" }, d: { op: "var", nom: "y" } } },
  { desc: "x + drapeau",   ast: { op: "+", g: { op: "var", nom: "x" }, d: { op: "var", nom: "drapeau" } } },
  { desc: "x + z (z inconnu)", ast: { op: "+", g: { op: "var", nom: "x" }, d: { op: "var", nom: "z" } } },
];
for (const c of cas) {
  try { console.log(c.desc.padEnd(22) + " : " + typer(c.ast)); }
  catch (e) { console.log(c.desc.padEnd(22) + " : ✗ " + e.message); }
}

function typer(n) {
  if (n.op === "nb")  return n.type;
  if (n.op === "var") {
    if (!(n.nom in TABLE)) throw new Error("identifiant non déclaré : " + n.nom);
    return TABLE[n.nom];
  }
  if (n.op === "<") {
    const tg = typer(n.g), td = typer(n.d);
    if (typeArith(tg, td) === "ERREUR")
      throw new Error("comparaison de non-numériques : " + tg + " < " + td);
    return "bool";                       // une comparaison a toujours le type bool
  }
  const tg = typer(n.g), td = typer(n.d);
  const r = typeArith(tg, td);
  if (r === "ERREUR") throw new Error("types incompatibles : " + tg + " " + n.op + " " + td);
  return r;
}

// ── Résultats ───────────────────────────────────────────────────────────────
//  x + 1              : int
//  x + y (int+float)  : float     <- l'int x est CONVERTI implicitement en float
//  x < y              : bool
//  x + drapeau        : ✗ types incompatibles : int + bool
//  x + z (z inconnu)  : ✗ identifiant non déclaré : z
//
// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Le type est un ATTRIBUT SYNTHÉTISÉ : il REMONTE des feuilles vers la
//    racine. On type les fils, puis on en déduit le type du parent. C'est un
//    schéma de traduction dirigé par la syntaxe — la même mécanique servira à
//    ENGENDRER du code au chapitre 8, avec d'autres attributs.
//
// 2. L'ÉQUIVALENCE de types décide si deux types « vont ensemble ». Ici
//    int et int, float et float. La CONVERSION IMPLICITE (coercion) élargit
//    int -> float automatiquement, parce qu'aucune information n'est perdue —
//    l'inverse (float -> int) serait au contraire une troncature, refusée en
//    implicite.
//
// 3. Une comparaison (<) a toujours le type bool, quel que soit le type de ses
//    opérandes numériques : le type du RÉSULTAT n'est pas celui des opérandes.
//
// 4. Les ERREURS SÉMANTIQUES détectées ici — « int + bool », « z non
//    déclaré » — sont exactement celles que l'analyse syntaxique ne pouvait
//    pas voir (chapitre 1) : l'arbre est bien formé, mais dénué de sens. La
//    table des symboles (chapitre 6) fournit le type des variables.

Ce que la suite en fait

Le front-end est complet : le programme est lu (lexical), structuré (syntaxique), et son sens est vérifié (sémantique). L'arbre qui en sort est correct — reste à le traduire en code.

Le bloc V ouvre la synthèse. Le chapitre 8 introduit les représentations intermédiaires — le code à trois adresses, ce pivot entre l'arbre et la machine — et le chapitre 9 traduit les constructions du langage. La traduction dirigée par la syntaxe posée ici en est l'outil : on reprendra le même parcours d'arbre, en émettant du code au lieu de calculer un type.

À retenir