Les arbres syntaxiques abstraits sont des structures de données largement utilisées dans les compilateurs pour représenter la structure du code du programme. Un AST est généralement le résultat de la phase d’analyse syntaxique d’un compilateur. Il sert souvent de représentation intermédiaire du programme à travers plusieurs étapes que le compilateur requiert, et a un fort impact sur la sortie finale du compilateur.
MotivationÉdition
Un AST a plusieurs propriétés qui aident les étapes ultérieures du processus de compilation :
- Un AST peut être édité et amélioré avec des informations telles que des propriétés et des annotations pour chaque élément qu’il contient. Une telle édition et annotation est impossible avec le code source d’un programme, car cela impliquerait de le modifier.
- Par rapport au code source, une AST ne comprend pas de ponctuation et de délimiteurs inessentiels (accolades, points-virgules, parenthèses, etc.).
- Une AST contient généralement des informations supplémentaires sur le programme, en raison des étapes consécutives d’analyse par le compilateur. Par exemple, il peut stocker la position de chaque élément dans le code source, permettant au compilateur d’imprimer des messages d’erreur utiles.
Les AST sont nécessaires en raison de la nature inhérente des langages de programmation et de leur documentation. Les langages sont souvent ambigus par nature. Afin d’éviter cette ambiguïté, les langages de programmation sont souvent spécifiés comme une grammaire sans contexte (CFG). Cependant, il y a souvent des aspects des langages de programmation qu’une GFC ne peut pas exprimer, mais qui font partie du langage et sont documentés dans sa spécification. Il s’agit de détails qui nécessitent un contexte pour déterminer leur validité et leur comportement. Par exemple, si un langage permet de déclarer de nouveaux types, un CFG ne peut pas prédire les noms de ces types ni la manière dont ils doivent être utilisés. Même si un langage dispose d’un ensemble prédéfini de types, l’application d’un usage approprié nécessite généralement un certain contexte. Un autre exemple est le typage en canard, où le type d’un élément peut changer en fonction du contexte. La surcharge des opérateurs est un autre cas où l’utilisation correcte et la fonction finale sont déterminées en fonction du contexte. Java fournit un excellent exemple, où l’opérateur ‘+’ est à la fois une addition numérique et une concaténation de chaînes de caractères.
Bien qu’il existe d’autres structures de données impliquées dans le fonctionnement interne d’un compilateur, l’AST remplit une fonction unique. Au cours de la première étape, celle de l’analyse syntaxique, un compilateur produit un arbre d’analyse. Cet arbre d’analyse peut être utilisé pour exécuter presque toutes les fonctions d’un compilateur au moyen de la traduction syntaxique. Bien que cette méthode puisse conduire à un compilateur plus efficace, elle va à l’encontre des principes d’ingénierie logicielle d’écriture et de maintenance des programmes. Un autre avantage que l’AST a par rapport à un arbre d’analyse est la taille, en particulier la plus petite hauteur de l’AST et le plus petit nombre d’éléments.
DesignEdit
La conception d’un AST est souvent étroitement liée à la conception d’un compilateur et à ses fonctionnalités attendues.
Les exigences fondamentales comprennent les suivantes :
- Les types de variables doivent être préservés, ainsi que l’emplacement de chaque déclaration dans le code source.
- L’ordre des déclarations exécutables doit être explicitement représenté et bien défini.
- Les composants gauche et droit des opérations binaires doivent être stockés et correctement identifiés.
- Les identifiants et leurs valeurs assignées doivent être stockés pour les déclarations d’affectation.
Ces exigences peuvent être utilisées pour concevoir la structure de données pour l’AST.
Certaines opérations nécessiteront toujours deux éléments, tels que les deux termes pour l’addition. Cependant, certaines constructions du langage nécessitent un nombre arbitrairement élevé d’enfants, comme les listes d’arguments passées aux programmes à partir du shell de commande. En conséquence, une AST utilisée pour représenter le code écrit dans un tel langage doit également être assez flexible pour permettre l’ajout rapide d’une quantité inconnue de fils.
Pour soutenir la vérification du compilateur, il devrait être possible de dé-parser une AST sous forme de code source. Le code source produit devrait être suffisamment similaire à l’original en apparence et identique en exécution, lors de la recompilation.
UtilisationEdit
L’AST est utilisé intensivement pendant l’analyse sémantique, où le compilateur vérifie l’utilisation correcte des éléments du programme et du langage. Le compilateur génère également des tables de symboles basées sur l’AST pendant l’analyse sémantique. Une traversée complète de l’arbre permet de vérifier la correction du programme.
Après avoir vérifié la correction, l’AST sert de base pour la génération du code. L’AST est souvent utilisé pour générer une représentation intermédiaire (IR), parfois appelée langage intermédiaire, pour la génération de code.
.