bnf.doc

xorp源码hg

\def\filedate{12/09/92 12:56pm}
%\iffalse
%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename        = "bnf.sty",
%%%     date            = "9 Dec 1992",
%%%     time            = "12:56 BST",
%%%     author          = "Mike Piff",
%%%     address         = "Dr M. J. Piff
%%%                        University of Sheffield
%%%                        Department of Pure Mathematics
%%%                        Hicks Building
%%%                        Hounsfield Road
%%%                        SHEFFIELD S3 7RH
%%%                        England",
%%%     telephone       = "0742-305468",
%%%     email           = "[e-mail] (Janet)",
%%%     keywords        = "Backus,Naur,syntax,grammar",
%%%     supported       = "yes",
%%%     checksum        = "10141 528 2414 20734",
%%%     docstring       = "A style option to LaTeX for producing
%%%                        Backus-Naur Form syntax notation.",
%%%  }
%%% ====================================================================
%% This is BNF.STY
%% Copyright (C) 1992 by Mike Piff.
%% All rights reserved.
%% Copying of this file is authorized only if
%% you make absolutely no changes to your copy.
%%
%% Usage:
%% \documentstyle[bnf]{article} %% in LaTeX
%<+driver>\documentstyle[12pt,doc,bnf]{article}
%<+driver>%    Select paper size.
%<+driver>\def\firstletter#1#2\end{#1}
%<+driver>\typein[\papersize]{Intended paper size?^^J%
%<+driver>Choices: US letter size or A4; enter u or a, please:}%
%<+driver>\edef\setpapersize{\lowercase{\edef\noexpand\papersize{%
%<+driver>  \noexpand\firstletter\papersize u\noexpand\end}}}
%<+driver>\setpapersize
%<+driver>\if a\papersize\relax
%<+driver>  \typeout{%
%<+driver>OK, adjusting textwidth and textheight for A4 paper size}
%<+driver>%    A4 paper size, 21cm x 30cm
%<+driver>  \textwidth 6.375 true in \textheight 42\baselineskip
%<+driver>\else
%<+driver>  \typeout{%
%<+driver>Adjusting textwidth and textheight for US letter paper size}
%<+driver>%    US letter-size paper, 8.5 x 11 in:
%<+driver>  \textwidth 6.5in \textheight 8.9in
%<+driver>\fi
%<+driver>\begin{document}
%<+driver>   \DocInput{bnf.doc}
%<+driver>\end{document}
%<*style>
%\fi
%
\typeout{Backus-Naur Form style option for LaTeX, (c) Mike Piff, \filedate}
%\CheckSum{334}
%\MakeShortVerb{\"}
%\emergencystretch1in
%\title{{\protect\bf Backus Naur Form in \protect\LaTeX}}
%\author{Mike Piff}
%\date{\filedate}
%\maketitle
%\thispagestyle{headings}
%\begin{abstract}
%  This article explains how to produce Backus-Naur Form
%  in a \LaTeX\ document.
%  The objective is to produce this notation as simply and efficiently
%  as possible.
%  Thus, short cuts looking like the teletype equivalents are set up
%  for most of the symbolism.
%  This has the advantage that the source looks generally comparable
%  to the typeset equivalent.
%\end{abstract}
%
%\section{Introduction}
%\begin{bnf}
%The macros described below grew out of a sub-task of the \LaTeX-3 project.
%The objective was to program \LaTeX\ to produce Backus-Naur Form, or BNF
%for short, which is a way of describing the syntax of formal languages.
%In particular, the context-free syntax of modern programming languages
%and of \TeX\ itself are described in this notation.
%
%The idea is that we set up an extended language consisting of all of
%the symbols that are part of our real language, the {\bf terminal}
%symbols, such as "a", "(", "@" or "{", and also some {\bf non-terminal}
%symbols which represent syntactic structures, such as
%$<statement>$, $<space token>$ or $<module>$.
%A list of {\bf productions} is then given.
%In the usual {\bf context-free} case, each one of these productions states
%that a certain non-terminal can be replaced by a string of terminal
%and non-terminal symbols. For instance, a production might express the fact
%that a $<statement>$ could be a $<while statement>$. We write
%$$<statement>-><while statement>$$
%in BNF. Another production might say
%$$<while statement>->"WHILE" <condition> "DO" <statement sequence> "END"$$
%to indicate the form of a while-loop in the language.
%
%In general there will be several productions from any given non-terminal.
%For instance, a $<statement>$ could also be a $<for statement>$.
%Each non-terminal defines a {\bf language} of strings or {\bf words}
%in the terminal alphabet. Starting from the non-terminal, randomly
%substitute a replacement string for it. Then, in that replacement string,
%choose any non-terminal and randomly substitute one of its replacement
%expressions. Continue randomly replacing non-terminals until a string
%with no non-terminals results. This string is in the language defined
%by the non-terminal. For instance, the non-terminal $<statement>$ would
%define a language consisting of all valid statements in the programming
%language, and a non-terminal $<module>$ would generate all valid
%modules.
%
%Because it is possible for a non-terminal to expand to nothing at all,
%we introduce the symbol $\Empty$ to indicate a null replacement string.
%
%In more complicated examples, we have {\bf context sensitive} productions,
%such as
%$$"a"<B>"cd"<E>->"d"<D>$$
%which say that the string $"a"<B>"cd"<E>$ may be replaced by the string
%$"d"<D>$ anywhere that it appears. There might not be any direct replacement
%for either $<B>$ or $<E>$.
%
%Backus-Naur Form allows us to condense several productions into one
%compound production.
%Thus, the productions
%\begin{eqnarray*}
%  <S>&->&"a"<B><D>"c"\\
%  <S>&->&"a"<C><D>"c"
%\end{eqnarray*}
%are condensed into the single production
%$$<S>->"a"(<B>|<C>)<D>"c".$$
%It indicates certain {\em alternatives\/} in the replacement.
%
%Similarly, the two productions
%\begin{eqnarray*}
%  <S>&->&"a"<B><C>"c"<D>"c"\\
%  <S>&->&"a"<D>"c"
%\end{eqnarray*}
%can be condensed into
%$$<S>->"a"[<B><C>"c"]<D>"c".$$
%This indicates that a substring $s$ in the replacement string
%is {\em optional}. We have the alternative form
%$$<S>->"a"(<B><C>"c"|\Empty)<D>"c".$$
%
%
%A more complex case is that of an unlimited number of repetitions of a
%substring. For instance, identifiers are often defined as consisting of
%a letter followed by arbitrarily many letters and digits.
%An example might then be
%\begin{eqnarray*}
%  <identifier>&->&<letter><sequence>\\
%  <sequence>&->&\Empty\\
%  <sequence>&->&<letter><sequence>\\
%  <sequence>&->&<digit><sequence>
%\end{eqnarray*}
%where it is assumed that these are the only productions that use the
%non-terminal $<sequence>$. The above productions are condensed into
%$$<identifier>-><letter>{@ <letter>|<digit>}.$$
%
%Further notation is used to express the fact that the string $w_2$ is
%obtained from the string $w_1$ by the use of just one substitution defined
%by one production. We write $w_1=>w_2$. If $w_2$ is obtainable from $w_1$
%by a sequence of substitutions we write $w_1=>^*w_2$.
%\end{bnf}
%
%\section{The macros}
%The macros in "bnf.sty" can be used in one of two ways.
%The first is to use the long forms of the commands to generate the
%BNF notation. These only work in mathematics mode.
%
%The second is to
%surround the block where BNF notation is required within a "bnf"
%environment, or to use the command "\bnf" locally or globally.
%In either case, the effect is to change the meaning of certain characters
%in the input stream when they are met in mathematics mode. This makes
%it possible to use the short forms of the commands.
%
%We first describe the long forms of the commands.
%
%The notation $\begin{NonTerminal}non terminal\end{NonTerminal}$
%is produced by the environment "NonTerminal",
%surrounding the name of the symbol. Spaces in the name are respected, and
%the font used is governed by the definition of "\NonTerminalStyle".
%
%A terminal letter or string is produced by the command "\Terminal",
%which equates to "\verb*" in \LaTeX; thus \verb*|\Terminal"xy z"|
%produces $\Terminal"xy z"$, and \verb*|\Terminal`"`|
%produces~$\Terminal`"`$.
%By redefining the commands "\PreTerminal" and "\PostTerminal", the
%terminal strings can be started and ended with given strings; for instance,
%we might want all such terminal strings to begin and end with a
%double quote symbol. We could achieve this by means of the following
%definitions.
%\begin{verbatim}
%   \def\PreTerminal{\mbox{\tt"}} \let\PostTerminal\PreTerminal
%\end{verbatim}
%The empty string $\Empty$ is generated
%by "\Empty".
%
%The production symbol $\Production$ is produced by "\Production", while
%"\Yields" yields $\Yields$. The alternative symbol $\OR$ is "\OR",
%and the optional brackets $\Optional w_1\endOptional$ are generated by
%the environment "Optional". Environment "Star" will generate the
%repetition braces $\Star w_2\endStar$. Ordinary round meta-brackets
%$\Bracket w_3\endBracket$ are generated by the "Bracket" environment.
%
%Here is an example, taken from Modula-2.
%\begin{verbatim}
%$$    \begin{NonTerminal}Case Statement\end{NonTerminal}
%      \Production\Terminal"CASE"
%      \begin{NonTerminal}expression\end{NonTerminal}
%      \Terminal"OF"
%      \begin{NonTerminal}case\end{NonTerminal}
%      \begin{Star}
%         \Terminal"|"\begin{NonTerminal}case\end{NonTerminal}
%      \end{Star}
%      \begin{Optional}
%         \Terminal"ELSE"
%         \begin{NonTerminal}Statement Sequence\end{NonTerminal}
%      \end{Optional}
%      \Terminal"END" $$
%\end{verbatim}
%{\small
%$$    \begin{NonTerminal}Case Statement\end{NonTerminal}
%      \Production\Terminal"CASE"
%      \begin{NonTerminal}expression\end{NonTerminal}
%      \Terminal"OF"
%      \begin{NonTerminal}case\end{NonTerminal}
%      \begin{Star}
%         \Terminal"|"\begin{NonTerminal}case\end{NonTerminal}
%      \end{Star}
%      \begin{Optional}
%         \Terminal"ELSE"
%         \begin{NonTerminal}Statement Sequence\end{NonTerminal}
%      \end{Optional}
%      \Terminal"END" $$
%}%
%
%\begin{bnf}
%The short forms are now described. We can get $<A>$ by typing "<A>",
%and
%\DeleteShortVerb\"
%$"ab c"$
%\MakeShortVerb\"
%by typing \verb*|"ab c"| or \verb*|`ab c`|. The pairs "->" and "=>" give
%$->$ and $=>$ respectively, and $[s_1](s_2|s_3)$ is obtained by
%typing "[s_1](s_2|s_3)". Notice that these yield "\left" and "\right"
%style brackets. The Star environment ${@w}$ can be produced by
%"{@w}". There seemed to be no obvious way to obtain this one
%directly from the braces. The "@" symbol produces a "Star" group
%starting at the current point and ending at the end of the current group.
%Thus, it must be used within grouping brackets "{" and~"}".
%
%There is another restriction on the use of "@". Because we might also want to
%produce $@<$ and $@>$ in some BNF text, these can be obtained by using
%the pairs "@<" and "@>". An alternative that is provided is to use
%"\lt" and~"\gt". Otherwise "<" and ">" will attempt to open and close
%a "NonTerminal" environment, probably unsuccessfully.
%\end{bnf}
%
%Here are some examples of the short forms.
%\begin{verbatim}
%\begin{bnf}
%   \begin{eqnarray*}