perm filename BNF.TEX[CLS,LSP] blob sn#847181 filedate 1987-10-16 generic text, type C, neo UTF8
C00001 00001
C00002 00002	\input macros
C00006 ENDMK
\input macros

We use an extended Backus Normal Form to describe the syntax of the \OS. The
extension we use is as follows:

$$\lbrack\!\lbrack O\lbrack\!\lbrack$$

An expression of this form will appear whenever a list of elements is
to be spliced into a larger structure. The meta-syntactic unit $O$ represents
a description of the syntax of some number of syntactic units to be spliced.
Suppose $O$ is of the form:

$$\eqalignno{O&=O\sub 1 \vert\ldots O\sub n\cr
  	     O\sub i &= S \vert S{\rm *}&1\leq i\leq n\cr}$$

If a syntactic unit in the expansion of a
$\lbrack\!\lbrack\ldots\lbrack\!\lbrack]]$ expression derived from
syntactic unit whose form is $S{\rm *}$, we say that the syntactic unit
``derives from a starred option.''

The expression $\lbrack\!\lbrack O\lbrack\!\lbrack$ means that a list
of the form

$$(O\sub{i\sub 1}\ldots O\sub{i\sub j})\quad 1\leq j$$

\noindent is spliced into the enclosing expression where if $n \neq m$, 
$1\leq n,m\leq j$,
then either $O\sub{i\sub n}\neq O\sub{i\sub m}$
or $O\sub{i\sub n}$ and $O\sub{i\sub m}$
are derived from starred options.
That is, a subset of the elements $O\sub i$, $1\leq i\leq n$ can appear in
any order, but no element is allowed to be repeated unless its
meta-syntactic unit is of the form $S{\rm *}$.

For example, the expression

$$(\hbox{{\tt foo}} {\lbrack\!\lbrack} \hbox{{\tt A}} 
 \vert \hbox{{\tt B}} \vert \hbox{{\tt C}}{\lbrack\!\lbrack}\hbox{{\tt bar}})$$

\noindent is a description of any of these:

(foo bar)
(foo A B bar)
(foo B A bar)
(foo A C B bar)

\noindent but not of any of these:

(foo A A bar)
(foo C B A B C foo)

\noindent The expression

$$(\hbox{{\tt foo}} {\lbrack\!\lbrack} \hbox{{\tt A}} 
 \vert \hbox{{\tt B}}{\rm *} \vert \hbox{{\tt C}}{\lbrack\!\lbrack}
 \hbox{{\tt bar}})$$

\noindent is a description of any of these:

(foo bar)
(foo A B C bar)
(foo A B B B B B C bar)
(foo C B A B B B bar)

\noindent but not of any of these:

(foo B B A A C C bar)
(foo C B C bar)