Traduction des constructions

Le chapitre 8 a linéarisé une expression en code à trois adresses. Mais un programme, ce sont surtout des constructions de contrôle : affectations, conditions, boucles, appels. Les traduire révèle une vérité inconfortable et féconde : au niveau intermédiaire, ni if ni while n'existent. Il n'y a que des étiquettes et des sauts. Toute la richesse du contrôle se ramène à ce squelette — celui du processeur.

C'est le chapitre le plus dense du bloc. On y consacre l'essentiel à if et while, les plus importants, et à l'évaluation en court-circuit des booléens — au lieu de survoler toutes les constructions.

Expressions et affectations

Le cas de base prolonge directement le chapitre 8. Une affectation x = e engendre le code qui calcule e dans un temporaire, puis copie ce temporaire dans x :

1x = a * b + 1      devient      t1 = a * b2                                t2 = t1 + 13                                x  = t2

C'est de la traduction dirigée par la syntaxe (chapitre 7) : l'attribut synthétisé « adresse » remonte de l'arbre de e, et la racine émet la copie finale. Rien de nouveau, sinon le point de destination.

Le contrôle par sauts

Voici le cœur du chapitre. Une machine ne connaît que deux primitives de contrôle, qu'on adopte au niveau intermédiaire :

• ifFalse C goto L : sauter à l'étiquette L si la condition C est fausse ;
• goto L : saut inconditionnel.

Toute structure de haut niveau se traduit en ces primitives. Le if (C) alors :

1    ifFalse (C) goto Lfin2    ... code de « alors » ...3Lfin:

Le if (C) alors sinon enjambe le bloc sinon par un goto après le bloc alors :

1    ifFalse (C) goto Lsinon2    ... code de « alors » ...3    goto Lfin4Lsinon:5    ... code de « sinon » ...6Lfin:

Et le while (C) corps, qui teste en tête, revient tester après chaque tour :

1Ldebut:2    ifFalse (C) goto Lfin3    ... code du corps ...4    goto Ldebut5Lfin:

Ces trois schémas sont à connaître par cœur : ce sont les briques dont tout programme impératif est fait. L'exercice construit celui du while.

Expressions booléennes et court-circuit

Comment évaluer la condition C elle-même, quand c'est une expression booléenne composée comme a < b && c < d ? Deux stratégies, mais une seule est correcte pour un langage courant.

On pourrait calculer la valeur booléenne complète (évaluer a < b, puis c < d, puis le &&), la ranger dans un temporaire, et la tester. Mais la sémantique de la plupart des langages impose l'évaluation en court-circuit : dès que a < b est faux, le résultat du && est faux, et c < d ne doit pas être évalué du tout.

Ce n'est pas une optimisation, c'est une exigence sémantique. Elle est vitale quand la seconde condition a un effet de bord, ou pourrait échouer :

1p != NULL && p->x > 0

Ici, p->x ne doit être lu que si p est non nul. Un calcul complet déréférencerait p même quand il est nul — un plantage. Le court-circuit l'interdit.

On l'obtient en traduisant && directement en sauts, jamais en calculant un booléen :

1a < b && c < d      devient      ifFalse (a < b) goto Lfaux2                                 ifFalse (c < d) goto Lfaux3                                 goto Lvrai

Si a < b est faux, on saute à Lfaux avant même d'atteindre le test de c < d. Le || symétrique saute vers Lvrai dès qu'une condition est vraie. C'est la seconde partie de l'exercice.

Le patchage de listes

Un problème pratique surgit à l'émission. Quand on écrit ifFalse (C) goto Lfin, l'étiquette Lfin n'est pas encore connue : elle marque un point du code qu'on n'a pas encore engendré (un saut vers l'avant). Comment remplir la cible d'un saut qu'on émet avant de savoir où il mène ?

La technique du patchage de listes (backpatching) répond à cela, et permet d'engendrer tout le code en une seule passe :

1. on émet le saut avec une cible en blanc ;
2. on retient l'instruction incomplète dans une liste (la liste des sauts à compléter) ;
3. quand l'étiquette de destination devient connue, on parcourt la liste et on remplit toutes les cibles d'un coup.

C'est un mécanisme élégant mais techniquement dense — la raison pour laquelle ce bloc mérite qu'on s'attarde sur if et while plutôt que de courir après toutes les constructions. En comprendre le principe suffit en L3 : émettre, retenir, compléter.

Appels, tableaux, structures

Les constructions restantes se traduisent selon des schémas que l'on cite ici pour la complétude.

Un appel de fonction f(a, b) engendre le passage des paramètres puis l'appel :

1param a2param b3t = call f, 2      (2 = nombre d'arguments)

Les détails — où vont les paramètres, comment la fonction retourne — relèvent de l'environnement d'exécution du chapitre 10.

L'accès à un tableau T[i] calcule une adresse : base(T) + i × taille_élément. C'est pourquoi T[i] équivaut à *(T + i) — l'indexation est de l'arithmétique d'adresses. L'accès à un champ de structure s.champ se traduit de même, par un décalage fixe connu de la table des symboles : base(s) + décalage(champ).

Ces schémas partagent tous la même logique : ramener une construction de haut niveau à des opérations à trois adresses sur des adresses et des sauts.

À vous

L'exercice traduit deux constructions au cœur du chapitre : une boucle while en étiquettes et sauts, puis l'évaluation en court-circuit d'un &&. Vous constaterez que while n'existe pas au niveau intermédiaire — seulement son squelette de sauts — et que le court-circuit se traduit directement en branchements, garantissant qu'une seconde condition n'est jamais évaluée à tort.

C'est la couche du compilateur du TP qui transforme un programme structuré en une suite d'instructions et de sauts, prête pour la machine.

// Au niveau intermédiaire, il n'y a ni « while » ni « if » : seulement des
// étiquettes (Ln:) et des sauts. Deux primitives suffisent :
//   ifFalse C goto L   : sauter à L si la condition C est fausse
//   goto L             : saut inconditionnel
//
// On traduit :   while (x < n) { x = x + 1; }
//
// Schéma standard d'une boucle while :
//   Ldebut:                      <- étiquette de test
//     ifFalse (x < n) goto Lfin  <- si faux, on sort
//     ...corps...
//     goto Ldebut                <- on retourne tester
//   Lfin:

let code3a = [];
let nEtiq = 0;
function nouvelleEtiquette() { return "L" + (++nEtiq); }
function emettre(s) { code3a.push(s); }

// ── À VOUS : traduireWhile(cond, corps) ─────────────────────────────────────
// 'cond' est une chaîne (ex. "x < n"), 'corps' un tableau d'instructions déjà
// engendrées (ex. ["x = x + 1"]). Émettre le schéma ci-dessus.
function traduireWhile(cond, corps) {
  const Ldebut = nouvelleEtiquette();
  const Lfin = nouvelleEtiquette();
  // à compléter :
  //   emettre(Ldebut + ":");
  //   emettre("ifFalse (" + cond + ") goto " + Lfin);
  //   for (const i of corps) emettre("  " + i);
  //   emettre("goto " + Ldebut);
  //   emettre(Lfin + ":");
}

traduireWhile("x < n", ["x = x + 1"]);
console.log("while (x < n) x = x + 1;");
code3a.forEach((s) => console.log("   " + s));

// ── Court-circuit d'un && ───────────────────────────────────────────────────
// « a < b && c < d » ne s'évalue PAS en calculant les deux comparaisons : si
// « a < b » est faux, on saute directement à Lfaux SANS évaluer « c < d ».
// À VOUS : compléter le court-circuit pour sauter vers Lfaux dès le 1er faux.
code3a = []; nEtiq = 0;
function traduireEt(condG, condD, Lvrai, Lfaux) {
  // à compléter : si condG est faux -> Lfaux ; sinon tester condD ;
  //               si condD est faux -> Lfaux ; sinon goto Lvrai.
}
const Lv = "Lvrai", Lf = "Lfaux";
traduireEt("a < b", "c < d", Lv, Lf);
console.log("\na < b && c < d (court-circuit) :");
code3a.forEach((s) => console.log("   " + s));

function traduireWhile(cond, corps) {
  const Ldebut = nouvelleEtiquette();
  const Lfin = nouvelleEtiquette();
  emettre(Ldebut + ":");
  emettre("ifFalse (" + cond + ") goto " + Lfin);
  for (const i of corps) emettre("  " + i);
  emettre("goto " + Ldebut);
  emettre(Lfin + ":");
}
// while (x < n) x = x + 1; devient :
//   L1:
//     ifFalse (x < n) goto L2
//     x = x + 1
//     goto L1
//   L2:

function traduireEt(condG, condD, Lvrai, Lfaux) {
  emettre("ifFalse (" + condG + ") goto " + Lfaux);   // 1er faux -> on abandonne
  emettre("ifFalse (" + condD + ") goto " + Lfaux);   // 2e faux -> idem
  emettre("goto " + Lvrai);                            // les deux vrais
}
// a < b && c < d (court-circuit) :
//   ifFalse (a < b) goto Lfaux    <- si a < b est faux, c < d n'est JAMAIS évalué
//   ifFalse (c < d) goto Lfaux
//   goto Lvrai

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. AU NIVEAU INTERMÉDIAIRE, if et while N'EXISTENT PAS. Il n'y a que des
//    étiquettes et des sauts (goto, ifFalse ... goto). Toute structure de
//    contrôle se ramène à ce squelette — c'est déjà le niveau de la machine.
//
// 2. Le schéma du WHILE : tester en tête (Ldebut), sortir si faux (vers Lfin),
//    exécuter le corps, revenir tester (goto Ldebut). Le if est plus simple :
//    « ifFalse C goto Lfin ; corps ; Lfin: ». Le if-else ajoute un « goto »
//    par-dessus le bloc else pour l'enjamber après le bloc then.
//
// 3. Le COURT-CIRCUIT est une propriété SÉMANTIQUE, pas une optimisation :
//    « a < b && c < d » ne DOIT PAS évaluer « c < d » si « a < b » est faux.
//    C'est vital quand la 2e condition a un effet ou pourrait planter :
//    « p != NULL && p->x > 0 » ne déréférence p que s'il est non nul. On
//    l'obtient en traduisant && directement en SAUTS, pas en calculant un
//    booléen puis en testant.
//
// 4. Les étiquettes de destination ne sont pas toujours connues au moment où
//    l'on émet le saut (« goto ??? » vers l'avant). La technique du PATCHAGE
//    DE LISTES (backpatching) consiste à laisser la cible en blanc, à retenir
//    l'instruction dans une liste, et à la COMPLÉTER une fois l'étiquette
//    connue. C'est ce qui permet d'engendrer le code en une seule passe.

Ce que la suite en fait

Le code intermédiaire est produit : expressions, affectations, contrôle, appels — tout est ramené à des instructions à trois adresses et à des sauts. Mais il reste abstrait sur un point majeur : où vivent les variables, et comment un appel de fonction s'organise réellement en mémoire.

Le bloc VI descend au niveau de la machine. Le chapitre 10 traite l'organisation mémoire — segments, pile d'appels, enregistrements d'activation — c'est-à-dire où atterrissent les param et les variables locales de ce chapitre. Le chapitre 11 produira enfin le code cible et l'optimisera.

À retenir