diff options
| -rw-r--r-- | notes-inf105.tex | 99 |
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 |