\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!!' 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!!' 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$}] :;\\ , , . :;,. :"0";"1";"2";"3";"4";"5";"6";"7";"8";"9". :"$=$";"$\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$}] :;\\ , , . :;,. :"0";"1";"2";"3";"4";"5";"6";"7";"8";"9". :"$=$";"$\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}