From a6cb485d98d5c0f84b3c42631ed7f69361110bd6 Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Wed, 9 Feb 2022 20:57:57 +0000 Subject: formal-grammar (9feb22) git-svn-id: svn://tug.org/texlive/trunk@61955 c570f23f-e606-0410-a88d-b1316a301751 --- .../source/latex/formal-grammar/formal-grammar.dtx | 99 ++++++++++++++++++++-- 1 file changed, 93 insertions(+), 6 deletions(-) (limited to 'Master/texmf-dist/source/latex/formal-grammar') 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 %\NeedsTeXFormat{LaTeX2e} -%\ProvidesPackage{formal-grammar}[2021/11/15 v1.1 A package to typeset formal grammars] +%\ProvidesPackage{formal-grammar}[2022/02/09 v1.2 A package to typeset formal grammars] %\RequirePackage{xparse} %\RequirePackage{newfloat} %\RequirePackage{xcolor} @@ -27,6 +27,7 @@ \documentclass{ltxdoc} \usepackage{formal-grammar} \usepackage[hidelinks]{hyperref} +\usepackage{amsfonts} \EnableCrossrefs \CodelineIndex \RecordChanges @@ -36,7 +37,7 @@ % % \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} -- cgit v1.2.3