summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-07 15:21:08 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-11-07 15:21:08 (GMT)
commitc4d98bd981a3a204b495bf3071f4b5728814a4b5 (patch)
tree8991617e41119a54ba280106d2f141746bc806f9
parentbd2a2a0ae5c0e50a6c731dd5dbc52c80c8a30dd7 (diff)
downloadinf105-c4d98bd981a3a204b495bf3071f4b5728814a4b5.zip
inf105-c4d98bd981a3a204b495bf3071f4b5728814a4b5.tar.gz
inf105-c4d98bd981a3a204b495bf3071f4b5728814a4b5.tar.bz2
Expand discussion about practical parsing of CFGs (LL and LR approaches).
-rw-r--r--notes-inf105.tex142
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).