From e13d529b4268ed5e8f2b9776662aae507b440205 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 31 Jan 2017 00:33:00 +0100
Subject: Try to explain a little more how LL and LR parsers work (vigorous
 handwaving).

---
 notes-inf105.tex | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 118 insertions(+), 6 deletions(-)

(limited to 'notes-inf105.tex')

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).
+
 
 %
 %
-- 
cgit v1.2.3