The idea of describing the structure of language using rewriting rules can be traced back to at least the work of
In Western society, grammar was long regarded as a subject for teaching, rather than scientific study; descriptions were informal and targeted at practical usage. In the first half of the 20th century,
Meanwhile, string rewriting rules as
BNF is a notation for Chomsky's context-free grammars. Apparently, Backus was familiar with Chomsky's work.
As proposed by Backus, the formula defined "classes" whose names are enclosed in angle brackets. For example,
<ab>. Each of these names denotes a class of basic symbols.
Further development of
BNF, as described by Peter Naur in the ALGOL 60 report is metalinguistic formula. "Sequences of characters enclosed in the brackets <> represent metalinguistic variables whose values are sequences of symbols. The marks "::=" and "|" (the latter with the meaning of "or") are metalinguistic connectives. Any mark in a formula, which is not a variable or a connective, denotes itself. Juxtaposition of marks or variables in a formula signifies juxtaposition of the sequence denoted."
Another example from the ALGOL 60 report illustrates a major difference between the BNF metalanguage and a Chomsky context-free grammar. Metalingustic variables do not require a rule defining their formation. Their formation may simply be described in natural language within the <> brackets. The following ALGOL 60 report section 2.3 comments specification, exemplifies how this works:
For the purpose of including text among the symbols of a program the following "comment" conventions hold:
The sequence of basic symbols: is equivalent to ; comment <any sequence not containing ';'>; ; begin comment <any sequence not containing ';'>; begin end <any sequence not containing 'end' or ';' or 'else'> end
By equivalence is here meant that any of the three structures shown in the left column may be replaced, in any occurrence outside of strings, by the symbol shown in the same line in the right column without any effect on the action of the program.
Naur changed two of Backus's symbols to commonly available characters. The "::=" symbol was originally a ":≡". The "|" symbol was originally the word "or" (with a bar over it).:14[
< > as non-terminals. Chomsky terminology was not originally used in describing BNF. Naur later described them as classes in ALGOL course materials. In the ALGOL 60 report they were called metalinguistic variables. Anything other than the metasymbols ::=, |, and class names enclosed in <,> are symbols of the language being defined. The metasymbols ::= is to be interpreted as "is defined as". The | is used to separate alternative definitions and is interpreted as "or". The metasymbols <,> are delimiters enclosing a class name. BNF is described as a
<expr> ::= <term>|<expr><addop><term>
The first symbol of an alternative may be the class being defined, the repetition, as explained by Naur, having the function of specifying that the alternative sequence can recursively begin with a previous alternative and can be repeated any number of times. For example, above
<expr> is defined as a
<term> followed by any number of
In some later metalanguages such as Schorre's
> bracket removed. Mathematical grouping
( ) were added. The
<expr> rule would appear in META II as
EXPR = TERM $('+' TERM .OUT('ADD') | '-' TERM .OUT('SUB'));
These changes made that META II and its derivative programming languages able to define and extend their own metalanguage. In so doing the ability to use a natural language description, metalinguistic variable, language construct description was lost. Many spin-off metalanguages were inspired by BNF. See
A BNF class describes a language construct formation, with formation defined as a pattern or the action of forming the pattern. The class name expr is described in a natural language as a
<term> followed by a sequence
<addop> <term>. A class is an abstraction, we can talk about it independent of its formation. We can talk about term, independent of its definition, as being added or subtracted in expr. We can talk about a term being a specific data type and how an expr is to be evaluated having specific combinations of data types. Or even reordering an expression to group data types and evaluation results of mixed types. The natural-language supplement provided specific details of the language class semantics to be used by a compiler implementation and a programmer writing an ALGOL program. Natural-language description further supplemented the syntax as well. The integer rule is a good example of natural and metalanguage used to describe syntax:
<integer> ::= <digit>|<integer><digit>
There are no specifics on white space in the above. As far as the rule states, we could have space between the digits. In the natural language we complement the BNF metalanguage by explaining that the digit sequence can have no white space between the digits. English is only one of the possible natural languages. Translations of the ALGOL reports were available in many natural languages.
The origin of BNF is not as important as its impact on programming language development. During the period immediately following the publication of the ALGOL 60 report BNF was the basis of many
<class name> became symbol identifiers dropping the enclosing <,> and using quoted strings for symbols of the target language. Arithmetic like grouping provided simplification that removed using classes where grouping was its only value. The META II arithmetic expression rule shows grouping use. Output expressions placed in a META II rule are used to output code and labels in an assembly language. Rules in META II are equivalent to a class definitions in BNF. The Unix utility