More about ambiguity.

1 files changed, 191 insertions, 26 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 9f36e62..98ed13c 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2837,6 +2837,25 @@ et les langages reconnus sont les mêmes.
 
 \section{Grammaires hors contexte}
 
+\setcounter{comcnt}{0}
+
+\thingy Alors que les langages et expressions rationnelles servent,
+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}.
+
+
 \subsection{Définition, notations et premier exemple}
 
 \thingy\label{definition-context-free-grammar} Une \textbf{grammaire
@@ -2907,12 +2926,23 @@ partie droite d'une production $T \rightarrow \alpha$ de la
 grammaire $G$ : on dit encore que $\lambda \Rightarrow \xi$ est une
 \textbf{dérivation immédiate} de $G$.  On pourra dire que $T
 \rightarrow \alpha$ est la règle \textbf{appliquée} dans cette
-dérivation immédiate, que $T$ est le \textbf{symbole réécrit}, et que
-$\gamma$ et $\gamma'$ sont respectivement le \textbf{contexte gauche}
-et le \textbf{contexte droit} de l'application de la règle.  Bien sûr,
-si nécessaire, on précisera la grammaire appliquée en écrivant
-$\lambda \mathrel{\Rightarrow_G} \xi$ au lieu de simplement
-$\lambda\Rightarrow\xi$.
+dérivation immédiate, que $T$ est le \textbf{symbole réécrit} (souvent
+souligné dans l'écriture de la dérivation immédiate), et que $\gamma$
+et $\gamma'$ sont respectivement le \textbf{contexte gauche} et le
+\textbf{contexte droit} de l'application de la règle\footnote{Pour
+  être extrêmement rigoureux, une dérivation immédiate doit comporter
+  la donnée du symbole réécrit (ou de façon équivalente, du contexte
+  gauche et/ou droit), car elle ne peut pas se déduire de la seule
+  donnée de $\lambda$ et $\mu$ (par exemple, dans $XX \Rightarrow
+  XXX$, même si on sait que la règle appliquée était $X \rightarrow
+  XX$, on ne peut pas deviner si c'est le $X$ de gauche ou de droite
+  qui a été réécrit : il faut donc écrire $\underline{X}X \Rightarrow
+  XXX$ ou bien $X\underline{X} \Rightarrow XXX$, en soulignant le
+  symbole réécrit, pour distinguer les deux).  De même, dans une
+  dérivation, on devrait inclure la donnée du symbole réécrit à chaque
+  étape.}.  Bien sûr, si nécessaire, on précisera la grammaire
+appliquée en écrivant $\lambda \mathrel{\Rightarrow_G} \xi$ au lieu de
+simplement $\lambda\Rightarrow\xi$.
 
 Une suite de pseudo-mots $(\lambda_0,\ldots,\lambda_n)$ telle que
 \[
@@ -3205,8 +3235,8 @@ est donc l'ensemble des mots de la forme $a^i b^j$ où $j=i$ \emph{ou
 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.)
 
-\thingy Sur l'alphabet $\Sigma = \{a,b,c\}$, considérons la grammaire
-(d'axiome $S$)
+\thingy\label{example-for-intrinsic-ambiguity} Sur l'alphabet $\Sigma
+= \{a,b,c\}$, considérons la grammaire (d'axiome $S$)
 \[
 \begin{aligned}
 S &\rightarrow UC \;|\; AV\\
@@ -3252,8 +3282,8 @@ suite de blocs parenthésés, et un bloc parenthésé est une expression
 bien-parenthésée entourée par une parenthèse ouvrante et une
 parenthèse fermante — c'est ce que traduit la grammaire).
 
-\thingy Sur l'alphabet $\Sigma = \{a,b\}$, montrons que la grammaire
-$G$ (d'axiome $S$) donnée par
+\thingy\label{example-grammar-equal-a-and-b} Sur l'alphabet $\Sigma =
+\{a,b\}$, montrons que la grammaire $G$ (d'axiome $S$) donnée par
 \[
 S\; \rightarrow\; aSbS \;|\; bSaS \;|\; \varepsilon
 \]
@@ -3320,13 +3350,13 @@ tandis que $G'$ ne l'est pas.
 
 \thingy Soit $G$ une grammaire hors contexte sur un alphabet $\Sigma$
 et $N$ l'ensemble de ses nonterminaux.  Un \textbf{arbre d'analyse}
-(ou \textbf{arbre de dérivation}) \textbf{incomplet} pour $G$ est un
-arbre (fini, enraciné et ordonné\footnote{C'est-à-dire que l'ensemble
-  des fils d'un nœud quelconque de l'arbre est muni d'un ordre total,
-  ou, ce qui revient au même, qu'ils sont numérotés (disons de la
-  gauche vers la droite).}) dont les nœuds sont étiquetés par des
-éléments de $\Sigma \cup N \cup \{\varepsilon\}$, vérifiant les
-propriétés suivantes :
+(ou \textbf{arbre de dérivation} ; en anglais \textbf{parse tree})
+\textbf{incomplet} pour $G$ est un arbre (fini, enraciné et
+ordonné\footnote{C'est-à-dire que l'ensemble des fils d'un nœud
+  quelconque de l'arbre est muni d'un ordre total, ou, ce qui revient
+  au même, qu'ils sont numérotés (disons de la gauche vers la
+  droite).}) dont les nœuds sont étiquetés par des éléments de $\Sigma
+\cup N \cup \{\varepsilon\}$, vérifiant les propriétés 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
@@ -3457,21 +3487,22 @@ associées le même arbre d'analyse sont dites \textbf{équivalentes}.
 illustré en \ref{example-of-parse-tree} est associé à la dérivation
 \[
 \begin{aligned}
-S &\Rightarrow TS \Rightarrow aSbS \Rightarrow aTSbS \Rightarrow
-aaSbSbS \Rightarrow aabSbS \Rightarrow aabbS\\
-&\Rightarrow aabbTS \Rightarrow aabbaSbS \Rightarrow aabbabS \Rightarrow aabbab\\
+\underline{S} &\Rightarrow \underline{T}S \Rightarrow a\underline{S}bS \Rightarrow a\underline{T}SbS \Rightarrow
+aa\underline{S}bSbS \Rightarrow aab\underline{S}bS \Rightarrow aabb\underline{S}\\
+&\Rightarrow aabb\underline{T}S \Rightarrow aabba\underline{S}bS \Rightarrow aabbab\underline{S} \Rightarrow aabbab\\
 \end{aligned}
 \]
-mais aussi à la dérivation
+(on a souligné à chaque fois le symbole réécrit), mais aussi à la
+dérivation
 \[
 \begin{aligned}
-S &\Rightarrow TS \Rightarrow TTS \Rightarrow TT \Rightarrow TaSb \Rightarrow Tab\\
-&\Rightarrow aSbab \Rightarrow aTSbab \Rightarrow aTbab \Rightarrow aaSbbab \Rightarrow aabbab\\
+\underline{S} &\Rightarrow T\underline{S} \Rightarrow TT\underline{S} \Rightarrow T\underline{T} \Rightarrow Ta\underline{S}b \Rightarrow \underline{T}ab\\
+&\Rightarrow a\underline{S}bab \Rightarrow aT\underline{S}bab \Rightarrow a\underline{T}bab \Rightarrow aa\underline{S}bbab \Rightarrow aabbab\\
 \end{aligned}
 \]
-(elles ont toutes les deux $10$ étapes puisque l'arbre considéré a
-$10$ nœuds qui ne sont pas des feuilles).  Ces deux dérivations sont
-donc équivalentes.
+Ces deux dérivations sont donc équivalentes.  Elles ont toutes les
+deux $10$ étapes puisque l'arbre considéré a $10$ nœuds qui ne sont
+pas des feuilles.
 
 \thingy On appelle \textbf{dérivation gauche} une dérivation (pour une
 grammaire hors contexte donnée) dans laquelle le symbole réécrit est
@@ -3510,6 +3541,140 @@ 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
 mot de $L(G)$ a une unique dérivation gauche.
 
+Les grammaires des langages informatiques réels sont évidemment
+(presque ?) toujours inambiguës : on souhaite qu'un programme
+(c'est-à-dire, dans la terminologie mathématique, un mot du langage)
+admette une unique interprétation, une unique analyse, autrement dit,
+un unique arbre d'analyse.
+
+\thingy\label{trivial-example-ambiguity} À titre d'exemple, la
+grammaire
+\[
+S\; \rightarrow\; SS \;|\; a
+\]
+sur l'alphabet $\{a\}$ est ambiguë.  En effet, le mot $aaa$ admet
+l'arbre d'analyse
+\begin{center}
+\tikzstyle{automaton}=[scale=0.5]
+%%% begin parsetree2 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (S3) at (99bp,90bp) [draw,draw=none] {$S$};
+  \node (S2) at (99bp,162bp) [draw,draw=none] {$S$};
+  \node (S1) at (27bp,162bp) [draw,draw=none] {$S$};
+  \node (S0) at (63bp,234bp) [draw,draw=none] {$S$};
+  \node (S4) at (171bp,90bp) [draw,draw=none] {$S$};
+  \node (a1) at (99bp,18bp) [draw,draw=none] {$a$};
+  \node (a0) at (27bp,90bp) [draw,draw=none] {$a$};
+  \node (a2) at (171bp,18bp) [draw,draw=none] {$a$};
+  \draw [] (S0) ..controls (48.521bp,204.85bp) and (41.357bp,190.92bp)  .. (S1);
+  \draw [] (S1) ..controls (27bp,132.85bp) and (27bp,118.92bp)  .. (a0);
+  \draw [] (S2) ..controls (127.96bp,132.85bp) and (142.29bp,118.92bp)  .. (S4);
+  \draw [] (S2) ..controls (99bp,132.85bp) and (99bp,118.92bp)  .. (S3);
+  \draw [] (S0) ..controls (77.479bp,204.85bp) and (84.643bp,190.92bp)  .. (S2);
+  \draw [] (S4) ..controls (171bp,60.846bp) and (171bp,46.917bp)  .. (a2);
+  \draw [] (S3) ..controls (99bp,60.846bp) and (99bp,46.917bp)  .. (a1);
+%
+\end{tikzpicture}
+
+%%% end parsetree2 %%%
+\end{center}
+mais aussi
+\begin{center}
+\tikzstyle{automaton}=[scale=0.5]
+%%% begin parsetree2b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (S3) at (27bp,90bp) [draw,draw=none] {$S$};
+  \node (S2) at (171bp,162bp) [draw,draw=none] {$S$};
+  \node (S1) at (99bp,162bp) [draw,draw=none] {$S$};
+  \node (S0) at (135bp,234bp) [draw,draw=none] {$S$};
+  \node (S4) at (99bp,90bp) [draw,draw=none] {$S$};
+  \node (a1) at (99bp,18bp) [draw,draw=none] {$a$};
+  \node (a0) at (27bp,18bp) [draw,draw=none] {$a$};
+  \node (a2) at (171bp,90bp) [draw,draw=none] {$a$};
+  \draw [] (S1) ..controls (70.042bp,132.85bp) and (55.714bp,118.92bp)  .. (S3);
+  \draw [] (S0) ..controls (120.52bp,204.85bp) and (113.36bp,190.92bp)  .. (S1);
+  \draw [] (S0) ..controls (149.48bp,204.85bp) and (156.64bp,190.92bp)  .. (S2);
+  \draw [] (S1) ..controls (99bp,132.85bp) and (99bp,118.92bp)  .. (S4);
+  \draw [] (S3) ..controls (27bp,60.846bp) and (27bp,46.917bp)  .. (a0);
+  \draw [] (S2) ..controls (171bp,132.85bp) and (171bp,118.92bp)  .. (a2);
+  \draw [] (S4) ..controls (99bp,60.846bp) and (99bp,46.917bp)  .. (a1);
+%
+\end{tikzpicture}
+
+%%% end parsetree2b %%%
+\end{center}
+
+Cette grammaire n'est donc pas ambiguë.  Remarquons que le langage
+qu'elle engendre est $\{a\}^+ = \{a^n : n\geq 1\}$ (car il est évident
+que tout mot engendré par la grammaire est dans $\{a\}^+$, et
+réciproquement il est facile de fabriquer une dérivation de $a^n$ pour
+tout $n\geq 1$, par exemple $\underline{S} \Rightarrow S\underline{S}
+\Rightarrow \cdots \Rightarrow S^{n-1} S \Rightarrow \cdots a^n$).
+
+Le \emph{même} langage $\{a\}^+ = \{a^n : n\geq 1\}$ peut aussi être
+engendré par la grammaire
+\[
+S\; \rightarrow\; aS \;|\; a
+\]
+(faiblement équivalente à la précédente, donc) qui, elle, \emph{n'est
+  pas} ambiguë : en effet, la seule manière de dériver $a^n$ consiste
+à appliquer $n-1$ fois la règle $S \rightarrow aS$ et finalement une
+fois la règle $S \rightarrow a$ (il y a donc une unique dérivation du
+mot, et \textit{a fortiori} un unique arbre d'analyse).
+
+\thingy La grammaire $G$ des expressions bien-parenthésées
+\[
+\begin{aligned}
+S &\rightarrow TS \;|\; \varepsilon\\
+T &\rightarrow aSb\\
+\end{aligned}
+\]
+considérée en \ref{example-well-parenthesized-expressions} est
+inambiguë.  Le point crucial pour s'en convaincre est que dans
+l'application de la règle $S \rightarrow TS$ dans l'analyse d'un mot
+$w \neq \varepsilon$ engendré par la grammaire, il n'y a qu'une seule
+possibilité sur la limite du préfixe $u$ qui dérivera de $T$ (et donc
+du suffixe qui dérivera de $S$) : en s'inspirant
+de \ref{example-grammar-equal-a-and-b} on peut se convaincre que $u$
+est le préfixe de $w$ de la plus petite longueur $>0$ possible
+comportant autant de $b$ que de $a$ (par exemple si $w = aabbab$ alors
+$u = aabb$) ; ce point étant acquis, tout mot $w\neq\varepsilon$ de la
+grammaire $L(G) = L(G,S)$ s'analyse de façon unique comme
+concaténation d'un mot $u \in L(G,T)$ (c'est-à-dire dérivant de $T$)
+et d'un mot $v \in L(G,S)$, et chacun de ces morceaux s'analyse à son
+tour de façon unique (la règle $T \rightarrow aSb$ ne permet
+manifestement qu'une seule analyse d'un mot de $L(G,T)$ : une fois
+qu'on enlève le $a$ initial et le $b$ final, il reste un mot de
+$L(G,S)$).
+
+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
+caractéristique de la \emph{grammaire} hors contexte et non du
+\emph{langage} algébrique qu'elle engendre.
+
+Cependant, certains langages algébriques ne sont définis \emph{que}
+par des grammaires hors contexte ambiguës.  De tels langages sont dits
+\textbf{intrinsèquement ambigus}.  C'est le cas du langage $\{a^i b^i
+c^j : i,j\in\mathbb{N}\} \cup \{a^i b^j c^j : i,j\in\mathbb{N}\}$ dont
+on a vu en \ref{example-for-intrinsic-ambiguity} qu'il était
+algébrique : il n'est pas évident (cela dépasse le cadre de ce cours)
+de démontrer qu'il est intrinsèquement ambigu, mais on peut au moins
+en donner une explication intuitive : quelle que soit la manière dont
+on construit une grammaire engendrant ce langage, elle devra forcément
+distinguer le cas de $a^i b^i c^j$ et celui de $a^i b^j c^j$, or ces
+cas ne sont pas disjoints, il existe des mots $a^i b^i c^i$ qui sont à
+l'intersection des deux, et ce sont ces mots qui forcent ce langage à
+être intrinsèquement ambigu.
+
 
 %
 %