summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-02 22:30:54 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-02 22:30:54 (GMT)
commit1d22c7afda86d4b7e8ecc6188e565a7efe9acbcd (patch)
tree6be03fbe688b516bfc8fc69c4b35c654b3b2575d /notes-inf105.tex
parent250b26a45655b27c33f30fcfebbb3633b7efac58 (diff)
downloadinf105-1d22c7afda86d4b7e8ecc6188e565a7efe9acbcd.zip
inf105-1d22c7afda86d4b7e8ecc6188e565a7efe9acbcd.tar.gz
inf105-1d22c7afda86d4b7e8ecc6188e565a7efe9acbcd.tar.bz2
Start discussing parse trees.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex105
1 files changed, 103 insertions, 2 deletions
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}
+
%
%