summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-30 23:33:00 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-30 23:33:00 (GMT)
commite13d529b4268ed5e8f2b9776662aae507b440205 (patch)
treee99e2410b581b8d2174910be999159b396ef3c23 /notes-inf105.tex
parentb9d6c889f69198a02353ea96856d82ce93a1d317 (diff)
downloadinf105-e13d529b4268ed5e8f2b9776662aae507b440205.zip
inf105-e13d529b4268ed5e8f2b9776662aae507b440205.tar.gz
inf105-e13d529b4268ed5e8f2b9776662aae507b440205.tar.bz2
Try to explain a little more how LL and LR parsers work (vigorous handwaving).
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex124
1 files changed, 118 insertions, 6 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index bdaa2bd..5c75960 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3875,12 +3875,17 @@ aSbS \,|\, \varepsilon$, on peut écarter la règle $S \rightarrow
pour analyser les langages définis par des grammaires hors contexte
(supposées \emph{au minimum} inambiguës) :
\begin{itemize}
-\item les analyseurs LL qui procèdent de façon \emph{descendante},
- parcourent le mot depuis la gauche (« L ») et génèrent la dérivation
- gauche (« L ») de l'arbre d'analyse fabriqué,
-\item et les analyseurs LR qui procèdent de façon \emph{ascendante},
- parcourent le mot depuis la gauche (« L ») et génèrent la dérivation
- droite (« R ») de l'arbre d'analyse fabriqué.
+\item Les analyseurs LL procèdent de façon \emph{descendante} (en
+ anglais « top-down »), parcourent le mot depuis la gauche (« L ») et
+ génèrent la dérivation gauche (« L ») de l'arbre d'analyse fabriqué,
+ 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.}.
+\item Les analyseurs 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
+ fabriqué, en partant des feuilles et en remontant jusqu'aux racines.
\end{itemize}
L'idée générale à retenir est que les analyseurs LR sont strictement
@@ -3889,6 +3894,113 @@ strictement plus de grammaires, cf. \ref{example-lr-non-ll-grammar}),
mais leur écriture est plus difficile et les messages d'erreur qu'ils
retournent sont plus difficiles à comprendre.
+\thingy Pour illustrer ces différences, considérons une grammaire très
+simple à analyser comme
+\[
+\begin{aligned}
+S &\rightarrow TS \;|\; c\\
+T &\rightarrow aSb\\
+\end{aligned}
+\]
+
+L'approche la plus évidente, si on doit écrire une fonction « analyser
+un mot comme dérivant de $S$ dans cette grammaire » consiste à faire
+deux fonctions mutuellement récursives, « chercher un préfixe qui
+dérive de $S$ » et « chercher un préfixe qui dérive de $T$ ». En
+observant que tout mot qui dérive de $T$ doit commencer par la
+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$ :
+\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 :
+\item appeler la fonction « rechercher un préfixe qui dérive
+ de $T$ » sur $w$, qui retourne un préfixe $u$ de $w$ et un
+ arbre $\mathscr{U}$,
+\item appeler la fonction « rechercher un préfixe qui dérive de $S$ »
+ sur le suffixe correspondant $t$ de $w$ (c'est-à-dire le $t$ tel que
+ $w=ut$), qui retourne un préfixe $v$ de $t$ et un arbre
+ $\mathscr{V}$,
+\item renvoyer le préfixe $uv$ de $w$ ainsi que l'arbre d'analyse dont
+ la racine est donnée par la règle $S\rightarrow TS$ et les
+ sous-arbres $\mathscr{U}$ et $\mathscr{V}$ (i.e., une racine
+ étiquetée $S$ et deux fils étiquetés $T$ et $S$ qui sont chacun
+ racines de sous-arbres donnés par $\mathscr{U}$ et $\mathscr{V}$
+ 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$ :
+\begin{itemize}
+\item vérifier que la première lettre est un $a$ (sinon, soulever une
+ exception indiquant une erreur d'analyse),
+\item appeler la fonction « rechercher un préfixe qui dérive de $S$ »
+ sur le suffixe correspondant $x$ de $u$ (c'est-à-dire le $x$ tel que
+ $u=ax$), qui retourne un préfixe $w$ de $x$ et un
+ arbre $\mathscr{W}$,
+\item vérifier que la lettre qui suit $w$ dans $x$ est bien $b$,
+ c'est-à-dire que $u$ commence par $awb$ (sinon, soulever une
+ exception indiquant une erreur d'analyse),
+\item renvoyer le préfixe $awb$ de $u$ ainsi que l'arbre d'analyse
+ dont la racine est donnée par la règle $T\rightarrow aSb$ et les
+ sous-arbres $a$, $\mathscr{W}$ et $b$ (i.e., une racine étiquetée
+ $T$ et trois fils étiquetés $a$, $S$ et $b$, celui du milieu étant
+ racine d'un sous-arbre donné par $\mathscr{W}$).
+\end{itemize}
+\end{itemize}
+
+Cette approche réussit sur cette grammaire très simple (où on peut
+notamment se convaincre que l'éventuel préfixe dérivant de $S$ ou de
+$T$ est toujours défini de façon unique). L'analyseur qu'on vient de
+décrire s'appelle un « analyseur par descente récursive » ; mais
+plutôt qu'utiliser la récursivité du langage de programmation
+(c'est-à-dire la pile système), on peut aussi utiliser une pile comme
+structure de données, et on obtient ainsi essentiellement un automate
+à pile, qui utilise sa pile pour retenir les règles qu'il a commencé à
+analyser (à partir de la racine de l'arbre d'analyse en cours de
+construction). On a essentiellement construit un analyseur LL, ou
+plus exactement LL($1$) (le « $1$ » indiquant qu'on se contente de
+lire une unique lettre du mot pour décider quelle règle chercher à
+analyser), pour ce langage. C'est ici l'approche « descendante » :
+l'arbre se construit à partir de la racine et la pile sert à retenir
+les règles qu'on a commencé à reconnaître.
+
+\smallbreak
+
+L'approche « ascendante » de la même grammaire serait plutôt la
+suivante : on parcourt le mot de gauche à droite en gardant de côté
+une pile (initialement vide) qui pourra contenir les symboles $a,S,T$,
+les deux derniers étant alors associés à des arbres d'analyse ;
+\begin{itemize}
+\item si on lit un $a$, on se contente de l'empiler,
+\item si on lit un $c$, on crée un arbre d'analyse $S\rightarrow c$ et
+ on empile le $S$, puis, tant que la pile contient $T$ et $S$ en son
+ sommet, on dépile ces deux symboles, on rassemble les deux arbres
+ d'analyse associés en les mettant sous un $S\rightarrow TS$ et on
+ empile le $S$ correspondant,
+\item si on lit un $b$, on vérifie que les deux symboles au sommet de
+ la pile sont $a$ et $S$ (sinon on soulève une erreur d'analyse), on
+ les dépile et on rassemble l'arbre d'analyse associé au $S$ en le
+ mettant sous un $T\rightarrow aSb$, et enfin on empile un $T$
+ associé à cet arbre,
+\item enfin, si on arrive à la fin du mot, la pile ne doit contenir
+ qu'un unique symbole $S$ (sinon on soulève une erreur d'analyse), et
+ l'arbre d'analyse final est celui qui lui est associé.
+\end{itemize}
+
+Il est un peu difficile d'expliquer en général comment construire un
+tel analyseur, mais sur cet exemple précis il est facile de se
+convaincre qu'il fonctionne et de comprendre pourquoi : il s'agit
+essentiellement là d'un analyseur LR (en fait, LR($0$), le « $0$ »
+indiquant qu'on n'a jamais eu besoin de regarder au-delà du symbole
+courant pour décider quoi faire), C'est ici l'approche
+« ascendante » : l'arbre se construit à partir des feuilles et la pile
+sert à retenir les nonterminaux au sommet des morceaux d'arbre déjà
+construits (et éventuellement les arbres eux-mêmes).
+
%
%