Definition:Backus-Naur Form

From ProofWiki
Jump to navigation Jump to search

Definition

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

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

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:


Rules of Formation

Let <word> be a metasymbol of an object language.

Let <word-1>, <word-2>, ..., <word-n> be letters of Backus-Naur form.

That is, <word-1>, ..., <word-n> 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:

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

This means that <word> on the left hand side may be replaced by the specified sequence of $n$ words on the right hand side.

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

This means that <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 $\mathcal L$ in Backus-Naur form is called a specification of $\mathcal L$.


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.


Source of Name

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


Sources