backus-naur form

1 definition found

backus-naur form - Free On-line Dictionary of Computing (26 May 2007) :

  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)