From 029a75c66768c84e1a10b7e364f564cf0249a3e5 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 10 Jan 2017 14:47:27 +0100 Subject: More about ambiguity. --- notes-inf105.tex | 217 ++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file 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. + % % -- cgit v1.2.3