Grammaires hors contexte

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