diff options
| -rw-r--r-- | notes-inf105.tex | 142 |
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). |