hugh@phoibos.cs.kun.nl (Hugh Osborne) (11/05/90)
% The macros have been posted seperately.
\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
\subsection{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 the right hand of a rule
\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}
A context free grammar for this notation is presented in
figure~\ref{grammar}.
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){$\langle$}{$\rangle$}]
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){$\langle$}{$\rangle$}]
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}
\subsection{The grammar environment: 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 aviod this situation by providing the layout
explicitly.
\end{document}