BACKUS-NAUR FORM

The Backus-Naur form (BNF) (also known as Backus normal form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages.

It is widely used as a notation for the grammars of computer programming languages, command sets and communication protocols; most textbooks for programming language theory and/or semantics document BNF. Some variants, for example ABNF, have their own documentation.

It was originally named after John Backus and later (at the suggestion of Donald Knuth) also after Peter Naur, two pioneers in computer science, namely in the art of compiler design, as part of creating the rules for Algol 60.

A BNF specification is a set of derivation rules, written as

::=

where is a nonterminal, and the expression consists of sequences of symbols and/or sequences separated by '|', indicating a choice, the whole being a possible substitution for the symbol on the left. Symbols that never appear on a left side are terminals.

Example

As an example, consider this BNF for a US postal address:

 ::=   
 ::=  |  "."

 ::=   []  |  

 ::= []   

 ::=  ","

This translates into English as:

"A postal-address consists of a name-part, followed by a street-address part, followed by a zip-code part. A personal-part consists of either a first name or an initial followed by a dot. A name-part consists of either: a personal-part followed by a last name followed by an optional "jr-part" (Jr., Sr., or dynastic number) and end-of-line, or a personal part followed by a name part (this rule illustrates the use of recursion in BNFs, covering the case of people who use multiple first and middle names and/or initials). A street address consists of an optional apartment specifier, followed by a street number, followed by a street name. A zip-part consists of a town-name, followed by a comma, followed by a state code, followed by a ZIP-code followed by an end-of-line."

Note that many things (such as the format of a personal-part, apartment specifier, or ZIP-code) are left unspecified here. If necessary, they may be described using additional BNF rules, or left as abstractions if irrelevant for the purpose at hand.

Variants

There are many variants and extensions of BNF, possibly containing some or all of the regexp wild cards such as "*" or "+". The Extended Backus-Naur form (EBNF) is a common one. In fact the example above isn't the pure form invented for the ALGOL 60 report. "[ ]" was introduced a few years later in IBM's PL/I definition but is now universally recognised. ABNF is another extension.

External links

[1] contains a posting on news:comp.compilers that explains some of the history of the two names (Backus-Naur form vs. Backus normal form).
http://www.garshol.priv.no/download/text/bnf.html

This article (or an earlier version of it) contains material from FOLDOC, used with permission.

Specialty Definition: BACKUS-NAUR FORM

Domain	Definition
Computing	Backus-Naur Form (BNF, originally "Backus Normal Form") A formal metasyntax used to express context-free grammars. Backus Normal Form was renamed Backus-Naur Form at the suggestion of Donald Knuth. BNF is one of the most commonly used metasyntactic notations for specifying the syntax of programming languages, command sets, and the like. It is widely used for language descriptions but seldom documented anywhere (how do you document a metasyntax?), so that it must usually be learned by osmosis (but see RFC 2234). Consider this BNF for a US postal address: ::= ::= \| "." ::= [] \| ::= [] ::= "," This translates into English as: "A postal-address consists of a name-part, followed by a street-address part, followed by a zip-code part. A personal-part consists of either a first name or an initial followed by a dot. A name-part consists of either: a personal-part followed by a last name followed by an optional "jr-part" (Jr., Sr., or dynastic number) and end-of-line, or a personal part followed by a name part (this rule illustrates the use of recursion in BNFs, covering the case of people who use multiple first and middle names and/or initials). A street address consists of an optional apartment specifier, followed by a street number, followed by a street name. A zip-part consists of a town-name, followed by a comma, followed by a state code, followed by a ZIP-code followed by an end-of-line." Note that many things (such as the format of a personal-part, apartment specifier, or ZIP-code) are left unspecified. These lexical details are presumed to be obvious from context or specified somewhere nearby. There are many variants and extensions of BNF, possibly containing some or all of the regexp wild cards such as "*" or "+". EBNF is a common one. In fact the example above isn't the pure form invented for the ALGOL 60 report. "[]" was introduced a few years later in IBM's PL/I definition but is now universally recognised. ABNF is another extension. (1997-11-23). Source: The Free On-line Dictionary of Computing.
Source: compiled by the editor from various references; see credits.

Modern Translation: BACKUS-NAUR FORM

Language		Translations for "BACKUS-NAUR FORM"; alternative meanings/domain in parentheses.
Danish		Backus-Naur form (backus normal form). (various references)

Dutch		Backus-naur formule (backus normal form). (various references)

Finnish		Backus-Naurin normaalimuoto (backus normal form), Backus-Naur form (backus normal form). (various references)

French		BNF (backus normal form). (various references)

German		BNF (backus normal form), Backus-Naur-Form (backus normal form). (various references)

Italian		rappresentazione normale di Backus (backus normal form), notazione di Backus (backus normal form), forma normale di Backus (backus normal form). (various references)

Pig Latin		ackus-naurbay ormfay

Portuguese		BNF (backus normal form). (various references)

Spanish		BNF (backus normal form), notación normal de Backus (backus normal form), notación de Backus-Naur (backus normal form). (various references)

Swedish		Backus-Naur formel (backus normal form). (various references)
Source: compiled by the editor from various translation references.

Anagrams: BACKUS-NAUR FORM

Scrabble® Enable2K-Verified Anagrams
	Words within the letters "a-a-b-c-f-k-m-n-o-r-r-s-u-u"
	-5 letters: barrancos, macrurans.
Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro.