Backus–Naur form
In computer science, Backus–Naur form () or Backus normal form (BNF) is a metasyntax notation for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocols. They are applied wherever exact descriptions of languages are needed: for instance, in official language specifications, in manuals, and in textbooks on programming language theory. Many extensions and variants of the original Backus–Naur notation are used; some are exactly defined, including extended Backus–Naur form (EBNF) and augmented Backus–Naur form (ABNF). Overview. A  BNF specification is a set of derivation rules, written as where: Symbols that never appear on a left side are "terminals". On the other hand, symbols that appear on a left side are "non-terminals" and are always enclosed between the pair <>. Example. As an example, consider this possible BNF for a U.S. postal address: <opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | "" 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 . If necessary, they may be described using additional BNF rules. History. 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. 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). Noam Chomsky, teaching linguistics to students of information theory at MIT, combined linguistics and mathematics by taking what is essentially Thue's formalism as the basis for the description of the syntax of natural language. He also introduced a clear distinction between generative rules (those of context-free  grammars) and transformation rules (1956). John Backus, a programming language designer at IBM, proposed a metalanguage of "metalinguistic formulas" to describe the syntax of the new programming language IAL, known today as ALGOL 58 (1959). His notation was first used in the ALGOL 60 report. BNF is a notation for Chomsky's context-free grammars. Backus was familiar with Chomsky's work. As proposed by Backus, the formula defined "classes" whose names are enclosed in angle brackets. For example, codice_1. Each of these names denotes a class of basic symbols. Further development of ALGOL led to ALGOL 60. In the  committee's 1963 report, Peter Naur called Backus's notation "Backus normal form". Donald Knuth argued that BNF should rather be read as "Backus–Naur form", as it is "not a normal form in the conventional sense", unlike, for instance, Chomsky normal form. The name "Pāṇini Backus form" was also once suggested in view of the fact that the expansion "Backus normal form" may not be accurate, and that Pāṇini had independently developed a similar notation earlier. BNF is described by Peter Naur in the ALGOL 60 report as "metalinguistic formula": Another example from the ALGOL 60 report illustrates a  major difference between the BNF metalanguage and a Chomsky context-free grammar. Metalinguistic 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: 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. Naur changed two of Backus's symbols to commonly available characters. The codice_2 symbol was originally a codice_3. The codice_4 symbol was originally the word "" (with a bar over it). BNF is very similar to canonical-form boolean algebra equations that are, and were at the time, used in logic-circuit design. Backus was a mathematician and the designer of the FORTRAN programming language. Studies of boolean algebra is commonly part of a mathematics curriculum. What we do know is that neither Backus nor Naur described the names enclosed in  codice_5 as non-terminals. Chomsky's 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 codice_2, codice_4, and class names enclosed in codice_5 are symbols of the language being defined. The metasymbols codice_2 is to be interpreted as "is defined as". The codice_4 is used to separate alternative definitions and is interpreted as "or". The metasymbols codice_5 are delimiters enclosing a class name. BNF is described as a metalanguage for talking about ALGOL by Peter Naur  and Saul Rosen. 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. He was the first managing editor of the Communications of the ACM. What we do know is that BNF was first used as a metalanguage to talk about the ALGOL language in the ALGOL 60 report. That is how it is explained in ALGOL programming course material developed by Peter Naur in 1962. Early ALGOL manuals by IBM, Honeywell, Burroughs and Digital Equipment Corporation followed the  ALGOL 60 report using it as a metalanguage. Saul Rosen in his book describes BNF as a metalanguage for talking about ALGOL. An example of its use as a metalanguage would be in defining an arithmetic expression: 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 codice_12 is defined as a codice_13 followed by any number of codice_14. 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 codice_15 and codice_16 brackets were removed. Parentheses codice_17codice_18 for mathematical grouping were added. The codice_12 rule would appear in META II as These changes enabled META II and its derivative programming languages to define and extend their own metalanguage, at the cost of the ability to use a natural language description, metalinguistic variable, language construct description. Many spin-off metalanguages were inspired by BNF. See META II, TREE-META, and Metacompiler. 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 codice_13 followed by a sequence codice_14. 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: 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 compiler-compiler systems. Some, like "A Syntax Directed Compiler for ALGOL 60" developed by Edgar T. Irons and "A Compiler Building System" Developed by Brooker and Morris, directly used BNF. Others, like the Schorre Metacompilers, made it into a programming language with only a few changes. codice_22  became symbol identifiers, dropping the enclosing <,> and using quoted strings for symbols of the target language. Arithmetic-like grouping provided a 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 yacc is based on BNF with code production similar to META II. yacc is most commonly used as a parser generator, and its  roots are obviously BNF. BNF today is one of the oldest computer-related languages still in use. Further examples. BNF's syntax itself may be represented with a BNF like the following: Note that "" is the empty string. The original BNF did not use quotes as shown in codice_23 rule. This assumes that no whitespace is necessary for proper interpretation of the rule. codice_24 represents the appropriate line-end specifier (in ASCII, carriage-return, line-feed or both depending on the operating system). codice_25 and codice_26 are to be substituted with a declared rule's name/label or literal text , respectively. In the U.S. postal address example above, the entire block-quote is a syntax. Each line or unbroken grouping of lines is a rule; for example one rule begins with codice_27. The other part of that rule (aside from a line-end) is an expression, which consists of two lists separated by a pipe codice_4. These two lists consists of some terms (three terms and two terms, respectively). Each term in this particular rule is a rule-name. Variants. EBNF. 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. One common feature of many variants is the use of regular expression repetition operators such as codice_29 and codice_30. The extended Backus–Naur form (EBNF) is a common one. Another common extension is the use of square brackets around optional items. 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. ABNF. Augmented Backus–Naur form (ABNF) and Routing Backus–Naur form (RBNF) are extensions commonly used to describe Internet Engineering Task Force (IETF) protocols. Parsing expression  grammars build on the BNF and regular expression notations to form an alternative class of formal grammar, which is essentially analytic rather than generative in character. Others. Many BNF specifications found online today are intended to be human-readable and are non-formal. These often include many of the following syntax rules and extensions: