Index: 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

Home > Backus-Naur form

The Backus-Naur form (BNF) (also known as Backus normal form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. BNF is widely used as a notation for the grammars of computer programming languages, command set s and communication protocols; most textbooks for programming language theory and/or semantics document BNF. Some variants, for example ABNF, have their own documentation.

BNF was originally named after John Backus and later (at the suggestion of Donald Knuth) also after Peter Naur, two pioneers in computer science, namely in the art of compiler design, as part of creating the rules for Algol 60.

1 Introduction

A BNF specification is a set of derivation rules , written as

::=

where < symbol> is a nonterminal , and the expressionAn expression combines numbers, operators, and/or variables. Expressions may be evaluated to values, and may be said to represent those values. The evaluation of an expression is dependent on the definition of the mathematical operators and system of valu consists of sequences of symbols and/or sequences separated by the vertical barVertical bar 'Verticon', or pipe is the name of the ASCII character at position 124 (decimal). The character is depicted as either a solid vertical bar or a vertical bar with a break in the middle (broken bar ). The character is usually depicted as a brok, '|', indicating a choice, the whole being a possible substitutionIn general, substitution is the replacement of one thing with another. There are many specific examples: In organic chemistry, a reaction where one functional group takes the place of another. A major type of substitution is nucleophilic substitution. for the symbol on the left. Symbols that never appear on a left side are terminalThe term Terminal can be used in several way and includes various topics: Usually terminal means forming or pertaining to an end. In Computing, it refers to an electronic or electromechanical hardware device. See Computer terminal. In Telecommunication, ts. Symbols inside brackets [] are optional.

2 Example

As an example, consider this BNF for a USThe United States of America also referred to as the United States U. America ¹ or the States is a federal republic in central North America, stretching from the Atlantic in the east to the Pacific Ocean in the west. It shares land borders with Canada in postal address :

::=

::= | "." ::=

[] |

::= []

::= ","

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 here. If necessary, they may be described using additional BNF rules, or left as abstraction if irrelevant for the purpose at hand.

Read more »

3 Further examples

Interestingly enough, BNF's syntax may be represented in BNF as follows:

::= [] ::= "<" ">" "::="

::= ( | | "[" "]") [] ::= [" " ] ::= [] [] This assumes that no whitespace is necessary for proper interpretation of the rule. is presumed to be the " character, and to be a carriage-return/line-feed. and are to be substituted with a declared rule's name/label or literal text, respectively.

4 Variants

There are many variants and extensions of BNF, possibly containing some or all of the regexp wild cards such as "*" or "+". The Extended Backus-Naur form (EBNF) is a common one. In fact the example above isn't 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 protocols.

Parsing expression grammars 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.

5 See also

Syntax diagram

6 References

This article was originally based on material from the Free On-line Dictionary of Computing, which is used under the GFDL.

7 External links

[1] contains a posting on news:comp.compilers that explains some of the history of the two names (Backus-Naur form vs. Backus normal form).
Article BNF and EBNF: What are they and how do they work? by Lars Marius Garshol

Formal languages

<Hide>

Topics: Backus-Naur Form, Introduction, Example, Further Examples...

Backus-Naur formThe Backus-Naur form BNF (also known as Backus normal form is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. BNF is widely used as a notation for the grammars of computer programming languages, comm

Backus Township, MichiganBackus Township is a township located in Roscommon County, Michigan. As of the 2000 census, the township had a total population of 350. Geography According to the United States Census Bureau, the township has a total area of 92. 3 mi²) of it is land and 4

Backus, MinnesotaBackus is a city located in Cass County, Minnesota. As of the 2000 census, the city had a total population of 311. Geography According to the United States Census Bureau, the city has a total area of 1. 6 mi²) of it is land and none of it is covered by wa