Parse trees versus derivations; left and right derivations.

1 files changed, 98 insertions, 16 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 782dc89..ea10ff6 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2905,13 +2905,14 @@ Concrètement, $\lambda\Rightarrow\xi$ signifie donc que $\xi$ est
 obtenu en remplaçant un nonterminal $T$ du pseudo-mot $\lambda$ par la
 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
+\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, 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}, 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$.
 
 Une suite de pseudo-mots $(\lambda_0,\ldots,\lambda_n)$ telle que
 \[
@@ -3302,16 +3303,17 @@ que la grammaire $G$ est ambiguë (un terme qui sera défini plus bas)
 tandis que $G'$ ne l'est pas.
 
 
-\subsection{Arbres d'analyse}
+\subsection{Arbres d'analyse, dérivations gauche et droite}
 
 \thingy Soit $G$ une grammaire hors contexte sur un alphabet $\Sigma$
-et $N$ l'ensemble de ses nonterminaux.  Un \textbf{arbre d'analyse
-  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 :
+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 :
 \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
@@ -3330,6 +3332,9 @@ supplémentaire suivante :
   (é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.)
+
 \thingy Si $T$ est un arbre d'analyse incomplet, et $\alpha$ le
 pseudo-mot obtenu en lisant les étiquettes des \emph{feuilles} de $T$
 en profondeur ordonnée (c'est-à-dire en commençant par toutes les
@@ -3341,8 +3346,8 @@ le pseudo-mot analysé par $T$.  La définition d'un arbre d'analyse
 complet signifie exactement qu'il est l'arbre d'analyse d'un
 \emph{mot} (c'est-à-dire, d'un mot sur $\Sigma$).
 
-\thingy À titre d'exemple, considérons la grammaire (considérée
-en \ref{example-well-parenthesized-expressions})
+\thingy\label{example-of-parse-tree} À titre d'exemple, considérons la
+grammaire (considérée en \ref{example-well-parenthesized-expressions})
 \[
 \begin{aligned}
 S &\rightarrow TS \;|\; \varepsilon\\
@@ -3403,6 +3408,83 @@ 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.
+
+Notons que l'arbre obtenu est complet exactement lorsque la dérivation
+aboutit à un mot (sur $\Sigma$).  Notons aussi que le nombre $n$
+d'étapes dans la dérivation est égal au nombre de nœuds de l'arbre qui
+\emph{ne sont pas} des feuilles.
+
+Deux dérivations (forcément du même mot ou pseudo-mot) auxquelles sont
+associées le même arbre d'analyse sont dites \textbf{équivalentes}.
+
+\thingy\label{example-of-derivations} À titre d'exemple, l'arbre
+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\\
+\end{aligned}
+\]
+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\\
+\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.
+
+\thingy On appelle \textbf{dérivation gauche} une dérivation (pour une
+grammaire hors contexte donnée) dans laquelle le symbole réécrit est
+toujours \emph{le nonterminal le plus à gauche} du pseudo-mot
+courant : autrement dit, une dérivation gauche est une dérivation
+telle que le contexte gauche de chaque dérivation immédiate la
+constituant ne comporte que des symboles terminaux (i.e., appartient
+à $\Sigma^*$).  Symétriquement, on appelle \textbf{dérivation droite}
+une dérivation dans laquelle le symbole réécrit est toujours \emph{le
+  nonterminal le plus à droite}, c'est-à-dire que le contexte droit de
+chaque dérivation immédiate la constituant ne comporte que des
+symboles terminaux.
+
+À titre d'exemple, les deux dérivations données
+en \ref{example-of-derivations} sont respectivement une dérivation
+gauche et une dérivation droite.
+
+À chaque arbre d'analyse est associée une et une seule dérivation
+gauche : on l'obtient de façon évidente en réécrivant à chaque étape
+le symbole nonterminal le plus à gauche en suivant la règle indiquée
+par l'arbre d'analyse sous le nœud correspondant ; cela revient à
+parcourir l'arbre d'analyse en profondeur de gauche à droite, et à
+réécrire le symbole correspondant à chaque nœud que l'on rencontre qui
+n'est pas une feuille.  De même, à chaque arbre d'analyse est associée
+une et une seule dérivation droite.
+
 
 %
 %