Schéma de Backus-Naur
Les premiers langages de haut niveau font leur apparition dans les années 1950 et avec eux surgit la problématique de la description claire et sans ambiguïté de leur syntaxe. À cette question, John Backus apporta une réponse qui allait transformer notre manière de concevoir les langages informatiques.
Avant, la description des langages relevait presque de l'art divinatoire. Les informaticiens s'évertuaient à expliquer en prose les règles syntaxiques, produisant des textes souvent confus. Le Fortran, création de Backus chez IBM, n'échappait pas à cette difficulté. Sa documentation regorgeait d'explications alambiquées du type « Un nombre réel est une séquence quelconque de chiffres décimaux avec un point décimal précédant ou intervenant entre deux chiffres ou suivant une séquence de chiffres, le tout pouvant être précédé d'un signe plus ou moins ». Pas vraiment limpide.
L'année 1959, lors du congrès IFIP à Zurich, Backus présenta une notation formelle pour décrire la syntaxe d'ALGOL. Sa proposition, qu'il avait élaborée sans prétention théorique particulière (il avoua plus tard sa méconnaissance relative de la logique mathématique), aurait pu passer inaperçue. Mais ce fut Peter Naur qui saisit immédiatement la portée de cette idée. Il retoucha la notation et l'appliqua à la définition d'ALGOL 60. Cette collaboration donna naissance au nom Backus-Naur Form (BNF), une appellation proposée par Donald Knuth pour remplacer le terme initial « Backus Normal Form » qu'il jugeait inadéquat sur le plan mathématique.
Le génie du BNF tient à sa capacité d'exprimer la récursivité avec une simplicité désarmante. Pour définir un nombre entier par exemple, écrire <integer> ::= <digit> | <integer><digit> indique qu'un entier est soit un chiffre unique, soit un entier suivi d'un chiffre. En une ligne, nous voilà capables de décrire des nombres de n'importe quelle longueur.
Backus fit un autre choix déterminant en s'affranchissant des contraintes matérielles. Contrairement au Fortran, qui limitait par exemple les nombres à l'intervalle [10−38,1038] pour des raisons de mémoire, le BNF se concentre sur la syntaxe pure, sans se soucier des limitations physiques des ordinateurs. Cette rupture conceptuelle a donné aux langages une dimension théorique indépendante de leur mise en œuvre technique.
Le succès du BNF ne tarda pas. Sa concision séduisit immédiatement : quelques lignes remplaçaient des pages entières d'explications. Sa précision balaya les ambiguïtés du langage naturel. Son aspect opérationnel acheva de convaincre : les règles BNF permettaient de construire directement des analyseurs syntaxiques automatiques.
ALGOL 60 devint ainsi le premier langage entièrement défini par une notation formelle. Cette standardisation donna aux développeurs sur différentes machines la possibilité de créer des compilateurs compatibles, concrétisant l'ambition universelle d'ALGOL. La façon de concevoir les langages informatiques s'en trouva bouleversée. Le BNF incita les informaticiens à adopter une démarche plus rigoureuse et systématique. Les étudiants purent saisir plus clairement la structure des langages de programmation grâce à ce formalisme pédagogique.
Au fil du temps, des extensions vinrent enrichir la notation originale. La EBNF (Extended BNF) intégra des opérateurs pour exprimer plus simplement la répétition ou le caractère optionnel d'éléments. Des représentations graphiques apparurent, mais les principes fondamentaux posés par Backus et Naur demeurèrent intacts.
Le BNF illustre l'apport des notations formelles à l'informatique. Il a transformé une approche artisanale en méthode scientifique, et ce, sous l'impulsion de praticiens confrontés à des problèmes concrets. La séparation qu'il opère entre syntaxe et mise en œuvre est devenue un principe cardinal dans la conception des langages.
Plus de soixante ans après son introduction, au XXIe siècle, cette notation demeure fondamentale. Elle sert aujourd'hui à définir la syntaxe des langages de programmation, les formats de données, les protocoles de communication et diverses notations formelles. Le BNF est ainsi l'un de ces outils discrets mais puissants qui transforment toute une discipline sans faire la une des journaux.