Fortunately, Sod is syntactically quite simple. The notation is slightly
unusual in order to make the presentation shorter and easier to read.
+
+\subsection{Empty production}
+
+The letter $\epsilon$ denotes the empty nonterminal
+\begin{quote}
+ \syntax{$\epsilon$ ::=}
+\end{quote}
+
+
+\subsection{Parentheses}
+
+Parentheses are used for grouping of alternatives within the right-hand side
+of a production rule. Specifically, a right-hand side
+\begin{quote}
+ \syntax{$\alpha$ @($\beta_1$ @! $\beta_2$ $| \cdots |$ $\beta_n$@) $\gamma$}
+\end{quote}
+where $\alpha$, $\beta_i$, and $\gamma$ are any sequence of nonterminal
+symbols or parenthesized groups, is equivalent to the right-hand side
+\begin{quote}
+ \syntax{$\alpha$ $b$ $\gamma$}
+\end{quote}
+together with the new production
+\begin{quote}
+ \syntax{$b$ ::= $\beta_1$ @! $\beta_2$ $| \cdots |$ $\beta_n$}
+\end{quote}
+where $b$ is a new nonterminal symbol.
+
+Given the indexed-nonterminal notation described below, one might consider a
+group \syntax{@($\beta_1$ @! $\beta_2$ $| \cdots |$ $\beta_n$@)} equivalent
+to \syntax{<group>@[$\beta_1$ @! $\beta_2$ $| \cdots |$ $\beta_n$@]}, where
+\begin{quote}
+ \syntax{<group>@[$x$@] ::= $x$}
+\end{quote}
+
+
+\subsection{Indexed nonterminals}
+
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
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
-$x[\alpha_1 | \beta_1 | \cdots, \ldots, \alpha_n | \beta_n | \cdots]$ means
-exactly the same as $x[a_1, \ldots, a_n]$ with the additional rules
+\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{$a_1$ ::= $\alpha_1$ @! $\beta_1$ @! $\cdots$} \\
- \hbox{}\qquad $\vdots$ \\
- \syntax{$a_n$ ::= $\alpha_n$ @! $\beta_n$ @! $\cdots$}
+ \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 letter $\epsilon$ denotes the empty nonterminal
-\begin{quote}
- \syntax{$\epsilon$ ::=}
-\end{quote}
+
+\subsection{Common indexed productions}
The following indexed productions are used throughout the grammar, some often
enough that they deserve special notation.