Le chapitre 6 s'est terminé sur une limite : les automates finis ne savent pas compter, et $a^n b^n$ leur échappe. Pour aller plus loin, on change de point de vue. Jusqu'ici, on reconnaissait les langages — on testait si un mot appartenait. Une grammaire fait l'inverse : elle engendre les mots, en partant d'un symbole de départ et en le réécrivant selon des règles. C'est le même mécanisme qui décrit la syntaxe des langages de programmation, du XML, des formats de données — et c'est la porte d'entrée de la compilation, au chapitre 9.

Ce basculement — de reconnaître à engendrer — n'est pas qu'un changement de vocabulaire : il ouvre une classe de langages strictement plus large que les réguliers.

La définition

Une grammaire hors contexte (ou algébrique, en anglais context-free grammar) est la donnée de quatre éléments $(V, \Sigma, R, S)$ :

Une règle $A \to \alpha$ se lit : « la variable $A$ peut être remplacée par $\alpha$ », où $\alpha$ est une suite quelconque de terminaux et de variables (éventuellement $\varepsilon$). Le nom « hors contexte » vient de là : on remplace $A$ quel que soit son entourage — le contexte autour de $A$ n'intervient pas. C'est cette liberté qui rend le modèle à la fois puissant et maniable.

L'exemple fondateur, celui qui justifie tout le bloc, engendre $a^n b^n$ :

1S → a S b2S → ε

Deux règles suffisent là où aucun automate fini ne pouvait réussir.

Dérivation et langage engendré

Dériver, c'est appliquer les règles depuis l'axiome jusqu'à n'obtenir que des terminaux. On note $\Rightarrow$ une étape de réécriture. Pour $aabb$ :

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb.$

À chaque étape, on remplace une variable par le membre droit d'une de ses règles. La dernière étape emploie $S \to \varepsilon$ pour terminer. Le langage engendré $L(G)$ est l'ensemble de tous les mots de terminaux qu'on peut obtenir ainsi depuis $S$.

Observez pourquoi cette grammaire tient le compte que l'automate ne pouvait pas tenir : chaque application de $S \to aSb$ ajoute un $a$ et un $b$ à la fois, de part et d'autre. L'égalité du nombre de $a$ et de $b$ n'est pas surveillée par une mémoire — elle est structurelle, portée par la forme de la règle récursive. C'est le gain conceptuel du chapitre.

Un langage engendré par une grammaire hors contexte est appelé langage algébrique (ou hors contexte). Tout langage régulier est algébrique — les grammaires font au moins autant que les automates —, mais la réciproque est fausse : $a^n b^n$ est algébrique et non régulier. La classe s'est bel et bien élargie.

L'arbre de dérivation

Une dérivation peut se représenter par un arbre de dérivation (ou arbre syntaxique) : la racine est l'axiome $S$, chaque nœud interne est une variable, ses enfants sont le membre droit de la règle appliquée, et les feuilles lues de gauche à droite donnent le mot engendré.

L'arbre est plus informatif que la suite de dérivations, car il fait abstraction de l'ordre dans lequel on a réécrit les variables. Deux dérivations qui ne diffèrent que par cet ordre — l'une réécrivant toujours la variable la plus à gauche (dérivation gauche), l'autre la plus à droite — donnent le même arbre. L'arbre capture la structure du mot ; c'est lui, et non la séquence d'étapes, qui porte le sens.

C'est capital pour la suite : dans un compilateur, l'arbre de dérivation d'une expression est sa structure de calcul. L'arbre de 1+2*3 dit dans quel ordre effectuer les opérations.

L'ambiguïté

Une grammaire est ambiguë s'il existe un mot admettant plus d'un arbre de dérivation. L'ambiguïté n'est pas un détail théorique : elle signifie que la structure d'un mot n'est pas déterminée, donc que son sens ne l'est pas.

La grammaire naïve des expressions arithmétiques est l'exemple canonique :

1E → E + E | E * E | ( E ) | nombre

Le mot 1+2*3 a deux arbres : l'un met le + à la racine et calcule 1+(2*3) = 7, l'autre met le * à la racine et calcule (1+2)*3 = 9. Deux résultats pour une même entrée — inacceptable pour un compilateur.

On désambiguïse en réécrivant la grammaire pour encoder les priorités et l'associativité dans sa structure :

1E → E + T | T          (l'addition, la moins prioritaire, est en haut)2T → T * F | F          (la multiplication est plus bas, donc prioritaire)3F → ( E ) | nombre

Cette grammaire n'engendre plus qu'un seul arbre pour 1+2*3, celui qui vaut 7. La priorité du * est devenue une propriété structurelle de la grammaire — exactement comme l'équilibre des $a$ et des $b$ tout à l'heure. C'est le travail que l'analyseur syntaxique du chapitre 9 exploitera.

Une mise en garde honnête : certains langages algébriques sont intrinsèquement ambigus — aucune grammaire non ambiguë ne les engendre. Et savoir si une grammaire donnée est ambiguë est, en général, indécidable. Ce sont des résultats profonds ; en L2, retenez le phénomène et la technique de désambiguïsation par priorités.

Formes normales et hiérarchie de Chomsky

Pour raisonner et pour programmer, on met souvent une grammaire sous une forme normale standardisée. La plus courante est la forme normale de Chomsky, où toute règle est de l'une des deux formes seulement :

$A \to BC \quad (\text{deux variables}) \qquad \text{ou} \qquad A \to a \quad (\text{un terminal}).$

Toute grammaire hors contexte peut être transformée en une forme normale de Chomsky engendrant le même langage (au mot vide près). Son intérêt est pratique : les arbres deviennent binaires, ce qui rend possibles des algorithmes d'analyse efficaces.

Enfin, situons ces objets. La hiérarchie de Chomsky classe les langages en quatre niveaux emboîtés, chacun associé à un type de grammaire et à un modèle de machine :

Chaque niveau contient strictement le précédent. Vous n'étudierez en L2 que les deux premiers — les plus utiles en pratique — mais il est bon de savoir que l'échelle continue au-dessus, jusqu'à la machine de Turing et la notion générale de calcul.

À vous

L'exercice vous fait d'abord dériver $aabb$ avec la grammaire $S \to aSb \mid \varepsilon$ : vous verrez le compte s'équilibrer tout seul, étape par étape, sans qu'aucun nombre ne soit mémorisé. Puis il rend l'ambiguïté tangible : vous évaluez 1+2*3 selon ses deux arbres et obtenez 7 ou 9, avant de comprendre pourquoi et comment on réécrit la grammaire pour n'en garder qu'un.

C'est le même geste que le chapitre 9 automatisera : d'une grammaire non ambiguë, un compilateur tire l'unique arbre qui donne le sens de l'expression.

// Une grammaire hors contexte engendre des mots en RÉÉCRIVANT des variables
// (non-terminaux) jusqu'à n'avoir que des terminaux.
//
// G1 engendre L = { a^n b^n | n >= 0 } — le langage que les automates finis
// ne savaient PAS reconnaître (chapitre 6). Une grammaire, elle, le peut.
//   S -> a S b        (on ajoute un a à gauche, un b à droite : compte gardé)
//   S -> ε            (cas de base)
// Axiome : S.

// Une dérivation gauche : on réécrit le non-terminal le plus à gauche.
// On représente une forme comme une chaîne mêlant 'a','b' (terminaux) et 'S'.
function derive(forme, regle) {
  // remplace le PREMIER 'S' par le membre droit de la règle
  return forme.replace("S", regle);
}

// ── À VOUS (1) : dériver le mot aabb depuis S ───────────────────────────────
// Appliquez les règles pour transformer "S" en "aabb". Notez chaque étape.
let f = "S";
console.log("Départ :", f);
// à compléter : suite d'appels à derive(f, "aSb") ou derive(f, "") pour
// aboutir à "aabb". (Indice : deux fois S->aSb, puis S->ε.)
// f = derive(f, "aSb"); console.log(f);
console.log("Arrivée :", f, f === "aabb" ? "  ✓ aabb engendré" : "  (pas encore aabb)");

// ── Ambiguïté : deux arbres pour un même mot ────────────────────────────────
// G2, la grammaire NAÏVE des expressions arithmétiques :
//   E -> E + E | E * E | ( E ) | nombre
// Le mot "1+2*3" a DEUX arbres de dérivation :
//   - l'un calcule (1+2)*3 = 9
//   - l'autre calcule 1+(2*3) = 7
// Une grammaire est AMBIGUË si un mot admet plus d'un arbre de dérivation.

// ── À VOUS (2) : évaluer selon chaque arbre ─────────────────────────────────
function evalGauchePrioritaire() {
  // arbre où + est en haut (racine) : 1 + (2*3)
  return 0; // à compléter : la valeur obtenue
}
function evalMultEnHaut() {
  // arbre où * est en haut (racine) : (1+2) * 3
  return 0; // à compléter
}

console.log("");
console.log("1+2*3, + à la racine  ->", evalGauchePrioritaire(), "(attendu 7)");
console.log("1+2*3, * à la racine  ->", evalMultEnHaut(), "(attendu 9)");

// ── (1) Dérivation de aabb ──────────────────────────────────────────────────
let f = "S";
f = derive(f, "aSb"); console.log(f);  // aSb
f = derive(f, "aSb"); console.log(f);  // aaSbb
f = derive(f, "");    console.log(f);  // aabb
// S ⇒ aSb ⇒ aaSbb ⇒ aabb. Chaque S->aSb garde l'équilibre : un a ET un b.
// S->ε termine. Impossible de produire plus de a que de b : le compte est
// STRUCTUREL, porté par la règle récursive. C'est ce qu'un automate fini ne
// pouvait pas faire.

// ── (2) Ambiguïté ───────────────────────────────────────────────────────────
function evalGauchePrioritaire() { return 1 + (2 * 3); } // 7
function evalMultEnHaut()       { return (1 + 2) * 3;   } // 9

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Une grammaire ENGENDRE (produit des mots) là où un automate RECONNAÎT
//    (teste des mots). Les deux points de vue sont complémentaires : le
//    chapitre 8 montrera l'automate à pile qui reconnaît ce que la grammaire
//    engendre.
//
// 2. La récursion S -> a S b porte un COMPTE que la mémoire finie d'un
//    automate ne pouvait pas tenir. C'est pour cela que les grammaires hors
//    contexte dépassent les langages réguliers : a^n b^n est algébrique mais
//    pas régulier.
//
// 3. L'AMBIGUÏTÉ n'est pas une curiosité théorique : ici, deux arbres donnent
//    7 ou 9 pour « 1+2*3 ». Un compilateur qui accepterait une grammaire
//    ambiguë calculerait des résultats non déterminés. On DÉSAMBIGUÏSE en
//    réécrivant la grammaire pour encoder les priorités :
//        E -> E + T | T        (le + est en haut)
//        T -> T * F | F        (le * est plus bas, donc prioritaire)
//        F -> ( E ) | nombre
//    Cette grammaire n'engendre qu'un seul arbre pour 1+2*3, valant 7. C'est
//    exactement le travail de l'analyseur syntaxique du chapitre 9.

Ce que la suite en fait

Vous savez maintenant engendrer les langages algébriques par des grammaires. Le chapitre 8 fournit la contrepartie que le bloc II avait pour les réguliers : la machine qui les reconnaît. Ce sera l'automate à pile — un automate fini augmenté d'une pile, cette mémoire supplémentaire qui lui permet enfin de compter, et donc de vérifier l'équilibre de $a^n b^n$.

On y établira l'équivalence entre grammaires hors contexte et automates à pile — l'analogue, un étage plus haut, du théorème de Kleene — puis un lemme de pompage algébrique qui tracera la frontière suivante : les langages, comme $a^n b^n c^n$, qui échappent même aux grammaires hors contexte.

À retenir

Exercices d'entraînement

Le chapitre 7 a montré comment engendrer les langages algébriques avec des grammaires. Il manque la contrepartie que le bloc II avait pour les réguliers : la machine qui les reconnaît. Le chapitre 6 avait diagnostiqué le manque avec précision — un automate fini ne sait pas compter, faute de mémoire non bornée. La solution est d'ajouter cette mémoire, sous une forme très particulière : une pile.

Ce choix n'est pas arbitraire. Une pile — dernier entré, premier sorti — est exactement ce qu'il faut pour apparier des symboles de part et d'autre : empiler à l'aller, dépiler au retour. C'est le mécanisme qui vérifie que les parenthèses d'un programme sont bien équilibrées, et c'est la même idée qui reconnaît $a^n b^n$.

L'automate à pile

Un automate à pile est un automate fini augmenté d'une pile de capacité illimitée. À chaque transition, il peut désormais :

• lire une lettre de l'entrée (ou $\varepsilon$, sans rien lire) ;
• consulter et dépiler le symbole au sommet de la pile ;
• empiler de nouveaux symboles.

La transition dépend donc de trois choses — l'état, la lettre lue, le sommet de la pile — et agit sur deux — l'état et la pile. La contrainte essentielle, celle qui définit le modèle et fixe sa puissance, est que l'automate n'accède qu'au sommet : il ne voit ni ne modifie le reste de la pile. Il travaille sur une mémoire non bornée, mais d'accès strictement discipliné.

L'intuition à garder : la hauteur de la pile est un compteur. Pour $a^n b^n$, on empile un jeton à chaque $a$ et on en dépile un à chaque $b$. La pile monte pendant les $a$, redescend pendant les $b$, et se retrouve vide exactement quand les deux nombres sont égaux. Ce compteur peut grimper aussi haut qu'on veut — c'est précisément la mémoire non bornée que les états finis ne pouvaient offrir.

Deux critères d'acceptation

Un automate à pile peut décider d'accepter de deux manières, et il faut connaître les deux :

• par pile vide : le mot est accepté si, après l'avoir entièrement lu, la pile est vide ;
• par état final : le mot est accepté si la lecture se termine dans un état acceptant, quelle que soit la pile.

Ces deux critères sont équivalents : tout langage reconnu par pile vide l'est aussi par état final, et réciproquement, quitte à transformer l'automate. On choisit celui qui rend la construction la plus naturelle. Pour $a^n b^n$, l'acceptation par pile vide est la plus directe — « autant de $b$ que de $a$ » se traduit littéralement par « la pile est retombée à vide » —, et c'est celle de l'exercice.

L'équivalence avec les grammaires

Voici le résultat central du chapitre, l'analogue du théorème de Kleene un étage plus haut :

Les automates à pile reconnaissent exactement les langages engendrés par les grammaires hors contexte.

Grammaire et automate à pile sont donc deux visages du même objet : le premier engendre, le second reconnaît, la même classe des langages algébriques. On peut transformer effectivement l'un en l'autre — d'une grammaire, on construit un automate à pile qui simule ses dérivations sur la pile ; d'un automate à pile, on extrait une grammaire.

Une différence capitale avec le bloc II mérite d'être soulignée, car elle prend à contre-pied l'intuition acquise au chapitre 4. Là, déterministe et non déterministe étaient équivalents. Ici, ce n'est plus vrai : les automates à pile non déterministes sont strictement plus puissants que les déterministes. Certains langages algébriques n'ont pas d'automate à pile déterministe. C'est le non-déterminisme qui donne toute sa force au modèle — et c'est aussi ce qui rend l'analyse syntaxique générale (chapitre 9) plus délicate que l'analyse lexicale, laquelle reste dans le monde déterministe des automates finis.

Le lemme de pompage algébrique

Ayant élargi la classe, on retrouve la question du chapitre 6 : y a-t-il des langages qui échappent même aux grammaires hors contexte ? Oui — et l'outil pour le prouver est un lemme de pompage algébrique, cousin de celui des réguliers.

L'idée est la même — un objet fini forcé de se répéter sur une entrée assez longue — mais un arbre de dérivation profond doit réutiliser une variable sur un chemin, ce qui crée deux zones pompables simultanément au lieu d'une. Le lemme s'énonce donc avec une décomposition en cinq morceaux : tout mot assez long $w \in L$ s'écrit $w = uvxyz$ avec $vy$ non vide, $|vxy|$ borné, et $uv^ixy^iz \in L$ pour tout $i \geq 0$. On pompe $v$ et $y$ ensemble.

L'usage est identique à celui du chapitre 6 : prouver qu'un langage n'est pas algébrique. Le cas d'école est $a^n b^n c^n$ — trois familles à équilibrer en même temps. Une pile sait apparier deux familles ($a$ contre $b$), mais elle n'a qu'un sommet : elle ne peut pas suivre simultanément un troisième compte. Le pompage à deux zones fait précisément apparaître ce déséquilibre, et prouve que $a^n b^n c^n$ dépasse les automates à pile.

On retrouve ainsi, un cran plus haut, exactement la structure du bloc II : un modèle de machine, une classe de langages, et un lemme de pompage qui en marque la frontière — au-dessus commencent les langages contextuels, puis la machine de Turing.

À vous

L'exercice rend tangible l'idée maîtresse du chapitre : la pile permet de compter. Vous implémentez le moteur d'un automate à pile qui reconnaît $a^n b^n$ par pile vide — empiler un jeton par $a$, dépiler un par $b$, accepter si la pile finit vide — et vous voyez la hauteur de la pile monter puis redescendre.

C'est ce compteur non borné, impossible avec un nombre fini d'états, qui fait basculer des langages réguliers aux langages algébriques. En le codant, vous touchez du doigt à la fois la puissance du modèle (il compte) et sa limite (il n'a qu'un sommet, d'où $a^n b^n c^n$ hors d'atteinte).

// Un automate à pile = un automate fini + une PILE. C'est la pile qui donne
// la mémoire non bornée qui manquait au chapitre 6.
//
// Idée pour L = { a^n b^n } : EMPILER un jeton à chaque 'a', DÉPILER un jeton
// à chaque 'b'. Si la pile est vide à la fin (et qu'on n'a jamais dépilé à
// vide, ni lu un a après un b), alors il y avait autant de b que de a.
// Acceptation PAR PILE VIDE.

// ── À VOUS : le moteur de reconnaissance ────────────────────────────────────
function accepte(mot) {
  const pile = [];
  let phase = "a";              // on lit d'abord des a, puis des b
  for (const c of mot) {
    if (c === "a") {
      // à compléter : on ne doit plus lire de a une fois en phase b
      // puis empiler un jeton
    } else if (c === "b") {
      // à compléter : passer en phase b ; dépiler un jeton ;
      // si la pile est déjà vide -> trop de b -> rejet
    } else {
      return false;            // symbole hors alphabet
    }
  }
  // à compléter : accepté si la pile est VIDE à la fin
  return false;
}

// ── Vérification ────────────────────────────────────────────────────────────
const tests = [
  ["",       true],    // n = 0
  ["ab",     true],    // n = 1
  ["aabb",   true],    // n = 2
  ["aaabbb", true],    // n = 3
  ["aab",    false],   // 2 a, 1 b
  ["abb",    false],   // 1 a, 2 b
  ["ba",     false],   // b avant a
  ["abab",   false],   // pas de la forme a...a b...b
];
for (const [mot, attendu] of tests) {
  const r = accepte(mot);
  console.log("'" + mot + "'".padEnd(8) + " -> " + r + (r === attendu ? "  ok" : "  ✗"));
}

function accepte(mot) {
  const pile = [];
  let phase = "a";
  for (const c of mot) {
    if (c === "a") {
      if (phase === "b") return false;   // un a après un b : forme interdite
      pile.push("X");                    // EMPILER : un jeton par a
    } else if (c === "b") {
      phase = "b";
      if (pile.length === 0) return false; // DÉPILER à vide : trop de b
      pile.pop();                          // DÉPILER : un jeton par b
    } else {
      return false;
    }
  }
  return pile.length === 0;               // pile vide <=> autant de b que de a
}

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. La PILE est la mémoire qui manquait. La hauteur de la pile compte les a
//    non encore appariés — elle peut monter aussi haut qu'on veut, ce qu'un
//    nombre FINI d'états ne pouvait pas faire (chapitre 6). C'est très
//    exactement ce qui fait passer des langages réguliers aux algébriques.
//
// 2. On n'accède qu'au SOMMET de la pile — c'est la contrainte du modèle, et
//    sa limite. On peut apparier a et b (a^n b^n), mais on ne peut pas
//    apparier TROIS familles à la fois : a^n b^n c^n échappe même aux
//    automates à pile (lemme de pompage algébrique, plus bas dans le cours).
//
// 3. Deux critères d'acceptation existent et sont équivalents :
//    - par PILE VIDE (utilisé ici) ;
//    - par ÉTAT FINAL (on accepte si on finit dans un état acceptant).
//    On passe de l'un à l'autre sans changer la classe de langages reconnus.
//
// 4. Équivalence fondamentale : les automates à pile (NON déterministes)
//    reconnaissent EXACTEMENT les langages engendrés par les grammaires hors
//    contexte (chapitre 7). C'est l'analogue du théorème de Kleene, un étage
//    plus haut. Attention : contrairement aux automates finis, les automates
//    à pile déterministes sont STRICTEMENT moins puissants que les non
//    déterministes.

Ce que la suite en fait

Le bloc III est complet : grammaires pour engendrer, automates à pile pour reconnaître, reliés par une équivalence, et un lemme de pompage pour en marquer la limite. Vous avez maintenant deux étages de la hiérarchie de Chomsky, chacun avec sa machine, sa notation et sa frontière.

Le bloc IV quitte la théorie pure pour l'application qui lui donne tout son sens. Le chapitre 9 montre comment ces deux étages travaillent ensemble dans un compilateur : les langages réguliers (automates finis, chapitres 3 à 6) découpent le texte source en unités lexicales, et les langages algébriques (grammaires, ce bloc) en reconstruisent la structure. Toute la théorie du cours converge là.

À retenir

Exercices d'entraînement