summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/source/latex/formal-grammar
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2022-02-09 20:57:57 +0000
committerKarl Berry <karl@freefriends.org>2022-02-09 20:57:57 +0000
commita6cb485d98d5c0f84b3c42631ed7f69361110bd6 (patch)
treeba42b3c1efdcf7e7a4689f6814b69363c4c524b3 /Master/texmf-dist/source/latex/formal-grammar
parent9b2ee457b89b42f999b1d2ec36364b73e41e3450 (diff)
formal-grammar (9feb22)
git-svn-id: svn://tug.org/texlive/trunk@61955 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/source/latex/formal-grammar')
-rw-r--r--Master/texmf-dist/source/latex/formal-grammar/formal-grammar.dtx99
1 files changed, 93 insertions, 6 deletions
diff --git a/Master/texmf-dist/source/latex/formal-grammar/formal-grammar.dtx b/Master/texmf-dist/source/latex/formal-grammar/formal-grammar.dtx
index da5f2bdae1e..dd688533f29 100644
--- a/Master/texmf-dist/source/latex/formal-grammar/formal-grammar.dtx
+++ b/Master/texmf-dist/source/latex/formal-grammar/formal-grammar.dtx
@@ -16,7 +16,7 @@
% \iffalse
%<package>\NeedsTeXFormat{LaTeX2e}
-%<package>\ProvidesPackage{formal-grammar}[2021/11/15 v1.1 A package to typeset formal grammars]
+%<package>\ProvidesPackage{formal-grammar}[2022/02/09 v1.2 A package to typeset formal grammars]
%<package>\RequirePackage{xparse}
%<package>\RequirePackage{newfloat}
%<package>\RequirePackage{xcolor}
@@ -27,6 +27,7 @@
\documentclass{ltxdoc}
\usepackage{formal-grammar}
\usepackage[hidelinks]{hyperref}
+\usepackage{amsfonts}
\EnableCrossrefs
\CodelineIndex
\RecordChanges
@@ -36,7 +37,7 @@
%</driver>
% \fi
%
-% \CheckSum{97}
+% \CheckSum{112}
%
% \CharacterTable
% {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
@@ -55,6 +56,7 @@
% Right brace \} Tilde \~}
%
%
+% \changes{v1.2}{2022/02/09}{Add the `center` option}
% \changes{v1.1}{2021/11/15}{Use Coloneqq if defined, internal changes, typos}
% \changes{v1.0}{2021/11/10}{Initial version for publication}
%
@@ -76,11 +78,63 @@
%
% \section{Introduction}
%
+% The notion of formal language is one of the most important in theoretical
+% computer science. Intuitively, it is defined as follow: we are given a set
+% \(\Sigma\) of \emph{letters} or \emph{symbols} (the \emph{alphabet}). For instance, we can consider
+% \(\Sigma = \{a, b, \dots, z\}\): our symbols is the set of lowercase
+% characters. A \emph{word} is a tuple of letters. For instance, \(\langle a, b,
+% c\rangle\) is a word of three letters over \(\Sigma\). Therefore, \(\Sigma^k\)
+% is the set of words of \(k\) letters over \(\Sigma\). Notice in particular
+% that \(\Sigma^0\) is the set \(\{\langle\rangle\}\). \(\langle\rangle\) is
+% the unique word that contains \(0\) letters. It is often noted
+% \(\varepsilon\).
+%
+% The set of all words over \(\Sigma\) (independently of their length) is
+% defined as \(\Sigma^\star = \bigcup_{i\in\mathbb{N}} \Sigma^i\).
+%
+% An important operation is the \emph{concatenation}, noted \(\cdot\), which
+% consists in sticking two words together. For instance \(\langle a,
+% b\rangle\cdot\langle c\rangle = \langle a, b, c\rangle\). For the sake of this
+% quick introduction, we do not specify further this operation.
+%
+% A (formal) language over \(\Sigma\) is a subset of \(\Sigma^\star\):
+% \(\mathbb{L}\subseteq\Sigma^\star\). That is, it consists in picking some of
+% the words of \(\Sigma^\star\). For instance we can define the language
+% \(\mathbb{L}_{a}\) which contains all words that begin with an \(a\):
+% \(\mathbb{L}_a = \{\langle a \rangle \cdot w, w\in \Sigma^\star\}\).
+%
+% We can see that describing languages by the mean of equations is quite
+% tedious. Therefore, we most often use \emph{grammars}, which are a set of
+% rules that characterise a language. In particular, one of the standard way to
+% define a grammar is what we call the \textsc{bnf}, for \emph{Backus-Naur form}
+% (or \emph{Backus normal form}). Such grammars are defined from two sets of
+% elements: \emph{terminal} and \emph{non-terminal} (by convention, in this
+% document, non-terminal are in calligraphic font, except when explicitely
+% stated otherwise). Basically, \emph{terminal}
+% correspond to the alphabet, and \emph{non-terminal} are names of rules.
+%
+%A rule
+% has the form \begin{grammar}\firstcase{R}{a}{}\end{grammar}, where
+% \(\nonterm{R}\) is the name of the rule, and \(a\) is the production. The name
+% of the rule is a non-terminal, and the production is a sequence of terminals
+% and non-terminal. If a rule has multiple possible productions, we separate
+% them as follow: \begin{grammar}\firstcase{S}{a\gralt
+% a\nonterm{S}}{}\end{grammar}.
+%
+% Finally, a grammar is a set of rules.
+%
+% A production defines a set of words. Without
+% going into formalities, a production produces
+% the words described by the terminal, and where non-terminal are replaced by
+% productions of the corresponding rule. For instance, the rule \(\nonterm{S}\)
+% above produces \(\{a, aa, aaa, \dots\}\). Notice that rules can be mutually
+% recursive.
+%
% This package provides a new environment (|grammar|) and associated commands to
-% typeset BNF grammars. It allows to easily write formal grammars. For instance,
-% the syntax of the \(\lambda\) calculus is given in Grammar~\ref{gr:lambda}.
+% typeset \textsc{bnf} grammars. It allows to easily write formal grammars. For instance,
+% the syntax of the \(\lambda\)-calculus is given in Grammar~\ref{gr:lambda}.
%
-%\begin{grammar}[\(\lambda\) calculus syntax][][gr:lambda]
+%\begin{grammar}[\(\lambda\)-calculus syntax][][gr:lambda]
% \firstcase{T}{\nonterm{V}}{Variable}
% \highlight
% \otherform{(\nonterm{T}\ \nonterm{T})}{Application}
@@ -91,6 +145,13 @@
%\end{grammar}
%
% \section{Usage}
+% \subsection{Loading the package (and loading options)}
+%
+% This package accepts a single option when loading: \verb+center+. If the
+% option is set, the initial \(\gralt\) of non-initial lines of multi-line rules is
+% centered with respect to the \(::=\) of the initial line. If
+% unset, the \(\gralt\) is aligned to the right.
+%
% \subsection{Basic usage}
%
% \paragraph{Creating a grammar.}
@@ -233,6 +294,22 @@
% \StopEventually{\PrintIndex}
%
% \section{Implementation}
+% We declare an option \verb+center+ for aligning definition symbol (\(::=\))
+% and separator symbol (\(\gralt\)) in center.
+% This is done by create a new conditional, and assign corresponding values
+% depending on the option.
+% \begin{macrocode}
+ \newif\if@formalalignsymbol\@formalalignsymbolfalse
+ \DeclareOption{center}{
+ \@formalalignsymboltrue
+ }
+% \end{macrocode}
+%
+% Now we process options.
+% \begin{macrocode}
+ \ProcessOptions\relax
+% \end{macrocode}
+%
%
% \begin{environment}{floatgrammar}
% This is a new float that contains floating grammars. This is needed so that
@@ -293,6 +370,16 @@
% if the third argument is provided, we use it as a label.
% Notice that, if the grammar is not a float (is inline), we do \emph{not}
% break line before and after the grammar.
+%
+% Depending on whether the option \verb+center+ is set, we align the symbols
+% accordingly. This is done via an auxiliary column type.
+% \begin{macrocode}
+ \if@formalalignsymbol
+ \newcolumntype{\formal@symbol}{c}
+ \else
+ \newcolumntype{\formal@symbol}{r}
+ \fi
+% \end{macrocode}
% \begin{macrocode}
\ExplSyntaxOn
%% 1st argument: caption (makes it float)
@@ -305,7 +392,7 @@
\centering
}
- \begin{tabular}{\formal@reset l \formal@add r \formal@add l \formal@add l}
+ \begin{tabular}{\formal@reset l \formal@add \formal@symbol \formal@add l \formal@add l}
}{
\end{tabular}