Vérification de types

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