Backus–Naur form
BNFs describe how to combine different symbols to produce a syntactically correct sequence.
[1] These so-called "derivation rules" are written as where: All syntactically correct sequences must be generated in the following manner: Applying rules in this manner can produce longer and longer sequences, so many BNF definitions allow for a special "delete" symbol to be included in the specification.
[1] As an example, consider this possible BNF for a U.S. postal address: This translates into English as: Note that many things (such as the format of a first-name, apartment number, ZIP-code, and Roman numeral) are left unspecified here.
The idea of describing the structure of language using rewriting rules can be traced back to at least the work of Pāṇini, an ancient Indian Sanskrit grammarian and a revered scholar in Hinduism who lived sometime between the 6th and 4th century BC.
[4][5] His notation to describe Sanskrit word structure is equivalent in power to that of Backus and has many similar properties.
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, linguists such as Leonard Bloomfield and Zellig Harris started attempts to formalize the description of language, including phrase structure.
Meanwhile, string rewriting rules as formal logical systems were introduced and studied by mathematicians such as Axel Thue (in 1914), Emil Post (1920s–40s) and Alan Turing (1936).
[12] As proposed by Backus, the formula defined "classes" whose names are enclosed in angle 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: Equivalence here means 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.
[9]: 14 BNF is very similar to canonical-form Boolean algebra equations that are, and were at the time, used in logic-circuit design.
BNF is described as a metalanguage for talking about ALGOL by Peter Naur and Saul Rosen.
[2] In 1947 Saul Rosen became involved in the activities of the fledgling Association for Computing Machinery, first on the languages committee that became the IAL group and eventually led to ALGOL.
In some later metalanguages, such as Schorre's META II, the BNF recursive repeat construct is replaced by a sequence operator and target language symbols defined using quoted strings.
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.
The integer rule is a good example of natural and metalanguage used to describe syntax: There are no specifics on white space in the above.
[citation needed] During the period immediately following the publication of the ALGOL 60 report BNF was the basis of many compiler-compiler systems.
The Unix utility yacc is based on BNF with code production similar to META II.
There are many variants and extensions of BNF, generally either for the sake of simplicity and succinctness, or to adapt it to a specific application.
Although not present in the original ALGOL 60 report (instead introduced a few years later in IBM's PL/I definition), the notation is now universally recognised.
