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