Fortunately, Sod is syntactically quite simple. The notation is slightly
unusual in order to make the presentation shorter and easier to read.
+The letter $\epsilon$ denotes the empty nonterminal
+\begin{quote}
+ \syntax{$\epsilon$ ::=}
+\end{quote}
+
Anywhere a simple nonterminal name $x$ may appear in the grammar, an
\emph{indexed} nonterminal $x[a_1, \ldots, a_n]$ may also appear. On the
left-hand side of a production rule, the indices $a_1$, \ldots, $a_n$ are
variables which vary over all nonterminal and terminal symbols, and the
variables may also appear on the right-hand side in place of a nonterminal.
-Such a rule stands for a family of rules, in each variable is replaced by
-each possible simple nonterminal or terminal symbol.
-
-The letter $\epsilon$ denotes the empty nonterminal
+Such a rule stands for a family of rules, in which each variable is replaced
+by each possible simple nonterminal or terminal symbol.
+
+As a notational convenience, where an indexed nonterminal appears on the
+right-hand side of a production rule, each actual argument may be a sequence
+of alternative right-hand sides, separated by `$|$', rather than a a simple
+terminal or nonterminal symbol. A complex indexing of this form, say
+\syntax{$x$@[$\alpha_1^1$ @! $\alpha_1^2$ $| \cdots |$ $\alpha_1^{m_1},
+\ldots,$ $\alpha_n^1$ @! $\alpha_n^2$ $| \cdots |$ $\alpha_n^{m_n}$@]}
+means exactly the same as \syntax{$x$@[$a_1, \ldots, a_n$@]} with the
+additional rules
\begin{quote}
- \syntax{$\epsilon$ ::=}
+ \syntax{$a_1$ ::= $\alpha_1^1$ @! $\alpha_1^2$ $| \cdots |$ $\alpha_1^{m_1}$} \\*
+ \hbox{}\qquad $\vdots$ \\*
+ \syntax{$a_n$ ::= $\alpha_n^1$ @! $\alpha_n^2$ $| \cdots |$ $\alpha_1^{m_n}$}
\end{quote}
+where $a_1$, \ldots, $a_n$ are new nonterminal symbols.
The following indexed productions are used throughout the grammar, some often
enough that they deserve special notation.