BNF & the Formal Definition

The ALGOL 60 Report defines syntax with metalinguistic formulae, now called BNF (Backus–Naur Form, a name popularized by Knuth in 1964; "Backus Normal Form" was used earlier):

3.1 Backus–Naur Form

The ALGOL 60 Report defines syntax with metalinguistic formulae, now called BNF (Backus–Naur Form, a name popularized by Knuth in 1964; "Backus Normal Form" was used earlier):

<...> brackets a metalinguistic variable (a nonterminal).

::= means "is defined as".

| means "or".

Everything else stands for itself (terminals).

Recursion replaces repetition: an unsigned integer is a digit, or an unsigned integer followed by a digit.

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<unsigned integer> ::= <digit> | <unsigned integer> <digit>
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

3.2 Selected ALGOL 60 syntax (from the Revised Report)

Notice how the grammar itself prevents the dangling else: an <if statement> must be followed by an *unconditional* statement, so if a then if b then s1 else s2 is not syntactically valid — you must write if a then begin if b then s1 else s2 end.

<program> ::= <block> | <compound statement>
<block> ::= <unlabelled block> | <label> : <block>
<unlabelled block> ::= <block head> ; <compound tail>
<block head> ::= begin <declaration> | <block head> ; <declaration>
<compound statement> ::= <unlabelled compound> | <label> : <compound statement>
<unlabelled compound> ::= begin <compound tail>
<compound tail> ::= <statement> end | <statement> ; <compound tail>

<if clause> ::= if <Boolean expression> then
<conditional statement> ::= <if statement> | <if statement> else <statement>
        | <if clause> <for statement> | <label> : <conditional statement>
<if statement> ::= <if clause> <unconditional statement>

<for statement> ::= <for clause> <statement> | <label> : <for statement>
<for clause> ::= for <variable> := <for list> do
<for list> ::= <for list element> | <for list> , <for list element>
<for list element> ::= <arithmetic expression>
        | <arithmetic expression> step <arithmetic expression> until <arithmetic expression>
        | <arithmetic expression> while <Boolean expression>

3.3 Syntax and semantics in the Report

Each section of the Report has the same structure:

Syntax — BNF rules.

Semantics — precise English prose.

Types / restrictions where relevant.

The Report is small enough to read in an afternoon — and you should (see Appendix 45.6).

3.4 What BNF cannot say

BNF is context-free. It cannot express rules such as:

An identifier must be declared before use (in an enclosing block).

The number of actual parameters must match the formal parameters.

Types must agree in assignments.

ALGOL 60 states such rules in prose. ALGOL 68 tried to capture them formally with a two-level grammar (Chapter 38).

3.5 Extended BNF variants

Later notations add convenience: { x } for repetition, [ x ] for optional parts (Wirth's EBNF, used for Pascal), ISO 14977 EBNF, and ABNF (used in Internet RFCs). All descend from the ALGOL 60 Report.

(* Wirth-style EBNF for an ALGOL-like for statement *)
ForStatement = "for" Variable ":=" ForElement { "," ForElement } "do" Statement .
ForElement   = Expr [ "step" Expr "until" Expr | "while" BoolExpr ] .