Expand discussion about practical parsing of CFGs (LL and LR approaches).

1 files changed, 97 insertions, 45 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 470a46c..818b58b 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -4820,8 +4820,8 @@ langage $L(G)$ que la précédente (elle est donc faiblement équivalente
   inambiguë (cf. \ref{ambiguous-grammar}), il ne peut pas être analysé
   par un analyseur LL (cf. \ref{handwaving-on-ll-and-lr}).)\par}
 
-\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire
-(d'axiome $S$)
+\thingy\label{example-unambiguous-but-not-deterministic-grammar} Sur
+l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$)
 \[
 \begin{aligned}
 S &\rightarrow U \;|\; V \;|\; \varepsilon\\
@@ -4830,11 +4830,12 @@ V &\rightarrow aVbb \;|\; abb\\
 \end{aligned}
 \]
 Il est clair que le langage $L(G,U)$ des mots qui dérivent de $U$ est
-$\{a^i b^i : i>0\}$ comme en \ref{basic-example-context-free-grammar},
-et de façon analogue, le langage $L(G,V)$ des mots qui dérivent de $V$
-est $\{a^i b^{2i} : i>0\}$.  Le langage $L(G) = L(G,U) \cup L(G,V)$
-est donc l'ensemble des mots de la forme $a^i b^j$ où $j=i$ \emph{ou
-  bien} $j=2i$.
+$\{a^i b^i : i\geq 1\}$ comme
+en \ref{basic-example-context-free-grammar}, et de façon analogue, le
+langage $L(G,V)$ des mots qui dérivent de $V$ est $\{a^i b^{2i} :
+i\geq 1\}$.  Le langage $L(G) = L(G,U) \cup L(G,V)$ est donc
+l'ensemble des mots de la forme $a^i b^j$ où $i\geq 1$ et $j=i$
+\emph{ou bien} $j=2i$.
 
 {\footnotesize (Ce langage est intéressant sur le plan théorique, car
   bien qu'il soit algébrique et défini par une grammaire inambiguë
@@ -5461,6 +5462,8 @@ les automates à pile déterministes (qu'il faut définir soigneusement)
 acceptent strictement moins de langages que les automates à pile
 non déterministes.
 
+\bigbreak
+
 \thingy Une approche simple, quoique terriblement inefficace, pour
 résoudre algorithmiquement, \emph{en théorie}, le problème de décider
 si un mot $w$ appartient au langage $L(G)$ engendré par une grammaire
@@ -5649,49 +5652,93 @@ cubique en la longueur de $w$.
 
 \par}
 
-\thingy\label{handwaving-on-ll-and-lr} Du point de vue pratique, il existe deux approches principales
-pour analyser les langages définis par des grammaires hors contexte
-(supposées \emph{au minimum} inambiguës) :
+\bigbreak
+
+\thingy\label{handwaving-on-ll-and-lr} Du point de vue pratique, on ne
+cherche pas simplement à savoir si un mot appartient au langage
+engendré par une grammaire, mais aussi à en construire un arbre
+d'analyse ; par ailleurs, la complexité algorithmique des approches
+décrites en \ref{algebraic-languages-are-decidable} et meme
+en \ref{handwaving-on-dynamical-programming} est inacceptable.  En
+contrepartie de ces exigences, on est prêt à accepter de mettre des
+contraintes sur la grammaire qui la rendent plus facile à analyser :
+\emph{au minimum}, on supposera que la grammaire est inambiguë
+(cf. \ref{ambiguous-grammar}), et en fait, on imposera des contraintes
+beaucoup plus fortes (par exemple, la grammaire présentée
+en \ref{example-unambiguous-but-not-deterministic-grammar}, bien
+qu'inambiguë, ne sera pas acceptable car il n'y a pas de manière
+déterministe de l'analyser, ni même d'analyser le langage qu'elle
+engendre) ; ces contraintes sont assez techniques et difficiles à
+décrire : dans la pratique, elles consistent essentiellement à essayer
+de fabriquer l'analyseur et à constater si l'algorithme échoue.
+
+Il existe deux principales approches pour construire un analyseur pour
+une grammaire hors contexte (sujette à diverses contraintes
+supplémentaires) ; dans les deux cas, on construit une sorte
+d'automate à pile (cf. \ref{handwaving-on-stack-automata})
+déterministe, mais l'utilisation de la pile est très différente dans
+les deux cas.   De façon très simplifiée :
 \begin{itemize}
-\item Les analyseurs \defin[LL (analyse)]{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 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
-  fabriqué, en partant des feuilles et en remontant jusqu'aux racines.
+\item Les analyseurs \defin[LL (analyse)]{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 feuilles en bas.}.  La pile de
+  l'analyseur LL sert, intuitivement, à mémoriser les règles qu'on a
+  commencé à reconnaître, en partant de l'axiome de la grammaire, et
+  qui restent encore à compléter.
+\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 fabriqué, en partant des feuilles et en remontant
+  jusqu'aux racines.  La pile de l'analyseur LR sert, intuitivement, à
+  mémoriser les fragments d'arbre déjà construit, en partant des
+  feuilles, et qui restent encore à regrouper.
 \end{itemize}
 
+On peut écrire un analyseur LL ou (plus difficilement) LR à la main
+dans un cas simple, mais en général ces analyseurs sont fabriqués par
+des algorithmes systématiques, implémentés dans des programmes tels
+que YACC ou Bison (qui produit des analyseurs LR, même si Bison peut
+dépasser ce cadre) ou JavaCC (qui produit des analyseurs LL).
+
 L'idée générale à retenir est que les analyseurs LR sont strictement
 plus puissants que les analyseurs LL (ils sont capables d'analyser
 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.
+mais leur génération est plus difficile et les messages d'erreur
+qu'ils retournent en cas de problème de syntaxe sont plus difficiles à
+comprendre pour l'utilisateur.
 
-\thingy Pour illustrer ces différences, considérons une grammaire très
-simple à analyser comme
+\thingy\label{example-ll-and-lr-analysis} Pour illustrer le
+fonctionnement et les différences des analyseurs LL et LR, considérons
+une grammaire très simple à analyser comme
 \[
 \begin{aligned}
 S &\rightarrow TS \;|\; c\\
 T &\rightarrow aSb\\
 \end{aligned}
 \]
+(il s'agit d'une variante de celle considérée
+en \ref{example-well-parenthesized-expressions}, où on a ajouté un $c$
+pour rendre l'analyse plus simple en évitant les
+productions $\varepsilon$ ; on peut imaginer, si on veut, qu'il s'agit
+d'une forme extrêmement primitive de XML où $a$ représente une balise
+ouvrante, $b$ une balise fermante, et $c$ une balise vide).
 
 L'approche la plus évidente, si on doit écrire une fonction « analyser
-un mot comme dérivant de $S$ dans cette grammaire » consiste à faire
+un mot comme dérivant de $S$ dans cette grammaire » consiste à coder
 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$) :
+\item La 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$) est définie comme
+  suit :
 \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,9 +5756,10 @@ $S\rightarrow TS$ et $S\rightarrow c$, on va écrire :
   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$) :
+\item La 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$) est définie comme
+  suit :
 \begin{itemize}
 \item vérifier que la première lettre est un $a$ (sinon, soulever une
   exception indiquant une erreur d'analyse),
@@ -5733,18 +5781,22 @@ $S\rightarrow TS$ et $S\rightarrow c$, on va écrire :
 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.
+décrire s'appelle un « analyseur par descente récursive ».  Or, 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 transformer les fonctions récursives en fonctions
+itératives\footnote{Ceci est un fait général : tout ensemble de
+  fonctions récursives peut se réécrire pour utiliser une pile comme
+  structure de données explicite à la place de la pile système.}.  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
 
@@ -5774,7 +5826,7 @@ 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
+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).