backus normal form

Backus-Naur Form
Backus Normal 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)