L3) EBNF

Le langage pour décrire les langages

Comment les créateurs de Python ont-ils défini la syntaxe de Python ? Avec un méta-langage, bien sûr. Bienvenue dans le monde de l’EBNF.

Où se situe cet article ?

Cet article fait partie de la série Langages formels (L). Il présente la notation EBNF utilisée pour écrire les grammaires context-free (CFG, Context-Free Grammar — voir L2). Cette notation sert directement dans le parseur (analyseur syntaxique) du projet BP2SC (BP3-to-SuperCollider, le transpileur qui traduit BP3 en SuperCollider — voir B7), qui utilise Lark, un générateur de parseur Python présenté plus loin dans cet article.

Pourquoi c’est important ?

Vous savez maintenant ce qu’est une grammaire context-free. Mais comment écrire ces grammaires de manière claire, non ambiguë, et lisible par des outils automatiques ?

La réponse s’appelle EBNF (Extended Backus-Naur Form, forme de Backus-Naur étendue). C’est la notation standard utilisée dans les spécifications officielles de pratiquement tous les langages de programmation. Quand vous lisez « la spécification de Python » ou « la grammaire de JSON », vous lisez de l’EBNF (ou une variante proche).

Qu’est-ce qu’un méta-langage ?

Un méta-langage est un langage utilisé pour décrire d’autres langages. C’est un niveau d’abstraction supérieur.

  • Le français peut décrire les règles du français : c’est un méta-langage pour lui-même
  • L’EBNF décrit la syntaxe de Python, JSON, SQL… : c’est un méta-langage pour ces langages

Analogie : Si un plan d’architecte décrit un bâtiment, alors les conventions de dessin technique (échelle, symboles, légende) sont le « méta-langage » qui permet de lire ce plan.

Pour le projet BP2SC, nous avons écrit la spécification complète de BP3 (Bol Processor 3, un langage de grammaires musicales — voir I2) en EBNF. Ce fichier de 575 lignes (bp3_ebnf.xml) est la référence normative : tout ce que le transpileur (programme qui traduit un langage source vers un autre langage de même niveau) accepte doit être couvert par cette grammaire.

L’idée en une phrase

L’EBNF est une notation standardisée pour écrire des grammaires context-free, avec des opérateurs pratiques pour exprimer les répétitions, les options et les alternatives.

Expliquons pas à pas

De BNF à EBNF : une évolution pratique

BNF (Backus-Naur Form, du nom de John Backus et Peter Naur) a été inventée en 1959 pour décrire la syntaxe d’ALGOL 60 (ALGOrithmic Language, l’un des premiers langages de programmation structurés). C’était révolutionnaire — pour la première fois, on avait une notation formelle pour définir un langage — mais la notation était verbeuse.

Pourquoi « Extended » ?

Le « E » d’EBNF signifie Extended (étendu) car EBNF ajoute des opérateurs à BNF sans rien retirer. Tout ce qui est exprimable en BNF l’est en EBNF, mais l’inverse n’est pas vrai directement.

Analogie : BNF est comme une calculatrice basique (+, -, ×, ÷). EBNF ajoute les fonctions avancées (racine carrée, puissance…). On peut tout faire avec la basique, mais c’est plus long.

Exemple en BNF pure :

 

<liste> ::= <element>
<liste> ::= <liste> "," <element>

 

Cette grammaire décrit une liste d’éléments séparés par des virgules. Mais on a besoin de deux règles pour exprimer « un ou plusieurs éléments ».

EBNF ajoute des opérateurs qui rendent l’écriture plus concise :

 

liste = element { "," element } ;

 

Une seule ligne! Les accolades { } signifient « zéro ou plusieurs répétitions ».

Les opérateurs EBNF

EBNF introduit trois opérateurs fondamentaux :

Opérateur Syntaxe Signification Exemple
Option [ x ] Zéro ou une fois [signe] nombre
Répétition { x } Zéro ou plusieurs fois { chiffre }
Alternative x &#124; y L’un ou l’autre "+" &#124; "-"

Opérateurs dérivés (variantes courantes) :

Certaines variantes d’EBNF empruntent aux expressions régulières (regex, un formalisme pour décrire des motifs de texte) des notations plus compactes :

Opérateur Signification Équivalent EBNF standard Origine
x+ Une ou plusieurs fois x { x } Regex
x? Zéro ou une fois (optionnel) [ x ] Regex
x* Zéro ou plusieurs fois { x } Regex

Lecture de ces symboles

Ces symboles viennent des expressions régulières (regex), un autre formalisme pour décrire des motifs de texte :

  • + évoque « au moins un » (comme un signe plus qui ajoute)
  • ? évoque « peut-être » (comme une question)
  • * évoque « n’importe quel nombre » (comme une étoile qui brille plusieurs fois)

Exemple 1 : Nombres entiers avec signe optionnel

En BNF (5 règles) :

 

<nombre>   ::= <signe> <entier>
<nombre>   ::= <entier>
<entier>   ::= <chiffre>
<entier>   ::= <entier> <chiffre>
<signe>    ::= "+" | "-"

 

En EBNF (2 règles) :

 

nombre = [ "+" | "-" ] chiffre { chiffre } ;
chiffre = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

 

La version EBNF est plus lisible et plus proche de l’intuition : « un nombre, c’est un signe optionnel suivi d’un ou plusieurs chiffres ».

Les conventions de notation

Il existe plusieurs variantes d’EBNF. Voici les conventions les plus courantes :

Notation ISO 14977 (standard officiel) :

 

règle = définition ;              (* point-virgule final *)
"terminal"                        (* guillemets pour les terminaux *)
non_terminal                      (* pas de crochets angulaires *)
(* commentaire *)                 (* entre parenthèses-étoiles *)

 

Notation W3C (World Wide Web Consortium, utilisée pour XML, HTML) :

 

règle ::= définition              (* double deux-points *)
'terminal'                        (* apostrophes simples aussi *)
[A-Z]                             (* classes de caractères *)

 

Qu’est-ce qu’une classe de caractères ?

La notation [A-Z] signifie « n’importe quel caractère de A à Z » (les 26 lettres majuscules).

Exemples courants :

  • [a-z] : lettres minuscules
  • [0-9] : chiffres
  • [a-zA-Z] : lettres minuscules ou majuscules
  • [a-zA-Z0-9_] : caractères alphanumériques et underscore

C’est une notation compacte empruntée aux expressions régulières.

Notation informelle (courante en documentation) :

 

règle → définition               (* flèche simple *)
<non_terminal>                    (* crochets angulaires *)

 

Exemple 2 : Extraits de la grammaire BP3

Voici des exemples réels tirés de notre spécification EBNF pour BP3 :

Structure d’un fichier BP3 :

 

<production name="bp_file">
    <rule>header_line* grammar_section+</rule>
</production>

 

Traduction : « Un fichier BP3, c’est zéro ou plusieurs lignes d’en-tête, suivies d’une ou plusieurs sections de grammaire. »

Une règle de production BP3 :

 

<production name="rule_line">
    <rule>rule_prefix? weight? flag* lhs "-->" rhs trailing_comment?</rule>
</production>

 

Traduction : « Une ligne de règle contient optionnellement un préfixe (gram#1[1]), optionnellement un poids (<50>), zéro ou plusieurs flags (/Ideas/), un côté gauche, la flèche -->, un côté droit, et optionnellement un commentaire. »

Les notes en notation française :

 

<production name="note_french">
    <rule>note_name_fr accidental? digit</rule>
</production>

<production name="note_name_fr">
    <rule>"do" | "ré" | "mi" | "fa" | "sol" | "la" | "si"</rule>
</production>

<production name="accidental">
    <rule>"#" | "b"</rule>
</production>

 

Traduction : « Une note française, c’est un nom de note (do, ré, etc.), une altération optionnelle (# ou b), et un chiffre d’octave. »

Exemples valides : do4, ré#5, sib3, fa4

Les expressions polymétriques :

 

<production name="polymetric">
    <rule>"{" polymetric_body "}"</rule>
</production>

<production name="poly_ratio">
    <rule>integer "," rhs_element+</rule>
</production>

 

Traduction : « Une expression polymétrique est entourée d’accolades. La forme poly_ratio est un entier, une virgule, puis un ou plusieurs éléments. »

Exemple : {2, do ré mi} — syntaxiquement : un entier suivi d’une virgule et de notes.

Lire une spécification EBNF

Quand vous consultez la documentation d’un langage, vous rencontrerez souvent sa grammaire EBNF. Voici comment la lire :

Exemple : la grammaire JSON (simplifiée)

 

json      = value ;
value     = object | array | string | number | "true" | "false" | "null" ;
object    = "{" [ member { "," member } ] "}" ;
member    = string ":" value ;
array     = "[" [ value { "," value } ] "]" ;
string    = '"' { caractère } '"' ;
number    = [ "-" ] entier [ fraction ] [ exposant ] ;

 

Lecture pas à pas de object :

  1. "{" : commence par une accolade ouvrante
  2. [...] : optionnellement…
  3. member : un membre (clé:valeur)
  4. { "," member } : suivi de zéro ou plusieurs (virgule + membre)
  5. "}" : termine par une accolade fermante

Résultat : {}, {"a": 1}, {"a": 1, "b": 2} sont tous valides.

EBNF et les outils

L’EBNF n’est pas qu’une notation théorique. De nombreux outils appelés générateurs de parseurs peuvent lire une grammaire EBNF et produire automatiquement le code d’un parseur fonctionnel :

Qu’est-ce qu’un générateur de parseur ?

Un générateur de parseur (ou parser generator) est un programme qui prend en entrée une grammaire et produit en sortie du code source capable d’analyser cette grammaire.

Analogie : C’est comme un « compilateur de grammaires ». Vous lui donnez les règles du langage, il vous donne le programme qui comprend ce langage.

Outil Langage cible Caractéristique
ANTLR (ANother Tool for Language Recognition) Java, Python, C#, etc. Très populaire, IDE intégré (ANTLRWorks)
Lark Python Syntaxe proche d’EBNF, simple à utiliser
PEG.js JavaScript Grammaires PEG (Parsing Expression Grammar, similaires aux CFG mais déterministes)
Bison/Yacc (Yet Another Compiler-Compiler) C Classiques Unix, très performants

Exemple avec Lark (Python) :

 

from lark import Lark

grammaire = """
    start: expression
    expression: terme (("+" | "-") terme)*
    terme: facteur (("*" | "/") facteur)*
    facteur: NOMBRE | "(" expression ")"
    NOMBRE: /[0-9]+/
"""

parser = Lark(grammaire)
arbre = parser.parse("2 + 3 * 4")
print(arbre.pretty())

 

Sortie :

start
  expression
    terme
      facteur       2
    terme
      facteur       3
      facteur       4

 

Les limites de l’EBNF

L’EBNF décrit la syntaxe (la forme, la structure), pas la sémantique (le sens, la signification — voir L5). Elle peut exprimer :

  • « Un nombre est un ou plusieurs chiffres » (forme)
  • « Une fonction a des paramètres entre parenthèses » (structure)

Elle ne peut PAS exprimer :

  • « Un nombre doit être inférieur à 2³¹ » (contrainte de valeur)
  • « Une variable doit être déclarée avant usage » (règles contextuelles)
  • « Le type de retour doit correspondre à la déclaration » (cohérence sémantique)

Ces vérifications nécessitent une analyse supplémentaire, effectuée après le parsing (analyse syntaxique).

Ce qu’il faut retenir

  • EBNF = BNF + opérateurs pratiques : les crochets [ ] pour l’option, les accolades { } pour la répétition, et la barre | pour l’alternative.
  • Plus lisible que BNF : une grammaire EBNF est souvent 2 à 3 fois plus courte que son équivalent BNF.
  • Standard de l’industrie : les spécifications officielles de Python, JSON, XML, SQL, et la plupart des langages utilisent l’EBNF.
  • Exploitable par des outils : des générateurs de parseurs comme ANTLR ou Lark peuvent lire l’EBNF et produire du code automatiquement.
  • Syntaxe seulement : l’EBNF décrit la forme du langage, pas son sens. La sémantique nécessite des analyses complémentaires.

Pour aller plus loin

  • Standard officiel : ISO/IEC 14977:1996 – Syntactic metalanguage (EBNF)
  • Tutoriel ANTLR : https://www.antlr.org/
  • Documentation Lark : https://lark-parser.readthedocs.io/
  • Grammaire Python officielle : https://docs.python.org/3/reference/grammar.html

Glossaire

Terme Définition
BNF Backus-Naur Form. Notation originale pour les grammaires formelles, inventée en 1959 par John Backus et Peter Naur pour décrire ALGOL 60.
Classe de caractères Notation [...] désignant un ensemble de caractères. [a-z] signifie « n’importe quelle lettre minuscule ». Empruntée aux expressions régulières.
EBNF Extended Backus-Naur Form. Extension de BNF ajoutant des opérateurs pour l’option [ ], la répétition { }, et d’autres commodités syntaxiques.
Expression régulière Formalisme pour décrire des motifs de texte, utilisant des opérateurs comme *, +, ?. Plus limité que les CFG mais plus efficace à analyser.
Générateur de parseur Outil qui prend une grammaire en entrée et produit automatiquement le code d’un parseur. Exemples : ANTLR, Lark, Bison.
ISO 14977 Norme internationale définissant la syntaxe officielle de l’EBNF, publiée en 1996.
Méta-langage Langage utilisé pour décrire d’autres langages. L’EBNF est un méta-langage pour Python, JSON, etc.
Non-terminal Symbole abstrait qui sera remplacé selon les règles de la grammaire.
Parseur Programme qui analyse une chaîne de caractères selon une grammaire et en extrait la structure. Synonyme : analyseur syntaxique.
Production Synonyme de « règle de grammaire ». Définit comment un symbole se décompose en d’autres symboles.
Terminal Symbole littéral du langage final (mots-clés, opérateurs, valeurs). Ne peut pas être remplacé.

Prérequis : L2 — Grammaires Context-Free
Temps de lecture : 8 min
Tags : #ebnf #bnf #grammaires #spécification #parsing

Prochain article : L4 — Qu’est-ce qu’un AST ?