Definition:Backus-Naur Form

Definition

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

As such, it is a formal grammar for $\LL$.

BNF is only applicable to formal languages that use the collation system of words and concatenation.

Alphabet

The alphabet of Backus-Naur form has the following components:

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

• The letters:
  • A collection of metasymbols, typically rendered as <metasymbol>
  • Words in the object language.

Rules of Formation

Let $\meta {word}$ be a metasymbol of an object language.

Let $\meta {word1}, \meta {word2}, \ldots, \meta {wordn}$ be letters of Backus-Naur form.

That is, $\meta {word1}, \ldots, \meta {wordn}$ may be either metasymbols of, or words in, the object language.

The rules of formation of Backus-Naur form specify two kinds of well-formed formulae:

$\meta {word} \ ::= \ \meta {word1} \meta {word2} \cdots \meta {wordn}$

This means that $\meta {word}$ on the left hand side may be replaced by the specified sequence of $n$ words on the right hand side.

$\meta {word} \ ::= \ \meta {word1} \ \mid \ \meta {word2} \ \mid \ \cdots \ \mid \ \meta {wordn}$

This means that $\meta {word}$ on the left hand side may be replaced by one of the $n$ words on the right hand side.

Specification

A definition of an object language $\LL$ in Backus-Naur form is called a specification of $\LL$.

Terminals and Non-Terminals

Non-Terminal

Symbols that appear on the left hand side of a specification in Backus-Naur form are called non-terminals.

Terminal

Symbols that never appear on the left hand side of a specification in Backus-Naur form are called terminals.

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

Also known as

Backus-Naur form was originally called Backus normal form.

However, after Peter Naur had worked on refining the work initially done by John Warner Backus, his name was added.

Although Peter Naur would prefer it kept its old name, the current name is prevalent.

Also see

• Results about Backus-Naur form can be found here.

Source of Name

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

Sources

• 1993: M. Ben-Ari: Mathematical Logic for Computer Science ... (previous) ... (next): Chapter $2$: Propositional Calculus: $\S 2.2$: Propositional formulas
• 2000: Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems ... (previous) ... (next): $\S 1.3$: Propositional logic as a formal language