Backus-Naur form

As the emerging discipline of computer science struggled with the need to precisely define the rules for new program-ming languages, the Backus-Naur form (BNF) was devised as a notation for describing the precise grammar of a com-puter language. BNF represents the unification of separate work by John W. Backus and Peter Naur in 1958, when they were trying to write a specification for the Algol language.

A series of BNF statements defines the syntax of a lan-guage by specifying the combinations of symbols that con-stitute valid statements in the language.

Thus in a hypothetical language a program can be defined as follows:

<program> ::= program <declaration_sequence>

begin <statements_sequence>
end;

Here the symbol ::= means “is defined as” and items in brackets <> are metavariables that represent placeholders for valid symbols. For example, <declaration_sequence> can consist of a number of different statements defined else-where.

Statements in square brackets [] indicate optional ele-ments. Thus the If statement found in most programming languages is often defined as:

<if_statement> ::= if >boolean_expression> then <statement_sequence>

[ else <statement_sequence> ]

end if ;

This can be read as “an If statement consists of a boolean_ expression (something that evaluates to “true” or “false”) followed by one or more statements, followed by an optional else that in turn is followed by one or more statements, fol-lowed by the keywords end if.” Of course each item in angle brackets must be further defined—for example, a Boolean_ expression.

Curly brackets {} specify an item that can be repeated one or more times. For example, in the definition

<identifier> ::= <letter> { <letter> | <digit> }

An identifier is defined as a letter followed by one or more instances of either a letter or a digit.

An extended version of BNF (EBNF) offers operators that make definitions more concise yet easier to read. The preceding definition in EBNF would be:

Identifier = Letter

{Letter | Digit}

BNF and EBNF are useful because they can provide unambiguous definitions of the syntax of any computer lan-guage that is not context-dependent (which is to say, nearly all of them). It can thus serve as a reference for introduc-tion of new languages (such as scripting languages) and for developers of parsers for compilers.