Backus-naur 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
::= personal-part
::= | “.” name-part
::= [] | street-address
::= [] zip-part
::= “,”
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)
Read Also:
- Backward analysis
backward analysis theory An analysis to determine properties of the inputs of a program from properties or context of the outputs. E.g. if the output of this function is needed then this argument is needed. Compare forward analysis. (1997-11-23)
- Backward and forward
toward the back or rear. with the back foremost. in the reverse of the usual or right way: counting backward from 100. toward the past: to look backward over one’s earlier mistakes. toward a less advanced state; retrogressively: Since the overthrow of the president the country has moved steadily backward. directed toward the back or […]
- Backward chaining
backward chaining algorithm An algorithm for proving a goal by recursively breaking it down into sub-goals and trying to prove these until facts are reached. Facts are goals with no sub-goals which are therefore always true. Backward training is the program execution mechanism used by most logic programming language like Prolog. Opposite: forward chaining. (2004-01-26)
- Backward combatability
backward combatability humour /bak’w*d k*m-bat’*-bil’*-tee/ (Play on “backward compatibility”) A property of hardware or software revisions in which previous protocols, formats, layouts, etc. are irrevocably discarded in favour of “new and improved” protocols, formats and layouts, leaving the previous ones not merely deprecated but actively defeated. (Too often, the old and new versions cannot definitively […]
- Backward compatibility
backward compatibility jargon Able to share data or commands with older versions of itself, or sometimes other older systems, particularly systems it intends to supplant. Sometimes backward compatibility is limited to being able to read old data but does not extend to being able to write data in a format that can be read by […]