The jargon file writeup at BNF is "often incorrectly expanded as `Backus-Naur Form'." That is incorrect. update 3/3/2002: The jargon file entry has been correctly updated, but I hope some of the other info in this writeup is still useful.

The B in BNF, or Backus-Naur form, is named after its originator, John Backus. John Backus developed this formal notation for specifying programming language syntax as part of a paper he published in 1959 describing the ALGOL 58 language.

The N, however, is in honor of Peter Naur, who modified the notation for the description of ALGOL 60. Context-free grammars, which BNF describes, was discovered by Noam Chomski.

Although context-free grammars are extremely useful, they do not completely describe programming language rules. Semantic rules such as "variables must be declared before they are used" cannot be described using BNF.


Reference: Concepts of Programming Languages Fourth Edition, Robert W Sebesta, pp 107-108

The Backus-Naur Form is a compact way to describe a context-free grammar.If you have a context-free grammar G=(N,T,P,o), where N is the not empty, finite set of non-terminal symbols, T is the not empty, finite set of terminal symbols, P is the finite set of derivation rules and o is ∈ N is the start symbol.
Example:
T = {a,b}, N = {a}, P = { o → aob, o → ε}
This grammar describes the following language: L(G)={a^n b^n | n ≥ 0}

Now let's come to the Backus-Naur Form. In this form there are several derivation rules summed up to one rule.
The rules for reducing the rules are:
A → b1, A → b2, ..., A → bn can be reduced to A → b1|b2|...|bn
A → ac, A → abc can be reduced to A → a[b]c
A → ac, A → aBc, B → b, B → Bb can be reduced to A → a{b}c (this simply means 0,1 or more bs)

Example: The example above is not useful for this. It would stay unchanged. So lets create a new example:
T={a,b,c,d}, N = {A,B,C,D}, P = {o → ABC, A → a, A → c, B → abc, B → ac, C → bDd, C → bd, D → a, D → Da}
The both A rules can be reduced to A → a|c
The both B rules can be reduced to B → a[b]c
The C and D rules can be reduced to C → b{a}d
Then P' = {o → ABC, A → a|c, B → a[b]c, C → b{a}d }

Log in or register to write something here or to contact authors.