Incomputer science,Backus–Naur form (BNF, pronounced/ˌbækəsˈnaʊər/), also known asBackus normal form, is a notation system for defining thesyntax ofprogramming languages and otherformal languages, developed byJohn Backus andPeter Naur. It is ametasyntax forcontext-free grammars, providing a precise way to outline the rules of a language's structure.
It has been widely used in official specifications, manuals, and textbooks onprogramming language theory, as well as to describedocument formats,instruction sets, andcommunication protocols. Over time, variations such asextended Backus–Naur form (EBNF) andaugmented Backus–Naur form (ABNF) have emerged, building on the original framework with added features.
BNF specifications outline how symbols are combined to form syntactically valid sequences. Each BNF consists of three core components: a set ofnon-terminal symbols, a set ofterminal symbols, and a series of derivation rules.[1] Non-terminal symbols represent categories or variables that can be replaced, while terminal symbols are the fixed, literal elements (such as keywords or punctuation) that appear in the final sequence. Derivation rules provide the instructions for replacing non-terminal symbols with specific combinations of symbols.
A derivation rule is written in the format:
<symbol>::= __expression__
where:
<symbol>[2] is a non-terminal symbol, enclosed in angle brackets (<>), identifying the category to be replaced::= is a metasymbol meaning "is replaced by,"__expression__ is the replacement, consisting of one or more sequences of symbols—either terminal symbols (e.g., literal text like "Sr." or ",") or non-terminal symbols (e.g.,<last-name>)—with options separated by avertical bar (|) to indicate alternatives.For example, in the rule<opt-suffix-part>::= "Sr." | "Jr." | "", the entire line is the derivation rule, "Sr.", "Jr.", and "" (an empty string) are terminal symbols, and<opt-suffix-part> is a non-terminal symbol.
Generating a valid sequence involves starting with a designated start symbol and iteratively applying the derivation rules.[3] This process can extend sequences incrementally. To allow flexibility, some BNF definitions include an optional "delete" symbol (represented as an empty alternative, e.g.,<item> ::=<thing> | ), enabling the removal of certain elements while maintaining syntactic validity.[3]
A practical illustration of BNF is a specification for a simplified U.S.postal address:
<postal-address>::=<name-part><street-address><zip-part><name-part>::=<personal-part><last-name><opt-suffix-part><EOL> |<personal-part><name-part><personal-part>::=<first-name> |<initial> "."<street-address>::=<house-num><street-name><opt-apt-num><EOL><zip-part>::=<town-name> ","<state-code><ZIP-code><EOL><opt-suffix-part>::= "Sr." | "Jr." |<roman-numeral> | ""<opt-apt-num>::= "Apt"<apt-num> | ""
This translates into English as:
Note that many things (such as the format of a first-name, apartment number, ZIP-code, and Roman numeral) are left unspecified here. If necessary, they may be described using additional BNF rules.
The concept of usingrewriting rules to describe language structure traces back to at leastPāṇini, an ancient Indian Sanskrit grammarian who lived sometime between the 6th and 4th centuriesBC.[5] His notation for describingSanskrit word structure is equivalent in power to that of BNF and exhibits many similar properties.[6]
In Western society, grammar was long regarded as a subject for teaching rather than scientific study; descriptions were informal and targeted at practical usage. This perspective shifted in the first half of the 20th century, when linguists such asLeonard Bloomfield andZellig Harris began attempts to formalize language description, includingphrase structure. Meanwhile, mathematicians explored related ideas throughstring rewriting rules asformal logical systems, such asAxel Thue in 1914,Emil Post in the 1920s–40s,[7] andAlan Turing in 1936.Noam Chomsky, teaching linguistics to students ofinformation theory atMIT combined linguistics and mathematics, adapting Thue's formalism to describe natural language syntax. In 1956, he introduced a clear distinction between generative rules (those ofcontext-free grammars) and transformation rules.[8][9]
BNF itself emerged whenJohn Backus, a programming language designer atIBM, proposed ametalanguage ofmetalinguistic formulas to define the syntax of the new programming language IAL, known today asALGOL 58, in 1959.[10] This notation was formalized in theALGOL 60 report, wherePeter Naur named itBackus normal form in the committee's 1963 report.[11] Whether Backus was directly influenced by Chomsky's work is uncertain.[12][13]
Donald Knuth argued in 1964 that BNF should be read asBackus–Naur form, as it is "not anormal form in the conventional sense," unlikeChomsky normal form.[14] In 1967, Peter Zilahy Ingerman suggested renaming itPāṇini Backus form to acknowledge Pāṇini's earlier, independent development of a similar notation.[15]
In the ALGOL 60 report, Naur described BNF as ametalinguistic formula:[16]
Sequences of characters enclosed in the brackets <> represent metalinguistic variables whose values are sequences of symbols. The marks "::=" and "|" (the latter with the meaning of "or") are metalinguistic connectives. Any mark in a formula, which is not a variable or a connective, denotes itself. Juxtaposition of marks or variables in a formula signifies juxtaposition of the sequence denoted.
This is exemplified in the report's section 2.3, where comments are specified:
For the purpose of including text among the symbols of a program the following "comment" conventions hold:
The sequence of basic symbols: is equivalent to ;comment <any sequence not containing ';'>; ; begincomment <any sequence not containing ';'>; begin end <any sequence not containing 'end' or ';' or 'else'> end Equivalence here means that any of the three structures shown in the left column may be replaced, in any occurrence outside of strings, by the symbol shown in the same line in the right column without any effect on the action of the program.
Naur altered Backus's original symbols for ALGOL 60, changing:≡ to::= and the overbarred "or" to|, using commonly available characters.[17]: 14
BNF is very similar tocanonical-formBoolean algebra equations (used in logic-circuit design), reflecting Backus's mathematical background as a FORTRAN designer.[18] Studies of Boolean algebra were commonly part of a mathematics curriculum, which may have informed Backus's approach. Neither Backus nor Naur described the names enclosed in< > as non-terminals—Chomsky's terminology was not originally used in describing BNF. Naur later called them "classes" in 1961 course materials.[18] In the ALGOL 60 report, they were "metalinguistic variables," with other symbols defining the target language.
Saul Rosen, involved with theAssociation for Computing Machinery since 1947, contributed to the transition from IAL to ALGOL and edited Communications of the ACM. He described BNF as a metalanguage for ALGOL in his 1967 book.[19] Early ALGOL manuals from IBM, Honeywell, Burroughs, and Digital Equipment Corporation followed this usage.
BNF significantly influenced programming language development, notably as the basis for earlycompiler-compiler systems. Examples include Edgar T. Irons' "A Syntax Directed Compiler for ALGOL 60" and Brooker and Morris' "A Compiler Building System," which directly utilized BNF.[20] Others, like Schorre'sMETA II, adapted BNF into a programming language, replacing< > with quoted strings and adding operators like $ for repetition, as in:
EXPR=TERM$('+'TERM.OUT('ADD')|'-'TERM.OUT('SUB'));
This influenced tools likeyacc, a widely usedparser generator rooted in BNF principles.[21] BNF remains one of the oldest computer-related notations still referenced today, though its variants often dominate modern applications.
Examples of its use as a metalanguage include defining arithmetic expressions:
<expr>::=<term> |<expr><addop><term>
Here,<expr> can recursively include itself, allowing repeated additions.
BNF today is one of the oldest computer-related languages still in use.[citation needed]
BNF's syntax itself may be represented with a BNF like the following:
<syntax>::=<rule> |<rule><syntax><rule>::=<opt-whitespace> "<"<rule-name> ">"<opt-whitespace> "::="<opt-whitespace><expression><line-end><opt-whitespace>::= " "<opt-whitespace> | ""<expression>::=<list> |<list><opt-whitespace> "|"<opt-whitespace><expression><line-end>::=<opt-whitespace><EOL> |<line-end><line-end><list>::=<term> |<term><opt-whitespace><list><term>::=<literal> | "<"<rule-name> ">"<literal>::= '"'<text1> '"' | "'"<text2> "'"<text1>::= "" |<character1><text1><text2>::= "" |<character2><text2><character>::=<letter> |<digit> |<symbol><letter>::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"<digit>::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"<symbol>::= "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"<character1>::=<character> | "'"<character2>::=<character> | '"'<rule-name>::=<letter> |<rule-name><rule-char><rule-char>::=<letter> |<digit> | "-"
Note that "" is theempty string.
The original BNF did not use quotes as shown in<literal> rule. This assumes that nowhitespace is necessary for proper interpretation of the rule.
<EOL> represents the appropriateline-end specifier (inASCII, carriage-return, line-feed or both depending on theoperating system).<rule-name> and<text> are to be substituted with a declared rule's name/label or literal text, respectively.
In the U.S. postal address example above, the entire block-quote is a<syntax>. Each line or unbroken grouping of lines is a rule; for example one rule begins with<name-part> ::=. The other part of that rule (aside from a line-end) is an expression, which consists of two lists separated by a vertical bar|. These two lists consists of some terms (three terms and two terms, respectively). Each term in this particular rule is a rule-name.
There are many variants and extensions of BNF, generally either for the sake of simplicity and succinctness, or to adapt it to a specific application. One common feature of many variants is the use ofregular expression repetition operators such as* and+. Theextended Backus–Naur form (EBNF) is a common one.
Another common extension is the use of square brackets around optional items. Although not present in the original ALGOL 60 report (instead introduced a few years later inIBM'sPL/I definition), the notation is now universally recognised.
Augmented Backus–Naur form (ABNF) and Routing Backus–Naur form (RBNF)[22] are extensions commonly used to describeInternet Engineering Task Force (IETF)protocols.
Parsing expression grammars build on the BNF andregular expression notations to form an alternative class offormal grammar, which is essentiallyanalytic rather thangenerative in character.
Many BNF specifications found online today are intended to be human-readable and are non-formal. These often include many of the following syntax rules and extensions:
[<item-x>].*) such as<word> ::= <letter> {<letter>} or<word> ::= <letter> <letter>* respectively.+, such as<word> ::= <letter>+.{{cite web}}: CS1 maint: multiple names: authors list (link)