Analyse descendante

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