diff options
| -rw-r--r-- | notes-inf105.tex | 243 |
1 files changed, 146 insertions, 97 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 054637f..3cd099e 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -4315,7 +4315,8 @@ démarré\footnote{Certains font remonter leur origine bien plus loin : 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é. +qu'en linguistique qu'elles ont trouvé leur utilité, à commencer +surtout par la définition de la syntaxe du langage ALGOL 60. Cette fois-ci, on ne s'intéressera pas simplement au langage défini (par la grammaire hors contexte, dit langage « algébrique »), mais @@ -4434,11 +4435,11 @@ nonterminal) qu'on peut obtenir de la sorte. Rendons maintenant cette définition précise : -\thingy Lorsque $G$ est une grammaire hors contexte comme -en \ref{definition-context-free-grammar}, on note $T -\mathrel{\rightarrow_G} \alpha$, ou simplement $T \rightarrow \alpha$ -(lorsque $G$ est clair) pour signifier que $(T,\alpha)$ est une règle -de $G$. +\thingy\label{derivations-and-contexts} Lorsque $G$ est une grammaire +hors contexte comme en \ref{definition-context-free-grammar}, on note +$T \mathrel{\rightarrow_G} \alpha$, ou simplement $T \rightarrow +\alpha$ (lorsque $G$ est clair) pour signifier que $(T,\alpha)$ est +une règle de $G$. On définit une relation $\Rightarrow$ en posant $\gamma T \gamma' \Rightarrow \gamma\alpha\gamma'$ pour toute règle $(T,\alpha)$ et tous @@ -4557,7 +4558,8 @@ rationnel : il existe donc des langages algébriques qui ne sont pas rationnels. En revanche, pour ce qui est de la réciproque, on verra dans la section suivante que tout langage rationnel est algébrique. -\thingy Mentionnons brièvement qu'il existe des types de grammaires +\thingy\label{more-general-formal-grammars} +Mentionnons brièvement qu'il existe des types de grammaires plus généraux que les grammaires hors contexte. Les \defin[grammaire contextuelle]{grammaires contextuelles} (ou grammaires de \textbf{type 1}) sont définies par des règles du type $\gamma T @@ -4575,6 +4577,13 @@ langage défini par la grammaire est l'ensemble de tous les mots (sans nonterminaux) qui peuvent s'obtenir par application des règles de remplacement à partir de l'axiome. +Les grammaires de types 0 et 1, avec celles de type 2 c'est-à-dire +hors contexte, et celles de type 3 (= régulières) qui seront définies +en \ref{regular-grammar} ci-dessous, forment une hiérarchie (plus le +numéro du type est élevé plus la grammaire est contrainte et plus la +classe de langages définie est petite) appelée \defin[Chomsky + (hiérarchie de)]{hiérarchie de Chomsky}. + \subsection{Langages rationnels et algébriques, stabilité} @@ -4590,10 +4599,11 @@ et à remplacer tout état $q$ anciennement initial par une ε-transition $q_0 \to q$). Soit $Q$ son ensemble des états et $\delta \subseteq Q \times (\Sigma\cup\{\varepsilon\}) \times Q$ sa fonction de transition. On construit une grammaire hors contexte $G$ dont -l'ensemble des nonterminaux est $Q$, l'axiome est $S := q_0$, (A) pour -chaque transition $(q,t,q') \in \delta$ une règle $q \to tq'$ (on -rappelle que $t \in \Sigma\cup\{\varepsilon\}$), et (B) pour chaque -état final $q\in F$ une règle $q\to\varepsilon$. +l'ensemble des nonterminaux est $Q$, dont l'axiome est $S := q_0$, et +dont les règles sont les suivantes : (A) pour chaque transition +$(q,t,q') \in \delta$ une règle $q \to tq'$ (on rappelle que $t \in +\Sigma\cup\{\varepsilon\}$), et (B) pour chaque état final $q\in F$ +une règle $q\to\varepsilon$. De même que dans l'exemple \ref{basic-example-context-free-grammar}, une dérivation partant de l'axiome va comporter un certain nombre @@ -4611,18 +4621,28 @@ t_n$ dérivé est précisément le mot formé en concacténant les étiquettes du chemin. On a donc bien $L(G) = L(A)$. \end{proof} -\thingy Une grammaire hors contexte telle que construite dans la -preuve de \ref{rational-languages-are-algebraic} est dite -\index{régulière (grammaire)|see{grammaire régulière}}\defin[grammaire - régulière]{régulière} : autrement dit, il s'agit d'une grammaire -ayant uniquement des règles de la forme (A) $Q \rightarrow tQ'$ où $t -\in \Sigma\cup\{\varepsilon\}$ (certains auteurs imposent $t \in -\Sigma$, ce qui revient à imposer qu'on part d'un NFA sans -ε-transition dans la construction) et (B) $Q \rightarrow \varepsilon$ -(certains auteurs préfèrent $Q \rightarrow x$ avec $x\in\Sigma$, ce -qui impose des petits changements dans la construction ci-dessus). -Les langages définis par des grammaires régulières sont donc -exactement les langages rationnels. +\thingy\label{regular-grammar} Une grammaire hors contexte telle que +construite dans la preuve de \ref{rational-languages-are-algebraic} +est dite \index{régulière (grammaire)|see{grammaire + régulière}}\defin[grammaire régulière]{régulière} : autrement dit, +il s'agit d'une grammaire ayant uniquement des règles de deux formes : +(A) $Q \rightarrow tQ'$ où $t \in \Sigma\cup\{\varepsilon\}$, et +(B) $Q \rightarrow \varepsilon$. Les langages définis par des +grammaires régulières sont donc exactement les langages rationnels. + +{\footnotesize La définition des grammaires régulières varie un peu + d'auteur en auteur, ces différences n'étant pas très importantes. + Certains auteurs imposent $t \in \Sigma$ dans les règles de + type (A), ce qui revient à imposer qu'on part d'un NFA sans + ε-transition dans la construction ; et certains autorisent (ou + autorisent uniquement) dans le type (B) les règles de la forme $Q + \rightarrow x$ avec $x\in\Sigma$, ce qui impose des petits + changements dans la construction ci-dessus. Dans tous les cas, il + reste vrai que les langages définis par des grammaires régulières + sont exactement les langages rationnels.\par} + +Les grammaires régulière sont également appelées grammaires de +\textbf{type 3}. \begin{prop}\label{cfg-union-concatenation-and-star} Si $L_1,L_2$ sont des langages algébriques (sur un même @@ -4775,9 +4795,12 @@ T &\rightarrow aTb \;|\; \varepsilon\\ \] Il n'est pas difficile de se convaincre qu'elle engendre le même langage $L(G)$ que la précédente (elle est donc faiblement équivalente -à $G$). (Ce langage est intéressant sur le plan théorique, car bien -qu'il soit algébrique et ici défini par une grammaire inambiguë, il ne -peut pas être analysé par un analyseur LL.) +à $G$). + +{\footnotesize (Ce langage est intéressant sur le plan théorique, car + bien qu'il soit algébrique, et ici défini par une grammaire $G'$ + inambiguë (cf. \ref{ambiguous-grammar}), il ne peut pas être analysé + par un analyseur LL (cf. \ref{handwaving-on-ll-and-lr}).)\par} \thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$) @@ -4793,9 +4816,13 @@ $\{a^i b^i : i>0\}$ comme en \ref{basic-example-context-free-grammar}, et de façon analogue, le langage $L(G,V)$ des mots qui dérivent de $V$ est $\{a^i b^{2i} : i>0\}$. Le langage $L(G) = L(G,U) \cup L(G,V)$ est donc l'ensemble des mots de la forme $a^i b^j$ où $j=i$ \emph{ou - bien} $j=2i$. (Ce langage est intéressant sur le plan théorique, -car bien qu'il soit algébrique et défini par une grammaire inambiguë, -il n'est pas analysable par un automate à pile déterministe.) + bien} $j=2i$. + +{\footnotesize (Ce langage est intéressant sur le plan théorique, car + bien qu'il soit algébrique et défini par une grammaire inambiguë + (cf. \ref{ambiguous-grammar}), il n'est pas analysable par un + automate à pile déterministe + (cf. \ref{handwaving-on-stack-automata}).)\par} \thingy\label{example-for-intrinsic-ambiguity} Sur l'alphabet $\Sigma = \{a,b,c\}$, considérons la grammaire (d'axiome $S$) @@ -4817,8 +4844,11 @@ et de même $L(G,V) = \{b^j c^j : j\in\mathbb{N}\}$. Finalement, $L(G) = L(G,U)\,L(G,C) \;\cup\; L(G,A)\,L(G,V)$ montre que $L(G) = \{a^i b^i c^j : i,j\in\mathbb{N}\} \cup \{a^i b^j c^j : i,j\in\mathbb{N}\}$ est le langage des mots de la forme $a^i b^r c^j$ où $r=i$ \emph{ou} -$r=j$. (Ce langage est intéressant sur le plan théorique, car il est -algébrique mais « intrinsèquement ambigu ».) +$r=j$. + +{\footnotesize (Ce langage est intéressant sur le plan théorique, car + il est algébrique mais « intrinsèquement ambigu » + (cf. \ref{intrinsic-ambiguity}).)\par} \thingy\label{example-well-parenthesized-expressions} Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$) @@ -4862,14 +4892,15 @@ S\; \rightarrow\; aSbS \;|\; bSaS \;|\; \varepsilon (c'est-à-dire $N = \{S\}$ où $S$ est l'axiome, et pour règles $S \rightarrow aSbS$ et $S \rightarrow bSaS$ et $S \rightarrow \varepsilon$) engendre le langage $L$ formé des mots ayant un nombre -total de $a$ égal au nombre total de $b$, i.e., $L = \{w \in\Sigma^* : +total de $a$ égal au nombre total de $b$, i.e., $L := \{w \in\Sigma^* : |w|_a = |w|_b\}$ où $|w|_x$ désigne le nombre total d'occurrences de la lettre $x$ dans le mot $w$ (cf. \ref{number-of-occurrences-of-letter}). -Dans un sens il est évident que tout pseudo-mot obtenu en dérivant $S$ -a un nombre de $a$ égal au nombre de $b$, puisque cette propriété est -conservée par toute dérivation immédiate. Autrement dit, $L(G) -\subseteq L$. +\begin{proof} +Dans un sens il est évident que tout pseudo-mot (et en particulier, +tout mot sur $\Sigma$) obtenu en dérivant $S$ a un nombre de $a$ égal +au nombre de $b$, puisque cette propriété est conservée par toute +dérivation immédiate. Autrement dit, $L(G) \subseteq L$. Pour ce qui est de la réciproque, on va montrer par récurrence sur $|w|$ que tout mot $w \in \Sigma^*$ ayant autant de $a$ que de $b$ est @@ -4894,6 +4925,7 @@ récurrence (ils sont de longueur strictement plus courte que $w$) appartiennent à $L(G)$. On peut donc dériver $u$ et $v$ de $S$, donc $w$ de $aSbS$, et comme $aSbS$ se dérive immédiatement de $S$, on a bien $w \in L(G)$, ce qui conclut la récurrence. +\end{proof} Un raisonnement analogue montre que la grammaire $G'$ donnée par \[ @@ -4907,15 +4939,15 @@ engendre le même langage $L = \{w \in\Sigma^* : |w|_a = |w|_b\}$ que ci-dessus (elle est donc faiblement équivalente à $G$) : l'idée est que le langage $L(G,U)$ des mots qui dérivent de $U$ est l'ensemble des expressions bien-parenthésées où $a$ est la parenthèse ouvrante et -$b$ la fermante (dans le raisonnement ci-dessus, ce sont les mots pour -lesquels la fonction $h$, partant de $0$, revient à $0$, et reste -toujours positive ou nulle), tandis que $L(G,V)$ est l'ensemble des -expressions bien-parenthésées où $b$ est la parenthèse ouvrante et $a$ -la fermante (la fonction $h$ reste toujours négative ou nulle), et -tout mot de $L$ peut s'écrire comme concaténation de tels mots (en -divisant selon le signe de $h$). Une différence entre $G$ et $G'$ est -que la grammaire $G$ est ambiguë (un terme qui sera défini plus bas) -tandis que $G'$ ne l'est pas. +$b$ la fermante (avec les notations de la démonstration ci-dessus, ce +sont les mots pour lesquels la fonction $h$, partant de $0$, revient à +$0$, et reste toujours positive ou nulle), tandis que $L(G,V)$ est +l'ensemble des expressions bien-parenthésées où $b$ est la parenthèse +ouvrante et $a$ la fermante (la fonction $h$ reste toujours négative +ou nulle), et tout mot de $L$ peut s'écrire comme concaténation de +tels mots (en divisant selon le signe de $h$). Une différence entre +$G$ et $G'$ est que la grammaire $G$ est ambiguë (terme qui sera +défini en \ref{ambiguous-grammar}) tandis que $G'$ ne l'est pas. \subsection{Arbres d'analyse, dérivations gauche et droite} @@ -4934,11 +4966,14 @@ suivantes : \begin{itemize} \item la racine de l'arbre est étiquetée par l'axiome $S$ de $G$ ; \item si un nœud de l'arbre est étiqueté par $T$ et n'est pas une - feuille (i.e., s'il a des fils), alors soit il a un unique fils - étiqueté $\varepsilon$ et il existe une règle $T \rightarrow - \varepsilon$ dans $G$, soit il a des fils étiquetés par des éléments - $x_1\cdots x_n$ (où $n\geq 1$) de $\Sigma \cup N$ et il existe une - règle $T \rightarrow x_1\cdots x_n$ dans $G$. + feuille (i.e., s'il a des fils), alors +\begin{itemize} +\item soit ce nœud a un unique fils étiqueté $\varepsilon$ et il + existe une règle $T \rightarrow \varepsilon$ dans $G$, +\item soit ce nœud a des fils étiquetés par des éléments $x_1\cdots + x_n$ (où $n\geq 1$) de $\Sigma \cup N$ et il existe une règle $T + \rightarrow x_1\cdots x_n$ dans $G$. +\end{itemize} \end{itemize} On dit de plus que l'arbre est \textbf{complet}, ou simplement qu'il @@ -4946,11 +4981,12 @@ s'agit d'un arbre d'analyse, lorsqu'il vérifie la propriété supplémentaire suivante : \begin{itemize} \item foute feuille de l'arbre est étiquetée soit par un terminal - (élément de $\Sigma$) soit par $\varepsilon$. + (= élément de $\Sigma$) soit par $\varepsilon$. \end{itemize} (Les feuilles étiquetées $\varepsilon$ servent uniquement à marquer la -complétude de l'arbre : certains auteurs procèdent différemment.) +complétude de l'arbre : certains auteurs procèdent différemment ou les +omettent.) \thingy Si $T$ est un arbre d'analyse incomplet, et $\alpha$ le pseudo-mot obtenu en lisant les étiquettes des \emph{feuilles} de $T$ @@ -4972,7 +5008,8 @@ T &\rightarrow aSb\\ \end{aligned} \] -L'arbre d'analyse suivant est un arbre d'analyse du mot $aabbab$ : +L'arbre d'analyse suivant est un arbre d'analyse du mot $aabbab$ +(c'est même le seul possible) : \begin{center} \tikzstyle{automaton}=[scale=0.5] %%% begin parsetree1 %%% @@ -5025,29 +5062,39 @@ L'arbre d'analyse suivant est un arbre d'analyse du mot $aabbab$ : %%% end parsetree1 %%% \end{center} -\thingy Si $S = \lambda_0 \Rightarrow \lambda_1 \Rightarrow \cdots -\Rightarrow \lambda_n$ est une dérivation à partir de l'axiome $S$ -dans une grammaire hors contexte $G$, on lui associe, par récurrence -sur $n$, un arbre d'analyse incomplet du pseudo-mot $\lambda_n$, de la -manière suivante : si $n=0$, il s'agit de l'arbre trivial (ayant pour -seul nœud la racine $S$) ; sinon, on part de l'arbre pour la -dérivation $\lambda_0 \Rightarrow \cdots \Rightarrow \lambda_{n-1}$, -on considère le symbole $T$ réécrit dans la dernière dérivation -immédiate $\lambda_{n-1} \Rightarrow \lambda_n$, il correspond à une -certaine feuille de l'arbre pour $n-1$ (à savoir la feuille, étiquetée -$T$, qui a autant de feuilles à gauche et à droite dans l'ordre de -profondeur que la longueur des contextes gauche et droit de la -dérivation immédiate $\lambda_{n-1} \Rightarrow \lambda_n$), et on -ajoute à ce nœud des fils correspondant à la règle $T \to \alpha$ -appliquée dans la dernière dérivation immédiate $\lambda_{n-1} -\Rightarrow \lambda_n$ (c'est-à-dire soit un unique fils étiqueté -$\varepsilon$ si $\alpha = \varepsilon$, soit $k$ fils étiquetés -$x_1,\ldots,x_k$ si $\alpha = x_1\cdots x_k$ avec $k\geq 1$). - -Concrètement, donc, on construit l'arbre d'analyse d'une dérivation en -partant de la racine et, à chaque fois qu'un symbole est réécrit, en -faisant pousser des fils à la feuille correspondante de l'arbre (qui -cesse donc d'être une feuille) pour indiquer la règle appliquée. +On obtient des exemples d'arbres d'analyse incomplet en effaçant +arbitrairement tous les descendants d'un ou plusieurs nœuds de cet +arbre. + +\thingy À toute dérivation à partir de l'axiome $S$ dans une grammaire +hors contexte $G$ on peut associer un arbre d'analyse incomplet : ce +dernier est construit en partant de la racine et, à chaque fois qu'un +symbole est réécrit (dans la dérivation), en faisant pousser des fils +à la feuille correspondante de l'arbre (qui cesse donc d'être une +feuille) pour indiquer la règle appliquée. + +De façon plus formelle : si $S =: \lambda_0 \Rightarrow \lambda_1 +\Rightarrow \cdots \Rightarrow \lambda_n$ est une dérivation à partir +de l'axiome $S$ dans une grammaire hors contexte $G$, on va lui +associer, par récurrence sur le nombre d'étapes $n$ de la dérivation, +un arbre d'analyse incomplet du pseudo-mot $\lambda_n$. Si $n=0$, +l'arbre $\mathscr{T}_0$ en question est simplement l'arbre trivial +(ayant pour seul nœud la racine $S$). Sinon, on part de l'arbre +$\mathscr{T}_{n-1}$ (qu'on a défini par récurrence) pour la dérivation +$\lambda_0 \Rightarrow \cdots \Rightarrow \lambda_{n-1}$ : supposons +que la dernière dérivation immédiate $\lambda_{n-1} \Rightarrow +\lambda_n$ réécrive le symbole nonterminal $T$ par application de la +règle $T \rightarrow \alpha$ avec pour contextes gauche et droit +$\gamma,\gamma'$ (cf. \ref{derivations-and-contexts}), si bien que +$\lambda_{n-1} = \gamma T \gamma'$ et $\lambda_n = \gamma \alpha +\gamma'$ ; le symbole $T$ réécrit correspond à un certain nœud de +l'arbre $\mathscr{T}_{n-1}$, à savoir la feuille, étiquetée $T$, telle +qu'on lise $\gamma$ à sa gauche et $\gamma'$ à sa droite en suivant +les feuilles dans l'ordre de profondeur ; on ajoute alors au nœud en +question des fils correspondant à la règle $T \to \alpha$, +c'est-à-dire soit un unique fils étiqueté $\varepsilon$ si $\alpha = +\varepsilon$, soit $k$ fils étiquetés $x_1,\ldots,x_k$ si $\alpha = +x_1\cdots x_k$ avec $k\geq 1$. Notons que l'arbre obtenu est complet exactement lorsque la dérivation aboutit à un mot (sur $\Sigma$). Notons aussi que le nombre $n$ @@ -5107,11 +5154,11 @@ une et une seule dérivation droite. \subsection{Ambiguïté} -\thingy On dit qu'une grammaire hors contexte est \defin[ambiguë - (grammaire)]{ambiguë} lorsqu'il existe un mot (i.e., un mot sur -l'alphabet $\Sigma$ des terminaux) qui admet deux arbres d'analyse -\emph{différents}. Dans le cas contraire, elle est dite -\defin[inambiguë (grammaire)]{inambiguë} : autrement dit, une +\thingy\label{ambiguous-grammar} On dit qu'une grammaire hors contexte +est \defin[ambiguë (grammaire)]{ambiguë} lorsqu'il existe un mot +(i.e., un mot sur l'alphabet $\Sigma$ des terminaux) qui admet deux +arbres d'analyse \emph{différents}. Dans le cas contraire, elle est +dite \defin[inambiguë (grammaire)]{inambiguë} : autrement dit, une grammaire inambiguë est une grammaire $G$ pour laquelle tout $w \in L(G)$ a un unique arbre d'analyse ; il revient au même de dire que tout mot de $L(G)$ a une unique dérivation droite, ou encore que tout @@ -5231,9 +5278,10 @@ Notamment, l'arbre représenté en \ref{example-of-parse-tree} est l'\emph{unique} arbre d'analyse de $aabbab$ pour la grammaire présentée ci-dessus. -\thingy Il arrive que le \emph{même} langage puisse être engendré par -une grammaire ambiguë et par une grammaire inambiguë (on a vu un -exemple en \ref{trivial-example-ambiguity}). L'ambiguïté est donc une +\thingy\label{intrinsic-ambiguity} Il arrive que le \emph{même} +langage puisse être engendré par une grammaire ambiguë et par une +grammaire inambiguë (on a vu un exemple +en \ref{trivial-example-ambiguity}). L'ambiguïté est donc une caractéristique de la \emph{grammaire} hors contexte et non du \emph{langage} algébrique qu'elle engendre. @@ -5317,18 +5365,19 @@ cette question est positive, mais plus délicate que dans le cadre des langages rationnels où la notion d'automate fini a permis de donner un point de vue clair (cf. \ref{rational-languages-are-recognizable}). -\thingy Il existe bien un modèle de calcul qu'on peut imaginer comme -l'analogue pour les langages algébriques (et grammaires hors contexte) -de ce que les automates finis sont pour les langages rationnels (et -expressions régulières) : il s'agit des \emph{automates à pile}. -Informellement, un automate à pile non déterministe fonctionne comme -un automate fini non déterministe à transitions spontanées, mais il a, -en plus de son état courant, accès à une « pile », qui contient des -éléments d'un autre alphabet (l'alphabet de pile), et pour choisir la -transition à effectuer, il peut consulter, en plus du symbole proposé, -les symboles au sommet de la pile (jusqu'à une profondeur bornée), et -une fois cette transition effectuée, décider de rajouter, retirer ou -remplacer des symboles au sommet de la pile. +\thingy\label{handwaving-on-stack-automata} Il existe bien un modèle +de calcul qu'on peut imaginer comme l'analogue pour les langages +algébriques (et grammaires hors contexte) de ce que les automates +finis sont pour les langages rationnels (et expressions régulières) : +il s'agit des \emph{automates à pile}. Informellement, un automate à +pile non déterministe fonctionne comme un automate fini non +déterministe à transitions spontanées, mais il a, en plus de son état +courant, accès à une « pile », qui contient des éléments d'un autre +alphabet (l'alphabet de pile), et pour choisir la transition à +effectuer, il peut consulter, en plus du symbole proposé, les symboles +au sommet de la pile (jusqu'à une profondeur bornée), et une fois +cette transition effectuée, décider de rajouter, retirer ou remplacer +des symboles au sommet de la pile. {\footnotesize @@ -5413,7 +5462,7 @@ aSbS \,|\, \varepsilon$, on peut écarter la règle $S \rightarrow \varepsilon$ quitte à ajouter des règles $S \rightarrow aSb$ et $S \rightarrow abS$ et $S \rightarrow ab$. -\thingy Du point de vue pratique, il existe deux approches principales +\thingy\label{handwaving-on-ll-and-lr} Du point de vue pratique, il existe deux approches principales pour analyser les langages définis par des grammaires hors contexte (supposées \emph{au minimum} inambiguës) : \begin{itemize} |