Backus Naur form (BNF)

The Backus-Naur form is originally a description means for the formal rules - that means the syntax - of a higher programming language, and is also called a metalanguage. Thus the Backus-Naur form is a text-based alternative to syntax graphs. However, it is also applied to the notation of general instruction sets for communication protocols, among other things. The Backus-Naur form makes it possible to represent context-free grammars, which in turn belong to the Type 2 grammars in the Chomsky hierarchy. The Backus-Naur form was named after its originators - the computer scientists John Backus and Peter Naur - who had used this representation form for the first time for the definition of the languageALGOL 60.

For the representation in the Backus-Naur form instead of the equal sign or the unification operator the metalinguistic connectors:

::= as definition sign and

l as an or sign.

The explicit representation of the concatenation operator is omitted. Each Backus Naur rule defines a syntactic category denoted by a metalinguistic variable. In principle, a rule consists of three components:

• the category denoted by a metalinguistic variable to the left of the definition sign,
• the metalinguistic definition sign ::=
• the syntactic formula to the right of the definition sign.

The metalinguistic variable is explained by the formula to the right of the definition sign. In the representation of a rule, the distinction of the metalinguistic variables from the terminal signs is essential. Therefore, meta-linguistic variables are specially marked, e.g., by enclosing them in a pair of angle brackets. A metalinguistic variable is an abstract term that should be chosen in the language definition to refer to the

• Meaning of the designated syntactic category (e.g. integer constant, mark),
• syntactic structure (e.g. list, agreement part) and
• usage (e.g. upper bound, run variable).

The syntactic formula consists of one or more alternatives. Multiple alternatives in a formula are separated by the or sign. An alternative is a character string of meta-linguistic variables and terminal characters of the alphabet. The terminal characters represent themselves. The meta-linguistic variables denote in an alternative the character series defined by them in a rule.

The Backus-Naur rule for defining an identifier is obviously recursive here. The recursion depth is not limited in this Backus-Naur rule. A restriction e.g. of the number of letters and digits of an identifier cannot be done easily with the means of expression described so far. In the extended Backus-Naur form, therefore, the power of a character series is included as a means of representation:

[...]exp n:m

The bracket pair [...] encloses the syntactic construction to be concatenated at least n times and at most m times. For

[...]exp n:n can also be [...]exp n or for [...]exp 0:oo (oo stands for infinite) can also be [...]exp* and for [...]exp 1:oo can also be[...]exp+ as well as for [...]exp 0:1 can also be [...]. Often, in the extended Backus-Naur form, alternatives are notated by the choice bracket pairs {...} enclosed below each other.

The Backus Naur rules were further developed in the 1990s into the Augmented Backus Naur Form( ABNF) and the Extended Backus Naur Form (EBFN).