L2) Grammaires Context-Free

La base de tout

Comment un ordinateur peut-il comprendre que 2 + 3 * 4 vaut 14 et non 20 ? La réponse tient en trois lettres : CFG.

Où se situe cet article ?

Cet article fait partie de la série Langages formels (L). Il approfondit le Type 2 de la hiérarchie de Chomsky (voir L1) : les grammaires context-free, fondement de la plupart des parseurs (analyseurs syntaxiques) et compilateurs (programmes qui traduisent un langage source en langage cible).

Pourquoi c’est important ?

Chaque fois que vous écrivez du code Python, du JSON, ou même une formule dans Excel, un programme doit comprendre la structure de ce que vous avez écrit. Cette compréhension ne se fait pas par magie : elle repose sur des règles précises qui décrivent comment les éléments s’assemblent.

Les grammaires context-free (CFG, pour Context-Free Grammar) sont l’outil fondamental pour décrire ces règles. Elles sont au cœur de tous les compilateurs, de tous les parseurs, de tous les outils qui transforment du texte structuré en quelque chose d’exploitable. Sans elles, pas de Python, pas de JavaScript, pas de HTML… et pas de BP3 (Bol Processor 3, un langage de grammaires musicales — voir I2), la notation musicale que nous transpilons (traduisons d’un langage source vers un autre langage de même niveau) vers SuperCollider (un environnement de programmation audio — voir I3).

Comprendre les CFG, c’est comprendre comment les langages sont définis et comment les machines les interprètent.

L’idée en une phrase

Une grammaire context-free est un ensemble de règles de réécriture qui décrivent comment construire toutes les phrases valides d’un langage, sans tenir compte du contexte.

Expliquons pas à pas

La structure d’une grammaire : G = (V, Σ, R, S)

Une grammaire context-free se définit par quatre éléments, traditionnellement notés G = (V, Σ, R, S) :

Symbole Nom Rôle Exemple
V Variables (non-terminaux) Symboles abstraits qui seront remplacés Expr, Terme, Facteur
Σ Alphabet (terminaux) Symboles concrets du langage final +, *, (, ), 0-9
R Règles de production Comment remplacer les variables Expr → Expr + Terme
S Symbole de départ Où commence la dérivation Expr

Pourquoi ces lettres grecques ?

  • Σ (sigma majuscule) représente l’alphabet, par tradition mathématique
  • La flèche → (ou -->) se lit « se réécrit en » ou « peut être remplacé par »
  • La barre verticale | signifie « ou » (alternative entre plusieurs possibilités)

Ainsi, Expr → Expr + Terme | Terme se lit : « Une expression peut être réécrite soit en ‘expression + terme’, soit en ‘terme’ seul. »

Pourquoi « context-free » ?

Le terme « context-free » (hors contexte) signifie que chaque règle peut s’appliquer indépendamment de ce qui entoure le symbole. Si on a la règle A → xy, on peut toujours remplacer A par xy, peu importe ce qu’il y a avant ou après A. C’est cette propriété qui rend les CFG analysables efficacement.

Exemple 1 : Les expressions arithmétiques

Construisons une grammaire pour des expressions comme 2 + 3 * 4 ou (1 + 2) * 3.

Les quatre composants :

 

V = { Expr, Terme, Facteur }          -- Variables
Σ = { +, *, (, ), 0, 1, ..., 9 }      -- Terminaux
S = Expr                               -- Symbole de départ
R = {                                  -- Règles
    Expr    → Expr + Terme | Terme
    Terme   → Terme * Facteur | Facteur
    Facteur → ( Expr ) | nombre
}

 

Dérivation de 2 + 3 * 4 :

Partons du symbole de départ et appliquons les règles :

 

Expr
→ Expr + Terme           (règle 1)
→ Terme + Terme          (règle 1, cas "Terme")
→ Facteur + Terme        (règle 2, cas "Facteur")
→ 2 + Terme              (règle 3, cas "nombre")
→ 2 + Terme * Facteur    (règle 2)
→ 2 + Facteur * Facteur  (règle 2, cas "Facteur")
→ 2 + 3 * Facteur        (règle 3)
→ 2 + 3 * 4              (règle 3)

 

Pourquoi ça donne 14 et pas 20 ?

La structure de la grammaire encode les priorités des opérateurs. La multiplication est « plus profonde » dans l’arbre (elle apparaît dans Terme), donc elle est évaluée en premier. La grammaire force l’interprétation 2 + (3 * 4) et non (2 + 3) * 4.

C’est la magie des CFG : la structure grammaticale capture la sémantique.

Le processus de dérivation

Une dérivation est une séquence de remplacements partant du symbole de départ et aboutissant à une chaîne de terminaux (le texte final). C’est le cœur du fonctionnement d’une grammaire.

Analogie : la dérivation comme recette de cuisine

Imaginez une recette : « Dessert → Tarte | Gâteau », « Tarte → Pâte + Garniture », etc.

La dérivation, c’est suivre les étapes : partir de « Dessert », remplacer par « Tarte », puis « Tarte » par « Pâte + Garniture », jusqu’à obtenir les ingrédients concrets (terminaux).

Types de dérivation :

  • Dérivation gauche (leftmost derivation) : à chaque étape, on remplace le non-terminal le plus à gauche
  • Dérivation droite (rightmost derivation) : à chaque étape, on remplace le non-terminal le plus à droite

Les deux stratégies aboutissent au même résultat final, mais l’ordre des étapes intermédiaires diffère. Cette distinction est importante car différents types de parseurs utilisent l’une ou l’autre stratégie :

Type de parseur Dérivation utilisée Exemple d’outil
LL (top-down, descendant) Gauche ANTLR (ANother Tool for Language Recognition), parseurs récursifs
LR (bottom-up, ascendant) Droite Bison, Yacc (Yet Another Compiler-Compiler)

Arbre de dérivation :

Chaque dérivation peut se représenter sous forme d’arbre, où :

  • La racine est le symbole de départ
  • Les nœuds internes sont des non-terminaux
  • Les feuilles sont des terminaux
  • Chaque niveau représente l’application d’une règle

 

        Expr
       /  |  \
    Expr  +  Terme
      |     /  |  \
   Terme Terme *  Facteur
      |     |        |
  Facteur Facteur    4
      |     |
      2     3

 

Exemple 2 : Une grammaire musicale simplifiée

Imaginons une notation musicale minimaliste :

 

V = { Phrase, Motif, Note }
Σ = { do, ré, mi, fa, sol, -, ( , ) }
S = Phrase
R = {
    Phrase → Motif | Phrase Motif
    Motif  → Note | ( Phrase )
    Note   → do | ré | mi | fa | sol | -
}

 

Cette grammaire permet de générer :

  • do ré mi (trois notes)
  • do - ré (note, silence, note)
  • ( do ré ) ( mi fa ) (deux motifs groupés)
  • ( do ( ré mi ) fa ) (imbrication)

Dérivation de do ( ré mi ) fa :

 

Phrase
→ Phrase Motif                     -- ajouter un motif
→ Phrase Motif Motif               -- ajouter encore
→ Phrase Motif fa                  -- Note → fa
→ Phrase ( Phrase ) fa             -- Motif → ( Phrase )
→ Phrase ( Phrase Motif ) fa       -- Phrase → Phrase Motif
→ Phrase ( Motif Motif ) fa        -- Phrase → Motif
→ Phrase ( ré Motif ) fa           -- Note → ré
→ Phrase ( ré mi ) fa              -- Note → mi
→ Motif ( ré mi ) fa               -- Phrase → Motif
→ do ( ré mi ) fa                  -- Note → do

 

Le problème de l’ambiguïté

Une grammaire est ambiguë si une même chaîne peut être dérivée de plusieurs façons différentes (plusieurs arbres de dérivation).

Exemple de grammaire ambiguë :

 

Expr → Expr + Expr | Expr * Expr | nombre

 

Pour 2 + 3 * 4, deux arbres sont possibles :

 

    Expr                    Expr
   / | \                   / | \
Expr + Expr            Expr * Expr
 |    / | \           / | \    |
 2  Expr * Expr     Expr + Expr 4
      |     |         |     |
      3     4         2     3

 

Le premier donne 2 + (3 * 4) = 14, le second donne (2 + 3) * 4 = 20.

Pourquoi c’est grave ?

L’ambiguïté signifie que le parseur ne sait pas quelle interprétation choisir. Pour un langage de programmation, c’est inacceptable : le code doit avoir un sens unique.

Solutions :

  1. Réécrire la grammaire pour éliminer l’ambiguïté (c’est ce qu’on a fait dans notre premier exemple avec Terme et Facteur)
  2. Règles de désambiguïsation : précédence et associativité des opérateurs
  3. Accepter l’ambiguïté et la résoudre sémantiquement (rare)

Propriétés des CFG

Ce que les CFG peuvent décrire :

  • Structures imbriquées (parenthèses, balises HTML/XML)
  • Récursion (définitions qui se réfèrent à elles-mêmes)
  • La syntaxe de la plupart des langages de programmation

Qu’est-ce que la récursion ?

Une définition est récursive quand elle se réfère à elle-même. Par exemple :

Expr → Expr + Terme

Une Expr contient une autre Expr ! C’est comme des poupées russes, ou des miroirs face à face.

La récursion permet d’exprimer des structures de profondeur arbitraire : 1+2+3+4+... avec une seule règle.

Ce que les CFG ne peuvent PAS décrire :

Limitation Notation formelle Exemple concret
Égalité de comptage triple aⁿbⁿcⁿ « autant de a, puis de b, puis de c »
Déclaration avant usage – Vérifier qu’une variable est déclarée avant d’être utilisée
Accords à distance – Accord sujet-verbe avec mots intercalés

Lecture de aⁿbⁿcⁿ

Cette notation mathématique signifie : « n répétitions de ‘a’, suivies de n répétitions de ‘b’, suivies de n répétitions de ‘c' ».

Exemples valides : abc (n=1), aabbcc (n=2), aaabbbccc (n=3)

Une CFG ne peut pas garantir que les trois groupes ont exactement le même nombre d’éléments.

Ces limitations motivent l’existence des grammaires context-sensitive (sensibles au contexte, Type 1 de la hiérarchie de Chomsky — voir L1) et des analyses sémantiques (portant sur le sens) supplémentaires effectuées après le parsing (analyse syntaxique).

Comment les CFG s’appliquent à BP3

La syntaxe de BP3, le langage de grammaires musicales, est elle-même décrite par une CFG. Voici un extrait simplifié :

 

bp_file      → header* grammar_section+
grammar_section → mode_line rule_line+
rule_line    → weight? lhs "-->" rhs
lhs          → nonterminal+
rhs          → element*
element      → note | rest | nonterminal | polymetric | ...

 

Une règle BP3 comme :

 

<50> S --> A B C

 

Se décompose en :

  • weight : <50>
  • lhs : S
  • rhs : A B C

Le parseur du transpileur BP2SC (BP3-to-SuperCollider, voir B7) utilise cette structure pour construire un AST (Abstract Syntax Tree, arbre syntaxique abstrait — voir L4), qui sera ensuite traduit en code SuperCollider.

Ce qu’il faut retenir

  1. G = (V, Σ, R, S) : Variables, Terminaux, Règles, Symbole de départ. Ces quatre éléments définissent complètement une grammaire.
  2. « Context-free » signifie que les règles s’appliquent indépendamment du contexte environnant. C’est ce qui rend l’analyse efficace.
  3. La dérivation est le processus de remplacement successif des variables jusqu’à obtenir une chaîne de terminaux.
  4. L’arbre de dérivation capture la structure hiérarchique de la phrase, ce qui détermine son interprétation.
  5. L’ambiguïté est l’ennemi : une grammaire ambiguë produit plusieurs interprétations possibles. On la résout par une conception soigneuse des règles.
  6. Les CFG sont au cœur de la compilation : la syntaxe de Python, Java, JSON, HTML, et BP3 est décrite par des CFG.

Pour aller plus loin

  • Livre de référence : Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools (le « Dragon Book »)
  • Cours en ligne : Coursera, Automata Theory par Jeffrey Ullman (Stanford)
  • Outil pratique : JFLAP pour visualiser les CFG et leurs dérivations
  • Standard formel : ISO 14977 pour la notation EBNF

Glossaire

Terme Définition
Ambiguïté Propriété d’une grammaire permettant plusieurs arbres de dérivation pour une même chaîne. Une grammaire ambiguë pose problème car le parseur ne sait pas quelle interprétation choisir.
Arbre de dérivation Représentation graphique d’une dérivation sous forme d’arbre. La racine est le symbole de départ, les feuilles sont les terminaux, et chaque nœud interne représente l’application d’une règle.
CFG Context-Free Grammar (grammaire hors contexte). Grammaire où chaque règle remplace un seul non-terminal, indépendamment de son contexte. Type 2 dans la hiérarchie de Chomsky.
Dérivation Séquence d’applications de règles transformant le symbole de départ en une chaîne de terminaux. Processus central du fonctionnement d’une grammaire.
Hiérarchie de Chomsky Classification des grammaires formelles en 4 types (0 à 3) selon leur pouvoir expressif, proposée par Noam Chomsky en 1956. Les CFG sont le Type 2.
Non-terminal Symbole abstrait (variable) qui sera remplacé par d’autres symboles selon les règles. Généralement noté en majuscules ou entre crochets.
Parseur Programme qui analyse une chaîne de caractères selon une grammaire et construit sa structure (arbre de dérivation ou AST). Synonyme : analyseur syntaxique.
Production Synonyme de « règle de réécriture ». Définit comment un non-terminal peut être remplacé.
Récursion Propriété d’une règle où un non-terminal apparaît dans sa propre définition (ex: Expr → Expr + Terme). Permet d’exprimer des structures de profondeur arbitraire.
Σ (Sigma) Lettre grecque traditionnellement utilisée pour désigner l’alphabet (ensemble des symboles terminaux) d’une grammaire.
Terminal Symbole concret du langage final, qui ne peut pas être remplacé. Ce sont les « mots » du vocabulaire : opérateurs, mots-clés, valeurs littérales.

Prérequis : L1 — Hiérarchie de Chomsky
Temps de lecture : 12 min
Tags : #grammaires #cfg #context-free #parsing #compilation

Prochain article : L3 — EBNF : le langage pour décrire les langages