summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-06 19:56:16 +0100
committerDavid A. Madore <david+git@madore.org>2017-11-06 19:56:16 +0100
commitbd2a2a0ae5c0e50a6c731dd5dbc52c80c8a30dd7 (patch)
treeaaa552d53b35a942593aac1b804d17e5ee5ce7b9
parentc0aec3835f1dc9068188044f905202e378432ca5 (diff)
downloadinf105-bd2a2a0ae5c0e50a6c731dd5dbc52c80c8a30dd7.tar.gz
inf105-bd2a2a0ae5c0e50a6c731dd5dbc52c80c8a30dd7.tar.bz2
inf105-bd2a2a0ae5c0e50a6c731dd5dbc52c80c8a30dd7.zip
Reread description of CYK algorithm.
-rw-r--r--notes-inf105.tex29
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),