BNF Notation

BNF (Backus-Naur Form, Definition 7.2.8, notes p. 138) is the practical
shorthand everyone actually uses to write context-free grammars. It was invented
to specify the syntax of ALGOL 60 and is now universal: every programming
language reference uses BNF.

BNF adds five convenience constructors to plain production rules:

1. Alternatives $s_1 \mid s_2 \mid \dots \mid s_n$ — choose one of the
$s_i$. This is shorthand for $n$ rules sharing a head.
2. Repetition $s^*$ — zero or more $s$'s. $s^+$ means one or more.
3. Optional $[s]$ — zero or one $s$.
4. Grouping $(s_1 ; s_2 ; \dots ; s_n)$ — usually for repetition.
5. Character sets $[s - t]$ — all characters $c$ with $s \le c \le t$.
6. Complements $[\hat{} \; s_1, \dots, s_n]$ — all characters except those.

All of these can be eliminated by introducing auxiliary nonterminals and
extra rules. So BNF is purely a notational convenience — it adds zero expressive
power. For example, $X \to Z (s^*) W$ expands to:
- $X \to Z Y W$
- $Y \to \epsilon$
- $Y \to Y s$

And $X \to Z (s^+) W$ expands to:
- $X \to Z Y W$
- $Y \to s$
- $Y \to Y s$

BNF is the lingua franca of compiler writers and language designers.