Grammaires pour la compilation

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));

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