Backus–Naur form

From Wikipedia, the free encyclopedia

The Backus–Naur form (also known as BNF, the Backus–Naur formalism, Backus normal form, or Panini–Backus 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, instruction sets and communication protocols, 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.

1 Overview
2 Introduction
3 Example
4 Further examples
5 Variants
6 See also
7 References
8 External links

[edit] 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 Pāṇini'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.

[edit] Introduction

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

<symbol> ::= <expression with symbols>

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 terminals.

[edit] Example

As an example, consider this possible BNF for a U.S. postal address:

<postal-address> ::= <name-part> <street-address> <zip-part>

     <name-part> ::= <personal-part> <last-name> <opt-jr-part> <EOL> 
                   | <personal-part> <name-part>
 
 <personal-part> ::= <first-name> | <initial> "." 

<street-address> ::= <opt-apt-num> <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 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 personal-part consists of either a first name or an initial followed by a dot.
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 things (such as the format of a first-name, apartment specifier, or ZIP-code) are left unspecified here. If necessary, they may be described using additional BNF rules.

[edit] Further examples

BNF's syntax 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> "|" <expression>
<line-end> ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | "<" <rule-name> ">"
<literal> ::= '"' <text> '"' | "'" <text> "'"

This assumes that no whitespace is necessary for proper interpretation of the rule. <EOL> to be the appropriate line-end specifier (in ASCII, carriage-return and/or line-feed, depending on the operating system). <rule-name> and <text> are to be substituted with a declared rule's name/label or literal text, respectively.

[edit] 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 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 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.

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:

Optional items enclosed in square brackets. E.g. [<item-x>]
Items repeating 0 or more times are enclosed in curly brackets. E.g. <word> ::= <letter> { <letter> }
Items repeating 1 or more times are followed by a '+'
Terminals may appear in bold and NonTerminals in plain text rather than using italics and angle brackets
Repetition of an item is signified by an asterisk placed after that item: ‘*’
Alternative choices in a production are separated by the ‘|’ symbol. E.g., <alternative-A> | <alternative-B>
Where items need to be grouped they are enclosed in simple parenthesis

[edit] See also

Ashtadhyayi (Sanskrit grammar with mathematical structure)
GOLD BNF parser
GNU bison GNU Version of Yacc
Yacc Parser Generator (used with Lex pre-processor)
ABNF
Regular Expression

[edit] References

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

[edit] External links

Algol-60 BNF, the original BNF.
[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.
RFC 4234 Augmented BNF for Syntax Specifications: ABNF
Grammatica Parser
Spirit Parser da:BNF