Backus-Naur Form

This page outlines basics of the Backus-Naur Form (BNF) notation, so that the file format pages can be more easily understood.

The basis of the Backus-Naur Form is a set of production rules, or in other words, rules for forming more complex objects from simpler ones. These objects may be simple (or terminal) symbols, or objects built from symbols by production rules. A production rule is of the form:

x ::= y

where x is a non-terminal symbol, and y is a sequence of one or more terminal and/or non-terminal symbols. Non-terminal symbols are enclosed in brackets <...>, whereas terminal symbols are represented in non-italic font. The symbol | may be used as an "or" on the right-hand side of a production so that it can be seen that x can be produced by one of several possible production rules.

The parsing of a data format proceeds by substitution. The components of a sentence are built up by starting with the head of the grammar and repeatedly substituting the right-hand part of a production for a corresponding non-terminal symbol until only terminal symbols remain. The special symbols of BNF are:

::= which means "is defined as".
| which means "or"
< > which are used to surround category names.

The angle brackets distinguish syntax rules names (also called non-terminal symbols) from terminal symbols which are written exactly as they are to be represented. A BNF rule defining a nonterminal has the form:

    nonterminal ::= sequence of alternatives consisting of strings of
                terminals or nonterminals separated by the meta-symbol |

For further details, see:
M. Marcotty & H. Ledgard, The World of Programming Languages, Springer-Verlag, Berlin 1986., pages 41 and following.

Jim Home