Backus Normal Form ==>
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)
Nearby terms:
backup pumpkin « backup rotation « backup software «
Backus-Naur Form » Backus Normal Form » backward
analysis » backward chaining
|
