BNF is widely used as a Notation for the Grammar s of computer Programming Language s, Command Set s and Communication Protocol s, as well as a notation for representing parts of Natural Language grammars (for example, ''meter'' In Venpa Poetry .) Most textbooks for programming language theory and/or semantics document the programming language in BNF. Some variants, such as ''augmented'' Backus-Naur Form (ABNF), have their own documentation.
Overview
BNF was originally named after John Backus and later (at the suggestion of Donald Knuth ) also after Peter Naur . They were two pioneers in Computer Science , especially in the art of Compiler Design . The Backus-Naur Form or BNF grammars have significant similarities to 's grammar rules, and is sometimes also referred to as Panini-Backus Form. BNF was created as part of creating the rules for Algol 60 .
Introduction
A BNF specification is a set of Derivation Rules , written as
::=
where < Symbol > is a '' Nonterminal '', and the Expression consists of sequences of symbols and/or sequences separated by the Vertical Bar , '|', indicating a Choice , the whole being a possible Substitution for the symbol on the left. Symbols that never appear on a left side are '' Terminal s''.
Example
As an example, consider this BNF for a US Postal Address :
::=
::= | "."
::= {Link without Title}
|
::= {Link without Title}
::= ","
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 house number, followed by a street name, followed by an end-of-line.
- 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 Thing s (such as the format of a personal-part, apartment specifier, or ZIP-code) are left unspecified here. If necessary, they may be described using additional BNF rules, or left as Abstraction if irrelevant for the purpose at hand.
Further examples
Interestingly enough, BNF's syntax may be represented in BNF as follows:
::= {Link without Title}
::= "<" ">" "::="
::=
::= [ "|"
]
::= ("<" ">"
| | "(" ")" | "["
"]") {Link without Title}
::= "
::= [
This assumes that no Whitespace is necessary for proper interpretation of the rule.
is presumed to be the " character, and to be the appropriate line-end specifier (in ASCII , carriage-return and/or line-feed, depending on the OS). and are to be substituted with a declared rule's name/label or literal text, respectively.
Variants
- " or "+". The Extended Backus-Naur Form (EBNF) is a common one. In fact the example above is not the pure form invented for the ALGOL 60 report. The bracket notation " " was introduced a few years later in IBM 's PL/I definition but is now universally recognised. ABNF is another extension commonly used to describe IETF Protocol s.
Parsing Expression Grammar s build on the BNF and Regular Expression notations to form an alternative class of Formal Grammar , which is essentially Analytic rather than Generative in character.
See also
References
External links
|
