Backus-Naur Form
The first high-level languages emerged in the 1950s, bringing with them the challenge of clearly and unambiguously describing their syntax. John Backus provided an answer to this question that would transform how we design computer languages.
Previously, describing languages was almost an art of divination. Computer scientists struggled to explain syntactic rules in prose, producing often confusing texts. Fortran, Backus’s creation at IBM, was no exception to this difficulty. Its documentation was full of convoluted explanations such as “A real number is any sequence of decimal digits with a decimal point preceding or intervening between two digits or following a sequence of digits, the whole potentially preceded by a plus or minus sign”. Not exactly crystal clear.
In 1959, at the IFIP congress in Zurich, Backus presented a formal notation for describing ALGOL’s syntax. His proposal, which he had developed without any particular theoretical pretensions (he later admitted his relative lack of knowledge in mathematical logic), could have gone unnoticed. But it was Peter Naur who immediately grasped the significance of this idea. He refined the notation and applied it to the definition of ALGOL 60. This collaboration gave birth to the name Backus-Naur Form (BNF), a designation proposed by Donald Knuth to replace the original term “Backus Normal Form” which he considered mathematically inadequate.
The brilliance of BNF lies in its ability to express recursion with disarming simplicity. To define an integer, for example, writing <integer> ::= <digit> | <integer><digit> indicates that an integer is either a single digit or an integer followed by a digit. In a single line, we can describe numbers of any length.
Backus made another decisive choice by breaking free from hardware constraints. Unlike Fortran, which limited numbers to the interval [10−38,1038] for memory reasons, BNF focuses on pure syntax without worrying about the physical limitations of computers. This conceptual break gave languages a theoretical dimension independent of their technical implementation.
BNF’s success came quickly. Its conciseness was immediately appealing: a few lines replaced entire pages of explanations. Its precision swept away the ambiguities of natural language. Its operational aspect sealed the deal: BNF rules allowed for the direct construction of automatic syntax analyzers.
ALGOL 60 thus became the first language entirely defined by a formal notation. This standardization gave developers on different machines the ability to create compatible compilers, realizing ALGOL’s universal ambition. The way computer languages were conceived was thereby transformed. BNF encouraged computer scientists to adopt a more rigorous and systematic approach. Students could grasp the structure of programming languages more clearly thanks to this pedagogical formalism.
Over time, extensions enriched the original notation. EBNF (Extended BNF) integrated operators to express repetition or the optional nature of elements more simply. Graphical representations emerged, but the fundamental principles established by Backus and Naur remained intact.
BNF illustrates the contribution of formal notations to computer science. It transformed a craft-based approach into a scientific method, driven by practitioners confronting concrete problems. The separation it establishes between syntax and implementation has become a cardinal principle in language design.
More than sixty years after its introduction, in the 21st century, this notation remains fundamental. It serves today to define the syntax of programming languages, data formats, communication protocols, and various formal notations. BNF is thus one of those discreet yet powerful tools that transform an entire discipline without making headlines.