diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 29 |
1 files changed, 15 insertions, 14 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index e08083d..470a46c 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -5504,7 +5504,7 @@ Plus exactement, on montre : Montrons d'abord l'affirmation du premier point. Pour cela, on va d'abord calculer l'ensemble $N_0$ des nonterminaux -« évanescents » de $G$, un nonterminal $T$ étant dit « évanescent » +« \index{évanescent (nonterminal)}évanescents » de $G$, un nonterminal $T$ étant dit « évanescent » lorsque $T \mathrel{\Rightarrow^*} \varepsilon$. Mais il est évident que toute dérivation de $\varepsilon$ dans $G$ ne peut faire intervenir que des nonterminaux évanescents. On peut donc calculer @@ -5570,7 +5570,8 @@ Il s'agit de travailler en deux étapes : \item Ensuite, utiliser un algorithme de programmation dynamique pour calculer, pour chaque facteur $u$ de $w$ (par ordre croissant de taille), l'ensemble de tous les terminaux $T$ tels que $T - \mathrel{\Rightarrow^*} u$. + \mathrel{\Rightarrow^*} u$ (ce qui répond notamment à la question de + savoir si $S \mathrel{\Rightarrow^*} w$). \end{itemize} Détaillons un peu plus chacune de ces étapes. @@ -5578,9 +5579,9 @@ Détaillons un peu plus chacune de ces étapes. Pour transformer la grammaire $G$ en une grammaire $G'$ sous forme normale de Chomsky, on effectue les transformations suivantes : \begin{itemize} -\item Introduire pour chaque terminal $x$ un nonterminal $X$ et une - règle $X \rightarrow x$, et remplacer chaque occurrence de $x$ - par $X$ dans le membre de droite de toute règle autre que $X +\item Introduire pour chaque terminal $x$ un nouveau nonterminal $X$ + et une règle $X \rightarrow x$, et remplacer chaque occurrence + de $x$ par $X$ dans le membre de droite de toute règle autre que $X \rightarrow x$. Ceci permet de faire en sorte qu'à part les règles $X \rightarrow x$, le membre de droite de toute règle soit uniquement constitué de nonterminaux. @@ -5608,8 +5609,8 @@ normale de Chomsky, on effectue les transformations suivantes : sortes de transitions spontanées d'un nonterminal vers un autre.) \end{itemize} -L'ordre de ces transformations peut être légèrement varié, mais -l'ordre proposé ci-dessus est sans doute le meilleur. +L'ordre de ces transformations peut être légèrement varié, mais celui +proposé ci-dessus est sans doute le meilleur. Une fois la grammaire $G'$ en forme normale de Chomsky connue, lorsqu'on a un mot $w$ dont on cherche à tester s'il appartient @@ -5618,13 +5619,13 @@ son point de départ et sa longueur), dans l'ordre croissant de longueur, l'ensemble $\Lambda(u)$ des nonterminaux $T$ tels que $u \in L(G',T)$ (on rappelle, cf. \ref{words-deriving-from-another-nonterminal}, que $L(G',T) := -\{w \in \Sigma^* : T \mathrel{\Rightarrow^*} w\}$) : +\{v \in \Sigma^* : T \mathrel{\Rightarrow^*} v\}$) : \begin{itemize} \item Si $|u|=1$, c'est-à-dire $u \in \Sigma$, il s'agit simplement de l'ensemble des $T$ tels que la règle $T \rightarrow u$ soit dans $G'$. \item Si $|u|\geq 2$, considérer chaque factorisation $u = v_1 v_2$ en - facteurs de taille $\geq 1$ (il y en a $|u|-1$ possibles), pour + deux facteurs de taille $\geq 1$ (il y en a $|u|-1$ possibles), pour chacune d'entre elles, pour chaque $X_1 \in \Lambda(v_1)$ (i.e., tel que $v_1 \in L(G',X_1)$) et chaque $X_2 \in \Lambda(v_2)$ (i.e., tel que $v_2 \in L(G',X_2)$) (ces deux ensembles étant connus par @@ -5658,7 +5659,7 @@ pour analyser les langages définis par des grammaires hors contexte en partant de la racine et en descendant jusqu'aux feuilles\footnote{En botanique, un arbre a la racine en bas et les feuilles en haut ; en informatique, on les représente plutôt - racine en haut et feuille en bas.}. + racine en haut et feuilles en bas.}. \item Les analyseurs \defin[LR (analyse)]{LR} procèdent de façon \emph{ascendante} (en anglais « bottom-up »), parcourent le mot depuis la gauche (« L ») et génèrent la dérivation droite (« R ») de l'arbre d'analyse @@ -5689,8 +5690,8 @@ lettre $a$, ce qui permet de distinguer les mots dérivant des règles $S\rightarrow TS$ et $S\rightarrow c$, on va écrire : \begin{itemize} \item Fonction « rechercher un préfixe qui dérive de $S$ » (prenant en - entrée un mot $w\in\{a,b\}^*$ et renvoyant un préfixe de $w$ et un - arbre de dérivation de $w$ à partir de $S$ : + entrée un mot $w\in\{a,b\}^*$, et renvoyant un préfixe de $w$ et un + arbre de dérivation de $w$ à partir de $S$) : \begin{itemize} \item si la première lettre de $w$ est $c$, renvoyer le préfixe $c$ et l'arbre trivial $S\to c$, sinon : @@ -5709,8 +5710,8 @@ $S\rightarrow TS$ et $S\rightarrow c$, on va écrire : respectivement). \end{itemize} \item Fonction « rechercher un préfixe qui dérive de $T$ » (prenant en - entrée un mot $u\in\{a,b\}^*$ et renvoyant un préfixe de $u$ et un - arbre de dérivation de $u$ à partir de $T$ : + entrée un mot $u\in\{a,b\}^*$, et renvoyant un préfixe de $u$ et un + arbre de dérivation de $u$ à partir de $T$) : \begin{itemize} \item vérifier que la première lettre est un $a$ (sinon, soulever une exception indiquant une erreur d'analyse), |