Definition:Backus-Naur Form

Definition

Backus-Naur Form (abbrevated BNF) is a (formal) metalanguage for defining the syntax of a formal language.

Alphabet

The alphabet of BNF has the following components:

• The signs:
  • The primitive symbol  ::= which means consists of;
  • The primitive symbol | which means or;

• The letters, which are words of the object language.

Rules of Formation

Let <word>, <word-1>, <word-2>, ... , <word-n> be metasymbols in an object language.

BNF has the following rules of formation:

• <word> ::= <word-1> <word-2> ... <word-n>

This means that <word> on the LHS may be replaced by the specified sequence of $n$ words on the RHS.

• <word> ::= <word-1> | <word-2> | ... | <word-n>

This means that <word> on the LHS may be replaced by one of the $n$ words on the RHS.

Specification

A definition of an object language $\mathcal F$ in BNF is called a specification of $\mathcal F$.

Terminals and Non-Terminals

Symbols that appear on the LHS of a specification are called non-terminals.

Symbols that never appear on the LHS of a specification are called terminals.

That is, non-terminals are analogous to grammatical clauses of a natural language, while terminals are analogous to its words.

Source of Name

This entry was named for John Warner Backus and Peter Naur.