From 918d8bbe0b7bcadf43ae0cc9881c0f55c9ad52de Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 3 Jan 2017 11:53:06 +0100 Subject: Parse trees versus derivations; left and right derivations. --- notes-inf105.tex | 114 +++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 98 insertions(+), 16 deletions(-) (limited to 'notes-inf105.tex') 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. + % % -- cgit v1.2.3