Analyse ascendante

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