Backus-Naur form: Encyclopedia - Backus-Naur form

Backus-Naur form

The Backus-Naur form (BNF) (also known as Backus normal form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. BNF is widely used as a notation for the grammars of computer programming languages, command sets and communication protocols. They can also be used as a notation for representing parts of natural language grammars. For example see the grammar for meter in Venpa poetry. Most textbooks for programming language theory and/or semantics document the programming language in BNF. Some variants, for example ABNF, have their own documentation.

BNF was originally named after John Backus and later (at the suggestion of Donald Knuth) also after Peter Naur. They were two pioneers in computer science, especially in the art of compiler design. The Backus-Naur Form or BNF grammars have significant similarities to Pāṇini's grammar rules, and is sometimes also referred to as Panini-Backus Form. BNF was created as part of creating the rules for Algol 60.

Backus-Naur form - Introduction

A BNF specification is a set of derivation rules, written as

<symbol> ::= <expression with symbols>

where <symbol> is a nonterminal, and the expression consists of sequences of symbols and/or sequences separated by the vertical bar, '|', indicating a choice, the whole being a possible substitution for the symbol on the left. Symbols that never appear on a left side are terminals.

Backus-Naur form - Example

As an example, consider this BNF for a US postal address:

<postal-address> ::= <name-part> <street-address> <zip-part>

<personal-part> ::= <first-name> | <initial> "."

<name-part> ::= <personal-part> <last-name> [<jr-part>] <EOL> | <personal-part> <name-part>

<street-address> ::= [<apt>] <house-num> <street-name> <EOL>

<zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>

This translates into English as:

Note that many things (such as the format of a personal-part, apartment specifier, or ZIP-code) are left unspecified here. If necessary, they may be described using additional BNF rules, or left as abstraction if irrelevant for the purpose at hand.

Backus-Naur form - Further examples

Interestingly enough, BNF's syntax may be represented in BNF as follows:

<syntax> ::= <rule> [<syntax>]
<rule> ::= <whitespace> "<" <rule-name> ">" <whitespace> "::=" <expression> <whitespace> <line-end>
<expression> ::= <whitespace> <or-expression>
<or-expression> ::= <whitespace> <list-expression> [ "|" <or-expression> ]
<list-expression> ::= <whitespace>  ("<" <rule-name> ">" | <QUOTE> <text> <QUOTE> | "(" <expression> ")" | "[" <expression> "]") [<list-expression>]
<whitespace> ::= [" " <whitespace>]
<line-end> ::= [<whitespace>] <EOL> [<line-end>]

This assumes that no whitespace is necessary for proper interpretation of the rule. <QUOTE> is presumed to be the " character, and <EOL> to be the appropriate line-end specifier (in ASCII, line-feed and/or new-line, depending on the OS). <rule-name> and <text> are to be substituted with a declared rule's name/label or literal text, respectively.

Backus-Naur form - Variants

There are many variants and extensions of BNF, possibly containing some or all of the regexp wild cards such as "*" or "+". The Extended Backus-Naur form (EBNF) is a common one. In fact the example above is not the pure form invented for the ALGOL 60 report. The bracket notation "[ ]" was introduced a few years later in IBM's PL/I definition but is now universally recognised. ABNF is another extension commonly used to describe IETF protocols.

Parsing expression grammars build on the BNF and regular expression notations to form an alternative class of formal grammar, which is essentially analytic rather than generative in character.

See also

• Ashtadhyayi (Sanskrit grammar with mathematical structure)

Adapted from the Wikipedia article "Backus-Naur form", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki