Introduction and clarifications on context-free grammars.

1 files changed, 82 insertions, 17 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 9a4c5b1..88a2366 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -44,6 +44,7 @@
 %
 \DeclareUnicodeCharacter{00A0}{~}
 \DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+\DeclareUnicodeCharacter{1E47}{\d{n}}
 %
 \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
 \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
@@ -4037,25 +4038,81 @@ et les langages reconnus sont les mêmes.
 dans le monde informatique, principalement à définir des outils de
 recherche de « motifs » (pour la recherche et le remplacement dans un
 texte, la validation d'entrées, la syntaxe de bas niveau, etc.), les
-grammaires, dont les plus importantes sont les grammaires \emph{hors
-  contexte} que nous allons maintenant considérer, ont pour principal
-intérêt de définir des \emph{syntaxes structurées}, par exemple la
-syntaxe d'un langage informatique (typiquement un langage de
-programmation).  Cette fois-ci, on ne s'intéressera pas simplement au
-langage défini (par la grammaire hors contexte, dit langage
-« algébrique »), mais aussi à la manière dont ces mots s'obtiennent
-par la grammaire, et donc, à la manière d'\emph{analyser} (en anglais,
-\emph{to parse}) un mot / programme en une structure de données qui le
-représente : pour cela, on va définir la notion d'\emph{arbre
-  d'analyse}.
+grammaires formelles, dont les plus importantes sont les grammaires
+\emph{hors contexte} que nous allons maintenant considérer, ont pour
+principal intérêt de définir des \emph{syntaxes structurées}, par
+exemple la syntaxe d'un langage informatique (typiquement un langage
+de programmation).  En fait, l'étude des grammaires formelles en
+général, et des grammaires hors contexte en particulier, a été
+démarré\footnote{Certains font remonter leur origine bien plus loin :
+  on peut trouver une forme de grammaire hors contexte dans la manière
+  dont l'Indien Pāṇini (probablement au IV\textsuperscript{e} siècle
+  av. notre ère) décrit la grammaire du sanskrit.} en 1956 par le
+linguiste (et activiste politique) Noam Chomsky pour servir dans
+l'analyse des langues naturelles ; mais c'est plus en informatique
+qu'en linguistique qu'elles ont trouvé leur utilité.
+
+Cette fois-ci, on ne s'intéressera pas simplement au langage défini
+(par la grammaire hors contexte, dit langage « algébrique »), mais
+aussi à la manière dont ces mots s'obtiennent par la grammaire, et
+donc, à la manière d'\emph{analyser} (en anglais, \emph{to parse}) un
+mot / programme en une structure de données qui le représente : pour
+cela, on va définir la notion d'\emph{arbre d'analyse}.
+
+\thingy Un exemple typique d'usage de grammaire hors contexte pour
+définir la syntaxe d'un langage de programmation hypothétique pourrait
+ressembler à ceci :
+\[
+\begin{aligned}
+\mathit{Statement} &\rightarrow \mathtt{begin}\ \mathit{Block}\ \mathtt{end}\\
+\mathit{Statement} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Block}\ \mathtt{fi}\\
+\mathit{Statement} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Block}\ \mathtt{else}\ \mathit{Block}\ \mathtt{fi}\\
+\mathit{Block} &\rightarrow \varepsilon\\
+\mathit{Block} &\rightarrow \mathit{Statement}\ \mathit{Block}\\
+\end{aligned}
+\]
+Il faut comprendre ces règles de la manière suivante : « pour définir
+une instruction ($\mathit{Statement}$), on peut mettre un
+$\mathtt{begin}$ suivi d'un bloc ($\mathit{Block}$) suivi d'un
+$\mathtt{end}$, ou bien un $\mathtt{if}$ suivi d'une expression
+($\mathit{Expression}$) suivi d'un $\mathtt{then}$ suivi d'une
+instruction, éventuellement suivie encore d'un $\mathtt{else}$ et
+d'une nouvelle instruction, et enfin un $\mathtt{fi}$ ; pour définir
+un bloc ($\mathit{Block}$), on peut soit ne rien mettre du tout, soit
+mettre une instruction suivi d'un nouveau bloc ».
+
+Notre but va être d'expliquer quel genre de règles de ce genre on peut
+autoriser, comment elles se comportent, quels types de langages elles
+définissent, et comment on peut analyser (essentiellement, retrouver
+la manière dont on a construit) un texte produit par une application
+de telles règles.
+
+\thingy Dans un contexte informatique, l'usage des grammaires
+formelles se fait à un niveau différent de celui des chaînes de
+caractères où nous nous sommes placés dans les sections précédentes :
+cette fois, les lettres de notre alphabet ne seront généralement pas
+des caractères mais des \defin[token]{tokens} du langage dont on
+définit la grammaire, un « token » pouvant être une unité variable
+selon le langage, mais généralement soit un caractère spécial, soit un
+mot-clé du langage (\texttt{begin}, \texttt{end}, \texttt{for}, etc.,
+constituent donc généralement un unique token dans l'analyse, et ne
+sont pas divisés en leurs lettres individuelles), soit encore une
+unité (« nombre », « identificateur », éventuellement « commentaire »)
+qui aura été découpée dans une première phase d'analyse, appelée
+« analyse lexicale ».
+
+Nous ne rentrerons pas ici dans ces considérations, et nous nous en
+tiendrons à l'approche mathématique où on continue à avoir affaire à
+des lettres d'un alphabet $\Sigma$ abstrait.
 
 
 \subsection{Définition, notations et premier exemple}
 
 \thingy\label{definition-context-free-grammar} Une \defin{grammaire
   hors contexte} (on dit parfois aussi « sans contexte » ; en anglais,
-« context-free grammar » ou « CFG » ; ou encore grammaire de
-\textbf{type 2}) sur un alphabet $\Sigma$ est la donnée
+« context-free grammar » ou \index{CFG|see{grammaire hors
+    contexte}}« CFG » ; ou encore grammaire de \textbf{type 2}) sur un
+alphabet $\Sigma$ est la donnée
 \begin{itemize}
 \item d'un second alphabet $N$, disjoint de $\Sigma$, appelé ensemble
   des \defin[nonterminal]{nonterminaux},
@@ -4079,10 +4136,18 @@ appellera \defin{symbole} un élément de $\Sigma \cup N$, ces symboles
 à $\Sigma$ (ou simplement « lettres »), et \textbf{nonterminaux}
 lorsqu'ils appartiennent à $N$.  Un mot sur $\Sigma\cup N$
 (c'est-à-dire, une suite finie de symboles) sera appelé
-\defin{pseudo-mot}, tandis que le terme « \index{mot}mot » sans
-précision supplémentaire sera utilisé pour désigner un mot
-sur $\Sigma$ (autrement dit, un mot est un pseudo-mot ne comportant
-que des symboles terminaux).
+\defin{pseudo-mot} (ou parfois une « forme »), tandis que le terme
+« \index{mot}mot » sans précision supplémentaire sera utilisé pour
+désigner un mot sur $\Sigma$ (autrement dit, un mot est un pseudo-mot
+ne comportant que des symboles terminaux).
+
+Pour redire les choses autrement, les symboles terminaux sont les
+lettres des mots du langage qu'on cherche à définir ; les symboles
+nonterminaux sont des symboles qui servent uniquement à titre
+transitoire dans l'utilisation de la grammaire, et qui sont destinés à
+disparaître finalement.  Un « pseudo-mot » est un mot pouvant contenir
+des nonterminaux, tandis qu'un « mot » sans précision du contraire ne
+contient que des terminaux.
 
 {\footnotesize Typographiquement, on aura tendance à utiliser des
   lettres minuscules pour désigner les symboles terminaux, et