Start discussing parse trees.

2 files changed, 147 insertions, 2 deletions

diff --git a/figs/parsetree1.dot b/figs/parsetree1.dot
new file mode 100644
index 0000000..cfa9001
--- /dev/null
+++ b/figs/parsetree1.dot
@@ -0,0 +1,44 @@
+graph parsetree1 {
+	node [texmode="math",shape="none"];
+	S0 [label="S"];
+	T0 [label="T"];
+	S1 [label="S"];
+	a0 [label="a"];
+	S2 [label="S"];
+	b0 [label="b"];
+	T1 [label="T"];
+	S3 [label="S"];
+	T2 [label="T"];
+	S4 [label="S"];
+	spacer [label="",style="invisible"];
+	a1 [label="a"];
+	S5 [label="S"];
+	b1 [label="b"];
+	e0 [label="e",texlbl="$\varepsilon$"];
+	a2 [label="a"];
+	S6 [label="S"];
+	b2 [label="b"];
+	e1 [label="e",texlbl="$\varepsilon$"];
+	e2 [label="e",texlbl="$\varepsilon$"];
+	e3 [label="e",texlbl="$\varepsilon$"];
+	S0 -- T0;
+	S0 -- S1;
+	T0 -- a0;
+	T0 -- S2;
+	T0 -- b0;
+	S1 -- T1;
+	S1 -- S3;
+	S2 -- T2;
+	S2 -- S4;
+	b0 -- spacer [style="invisible"];
+	T1 -- a1;
+	T1 -- S5;
+	T1 -- b1;
+	S3 -- e0;
+	T2 -- a2;
+	T2 -- S6;
+	T2 -- b2;
+	S4 -- e1;
+	S5 -- e2;
+	S6 -- e3;
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index b87818d..782dc89 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3214,8 +3214,8 @@ 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 ».)
 
-\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire
-(d'axiome $S$)
+\thingy\label{example-well-parenthesized-expressions} Sur l'alphabet
+$\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$)
 \[
 S\; \rightarrow\; aSbS \;|\; \varepsilon
 \]
@@ -3302,6 +3302,107 @@ 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}
+
+\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 :
+\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$.
+\end{itemize}
+
+On dit de plus que l'arbre est \textbf{complet}, ou simplement qu'il
+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$.
+\end{itemize}
+
+\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
+feuilles qui descendent du premier fils de la racine elles-mêmes dans
+le même ordre, puis toutes celles qui descendent du second fils, et
+ainsi de suite) et en ignorant tous les $\varepsilon$, alors on dit
+que $T$ est un arbre d'analyse \emph{de} $\alpha$, ou que $\alpha$ est
+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})
+\[
+\begin{aligned}
+S &\rightarrow TS \;|\; \varepsilon\\
+T &\rightarrow aSb\\
+\end{aligned}
+\]
+
+L'arbre d'analyse suivant est un arbre d'analyse du mot $aabbab$ :
+\begin{center}
+\tikzstyle{automaton}=[scale=0.5]
+%%% begin parsetree1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (e3) at (99bp,18bp) [draw,draw=none] {$\varepsilon$};
+  \node (S3) at (549bp,234bp) [draw,draw=none] {$S$};
+  \node (S2) at (225bp,234bp) [draw,draw=none] {$S$};
+  \node (S1) at (441bp,306bp) [draw,draw=none] {$S$};
+  \node (S0) at (369bp,378bp) [draw,draw=none] {$S$};
+  \node (T2) at (117bp,162bp) [draw,draw=none] {$T$};
+  \node (S6) at (99bp,90bp) [draw,draw=none] {$S$};
+  \node (T0) at (261bp,306bp) [draw,draw=none] {$T$};
+  \node (T1) at (441bp,234bp) [draw,draw=none] {$T$};
+  \node (a1) at (369bp,162bp) [draw,draw=none] {$a$};
+  \node (a0) at (153bp,234bp) [draw,draw=none] {$a$};
+  \coordinate (spacer) at (297bp,162bp);
+  \node (a2) at (27bp,90bp) [draw,draw=none] {$a$};
+  \node (b0) at (297bp,234bp) [draw,draw=none] {$b$};
+  \node (S5) at (441bp,162bp) [draw,draw=none] {$S$};
+  \node (b2) at (171bp,90bp) [draw,draw=none] {$b$};
+  \node (S4) at (225bp,162bp) [draw,draw=none] {$S$};
+  \node (e1) at (243bp,90bp) [draw,draw=none] {$\varepsilon$};
+  \node (e0) at (585bp,162bp) [draw,draw=none] {$\varepsilon$};
+  \node (e2) at (441bp,90bp) [draw,draw=none] {$\varepsilon$};
+  \node (b1) at (513bp,162bp) [draw,draw=none] {$b$};
+  \draw [] (S1) ..controls (484.16bp,277.03bp) and (505.72bp,263.05bp)  .. (S3);
+  \draw [] (S0) ..controls (397.96bp,348.85bp) and (412.29bp,334.92bp)  .. (S1);
+  \draw [] (S5) ..controls (441bp,132.85bp) and (441bp,118.92bp)  .. (e2);
+  \draw [] (S2) ..controls (225bp,204.85bp) and (225bp,190.92bp)  .. (S4);
+  \draw [] (T2) ..controls (109.76bp,132.85bp) and (106.18bp,118.92bp)  .. (S6);
+  \draw [] (T1) ..controls (469.96bp,204.85bp) and (484.29bp,190.92bp)  .. (b1);
+  \draw [] (T0) ..controls (217.84bp,277.03bp) and (196.28bp,263.05bp)  .. (a0);
+  \draw [] (T2) ..controls (80.802bp,132.85bp) and (62.893bp,118.92bp)  .. (a2);
+  \draw [] (T2) ..controls (138.72bp,132.85bp) and (149.46bp,118.92bp)  .. (b2);
+  \draw [] (S1) ..controls (441bp,276.85bp) and (441bp,262.92bp)  .. (T1);
+  \draw [] (S4) ..controls (232.24bp,132.85bp) and (235.82bp,118.92bp)  .. (e1);
+  \draw [] (S3) ..controls (563.48bp,204.85bp) and (570.64bp,190.92bp)  .. (e0);
+  \draw [] (S0) ..controls (325.84bp,349.03bp) and (304.28bp,335.05bp)  .. (T0);
+  \draw [] (S6) ..controls (99bp,60.846bp) and (99bp,46.917bp)  .. (e3);
+  \draw [] (T0) ..controls (275.48bp,276.85bp) and (282.64bp,262.92bp)  .. (b0);
+  \draw [] (T0) ..controls (246.52bp,276.85bp) and (239.36bp,262.92bp)  .. (S2);
+  \draw [] (T1) ..controls (412.04bp,204.85bp) and (397.71bp,190.92bp)  .. (a1);
+  \draw [] (T1) ..controls (441bp,204.85bp) and (441bp,190.92bp)  .. (S5);
+  \draw [] (S2) ..controls (181.84bp,205.03bp) and (160.28bp,191.05bp)  .. (T2);
+%
+\end{tikzpicture}
+
+%%% end parsetree1 %%%
+\end{center}
+
 
 %
 %