diff options
| -rw-r--r-- | figs/parsetree1.dot | 44 | ||||
| -rw-r--r-- | notes-inf105.tex | 105 |
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} + % % |