Communication entre lexer et analyseur syntaxique

Question

Chaque fois que j'écris un lexer et un analyseur simple, je tombe sur la même question : comment le lexer et l'analyseur doivent-ils communiquer ? Je vois quatre approches différentes :

1. Le lexeur convertit rapidement la chaîne d'entrée entière en un vecteur de mots. Une fois cette opération effectuée, le vecteur est transmis à l'analyseur syntaxique qui le convertit en un arbre. C'est de loin la solution la plus simple à mettre en œuvre, mais comme tous les tokens sont stockés en mémoire, elle gaspille beaucoup d'espace.

2. Chaque fois que le lexeur trouve un token, il invoque une fonction sur l'analyseur syntaxique, en passant le token courant. D'après mon expérience, cela ne fonctionne que si l'analyseur syntaxique peut naturellement être implémenté comme une machine à état comme les analyseurs syntaxiques LALR. En revanche, je ne pense pas que cela fonctionne du tout pour les analyseurs descendants récursifs.

3. Chaque fois que l'analyseur a besoin d'un token, il demande au lexer le token suivant. Ceci est très facile à mettre en œuvre en C# grâce à la fonction yield mais assez difficile en C++ qui ne le possède pas.

4. Le lexeur et l'analyseur syntaxique communiquent par le biais d'une file d'attente asynchrone. Cette solution est connue sous le nom de "producteur/consommateur" et devrait simplifier considérablement la communication entre le lexer et l'analyseur syntaxique. Est-ce que cette solution est également plus performante que les autres sur les multicoeurs ? Ou le lexing est-il trop trivial ?

Mon analyse est-elle valable ? Existe-t-il d'autres approches auxquelles je n'ai pas pensé ? Qu'est-ce qui est utilisé dans les compilateurs du monde réel ? Ce serait vraiment cool si des auteurs de compilateurs comme Eric Lippert pouvaient apporter un éclairage sur cette question.

Answer 1

Bien que je ne classerais pas tout ce qui précède comme étant incorrect mais je pense que plusieurs éléments sont trompeurs.

1. L'analyse lexicale d'une entrée entière avant de lancer un analyseur syntaxique présente de nombreux avantages par rapport aux autres options. Les implémentations varient, mais en général la mémoire requise pour cette opération n'est pas un problème, surtout si l'on considère le type d'informations que l'on souhaite avoir à disposition pour signaler les erreurs de compilation.

   • Avantages
     • Potentiellement plus d'informations disponibles lors des rapports d'erreurs.
     • Les langages écrits d'une manière qui permet à la lexie de se produire avant l'analyse syntaxique sont plus faciles à spécifier et à écrire des compilateurs.
   • Inconvénients
     • Certains langages nécessitent des lexiques sensibles au contexte qui ne peuvent tout simplement pas fonctionner avant la phase d'analyse syntaxique.

   Note sur la mise en œuvre de la langue : C'est la stratégie que je préfère, car elle permet d'obtenir un code séparable et convient mieux à la traduction pour mettre en œuvre un IDE pour le langage.

   Note sur l'implémentation de l'analyseur : J'ai expérimenté avec ANTLR v3 concernant l'overhead mémoire avec cette stratégie. La cible C utilise plus de 130 octets par token, et la cible Java utilise environ 44 octets par token. Avec une cible C# modifiée, j'ai montré qu'il est possible de représenter complètement l'entrée tokenisée avec seulement 8 octets par token, ce qui rend cette stratégie pratique même pour des fichiers sources assez volumineux.

   Note de conception linguistique : J'encourage les personnes qui conçoivent un nouveau langage à le faire d'une manière qui permet à cette stratégie d'analyse, qu'ils finissent ou non par la choisir pour leur compilateur de référence.

2. Il semble que vous avez décrit une version "push" de ce que je vois généralement décrit comme un analyseur "pull" comme vous l'avez dans #3. Mon travail a toujours mis l'accent sur l'analyse syntaxique LL, donc ce n'était pas vraiment une option pour moi. Je serais surpris s'il y a des avantages à cela par rapport à #3, mais je ne peux pas les exclure.

3. La partie la plus trompeuse de ce document est la déclaration concernant le C++. L'utilisation correcte des itérateurs en C++ permet de exceptionnellement bien adapté à ce type de comportement.

4. Une file d'attente semble être une répétition de #3 avec un intermédiaire. Si l'abstraction d'opérations indépendantes présente de nombreux avantages dans des domaines tels que le développement de logiciels modulaires, une paire lexer/parser pour une offre de produits distribuables est très sensible aux performances, et ce type d'abstraction supprime la possibilité d'effectuer certains types d'optimisation concernant la structure des données et la disposition de la mémoire. J'encouragerais l'utilisation de l'option 3 plutôt que cette option.

   Une remarque supplémentaire sur l'analyse syntaxique multi-core : Les phases initiales de lexer/parser de la compilation pour une seule unité de compilation ne peuvent généralement pas être parallélisées, et n'ont pas besoin de l'être étant donné la facilité avec laquelle il est possible d'exécuter des tâches de compilation parallèles sur différentes unités de compilation (par exemple, une opération de lexer/parser sur chaque fichier source, une parallélisation à travers les fichiers sources mais en utilisant seulement un seul thread pour un fichier donné).

Concernant les autres options : Pour un compilateur destiné à une utilisation généralisée (commerciale ou autre), les implémenteurs choisissent généralement une stratégie d'analyse syntaxique et une implémentation qui fournissent les meilleures performances sous les contraintes du langage cible. Certains langages (par exemple Go) peuvent être analysés exceptionnellement rapidement avec une simple stratégie d'analyse LR, et l'utilisation d'une stratégie d'analyse "plus puissante" (lire : fonctionnalités inutiles) ne ferait que ralentir les choses. D'autres langages (par exemple C++) sont extrêmement difficiles, voire impossibles à analyser avec les algorithmes habituels, de sorte que des analyseurs plus lents mais plus puissants/flexibles sont utilisés.

Answer 2

Je pense qu'il n'y a pas de règle d'or ici. Les exigences peuvent varier d'un cas à l'autre. Ainsi, les solutions raisonnables peuvent également être différentes. Permettez-moi de commenter vos options à partir de ma propre expérience.

1. "Vecteur de jetons". Cette solution peut avoir une grande empreinte mémoire. Imaginez la compilation d'un fichier source avec beaucoup d'en-têtes. Stocker le jeton lui-même n'est pas suffisant. Le message d'erreur devrait contenir le contexte avec le nom du fichier et le numéro de ligne. Il peut arriver que le lexer dépende de l'analyseur. Exemple raisonnable : ">>" - est-ce un opérateur de décalage ou la fermeture de deux couches d'instanciation de modèles ? Je voterais contre cette option.

2. (2,3). "Une partie appelle une autre". Mon impression est qu'un système plus complexe devrait appeler un système moins complexe. Je considère que le lexer est plus simple. Cela signifie que l'analyseur syntaxique devrait appeler le lexer. Je ne vois pas pourquoi le C# est meilleur que le C++. J'ai implémenté le lexer C/C++ comme une sous-routine (en réalité, c'est une classe complexe) qui est appelée par l'analyseur basé sur la grammaire. Il n'y a eu aucun problème dans cette implémentation.

3. "Communiquer les processus". Cela me semble exagéré. Il n'y a rien de mal dans cette approche, mais peut-être est-il préférable de garder les choses simples ? L'aspect multicore. Compiler un seul fichier est un cas relativement rare. Je recommande de charger chaque noyau avec son propre fichier.

Je ne vois pas d'autres options raisonnables pour combiner lexer et analyseur syntaxique ensemble.

J'ai écrit ces notes en pensant à la compilation des sources du projet de logiciel. L'analyse des requêtes courtes est une chose complètement différente, et les raisons peuvent être très différentes. Ma réponse est basée sur ma propre expérience. D'autres personnes peuvent voir cela différemment.

Answer 3

La relation lexer-parser est plus simple que le cas le plus général de coroutines En effet, la communication est généralement à sens unique ; l'analyseur syntaxique n'a pas besoin de renvoyer des informations au lexer. C'est pourquoi la méthode de génération rapide fonctionne (avec une certaine pénalité, bien que cela signifie que vous pouvez rejeter l'entrée plus tôt).

Comme vous l'avez observé, si le lexeur ou l'analyseur syntaxique peuvent être écrits dans un style réinvocable, alors l'autre peut être traité comme une simple sous-routine. Ceci peut toujours être implémenté comme une transformation de code source, avec des variables locales traduites en slots d'objets.

Bien que le C++ n'ait pas langue pour les coroutines, il est possible de faire usage de bibliothèque soutien, en particulier fibres . Le système Unix setcontext est une option ; une autre est d'utiliser le multithreading mais avec une synchrone (essentiellement du single-threading mais avec une commutation entre deux threads de contrôle).

Answer 4

Considérez également pour le numéro 1 que vous lâchez des jetons qui n'en ont pas besoin, par exemple en cas d'erreur, et en outre, vous pouvez manquer de mémoire ou de bande passante d'E/S. Je pense que la meilleure solution est celle employée par les analyseurs générés par des outils comme Bison, où l'analyseur appelle le lexer pour obtenir le token suivant. Cela minimise les besoins en espace et en bande passante mémoire.

#4 n'en vaut pas la peine. Le lexing et le parsing sont intrinsèquement synchrones - il n'y a tout simplement pas assez de traitement en cours pour justifier les coûts de communication. De plus, vous analysez et lisez généralement plusieurs fichiers simultanément, ce qui peut déjà épuiser tous vos cœurs en même temps.

Answer 5

La façon dont je gère cela dans mon projet de système de construction en cours est d'avoir une classe "lecteur de fichiers", avec une fonction bool next_token(std::string&,const std::set<char>&) . Cette classe contient une ligne d'entrée (pour les rapports d'erreur avec le numéro de ligne). La fonction accepte un std::string pour y placer le jeton, et un std::set<char> qui contient les caractères de "fin de jeton". Ma classe d'entrée est à la fois un analyseur et un lexer, mais vous pouvez facilement la séparer si vous avez besoin de plus de fantaisie. Ainsi, les fonctions d'analyse syntaxique appellent simplement next_token et peuvent faire leur travail, y compris une sortie d'erreur très détaillée.

Si vous devez conserver l'entrée verbatim, vous devrez stocker chaque ligne lue dans un fichier vector<string> ou quelque chose comme ça, mais sans stocker chaque jeton séparément et/ou en double.

Le code dont je parle se trouve ici :

https://github.com/rubenvb/Ambrosia/blob/master/libAmbrosia/Source/nectar_loader.cpp

(recherche de ::next_token et le extract_nectar la fonction est là où tout commence)