\documentstyle[bnf]{article}
\title{Pretty Printing Context Free Grammars}
\author{Hugh Osborne\\
        Department of Informatics,\\
        Faculty of Mathematics and Informatics,\\
        University of Nijmegen,\\
        Toernooiveld,\\
        6525 ED Nijmegen,\\
        The Netherlands.\\
        tel. +31.(0)80.652599\\
        email {\tt hugh@cs.kun.nl}}

\begin{document}
\maketitle
\section{The grammar Environment}
The {\tt grammar}
environment will take a context free grammar, written using the notation
used in~LP81\footnote{Harry R.\ Lewis and Christos H.\ 
Papadimitriou, {\sl Elements of the Theory of Computation,}
Prentice-Hall, 1981} and pretty print the grammar. The {\tt grammar}
environment has up to five optional parameters, which specify the notation to
be used to print the grammar. Note that whichever notation is chosen for
the output, the {\tt grammar} environment only recognises the LP81~notation in the input.

A short summary of the notation used in~LP81 is presented here for
those readers not familiar with it. It is assumed that the reader is
familiar with context free grammars.
\begin{itemize}
 \item There is a ``:'' between the left hand side of a rule and its right hand side
 \item Two alternatives within a rule are separated by a ``;''
 \item A ``,'' is placed between members of the same alternative
 \item Each rule ends with a ``.''
\end{itemize}

The optional parameters of the {\tt grammar} environment are all of the
form \verb![(!{\sc symbol name}\verb!)!{\sc replacement}\verb!]!, where
{\sc symbol name} is one of ``{\tt colon}'', ``{\tt semicolon}'', ``{\tt
period}'', ``{\tt comma}'' and ``{\tt quote}''. {\sc replacement} is then the text\footnote{In the case of ``{\tt quote}'', the texts --- the first text
is the replacement for an opening quote, the second for a closing quote.} that
will replace the symbol specified by {\sc symbol name}. Note that a new
line (\verb!\\!) can be included in the replacement text, in which case
the output will automatically start on a new line after each occurrence
of the symbol specified. The default values are
\begin{itemize}
  \item \verb![(!colon\verb!){:\\}]!
  \item \verb![(!semicolon\verb!){;\\}]!
  \item \verb![(!period\verb!){.\\}]!
  \item \verb![(!comma\verb!){,}]!
  \item \verb![(!quote\verb!){``}{''}]!
\end{itemize}

Strings in the grammar environment are indicated by double-quote symbols
(\verb!"!). The colon, semicolon, period and comma have no special
significance within a string, but are the same simple characters they
are outside the grammar environment. A double-quote symbol can be
produced by using the \verb!\quotesymbol! command.

All of these features are demonstrated below. The text:
\begin{verbatim}
\begin{grammar}
  [(colon){::$\Rightarrow$}]
  [(semicolon){ $|$}]
  [(period){ \rule{1ex}{1ex}\\}]
  [(quote){`}{'}]
grammar environment:\\
  "\verb!\begin{grammar}!",\\
	optional parameters,\\
	 context free grammar,\\
	  "\verb!\end{grammar}!".
optional parameters:\\
  "[",optional parameter,"]",\\
   optional parameters;.
optional parameter:\\
  "(", specification, ")",\\
   \LaTeX\ strings.
\LaTeX\ strings:\\
   \LaTeX\ string;\\
   "\{",\LaTeX\ string,"\}",\\
   \LaTeX\ strings.
specification:\\
  "{\tt colon}";\\
  "{\tt semicolon}";\\
  "{\tt period}";\\
  "{\tt comma}";\\
  "{\tt quote}".
context free grammar:\\
  rule,\\
  context free grammar;.
rule:\\
  nonterminal,":",\\
  alternatives,".".
alternatives:\\
  alternative,";",\\
   alternatives;.
alternative:
  members;.
members:\\
  member,",",members;\\
  member.
member:\LaTeX\ string,string.
string:"{\tt \quotesymbol}",
  \LaTeX\ string ,
  "{\tt \quotesymbol}".
\end{grammar}
\end{verbatim}
produces the following output:
\begin{grammar}
  [(colon){::$\Rightarrow$}]
  [(semicolon){ $|$}]
  [(period){ \rule{1ex}{1ex}\\}]
  [(quote){`}{'}]
grammar environment:\\
  "\verb!\begin{grammar}!",\\
	optional parameters,\\
	 context free grammar,\\
	  "\verb!\end{grammar}!".
optional parameters:\\
  "[",optional parameter,"]",\\
   optional parameters;.
optional parameter:\\
  "(", specification, ")",\\
   \LaTeX\ strings.
\LaTeX\ strings:\\
   \LaTeX\ string;\\
   "\{",\LaTeX\ string,"\}",\\
   \LaTeX\ strings.
specification:\\
  "{\tt colon}";\\
  "{\tt semicolon}";\\
  "{\tt period}";\\
  "{\tt comma}";\\
  "{\tt quote}".
context free grammar:\\
  rule,\\
  context free grammar;.
rule:\\
  nonterminal,":",\\
  alternatives,".".
alternatives:\\
  alternative,";",\\
   alternatives;.
alternative:
  members;.
members:\\
  member,",",members;\\
  member.
member:\LaTeX\ string,string.
string:"{\tt \quotesymbol}",
  \LaTeX\ string ,
  "{\tt \quotesymbol}".
\end{grammar}
\section{Update}
The {\tt grammar} environment has been extended to allow the use of the
`\verb!<!' and `\verb!>!' symbols to delimit nonterminals in the grammar
(in a manner reminiscent of Backus-Naur form). These symbols can then be
redefined in the same way as the `\verb!"!' symbol by means of an
optional paramter at the start of the environment. The {\sc symbol name}
part is then ``\verb!nonterminal!''. The default value is to use the
symbols themselves. If the symbols have been redefined, the `\verb!<!'
and `\verb!>!' symbols can be produced using \verb!\lessthan! and
\verb!\greaterthan! respectively.
\begin{verbatim}
\begin{grammar}
      [(colon){$\rightarrow$}]
      [(semicolon)$|$]
      [(comma){}]
      [(period){\\}]
      [(quote){\begin{bf}}{\end{bf}}]
      [(nonterminal){$\langle$}{$\rangle$}]
<expression>:<number>;\\
             <number>, <relational operator>, <number>.
<number>:<digit>;<digit>,<number>.
<digit>:"0";"1";"2";"3";"4";"5";"6";"7";"8";"9".
<relational operator>:"$=$";"$\lessthan\greaterthan$";
                      "$\lessthan$";"$\greaterthan$";
                      "$\lessthan=$";"$\greaterthan=$";"in".
\end{grammar}
\end{verbatim}
gives
\begin{grammar}
      [(colon){$\rightarrow$}]
      [(semicolon)$|$]
      [(comma){}]
      [(period){\\}]
      [(quote){\begin{bf}}{\end{bf}}]
      [(nonterminal){$\langle$}{$\rangle$}]
<expression>:<number>;\\
             <number>, <relational operator>, <number>.
<number>:<digit>;<digit>,<number>.
<digit>:"0";"1";"2";"3";"4";"5";"6";"7";"8";"9".
<relational operator>:"$=$";"$\lessthan\greaterthan$";
                      "$\lessthan$";"$\greaterthan$";
                      "$\lessthan=$";"$\greaterthan=$";"in".
\end{grammar}
There is one feature of the {\tt grammar} environment which could be
considered a bug. The normal line breaking routine is still in force
inside a {\tt grammar} environment but a new line produced by \LaTeX\
will {\em not} use the {\tt grammar} environment's layout. {\em Only
newlines given explicitly with a \verb!\\! or \verb!\newline! command,
or implicitly by means of one the redefined symbols (`\verb!:!',
`\verb!;!' etc.) will use the {\tt grammar} layout!}\/ It is therefore
recommended that you avoid this situation by providing the layout
explicitly.
\section{Second Update}
Some bugs have been reported. Most of these have been corrected. See the
{\tt bnf.bugs} file accompanying this package. Two additions have been
made to the grammar environment.

Firstly the (font type) command
\verb!\escapegrammar! has been provided. This declares a non-grammar
``font'' to be in effect, so that the ``\verb!:;.,"<>!'' characters all
have their normal meaning. Be careful to enclose uses of
\verb!\escapegrammar! in braces, as you would an ordinary font command,
otherwise the rest of your grammar will not be pretty printed.

The second addition is to the optional parameter declarations. For the
sake of consisitency with the {\tt [(nonterminal)\ldots]} declaration, a
{\tt [(terminal)\ldots]} declaration has been provided. In order to maintain 
compatability, the old {\tt [(quote)\ldots]} declaration remains
possible.

A short example using both of these innovations is
\begin{verbatim}
\begin{grammar}[(terminal){(}{)}]
{\escapegrammar This grammar only uses the `{\tt :}', `{\tt "}'
and `{\tt .}' ``grammar symbols''.}

S:"a".
\end{grammar}
\end{verbatim}
produces
\begin{grammar}[(terminal){(}{)}]
{\escapegrammar This grammar only uses the `{\tt :}', `{\tt "}'
and `{\tt .}' ``grammar symbols''.}

S:"a".
\end{grammar}
\end{document}
