Backus-Naur Form

language, grammar (BNF, originally "Backus Normal Form") A

formal metasyntax used to express context-free grammars.

Backus Normal Form was renamed Backus-Naur Form at the

suggestion of Donald Knuth.

BNF is one of the most commonly used metasyntactic notations

for specifying the syntax of programming languages, command

sets, and the like. It is widely used for language

descriptions but seldom documented anywhere (how do you

document a metasyntax?), so that it must usually be learned

by osmosis (but see RFC 2234).

Consider this BNF for a US postal address:

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

personal-part ::= 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: "A postal-address consists of

a name-part, followed by a street-address part, followed by a

zip-code part. A personal-part consists of either a first

name or an initial followed by a dot. A name-part consists of

either: a personal-part followed by a last name followed by an

optional "jr-part" (Jr., Sr., or dynastic number) and

end-of-line, or a personal part followed by a name part (this

rule illustrates the use of recursion in BNFs, covering the

case of people who use multiple first and middle names and/or

initials). A street address consists of an optional apartment

specifier, followed by a street number, followed by a street

name. A zip-part consists of a town-name, followed by a

comma, followed by a state code, followed by a ZIP-code

followed by an end-of-line."

Note that many things (such as the format of a personal-part,

apartment specifier, or ZIP-code) are left unspecified. These

lexical details are presumed to be obvious from context or

specified somewhere nearby.

There are many variants and extensions of BNF, possibly

containing some or all of the regexp wild cards such as

"*" or "+". EBNF is a common one. In fact the example

above isn't the pure form invented for the ALGOL 60 report.

"[]" was introduced a few years later in IBM's PL/I

definition but is now universally recognised. ABNF is

another extension.

(1997-11-23)