La dernière fois, nous avons obtenu un simple générateur d'analyseur PEG. Je vais maintenant montrer ce que fait réellement l'analyseur généré lors de l'analyse du programme. J'ai plongé dans le monde rétro de l'art ASCII, en particulier, une bibliothèque appelée "curses", qui est disponible dans la distribution Python standard pour Linux et Mac, ainsi qu'un module complémentaire pour Windows.
Contenu de la série Python PEG Parser 
<A la fin de l'article, un gif est donné sous le spoiler. Cela me semblait plus compréhensible qu'une image statique>
Regardons la visualisation. L'écran est divisé en trois parties, comme c'est la coutume en ASCII, avec une ligne de trait d'union:
- La partie supérieure montre la pile d'appels de l'analyseur, qui, comme vous vous en souvenez, est un analyseur de descente récursif à retour illimité. Ci-dessous, je vais expliquer plus en détail.
- La section d'une ligne au milieu montre le contenu du tampon de jeton avec un curseur pointant vers le jeton qui sera analysé ensuite.
- Ci-dessous, nous visualisons le cache utilisé par l'algorithme de l'analyseur packrat. L'enregistrement de ses éléments est quelque peu similaire à certains éléments de la pile d'analyse (avec des résultats).
La principale chose que vous devez savoir pour comprendre cette visualisation est que l'indentation des lignes dans les parties supérieure et inférieure correspond au tampon de jeton.
- Les deux premières lignes (commençant par l'
statement et l' assignment ) montrent les appels aux méthodes d'analyseur correspondantes qui effectuent l'analyse en ce moment. Ils ont été appelés lorsque le pointeur du jeton était avant le premier jeton ( 'aap' ). - Les deux lignes suivantes (commençant par
expr et term ) sont alignées avec le début du jeton 'cat' , où les méthodes d'analyseur correspondantes ont été appelées. - La cinquième et dernière ligne de rendu de pile montre l'appel à
expect('/') , qui renvoie None . Il s'est porté volontaire au poste de jeton '+' .
L'indentation des éléments dans le cache correspond également à une position dans le tampon de jetons. Par exemple, en bas, il y a des entrées négatives dans le cache, elles ont été obtenues lors de la recherche du jeton 'if' et de la règle if_statement au début du tampon de jeton. Nous trouvons également des entrées de cache réussies pour le jeton '=' et pour NAME (en particulier, 'cat' ) correspondant à d'autres positions d'entrée.
Tant dans le bloc de pile de l'analyseur que dans le bloc de cache, les appels retournés sont affichés en tant que function(args) -> result . Parfois, plusieurs méthodes renvoyées sont affichées sur la pile de l'analyseur - J'ai fait cela pour réduire la gigue du texte due aux changements de contenu fréquents.
(En parlant de gigue, les lignes supérieures de la pile de l'analyseur montent quand un appel est ajouté à la pile et tombent quand il est retiré de la pile. C'est-à-dire que chaque nouvel appel est inséré tout en bas du bloc de visualisation de la pile, déplaçant les lignes existantes vers le haut. Il me semble que regarder cette partie de l'écran n'est pas un problème, du moins pour moi. Probablement, une partie importante de notre cerveau est consacrée au suivi des objets en mouvement. :-)
Le cache est rendu en LRU, avec les éléments fréquemment utilisés en haut; les plus rares descendent sur l'écran. (Le prototype de l'analyseur de packrat que j'ai montré dans les articles précédents n'utilise pas LRU, mais c'est probablement une bonne idée pour optimiser la consommation de mémoire.)
Regardons quelques détails lors du rendu de la pile d'analyse. Les quatre premières entrées correspondent aux méthodes de l'analyseur qui sont toujours en cours de traitement, chaque ligne est une ligne de la grammaire. L'élément en surbrillance est celui qui a généré le prochain défi.
C'est-à-dire à en juger par la capture d'écran, nous sommes sur la deuxième alternative pour la statement , à savoir la assignment . Dans cette règle, nous en sommes au troisième point, à savoir expr . Dans la règle expr , nous ne sommes qu'au premier paragraphe de la première alternative ( term '+' expr ); et dans la règle du term nous sommes dans la dernière alternative ( atom ).
Ci-dessous, nous voyons le résultat qui a conduit à l'échec de la deuxième alternative ( atom '/' term ): expect('/') -> None retrait avec le jeton '+' . Dans l'étape suivante, nous verrons comment il pénètre dans le cache.
Mais vous préférez sûrement voir toute l'animation vous-même!
J'ai enregistré une analyse complète du programme d'exemple canonique Vous pouvez également jouer avec du code prêt à l'emploi, mais gardez à l'esprit que ce n'est pas du sport.
Lorsque vous affichez un GIF enregistré , il peut sembler un peu étrange que parfois le prochain jeton ne s'affiche pas (par exemple, au tout début, la pile augmente de plusieurs enregistrements avant que le jeton 'aap' soit détecté). C'est exactement ce que voit l'analyseur: le tampon de jetons est rempli paresseusement. Les jetons ne sont analysés que lorsque l'analyseur le demande en appelant la fonction expect() . Dès que le jeton entre dans le tampon, il y reste, même si l'analyseur rembobine la séquence de jetons. Le suivi inverse est affiché dans le tampon de jetons avec un curseur qui saute vers la gauche; il existe de nombreuses situations de ce genre dans le dossier. Vous pouvez également observer le remplissage du cache lorsque l'analyseur n'effectue pas d'appels récursifs supplémentaires. (Je dois souligner quand cela se produit, mais je n'ai pas eu assez de temps.)
La semaine prochaine, je développerai un analyseur, ajoutant peut-être mon point de vue sur les règles de gauche de la grammaire récursive. (Ils sont super!)
Remerciements: pour mémoire, j'ai utilisé ttygif d'Ilya Choli et ttyrec de Matthew Jording.
Licence pour cet article et code cité: CC BY-NC-SA 4.0