Debian Codegraph @

texmf-dist/source/latex/formal-grammar/formal-grammar.dtx

raw
1 % \iffalse meta-comment
2 % Copyright (C) 2021 by Martin Vassor
3 % This file may be distributed and/or modified under the
4 % conditions of the LaTeX Project Public License, either
5 % version 1.3 of this license or (at your option) any later
6 % version. The latest version of this license is in:
7 %
8 % http://www.latex-project.org/lppl.txt
9 %
10 % and version 1.3 or later is part of all distributions of
11 % LaTeX version 2005/12/01 or later.
12 %
13 % \fi
14
15
16
17 % \iffalse
18 %<package>\NeedsTeXFormat{LaTeX2e}
19 %<package>\ProvidesPackage{formal-grammar}[2022/02/09 v1.2 A package to typeset formal grammars]
20 %<package>\RequirePackage{xparse}
21 %<package>\RequirePackage{newfloat}
22 %<package>\RequirePackage{xcolor}
23 %<package>\RequirePackage{colortbl}
24 %<package>\RequirePackage{array}
25 %<package>\definecolor{LightCyan}{rgb}{0.8,1,1}
26 %<*driver>
27 \documentclass{ltxdoc}
28 \usepackage{formal-grammar}
29 \usepackage[hidelinks]{hyperref}
30 \usepackage{amsfonts}
31 \EnableCrossrefs
32 \CodelineIndex
33 \RecordChanges
34 \begin{document}
35 \DocInput{formal-grammar.dtx}
36 \end{document}
37 %</driver>
38 % \fi
39 %
40 % \CheckSum{112}
41 %
42 % \CharacterTable
43 % {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
44 % Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
45 % Digits \0\1\2\3\4\5\6\7\8\9
46 % Exclamation \! Double quote \" Hash (number) \#
47 % Dollar \$ Percent \% Ampersand \&
48 % Acute accent \' Left paren \( Right paren \)
49 % Asterisk \* Plus \+ Comma \,
50 % Minus \- Point \. Solidus \/
51 % Colon \: Semicolon \; Less than \<
52 % Equals \= Greater than \> Question mark \?
53 % Commercial at \@ Left bracket \[ Backslash \\
54 % Right bracket \] Circumflex \^ Underscore \_
55 % Grave accent \` Left brace \{ Vertical bar \|
56 % Right brace \} Tilde \~}
57 %
58 %
59 % \changes{v1.2}{2022/02/09}{Add the `center` option}
60 % \changes{v1.1}{2021/11/15}{Use Coloneqq if defined, internal changes, typos}
61 % \changes{v1.0}{2021/11/10}{Initial version for publication}
62 %
63 % \GetFileInfo{formal-grammar.sty}
64 %
65 % \title{The \textsf{formal-grammar} package\thanks{This document
66 % corresponds to \textsf{formal-grammar}~\fileversion,
67 % dated \filedate.}}
68 % \author{Martin Vassor\\ \texttt{[email protected]}}
69 %
70 % \maketitle
71 %
72 %\iffalse
73 %% \begin{abstract}
74 %% The \textsf{formal-grammar} package provides commands to typeset formal grammars.
75 %% \end{abstract}
76 %\fi
77 % \tableofcontents
78 %
79 % \section{Introduction}
80 %
81 % The notion of formal language is one of the most important in theoretical
82 % computer science. Intuitively, it is defined as follow: we are given a set
83 % \(\Sigma\) of \emph{letters} or \emph{symbols} (the \emph{alphabet}). For instance, we can consider
84 % \(\Sigma = \{a, b, \dots, z\}\): our symbols is the set of lowercase
85 % characters. A \emph{word} is a tuple of letters. For instance, \(\langle a, b,
86 % c\rangle\) is a word of three letters over \(\Sigma\). Therefore, \(\Sigma^k\)
87 % is the set of words of \(k\) letters over \(\Sigma\). Notice in particular
88 % that \(\Sigma^0\) is the set \(\{\langle\rangle\}\). \(\langle\rangle\) is
89 % the unique word that contains \(0\) letters. It is often noted
90 % \(\varepsilon\).
91 %
92 % The set of all words over \(\Sigma\) (independently of their length) is
93 % defined as \(\Sigma^\star = \bigcup_{i\in\mathbb{N}} \Sigma^i\).
94 %
95 % An important operation is the \emph{concatenation}, noted \(\cdot\), which
96 % consists in sticking two words together. For instance \(\langle a,
97 % b\rangle\cdot\langle c\rangle = \langle a, b, c\rangle\). For the sake of this
98 % quick introduction, we do not specify further this operation.
99 %
100 % A (formal) language over \(\Sigma\) is a subset of \(\Sigma^\star\):
101 % \(\mathbb{L}\subseteq\Sigma^\star\). That is, it consists in picking some of
102 % the words of \(\Sigma^\star\). For instance we can define the language
103 % \(\mathbb{L}_{a}\) which contains all words that begin with an \(a\):
104 % \(\mathbb{L}_a = \{\langle a \rangle \cdot w, w\in \Sigma^\star\}\).
105 %
106 % We can see that describing languages by the mean of equations is quite
107 % tedious. Therefore, we most often use \emph{grammars}, which are a set of
108 % rules that characterise a language. In particular, one of the standard way to
109 % define a grammar is what we call the \textsc{bnf}, for \emph{Backus-Naur form}
110 % (or \emph{Backus normal form}). Such grammars are defined from two sets of
111 % elements: \emph{terminal} and \emph{non-terminal} (by convention, in this
112 % document, non-terminal are in calligraphic font, except when explicitely
113 % stated otherwise). Basically, \emph{terminal}
114 % correspond to the alphabet, and \emph{non-terminal} are names of rules.
115 %
116 %A rule
117 % has the form \begin{grammar}\firstcase{R}{a}{}\end{grammar}, where
118 % \(\nonterm{R}\) is the name of the rule, and \(a\) is the production. The name
119 % of the rule is a non-terminal, and the production is a sequence of terminals
120 % and non-terminal. If a rule has multiple possible productions, we separate
121 % them as follow: \begin{grammar}\firstcase{S}{a\gralt
122 % a\nonterm{S}}{}\end{grammar}.
123 %
124 % Finally, a grammar is a set of rules.
125 %
126 % A production defines a set of words. Without
127 % going into formalities, a production produces
128 % the words described by the terminal, and where non-terminal are replaced by
129 % productions of the corresponding rule. For instance, the rule \(\nonterm{S}\)
130 % above produces \(\{a, aa, aaa, \dots\}\). Notice that rules can be mutually
131 % recursive.
132 %
133 % This package provides a new environment (|grammar|) and associated commands to
134 % typeset \textsc{bnf} grammars. It allows to easily write formal grammars. For instance,
135 % the syntax of the \(\lambda\)-calculus is given in Grammar~\ref{gr:lambda}.
136 %
137 %\begin{grammar}[\(\lambda\)-calculus syntax][][gr:lambda]
138 % \firstcase{T}{\nonterm{V}}{Variable}
139 % \highlight
140 % \otherform{(\nonterm{T}\ \nonterm{T})}{Application}
141 % \highlight
142 % \otherform{\lambda \nonterm{V}\cdot\nonterm{T}}{Abstraction}
143 % \downplay
144 % \firstcase{V}{x, y, \dots}{Variables}
145 %\end{grammar}
146 %
147 % \section{Usage}
148 % \subsection{Loading the package (and loading options)}
149 %
150 % This package accepts a single option when loading: \verb+center+. If the
151 % option is set, the initial \(\gralt\) of non-initial lines of multi-line rules is
152 % centered with respect to the \(::=\) of the initial line. If
153 % unset, the \(\gralt\) is aligned to the right.
154 %
155 % \subsection{Basic usage}
156 %
157 % \paragraph{Creating a grammar.}
158 % We first start creating a grammar using the |grammar| environment.
159 %
160 % \DescribeEnv{grammar}
161 % This is the main environment to write your grammar. |grammar| accepts 3
162 % optional arguments: the first one is a possible caption; the second is a
163 % positionning option; and the third is a label.
164 %
165 % If none of the optional arguments are provided, the grammar is inlined (i.e.
166 % not in a float environment. If the first argument is set (the optional
167 % caption), the grammar is typeset in a float, captionned with the provided
168 % caption.
169 % The second optional argument is a positionning option (one of \texttt{t},
170 % \texttt{b}, \texttt{p}, \texttt{h}, etc.). The default is \texttt{p}.
171 % The last argument is a label, used to reference the grammar elsewhere in the
172 % document.
173 %
174 % The grammar can then be populated using two basic constructs: |firstcase| and
175 % |otherform|.
176 %
177 % \DescribeMacro{\firstcase}
178 % The |firstcase| command creates a new non-terminal of the grammar. It takes 3 mandatory
179 % arguments: the letter(s) of the non-terminal, the definition, and an
180 % explanation.
181 % \DescribeMacro{\otherform}
182 % On the other hand, |otherform| create an alternative for the preceding
183 % non-terminal, on a new line. It takes two arguments: the definition of the
184 % alternative, and an explanation. For instance, the following grammar typesets
185 % as the grammar in Grammar~\ref{gr:simple_grammar}.
186 % \begin{verbatim}
187 % \begin{grammar}[A simple grammar][t][gr:simple_grammar]
188 % \firstcase{A}{()}{Parenthesis}
189 % \otherform{\{\}}{Curly brackets}
190 % \end{grammar}
191 % \end{verbatim}
192 % \begin{grammar}[A simple grammar][t][gr:simple_grammar]
193 % \firstcase{A}{()}{Parenthesis}
194 % \otherform{\{\}}{Curly brackets}
195 % \end{grammar}
196 %
197 % \paragraph{Referencing non-terminals.}
198 %
199 % \DescribeMacro{\nonterm}
200 % This allows you to typeset a symbol as a non-terminal. In the current version,
201 % the default typesetting is to wrap in a \verb+\mathcal+ command. This allow
202 % to reference those non-terminals, both in grammar rules and elsewhere in the
203 % document. Notice that, since the typesetting is just a wrapper over
204 % \verb+\mathcal+, it should be used in a math environment. For instance, the
205 % only non-terminal of Grammar~\ref{gr:simple_grammar} is \(\nonterm{A}\)
206 % (\verb+\(\nonterm{A}\)+).
207 %
208 %
209 % \subsection{Advanced capabilities}
210 % In this subsection, we will explain the more advanced capabilities of the
211 % package. These would allow to typeset more complex grammars such as the one
212 % displayed in Grammar~\ref{gr:advanced_grammar}.
213 %
214 % \begin{grammar}[A more advanced grammar][t][gr:advanced_grammar]
215 % \firstcase{B}{(\nonterm{B})\gralt \{\nonterm{B}\}}{Nested parenthesis or brackets}
216 % \firstcasesubtil{\(\nonterm{C}_1\)}{\nonterm{B}}{Example of subtil non-terminal}
217 % \highlight
218 % \firstcase{D}{\nonterm{B}}{An interesting line}
219 % \downplay
220 % \otherform{\nonterm{D}}{An uninteresting line}
221 % \otherform{\lochighlight{\nonterm{D} + \nonterm{D}}
222 % \gralt \nonterm{A}}{Important item}
223 % \end{grammar}
224 %
225 % \paragraph{Variants on the same line.}
226 % \DescribeMacro{\gralt}
227 % When variants are short and simple, it is possible to display multiple of them
228 % on the same line using |\gralt|. For instance, the first line of
229 % Grammar~\ref{gr:advanced_grammar} is typeset with the following command:
230 % \begin{verbatim}
231 % \firstcase{B}{(\nonterm{B})\gralt \{\nonterm{B}\}}{Nested parenthesis or brackets}
232 % \end{verbatim}
233 % \paragraph{Subtle typesetting of non-terminals.}
234 % Since nonterminals are, by default, typeset using \verb+\mathcal+, it can lead
235 % to the usual issues of \verb+\mathcal+ (typically, for lowercases). Therefore, we provide \emph{subtle}
236 % variants of |\firstcase| and |\nonterm|, in which the non-terminal symbol is
237 % not typeset (i.e. as the user, you have to typeset it manually).
238 %
239 % \DescribeMacro{\nontermsubtil}
240 % This is equivalent to |\nonterm|, but where typesetting is left to the user.
241 % In the current implementation does nothing. However users are encouraged to
242 % use it for future modifications of the package. For instance, it is possible
243 % to typeset a non-terminal with a number index as follow
244 % \(\nontermsubtil{\nonterm{C}_1}\) with the following command:
245 % \verb+\(\nontermsubtil{\nonterm{C}_1}\)+
246 %
247 % \DescribeMacro{\firstcasesubtil}
248 % The subtle variant of |\firstcase|. It works similarly, except that the
249 % non-terminal (i.e. the first argument) is not embedded in a \verb+\mathcal+
250 % macro. For instance, the \(\nontermsubtil{\nonterm{C}_1}\) in
251 % Grammar~\ref{gr:advanced_grammar} is typeset with the following command:
252 % \begin{verbatim}
253 % \firstcasesubtil{\(\nonterm{C}_1\)}{\nonterm{B}}{Example of subtil non-terminal}
254 % \end{verbatim}
255 %
256 % \paragraph{Highlighting and downplaying variants.}
257 % Three commands are provided to highlight or downplay some parts of a grammar.
258 % |\highlight| highlights a whole line, |\loghighlight| highlights a part of a
259 % line, while |\downplay| downplays a line.
260 %
261 % \DescribeMacro{\downplay}
262 % \DescribeMacro{\highlight}
263 % The two commands |\highlight| and |\downplay| work similarly: when used before
264 % a |\firstcase|, |\firstcasesubtil|, or |\otherform|, the next line is
265 % highlighted in blue, or printed in light grey. For instance, in
266 % Grammar~\ref{gr:advanced_grammar}, the rule for non-terminal \(\nonterm{D}\)
267 % is typeset with:
268 % \begin{verbatim}
269 % \highlight
270 % \firstcase{D}{\nonterm{B}}{An interesting line}
271 % \downplay
272 % \otherform{\nonterm{D}}{An uninteresting line}
273 % \end{verbatim}
274 %
275 % \DescribeMacro{\lochighlight}
276 % For more local highlighting, it is possible to use |\lochighlight|, which
277 % prints some part of a rule in red. The last line of
278 % Grammar~\ref{gr:advanced_grammar}, which contains such local highlight, is
279 % typeset with the following command:
280 % \begin{verbatim}
281 % \otherform{\lochighlight{\nonterm{D} + \nonterm{D}}
282 % \gralt \nonterm{A}}{Important item}
283 % \end{verbatim}
284 %
285 % \paragraph{Customizing the \(::=\) symbol.}
286 % At the end of the preamble (i.e. before the \verb+\begin{document}+), the
287 % package checks if a command \verb+\Coloneqq+ is defined. If that is the case,
288 % it is used instead of \(::=\). Typically, packages
289 % \href{https://www.ctan.org/pkg/mathtools}{mathtools},
290 % \href{https://www.ctan.org/pkg/txfonts}{txfonts} and
291 % \href{https://www.ctan.org/pkg/pxfonts}{pxfonts} define this command, but you
292 % can also define it manually if you use the symbol elsewhere in the document.
293 %
294 % \StopEventually{\PrintIndex}
295 %
296 % \section{Implementation}
297 % We declare an option \verb+center+ for aligning definition symbol (\(::=\))
298 % and separator symbol (\(\gralt\)) in center.
299 % This is done by create a new conditional, and assign corresponding values
300 % depending on the option.
301 % \begin{macrocode}
302 \newif\if@formalalignsymbol\@formalalignsymbolfalse
303 \DeclareOption{center}{
304 \@formalalignsymboltrue
305 }
306 % \end{macrocode}
307 %
308 % Now we process options.
309 % \begin{macrocode}
310 \ProcessOptions\relax
311 % \end{macrocode}
312 %
313 %
314 % \begin{environment}{floatgrammar}
315 % This is a new float that contains floating grammars. This is needed so that
316 % they are labeled with 'Grammar'.
317 % \begin{macrocode}
318 \DeclareFloatingEnvironment[
319 name=Grammar,
320 listname={List of Grammars},
321 placement=tbhp,
322 ]{floatgrammar}
323 % \end{macrocode}
324 % \end{environment}
325 %
326 %\iffalse
327 %% Taken from https://tex.stackexchange.com/a/26364/107341
328 %\fi
329 %
330 % \begin{macro}{\formal@rowstyle}
331 % The default \verb+rowstyle+ is empty.
332 % \begin{macrocode}
333 \newcommand*{\formal@rowstyle}{}
334 % \end{macrocode}
335 % \end{macro}
336 %
337
338 % \begin{macro}{\rowstyle}
339 % An command used to set the style of a row. In addition, we add column
340 % types to reset the style (\verb:=:) and to keep the style from one column to
341 % the other (\verb:+:).
342 % As of today, it is not advised for the user to use \verb+\rowstyle+ to define
343 % their own style (i.e.\ I have not tested it), although I hope it will someday
344 % be possible.
345 % \begin{macrocode}
346 \newcommand*{\rowstyle}[1]{% sets the style of the next row
347 \gdef\formal@rowstyle{#1}%
348 \formal@rowstyle\ignorespaces%
349 }
350 % \end{macrocode}
351 % \begin{macrocode}
352 \newcolumntype{\formal@reset}{% resets the row style
353 >{\gdef\formal@rowstyle{}}%
354 }
355
356 \newcolumntype{\formal@add}{% adds the current row style to the next column
357 >{\formal@rowstyle}%
358 }
359 % \end{macrocode}
360 % \end{macro}
361 %\iffalse
362 %% End of stackexchange
363 %\fi
364 %
365 % \begin{environment}{grammar}
366 % This is the implementation of the |grammar| environment. The main difficulty
367 % is to check whether optional arguments are provided. If the first is provided,
368 % we embed the grammar into a \verb+floatgrammar+; then if the second argument
369 % is provided, we use it as the position, (otherwise, we use \verb+p+). Finally,
370 % if the third argument is provided, we use it as a label.
371 % Notice that, if the grammar is not a float (is inline), we do \emph{not}
372 % break line before and after the grammar.
373 %
374 % Depending on whether the option \verb+center+ is set, we align the symbols
375 % accordingly. This is done via an auxiliary column type.
376 % \begin{macrocode}
377 \if@formalalignsymbol
378 \newcolumntype{\formal@symbol}{c}
379 \else
380 \newcolumntype{\formal@symbol}{r}
381 \fi
382 % \end{macrocode}
383 % \begin{macrocode}
384 \ExplSyntaxOn
385 %% 1st argument: caption (makes it float)
386 %% 2nd argument: positionning option (`p` by default)
387 %% 3rd argument: label
388 \NewDocumentEnvironment{grammar} {o O{p} o}
389 {
390 \IfNoValueF{#1}{
391 \begin{floatgrammar}[#2]
392 \centering
393 }
394
395 \begin{tabular}{\formal@reset l \formal@add \formal@symbol \formal@add l \formal@add l}
396 }{
397 \end{tabular}
398
399 \IfNoValueF{#1}{
400 \caption{#1}
401 \IfNoValueF{#3}{
402 \label{#3}
403 }
404 \end{floatgrammar}
405 }
406 }
407 \ExplSyntaxOff
408 % \end{macrocode}
409 % \end{environment}
410
411 % \begin{macro}{\firstcase}
412 % The |\firstcase| is typeset as a new line in the array, which first cell is
413 % the symbol of the non-terminal, the second cell is just \(::=\), the third
414 % cell is the rule (it is directly printed, without any modification), and the
415 % last cell is the description of the rule, in greyish color.
416 % \begin{macrocode}
417 \newcommand{\firstcase}[3]{\(\mathcal{#1}\) & \(\formal@Coloneqq\) & \(#2\) & {\itshape \color{gray!90!black} #3}\\}
418 % \end{macrocode}
419 % \end{macro}
420 %
421 % \begin{macro}{\firstcasesubtil}
422 % The |\firstcasesubtil| is implemented similarly to |\firstcase|, except that
423 % the first argument is not surrounded by \verb+\mathcal+.
424 % \begin{macrocode}
425 \newcommand{\firstcasesubtil}[3]{#1 & \(\formal@Coloneqq\) & \(#2\) & {\itshape \color{gray!90!black} #3}\\}
426 % \end{macrocode}
427 % \end{macro}
428
429 % \begin{macro}{\otherform}
430 % Adds a line with an empty first cell, and which second cell is just a pipe.
431 % The third and fourth cells are similar to |\firstcase|.
432 % \begin{macrocode}
433 \newcommand{\otherform}[2]{& \(|\) & \(#1\) & {\itshape \color{gray!90!black} #2}\\}
434 % \end{macrocode}
435 % \end{macro}
436
437 % \begin{macro}{\nonterm}
438 % Typesets in \verb+\mathcal+.
439 % \begin{macrocode}
440 \newcommand{\nonterm}[1]{\mathcal{#1}}
441 % \end{macrocode}
442 % \end{macro}
443
444 % \begin{macro}{\nontermsubtil}
445 % Does nothing right now.
446 % \begin{macrocode}
447 \newcommand{\nontermsubtil}[1]{#1}
448 % \end{macrocode}
449 % \end{macro}
450
451 % \begin{macro}{\gralt}
452 % |\gralt| is simply a pipe surrounded by large spaces.
453 % \begin{macrocode}
454 \newcommand{\gralt}[0]{\quad |\quad }
455 % \end{macrocode}
456 % \end{macro}
457
458
459 % \begin{macro}{\highlight}
460 % We simply set the row color to LightCyan.
461 % \begin{macrocode}
462 \newcommand{\highlight}[0]{\rowcolor{LightCyan}}
463 % \end{macrocode}
464 % \end{macro}
465
466 % \begin{macro}{\lochighlight}
467 % We simply surround the argument with red.
468 % \begin{macrocode}
469 \newcommand{\lochighlight}[1]{{\color{red} #1}}
470 % \end{macrocode}
471 % \end{macro}
472
473 % \begin{macro}{\downplay}
474 % We simply apply a style that write in light grey for the row.
475 % \begin{macrocode}
476 \newcommand{\downplay}[0]{\rowstyle{\color{white!80!black}}}
477 % \end{macrocode}
478 % \end{macro}
479 %
480 % Finally, we check, at the end of the preamble, if there already exist a
481 % \verb+::=+ symbol. We search for a command called \verb+Coloneqq+, e.g.
482 % defined in the \href{https://www.ctan.org/pkg/mathtools}{mathtools}.
483 % \begin{macrocode}
484 \AtBeginDocument{%
485 \ifdefined\Coloneqq
486 \let\formal@Coloneqq\Coloneqq
487 \else
488 \newcommand{\formal@Coloneqq}{::=}
489 \fi
490 }
491 % \end{macrocode}
492 %
493 % \Finale
494 \endinput