L'analyse syntaxique est le cœur du cours, et ce chapitre en prépare le terrain. La suite de tokens produite par le lexeur (chapitre 2) est plate ; un programme, lui, est une structure : expressions imbriquées, blocs, conditions. Reconstruire cette structure demande une grammaire — et pas n'importe laquelle. Une grammaire mathématiquement correcte peut être inutilisable par un analyseur ; ce chapitre montre comment la mettre en forme.

Vous connaissez déjà les grammaires hors contexte depuis la Théorie des langages. On les reprend ici avec l'œil du compilateur : ce qui compte n'est plus seulement le langage engendré, mais la forme des arbres et l'aptitude de la grammaire à être analysée.

Arbre concret, arbre abstrait

L'analyse syntaxique produit un arbre. Il en existe deux variantes, qu'il faut distinguer.

L'arbre syntaxique concret (ou arbre de dérivation, cf. Théorie des langages) reflète toutes les règles appliquées, y compris les non-terminaux intermédiaaires et les détails de ponctuation. Pour 3 + 4 * 5 avec une grammaire à niveaux E → E + T, T → T * F, F → nombre, il contient des nœuds E, T, F en cascade, ainsi que les parenthèses éventuelles.

L'arbre syntaxique abstrait (AST) ne garde que l'essentiel du sens : les opérateurs et leurs opérandes. Le même 3 + 4 * 5 devient simplement :

1      (+)2      / \3     3  (*)4        / \5       4   5

Plus de T, de F, ni de parenthèses : elles ont joué leur rôle (fixer la structure) et disparaissent. C'est l'AST qui circule dans tout le reste du compilateur — analyse sémantique, génération de code. Le concret sert à l'analyse, l'abstrait à la suite.

Ambiguïté, priorité, associativité

Le danger d'une grammaire, on l'a vu en Théorie des langages, est l'ambiguïté : un mot ayant plusieurs arbres, donc plusieurs sens. Pour un compilateur, c'est rédhibitoire — 1 + 2 * 3 ne peut pas valoir tantôt 7, tantôt 9.

On lève l'ambiguïté en encodant priorité et associativité dans la structure de la grammaire, par des niveaux :

1E → E + T | T        (+ : priorité faible, en haut)2T → T * F | F        (* : priorité forte, plus bas)3F → ( E ) | nombre

La règle est mécanique : plus un opérateur est prioritaire, plus il est bas dans la grammaire — donc plus profond dans l'arbre, donc évalué en premier. Un niveau par priorité. Quant à l'associativité, elle se lit dans le sens de la récursivité : E → E + T (récursif à gauche) donne une addition associative à gauche, ce qui est correct pour - et / (5 - 3 - 1 doit valoir (5-3)-1).

Éliminer la récursivité gauche

Voici le premier obstacle de méthode. Une grammaire récursive à gauche — un non-terminal dont une règle commence par lui-même, comme E → E + T — est parfaite pour la lecture, mais fatale à l'analyse descendante (chapitre 4) : la fonction chargée d'analyser E commencerait par s'appeler elle-même sans consommer aucun token, en boucle infinie.

On l'élimine par une transformation mécanique, sans changer le langage engendré :

$A \to A\,\alpha \mid \beta \qquad\Longrightarrow\qquad A \to \beta\,A', \quad A' \to \alpha\,A' \mid \varepsilon.$

L'idée : au lieu d'empiler E à gauche, on écrit β (le cas de base) suivi d'une répétition de α. C'est le passage d'une récursion gauche à une récursion droite — équivalente pour le langage, mais analysable de haut en bas. Un effet de bord à connaître : la transformation inverse l'associativité (elle associe à droite), qu'il faudra rétablir à la construction de l'AST pour les opérateurs non commutatifs. L'exercice de ce chapitre déroule précisément cette transformation.

La factorisation gauche

Le second obstacle. Quand deux règles d'un même non-terminal commencent par le même préfixe, l'analyseur descendant ne peut pas choisir laquelle appliquer avec un seul token d'avance :

1instr → if ( E ) instr           (deux règles qui commencent par « if ( E ) instr »)2      | if ( E ) instr else instr

On factorise le préfixe commun dans une règle, et on repousse la partie qui diffère dans un non-terminal auxiliaire :

$A \to \gamma\,\beta_1 \mid \gamma\,\beta_2 \qquad\Longrightarrow\qquad A \to \gamma\,A', \quad A' \to \beta_1 \mid \beta_2.$

Après factorisation, l'analyseur lit d'abord le préfixe commun γ, puis décide entre β₁ et β₂ — un choix qu'un seul token d'avance suffit désormais à trancher.

Récursivité gauche et facteur commun sont les deux préparations qu'une grammaire doit subir avant l'analyse descendante. Le chapitre 4 les suppose faites.

À vous

L'exercice applique la transformation clé du chapitre : éliminer la récursivité gauche de E → E + T | T, et vérifier que la grammaire obtenue engendre exactement le même langage. Vous observerez l'effet sur l'associativité — le piège à connaître — et la seconde préparation utile, la factorisation gauche.

C'est la mise en forme qui rend possible l'analyseur descendant du chapitre suivant, prochaine couche du compilateur du TP.

// La grammaire des additions, telle qu'on l'écrit naturellement :
//   E -> E + T | T
// Elle est RÉCURSIVE À GAUCHE : le membre droit de la 1re règle commence par
// E lui-même. Un analyseur descendant récursif appellerait analyserE() qui
// rappellerait analyserE() sans rien consommer -> boucle infinie.
//
// La transformation standard : A -> A alpha | beta  devient
//   A  -> beta A'
//   A' -> alpha A' | epsilon
// Ici A = E, alpha = "+ T", beta = "T".

// On teste l'équivalence en ENGENDRANT les mots (jusqu'à une longueur), avec
// un terminal 't' pour T et le symbole '+'.

function motsGauche(max) {
  // E -> E + T | T   (récursive à gauche) : E = t (+ t)*
  const s = new Set();
  let courant = "t";
  while (courant.length <= max) { s.add(courant); courant += "+t"; }
  return s;
}

// ── À VOUS : engendrer avec la grammaire TRANSFORMÉE ────────────────────────
// E  -> T E'
// E' -> + T E' | epsilon
// (avec T = t). Écrire motsDroite(max) qui engendre le même ensemble.
function motsDroite(max) {
  const s = new Set();
  // à compléter : partir de "t", et tant que possible, ajouter "+t"
  return s;
}

// ── Vérification ────────────────────────────────────────────────────────────
const g = [...motsGauche(9)].sort();
const d = [...motsDroite(9)].sort();
console.log("gauche   :", g.join("  "));
console.log("droite   :", d.join("  "));
console.log("mêmes mots ?", JSON.stringify(g) === JSON.stringify(d));

function motsDroite(max) {
  // E -> T E' ; E' -> + T E' | epsilon  engendre t, t+t, t+t+t, ...
  // c'est-à-dire EXACTEMENT le même langage, mais en associant à DROITE
  // pendant la dérivation. L'ensemble des mots est identique.
  const s = new Set();
  let courant = "t";
  while (courant.length <= max) { s.add(courant); courant += "+t"; }
  return s;
}
// gauche et droite engendrent { t, t+t, t+t+t, ... } : mêmes mots. ✓

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. La récursivité gauche est INCOMPATIBLE avec la descente récursive : la
//    fonction analyserE() commencerait par s'appeler elle-même sans avoir
//    consommé le moindre token -> récursion infinie. C'est un obstacle de
//    MÉTHODE, pas de langage : le langage est parfaitement analysable, c'est
//    l'écriture de la grammaire qui bloque.
//
// 2. La transformation A -> A alpha | beta  =>  A -> beta A', A' -> alpha A' | eps
//    engendre le MÊME langage. On ne change pas ce qui est reconnu, seulement
//    la FORME des règles, pour la rendre analysable de haut en bas.
//
// 3. Attention : cette transformation change l'ASSOCIATIVITÉ implicite des
//    arbres (elle associe à droite). Pour un opérateur comme la soustraction,
//    il faudra rétablir l'associativité gauche à la construction de l'arbre
//    (chapitre 4) — sinon « 5 - 3 - 1 » se calculerait 5 - (3 - 1) = 3 au lieu
//    de (5 - 3) - 1 = 1.
//
// 4. L'autre préparation courante est la FACTORISATION GAUCHE : deux règles
//    d'un même non-terminal qui commencent pareil (A -> a b | a c) empêchent
//    de choisir avec un seul symbole d'avance ; on factorise en
//    A -> a A', A' -> b | c. Récursivité gauche et facteur commun sont les
//    deux obstacles que le chapitre 4 exige d'avoir levés.

Ce que la suite en fait

La grammaire est prête. Les deux chapitres suivants la mettent au travail selon deux stratégies opposées et complémentaires.

Le chapitre 4 construit l'arbre par le haut (analyse descendante) : on part de l'axiome et on prédit les règles à appliquer — la méthode la plus intuitive, celle qu'on écrit à la main, et qui exige justement une grammaire débarrassée de récursivité gauche et de facteurs communs. Le chapitre 5 construira l'arbre par le bas (analyse ascendante), plus puissante mais moins intuitive.

À retenir

Nous entrons dans l'analyse syntaxique proprement dite, avec la méthode la plus intuitive : l'analyse descendante. Elle construit l'arbre par le haut — on part de l'axiome de la grammaire et on descend vers les feuilles, en prédisant à chaque étape quelle règle appliquer. C'est la méthode qu'on écrit le plus naturellement à la main, et le prolongement direct de l'analyse LL(1) vue en Théorie des langages.

Le cours en fait un choix pédagogique : écrire d'abord un analyseur descendant à la main, avant de laisser un outil (chapitre 5) faire le travail. On comprend ainsi ce que l'outil automatise.

La descente récursive

L'idée est d'une simplicité remarquable : une fonction par non-terminal. La fonction chargée d'un non-terminal lit les tokens correspondant à l'une de ses règles, en appelant les fonctions des non-terminaux qui y figurent. La structure du code calque celle de la grammaire.

Pour la grammaire des expressions préparée au chapitre 3 :

1E → T (('+' | '-') T)*2T → F (('*' | '/') F)*3F → nombre | '(' E ')'

on écrit trois fonctions E(), T(), F(). E() appelle T(), boucle tant qu'elle voit + ou -, et rappelle T() ; F() traite un nombre ou, sur une parenthèse ouvrante, rappelle E(). Deux propriétés émergent gratuitement de cette structure, sans une ligne de code dédiée :

• la priorité vient de l'imbrication des appels : E appelle T qui appelle F, donc * est « plus bas » et lié plus fort que + ;
• l'associativité gauche vient de la boucle qui accumule le résultat de gauche à droite.

C'est ce que construit l'exercice — un analyseur qui, au passage, évalue l'expression (un premier schéma dirigé par la syntaxe, chapitre 7).

Prédire : PREMIER et SUIVANT

Pour être prédictif — choisir la bonne règle en ne regardant qu'un token d'avance, le « 1 » de LL(1) — l'analyseur a besoin de deux ensembles, déjà croisés en Théorie des langages.

PREMIER(α) est l'ensemble des terminaux par lesquels peut commencer un mot dérivé de α. Il répond à : « si je vois ce token, cette règle peut-elle démarrer ? ». Pour F → nombre | ( E ), $\text{PREMIER}(F) = \{\text{nombre}, \text{(}\}$.

SUIVANT(A) est l'ensemble des terminaux qui peuvent suivre immédiatement le non-terminal A dans une dérivation. Il n'est utile que pour les règles pouvant produire le vide (A → ε) : quand faut-il choisir la règle vide ? Réponse : quand le token courant est dans SUIVANT(A).

Ces deux ensembles se calculent mécaniquement à partir de la grammaire, et alimentent soit les tests d'un analyseur écrit à la main, soit la table LL(1) ci-dessous.

La table LL(1)

Écrire les fonctions à la main est commode pour une petite grammaire ; pour une grande, on préfère un analyseur piloté par une table. La table LL(1) est un tableau à double entrée (non-terminal × token courant) qui indique la règle à appliquer :

1              nombre     +        *        (        )       $2   E          E→T E'                       E→T E'3   E'                    E'→+T E'                  E'→ε    E'→ε4   ...

On la remplit avec PREMIER et SUIVANT : la règle A → α va dans la case (A, t) pour chaque t de PREMIER(α), et dans les cases (A, t) pour t de SUIVANT(A) si α peut produire ε. Un analyseur générique lit alors la table, une pile à la main, sans code spécifique à la grammaire.

Une grammaire est LL(1) exactement quand cette table n'a jamais deux règles dans une même case : un seul token d'avance suffit toujours à décider. C'est la condition qu'imposaient l'élimination de la récursivité gauche et la factorisation gauche du chapitre 3.

Limites du prédictif, et récupération sur erreur

L'analyse LL(1) est simple et rapide, mais limitée. Certaines grammaires ne sont pas LL(1) même après préparation : un seul token d'avance ne suffit pas à trancher. On peut parfois passer à LL(k) (k tokens d'avance), mais la vraie réponse, quand LL(1) ne suffit pas, est l'analyse ascendante du chapitre 5, strictement plus puissante.

Enfin, un analyseur ne doit pas s'effondrer à la première faute. La récupération sur erreur consiste, après un token inattendu, à se resynchroniser — typiquement en sautant des tokens jusqu'à un point de reprise sûr (un ;, un }) — pour continuer l'analyse et signaler plusieurs erreurs en une compilation. C'est le mode « panique », simple et efficace, que tout compilateur pratique.

À vous

L'exercice construit la prochaine couche du compilateur du TP : un analyseur descendant récursif qui analyse et évalue une expression arithmétique — une fonction par non-terminal, exactement comme la grammaire. Vous vérifierez que priorité (1+2*3 = 7) et associativité gauche (10-3-1 = 6) tombent de la structure des appels et de la boucle d'accumulation, sans code dédié.

C'est l'analyseur qu'on écrit à la main ; le chapitre 5 montrera comment un outil en engendre un plus puissant.

// Grammaire (débarrassée de récursivité gauche, cf. chapitre 3), en forme
// itérative — la boucle joue le rôle de la récursion droite :
//   E -> T (('+' | '-') T)*
//   T -> F (('*' | '/') F)*
//   F -> nombre | '(' E ')'
//
// On analyse ET on évalue en même temps : c'est un schéma dirigé par la
// syntaxe (chapitre 7). Entrée : une liste de tokens.

function analyser(src) {
  // Lexeur minimal : chiffres, opérateurs, parenthèses.
  const toks = src.match(/\d+|[-+*/()]/g) || [];
  let i = 0;
  const voir = () => toks[i];
  const manger = (t) => { if (t && toks[i] !== t) throw new Error("attendu " + t + " mais " + toks[i]); return toks[i++]; };

  // F -> nombre | ( E )
  function F() {
    if (voir() === "(") { manger("("); const v = E(); manger(")"); return v; }
    const n = manger();
    if (!/^\d+$/.test(n)) throw new Error("nombre attendu, reçu " + n);
    return Number(n);
  }

  // ── À VOUS : T et E ─────────────────────────────────────────────────────
  // T -> F (('*'|'/') F)* : associe à gauche en accumulant dans une boucle.
  function T() {
    let v = F();
    // à compléter : tant que le prochain token est '*' ou '/', consommer
    // l'opérateur, lire un F, et combiner (v = v * ... ou v / ...)
    return v;
  }
  // E -> T (('+'|'-') T)* : même schéma avec + et -.
  function E() {
    let v = T();
    // à compléter
    return v;
  }

  const v = E();
  if (i < toks.length) throw new Error("tokens en trop : " + toks.slice(i).join(" "));
  return v;
}

// ── Vérification ────────────────────────────────────────────────────────────
for (const s of ["1+2*3", "(1+2)*3", "10-3-1", "2*3+4*5", "20/2/5"]) {
  try { console.log(s.padEnd(10) + " = " + analyser(s)); }
  catch (e) { console.log(s.padEnd(10) + " ! " + e.message); }
}

  function T() {
    let v = F();
    while (voir() === "*" || voir() === "/") {
      const op = manger();
      const d = F();
      v = op === "*" ? v * d : v / d;   // combine à GAUCHE : (v op d) devient le nouveau v
    }
    return v;
  }
  function E() {
    let v = T();
    while (voir() === "+" || voir() === "-") {
      const op = manger();
      const d = T();
      v = op === "+" ? v + d : v - d;
    }
    return v;
  }

// Résultats : 1+2*3 = 7 | (1+2)*3 = 9 | 10-3-1 = 6 | 2*3+4*5 = 26 | 20/2/5 = 2.

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Une FONCTION PAR NON-TERMINAL : E(), T(), F(). La structure du code
//    calque exactement celle de la grammaire — c'est la marque de l'analyse
//    descendante récursive, la plus intuitive à écrire à la main.
//
// 2. La PRIORITÉ émerge de l'imbrication des appels : E() appelle T() qui
//    appelle F(). Le * est donc « plus bas » et se calcule avant le + —
//    « 1+2*3 » donne 7, pas 9, sans aucun code dédié aux priorités.
//
// 3. L'ASSOCIATIVITÉ GAUCHE vient de la BOUCLE qui accumule dans v :
//    « 10-3-1 » se calcule ((10-3)-1) = 6, et non (10-(3-1)) = 8. Rappel du
//    chapitre 3 : la transformation en récursion droite aurait associé à
//    droite ; la boucle rétablit la bonne associativité.
//
// 4. Pour DÉCIDER quelle règle appliquer, on ne regarde qu'UN token d'avance
//    (voir()) — c'est le « 1 » de LL(1). Cela n'est possible que parce que la
//    grammaire a été préparée au chapitre 3 : sans élimination de la
//    récursivité gauche, E() bouclerait à l'infini.
//
// 5. Le token « en trop » ou « attendu X » déclenche une erreur SYNTAXIQUE.
//    Un vrai analyseur s'en remettrait (récupération sur erreur) pour
//    signaler plusieurs fautes.

Ce que la suite en fait

L'analyse descendante prédit les règles depuis l'axiome — intuitive, mais limitée aux grammaires LL(1), et exigeante sur leur forme (pas de récursivité gauche). Le chapitre 5 prend le problème à l'envers : l'analyse ascendante construit l'arbre depuis les feuilles, en reconnaissant les membres droits des règles au fur et à mesure.

Plus puissante (elle accepte la récursivité gauche, et une classe de grammaires bien plus large), elle est aussi moins intuitive — et sa construction de tables est le point qui coince du cours. C'est elle que Bison met en œuvre.

À retenir

L'analyse descendante prédit les règles depuis l'axiome. L'analyse ascendante prend le problème à l'envers : elle construit l'arbre par le bas, depuis les feuilles, en reconnaissant des membres droits de règles à mesure qu'ils apparaissent, pour les réduire à leur membre gauche. Plus puissante que la descendante — elle accepte la récursivité gauche et une classe de grammaires bien plus large — elle est le moteur de Bison et de la plupart des générateurs sérieux.

C'est aussi le chapitre le plus exigeant, et le point qui coince du cours : la construction des tables LR. Items, fermetures, transitions restent abstraits tant qu'on n'a pas déroulé un automate entier à la main sur une grammaire minuscule. L'exercice — et une feuille de papier — sont ici indispensables.

Décalage-réduction

L'analyse ascendante manipule une pile et effectue, à chaque étape, l'une de deux actions :

• décalage (shift) : empiler le prochain token d'entrée ;
• réduction (reduce) : quand le sommet de la pile correspond au membre droit d'une règle A → β, remplacer ce β par le non-terminal A.

On répète jusqu'à réduire toute l'entrée à l'axiome : le programme est alors reconnu. C'est la stratégie décalage-réduction. Sur x avec la grammaire S → x : on décale x, on reconnaît le membre droit de la règle 2, on réduit x en S. Terminé.

Toute la difficulté tient en une question : à chaque instant, faut-il décaler ou réduire, et si on réduit, par quelle règle ? Répondre demande de savoir « où l'on en est » dans la reconnaissance de chaque règle possible — c'est le rôle des items.

Items et automate LR(0)

Un item LR(0) est une règle munie d'un point qui marque jusqu'où le membre droit a été reconnu :

1S → ( · S )     j'ai lu '(', j'attends un S, puis ')'2S → x ·         j'ai reconnu tout le membre droit : je peux réduire

Un point devant un terminal appelle un décalage ; un point à la fin signale une réduction. On regroupe les items en états, et deux opérations construisent l'automate — exactement les analogues LR de ce que vous connaissez :

• la fermeture (closure) : si le point précède un non-terminal B, alors toutes les règles de B peuvent commencer ici ; on ajoute leurs items « point au début ». C'est l'équivalent de l'ensemble PREMIER.
• la transition GOTO(I, X) : avancer le point sur le symbole X dans tous les items où c'est possible, puis fermer. C'est la transition de l'automate.

Les états sont des ensembles d'items, engendrés par fermetures et transitions successives depuis l'item de départ — exactement comme la déterminisation construisait des ensembles d'états en Théorie des langages. Le résultat est l'automate LR(0), qui reconnaît les préfixes viables de la grammaire. C'est cet automate que l'exercice vous fait construire, closure comprise.

SLR(1), LR(1) canonique, LALR(1)

L'automate LR(0) ignore le contexte droit : il réduit dès qu'il voit un item complet, sans regarder le token suivant. Cela suffit rarement. On raffine en ajoutant un token de prévision (lookahead), d'où une famille de méthodes de puissance croissante :

LALR(1) est le compromis retenu par Bison et Yacc : il capture la quasi-totalité des grammaires de langages réels avec des tables de taille raisonnable. SUIVANT, croisé au chapitre 4, réapparaît ici comme la prévision de la méthode SLR — les deux mondes, descendant et ascendant, partagent leurs ingrédients de base.

Les conflits

Quand l'automate ne peut pas décider, il y a conflit — et c'est précisément ce que signale un message d'erreur de Bison :

• conflit décalage/réduction : dans un même état, on pourrait décaler le token courant ou réduire par une règle. L'exemple canonique est le else pendant (dangling else) : après if (E) instr, faut-il réduire ce if sans else, ou décaler le else qui suit ? Bison le résout par défaut en décalant (le else se rattache au if le plus proche), ce qui est presque toujours le comportement voulu.
• conflit réduction/réduction : deux règles différentes pourraient être réduites dans le même état. Plus grave, il révèle en général une grammaire mal conçue.

L'essentiel à comprendre : un conflit n'est pas un bug de l'outil, c'est l'automate qui constate qu'un token d'avance ne suffit pas à trancher. Savoir lire un état LR(0) — repérer qu'il contient à la fois une réduction et un décalage possibles — c'est savoir d'où vient concrètement le message.

Bison, et LL contre LR

Bison (successeur libre de Yacc) engendre un analyseur ascendant LALR(1) à partir d'une grammaire annotée d'actions. On écrit les règles, Bison construit l'automate et les tables, et signale les conflits — qu'il faut alors savoir interpréter. Le choix du cours : construire un automate LR(0) à la main avant de lancer Bison, pour comprendre ce que l'outil calcule.

Le bilan entre les deux grandes familles :

En pratique : LL(1) écrit à la main pour un petit langage, LR/LALR via un outil pour tout le reste.

À vous

L'exercice attaque le point qui coince de front : construire l'automate LR(0) d'une grammaire de trois règles. Vous implémentez la fermeture (fermer un ensemble d'items), GOTO engendre la collection canonique des états, et vous repérez les états de réduction (point à la fin) et de décalage.

Faites-le aussi sur papier : c'est le seul moyen de rendre concrets items, fermetures et transitions — et de reconnaître, plus tard, d'où vient un conflit signalé par Bison.

// Grammaire minuscule, augmentée (règle 0). '(' ')' 'x' sont des terminaux,
// S' et S des non-terminaux.
//   0 : S' -> S
//   1 : S  -> ( S )
//   2 : S  -> x
const GRAMMAIRE = [
  { g: "S'", d: ["S"] },
  { g: "S",  d: ["(", "S", ")"] },
  { g: "S",  d: ["x"] },
];
const nonTerminaux = new Set(["S'", "S"]);

// Un ITEM = une règle avec un point. On le note "S -> ( . S )".
function item(i, pos) {
  const r = GRAMMAIRE[i];
  const d = [...r.d]; d.splice(pos, 0, ".");
  return r.g + " -> " + d.join(" ");
}
function apresPoint(it) {
  const t = it.split(" ");
  const k = t.indexOf(".");
  return t[k + 1];   // symbole juste après le point, ou undefined si point à la fin
}

// ── À VOUS : CLOSURE ────────────────────────────────────────────────────────
// Règle : pour tout item « A -> alpha . B beta » avec B non-terminal, ajouter
// tous les items « B -> . gamma » (point au début), et recommencer jusqu'à
// stabilité.
function closure(items) {
  const ens = new Set(items);
  let change = true;
  while (change) {
    change = false;
    for (const it of [...ens]) {
      const B = apresPoint(it);
      if (B && nonTerminaux.has(B)) {
        // à compléter : pour chaque règle GRAMMAIRE[i] dont g === B,
        // ajouter item(i, 0) à 'ens' ; noter change = true si nouveau.
      }
    }
  }
  return [...ens].sort();
}

// GOTO(I, X) : avancer le point sur X dans tous les items où c'est possible,
// puis fermer.
function goto(items, X) {
  const avances = [];
  for (const it of items) {
    if (apresPoint(it) === X) {
      const t = it.split(" "); const k = t.indexOf(".");
      [t[k], t[k + 1]] = [t[k + 1], t[k]];   // échange point et symbole
      avances.push(t.join(" "));
    }
  }
  return avances.length ? closure(avances) : null;
}

// ── Collection canonique des états ──────────────────────────────────────────
const etats = [];
const cle = (I) => I.join(" | ");
const depart = closure([item(0, 0)]);   // closure de { S' -> . S }
etats.push(depart);
const transitions = [];
for (let s = 0; s < etats.length; s++) {
  const symboles = new Set(etats[s].map(apresPoint).filter(Boolean));
  for (const X of symboles) {
    const J = goto(etats[s], X);
    if (!J) continue;
    let idx = etats.findIndex((E) => cle(E) === cle(J));
    if (idx < 0) { etats.push(J); idx = etats.length - 1; }
    transitions.push([s, X, idx]);
  }
}

console.log(etats.length + " états LR(0) :\n");
etats.forEach((I, s) => { console.log("I" + s + " :"); I.forEach((it) => console.log("   " + it)); });
console.log("\ntransitions :");
transitions.forEach(([a, X, b]) => console.log("   I" + a + " --" + X + "--> I" + b));

function closure(items) {
  const ens = new Set(items);
  let change = true;
  while (change) {
    change = false;
    for (const it of [...ens]) {
      const B = apresPoint(it);
      if (B && nonTerminaux.has(B)) {
        for (let i = 0; i < GRAMMAIRE.length; i++) {
          if (GRAMMAIRE[i].g === B) {
            const nouv = item(i, 0);
            if (!ens.has(nouv)) { ens.add(nouv); change = true; }
          }
        }
      }
    }
  }
  return [...ens].sort();
}

// ── Résultat (5 états) ──────────────────────────────────────────────────────
//  I0 : S' -> . S | S -> . ( S ) | S -> . x
//  I1 : S' -> S .                          (GOTO I0 sur S)
//  I2 : S -> ( . S ) | S -> . ( S ) | S -> . x   (GOTO I0 sur '(')
//  I3 : S -> x .                           (GOTO I0 sur x)
//  I4 : S -> ( S . )                        (GOTO I2 sur S)
//  I5 : S -> ( S ) .                        (GOTO I4 sur ')')
//
// ── Ce que l'exercice enseigne (le point qui coince) ────────────────────────
//
// 1. Un ITEM est une règle avec un POINT marquant « jusqu'où on a reconnu ».
//    « S -> ( . S ) » signifie : j'ai lu '(', j'attends un S, puis ')'.
//
// 2. La CLOSURE rend explicite ce qu'on peut commencer à reconnaître : si le
//    point précède un non-terminal B, alors TOUTES les règles de B peuvent
//    démarrer ici, donc on ajoute leurs items « point au début ». C'est
//    l'équivalent LR de l'ensemble PREMIER.
//
// 3. GOTO(I, X) = avancer le point sur X, puis fermer. C'est la TRANSITION de
//    l'automate : les états sont des ENSEMBLES d'items, exactement comme la
//    déterminisation transformait des ensembles d'états (Théorie des langages).
//
// 4. Un item « point à la fin » (S -> x .) est un état de RÉDUCTION : on a
//    reconnu tout un membre droit, on peut le remplacer par le membre gauche.
//    Un item « point devant un terminal » appelle un DÉCALAGE (shift).
//    Ici aucun état ne mélange les deux de façon ambiguë : la grammaire est
//    LR(0). Quand un état contient à la fois une réduction et un décalage
//    possible sur le même symbole, c'est un CONFLIT décalage/réduction — le
//    message d'ambiguïté que crache Bison.
//
// Construire cet automate À LA MAIN, sur trois règles, est le seul moyen de
// rendre concrets items, fermetures et transitions. Faites-le sur papier
// aussi.

Ce que la suite en fait

Le bloc III est complet : à partir d'une suite de tokens, vous savez construire l'arbre syntaxique, par le haut ou par le bas. Mais un arbre bien formé n'est pas encore un programme correct : x = y + 1 est syntaxiquement impeccable même si y n'a jamais été déclarée, ou si y est une chaîne.

Le bloc IV donne un sens à l'arbre. Le chapitre 6 construit la table des symboles — qui suit les déclarations et les portées — et le chapitre 7 s'en sert pour la vérification de types. C'est là que les erreurs sémantiques du chapitre 1, invisibles à l'analyse syntaxique, sont enfin détectées.

À retenir